Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
также дает определение квантовых сетей (Deutsch, 1989) и квантовых
технических гейтов. Последние имеют огромное значение, поскольку
позволяют напрямую говорить о квантовом вычислении.
В начале 1990-х годов несколько авторов (Deutsch и Jazsa, 1992,
Berthiaume and Brassard, 1992, Bernstein и Vazirani, 1993) занимались
поиском задач, чье решение с помощью квантового компьютера было бы более
эффективно, чем их решение посредством любого классического компьютера.
При определении каких-либо понятий, относящихся к основам квантовой
механики, подобный квантовый алгоритм может играть такую же
основополагающую роль, что и неравенство Белла. Первоначально были
обнаружены лишь небольшие различия в работе (алгоритмов): в случае, когда
квантовая механика при условии, что на квантовую систему не действуют
помехи, могла дать определенный ответ - вероятностный классический
компьютер мог получить тот же ответ только с высокой вероятностью. Симон
(Simon) в 1994 году сделал важное открытие, описав эффективный квантовый
алгоритм
Введение
19
для решения (в некотором смысле абстрактной) задачи, не имеющей
классических эффективных решений даже при использовании вероятностных
методов. Это открытие вдохновило Шора (Shor), и он поразил
общественность, когда в 1994 году описал алгоритм, который был не только
эффективен при его реализации на квантовом компьютере, но также был
адресован для решения основной задачи информатики: разложению на
множители простых целых чисел.
Шор, применяя метод квантового Фурье-преобразования, открытый
Копперсмитом (Coppersmith) и Дойчем, описал как разложение на множители,
так и дискретные логарифмы. Другие важные квантовые алгоритмы были
описаны Гровером (Grover, 1997) и Китаевым (Kitaev, 1995).
Как и в случае с классическими вычислениями и теорией информации, при
появлении идей, теоретически описывающих вычисления, возникла попытка
определения основ квантовой информации - задача, сходная с работой
Шеннона. Сложность здесь может заключаться в рассмотрении такой
простейшей квантовой системы, как спина-|
в магнитном поле (система с двумя состояниями). Квантовое состояние спина
есть непрерывная величина, определяемая двумя вещественными числами и, в
принципе, способная хранить бесконечное количество классической
информации. Однако измерение спина дает лишь одно число, способное
принимать два значения ("спин вверх", "спин вниз"), и, таким образом, не
существует какого-либо способа доступа к тому бесконечному объему
информации, который должен храниться данным квантовым состоянием.
Следовательно, будет некорректным давать хранимой информации подобное
определение. Все вышесказанное схоже с задачей перенормировки в квантовой
электродинамике. В таком случае, какой объем информации может хранить
квантовая система с двумя состояниями? Ответ, предложенный Jozca and
Schumacher (1995), заключался в том, что информация, содержащаяся в
системе с двумя состояниями, может использоваться как единица измерения!
Разумеется, Шумахер и Джозса не только предложили этот простой ответ, но
и показали, что системы с двумя состояниями имеют то же значение в
квантовой теории информации, что и бит в классической теории информации.
Они также показали, что объем квантовой информации, содержащийся в любой
квантовой системе, может быть выражен минимальным числом систем с двумя
состояниями - называв-
20
Глава 1
мыми теперь квантовыми битами или кубитами, и которые необходимы для
хранения или передачи с высокой точностью состояния системы. Здесь нужно
вернуться к вопросу об осуществимости квантового вычисления. Существует
простое, но имеющее фундаментальное значение наблюдение, заключающееся в
том. что эффект квантовой интерференции, которая обеспечивает
функционирование алгоритмов, подобных алгоритму Шора, является очень
хрупким: квантовый компьютер очень чутко реагирует на помехи при
эксперименте и прочие воздействия.
Было бы неверным полагать, что первые разработчики не знали о
существовании этой проблемы. Но их главная цель заключалась в
доказательстве (или опровержении) фундаментального значения квантового
компьютера. Опираясь на алгоритм Шора, это фундаментальное значение можно
считать доказанным посредством следующего аргумента: либо природа
допускает существование устройства, работающего с точностью, достаточной
для реализации алгоритма Шора для больших чисел (больших, чем, скажем,
гугол (googol) (Ю100)), либо существует фундаментальное естественное
ограничение точности для реальных систем. Оба возможных случая
представляют собой существенное продвижение в изучении законов природы.
На данном этапе происходит объединение квантовой теории информации и
теории квантовых вычислений. Причина в том, что можно снизить
чувствительность квантового компьютера к шумовым помехам с помощью нового
метода, полученного непосредственно вследствие объединения квантовой
механики и классической теории информации: метода исправления квантовых
