М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 6
Текст из файла (страница 6)
Вероятно, в будущем одним из главных применений квантовых компьютеров станет моделирование квантовомеханических систем, слишком сложных для моделирования на классическом компьютере. Решение этой задачи требует глубоких научных и технологических разработок. Какие еще задачи квантовые компьютеры могут решать быстрее, чем классические? Краткий ответ таков: мы не знаем. Разработать хороший квантовый алгоритм гврудио. Пессимист может усмотреть причину в том, что квантовые компьютеры подходят только для уже известных применений.
Мы придерживаемся другой точки зрения. Разработка алгоритмов для квантовых компьютеров трудна потому, что здесь приходится сталкиваться с двумя непростыми проблемами, которых нет при разработке алгоритмов для классических компьютеров. Во-первых, наша интуиция имеет корни в классическом мире. Если мы прибегнем к помощи этой интуиции при разработке алгоритмов, то алгоритмические идеи, к которым придем, будут классическими. Для создания хороших квантовых алгоритмов необходимо «отключитьэ классическую интуицию хотя бы на каком-то этапе процесса разработки, используя для достижения желаемого результата чисто квантовые эффекты. Во-вторых, недостаточно разработать алгоритм, который просто является квантовомеханическим.
Этот алгоритм должен быть лучше, чем любой из существующих классических алгоритмов! Ведь может случиться так, что кто-то найдет алгоритм, использующий чисто квантовые аспекты квантовой механики, но этот алгоритм не будет представлять большого интереса из-за существования классических алгоритмов со сравнимой производительностью. Сочетание двух описанных проблем делает разработку новых квантовых алгоритмов многообещающей задачей для будущего. 1.1. Глобальные перспективы 27 Поставим вопрос еще шире: можно ли сделать какие-либо обобщения относительно производительности квантовых компьютеров по сравнению с классическими? Что именно делает квантовые компьютеры эффективнее классических, если, конечно, это на самом деле таи? Задачи какого класса можно эффективно решать на квантовом компьютере и как этот класс соотносится с классом задач, эффективно решаемых на классическом компьютере? Одной нз самых интригующих особенностей квантовых вычислений и квантовой информации является то, насколько мало известно об ответах на эти вопросы! Необходимость их лучшего понимания представляет собой великий вызов будущему.
Подойдя к переднему краю квантовых вычислений, давайте обратимся к истории другого направления мысли, внесшего вклад в квантовые вычисления и квантовую информацию: теории информации. В 40-х гг. одновременно со взрывным развитием информатики происходила революция в понимании связи (соботки»сайоп). В 1948 г. Клод Шеннон опубликовал пару выдающихся рабат, заложивших основы современной теории информации и связи. Возможно, самый важный шаг, сделанный Шенноном, состоял в математическом определении покяп»ия икформоциш Во многих математических науках существует значительная гибкость в выборе фундаментальных определений.
Попробуйте несколько минут подумать, исходя из самых обычных соображений, иад следующим вопросом: как бы вы подошли к математическому определению понятия «источник информации»? Широкое распространение получили сразу несколько решений этой проблемы; однако определение Шеннона оказалось гораздо более плодотворным в плане улучшения понимания. Его использование привело к получению целого ряда серьезных результатов и созданию обширной теории, которая, по всей видимости, адекватно отражает многие (хотя и не все) реальные проблемы связи.
Шеннона интересовали два ключевых вопроса, относящихся к обмену информацией по каналу связи. Во-первых, какие ресурсы требуются для передачи информации по каналу связи? Например, телефонным компаниям нужно знать, сколько информации они могут надежно передать по данному телефонному кабелю. Во-вторых, может ли информация передаваться таким образом, чтобы она была защищена от шумов в канале связи? Шеннон ответил иа два этих вопроса, доказав две фундаментальные теоремы теории информации.
Первая из них — теорема о кодировании для канала без шума — определяет, какое количество физических ресурсов требуется для хранения выходных данных источника информации. Вторая фундаментальная теорема Шеннона — теорема о кодировании для канала с шумам — определяет, какое количество информации можно надежно передать по каналу связи в присутствии шума.
Шеннон показал, что для достижения надежной передачи в присутствии шума можно использовать коды, исправляющие ошибки. Теорема Шеннона о кодировании для канала с шумом устанавливает верхний предел защиты информации, обеспечиваемой кодами, исправляющими ошибки. К сожалению, теорема не дает явного вида кодов, при помощи которых можно было бы достичь этого предела на практике. С момента опубликования 28 Глава 1. Введение и общий обзор работ Шеннона и до настоящего времени исследователи разрабатывают все новые и лучшие классы кодов, исправляющих ошибки, пытаясь приблизиться к пределу, установленному теоремой Шеннона.
Существует сложная теория кодов, исправляющих ошибки, которая предлагает пользователю, желающему разработать хороший код, множество вариантов выбора. Такие коды широко применяются; они используются, например, в проигрывателях компакт-дисков, компьютерных модемах и спутниковых системах связи. Квантовая теория информации развивалась похожим образом. В 1995 г. Вен Шумахер доказал аналог теоремы Шеннона о кодировании в отсутствие шума, по ходу дела определив «квантовый бит», или «кубит», как реальный физический ресурс. Однако до сих пор неизвестно никакого аналога теоремы Шеннона о кодировании для канала с шумом применительно к квантовой информации.
Несмотря на это, по аналогии с классическими эквивалентами была разработана теория исправления квантовых ошибок, которая, как уже упоминалось, позволяет квантовым компьютерам эффективно проводить вычисления в присутствии шума, а также осуществлять надежную связь по квантов»«м каналам с шумом. Классические идеи исправления ошибок оказались очень важными для разработки и понимания кодов, исправляющих квантовые ошибки. В 1996 г.
независимо работавшие Роберт Калдербанк с Питером Шором и Эндрю Стин открыли важный класс квантовых кодов, называемых сейчас СБЯ-кодами, по первым буквам их фамилий. Впоследствии эти коды были отнесены к категории симплектических (стабилизирующих) кодов, независимо разработанных Робертом Калдербанком, Эриком Рейнсом, Питером Шором и Нейлом Слоуном, а также Даниэлем Готтесманом. Эти открытия, опирающиеся на основные идеи классической теории линейного кодирования, в значительной степени способствовали быстрому пониманию кодов, исправляющих квантовые ошибки, и их применению в области квантовых вычислений и квантовой информации.
Теория кодов, исправляющих квантовые ошибки, была разработана с целью защиты квантовых состояний от шума. А как насчет передачи обычной классической информации по квантовому каналу? Насколько эффективно это можно делать? В этой области было обнаружено несколько сюрпризов. В 1992 г. Чарльз Беннет и Стивен Уиснер объяснили, как передавать два классических бита информации путем передачи от отправителя к получателю только одного квантового бита. Это было названо сеерхплотным кодированием. Еще больший интерес представляют результаты в области распределенных кеантиовых вычислений.
Представьте, что у вас есть два соединенных в сеть компьютера, на которых решается некоторая задача. Сколько передач по сети требуется для решения этой задачи? Недавно было показано, что квантовые компьютеры могут потребовать экспоненциально меньшего количества передач для решения определенных задач по сравнению с классическими сетевыми компьютерами! К сожалению, эти задачи пока не представляют особого интереса в реальных условиях, и имеют некоторые нежелательные технические ограничения. Важным вопросом, которым нужно заняться в области кванто- 1.1.
Глобальные перспективы 29 вых вычислений и квантовой информации в будущем, является поиск практически важных задач, для которых распределенные квантовые вычисления имеЮт значительное преимущество нзд распределенными классическими вычислениями. Но вернемся к теории информации. Эта теория начинается с изучения свойств одиночного канала связи. В приложениях мы часто имеем дело не с одним каналом связи, а с сетью из многих канапов.
Свойства таких сетей, относящиеся к передаче информации, изучаются в сепзевоб теории информации, которая развилась в обширную и сложную науку. Сетевая квантовая теория информации, напротив, во многом еще только зарождается. Мы очень мало знаем даже о возможностях передачи информации по сетям квантовых каналов. В последние несколько лет был получен ряд довольно ошеломляющих предварительных результатов; однако единой сетевой теории информации для квантовых каналов пока не существует.