Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
преимущества строения (структуры) окружающего мира, можно легко избежать
проблемы шантажа с целью получения кода, которая встречается в анналах
шпионажа.
В то время, пока анализировалась и демонстрировалась квантовая
криптография, на свет незаметно появился квантовый компьютер. В поведении
всех систем, даже тех, которые называются классическими, лежит квантовая
механика. ("Даже отвертка является квантовомеханической системой" -
Landauer, 1995 г.) Несмотря на это, было сложно представить квантово-
механический компьютер, который воспроизводил бы метод работы машины
Тьюринга. Очевидно, недостаточно просто охарактеризовать квантово-
механическую систему, чья эволюция может рассматриваться как вычисление -
необходимо более серьезное доказательство. С другой стороны, известно,
что классические компьютеры могут имитировать посредством вычислений
эволюцию любой квантовой системы. Здесь есть одно "но": ни один
классический процесс не позволяет создавать разделенные системы,
корреляция которых не подчиняется неравенству Белла. Из этого следует,
что корреляции EPR-Bell являются основным квантово-механическим свойством
(Feyman 1982 г.).
Первые идеи рассмотрения вычислений с квантово-механической
Введение
17
точки зрения заключались в преобразовании работы машины Тьюринга к
эквивалентному обратимому процессу и содержали новое понятие -
гамильтониан, способствовавший такой эволюции квантовой системы, которая
копировала бы обратимую машину Тьюринга. Эти идеи появились благодаря
работе Bennett (1973 г., см. также Lecerf 1963 г.), в которой он показал,
что универсальная классическая вычислительная машина (такая, как машина
Тьюринга) может быть обратимой, без потери своей простоты. Benioff (1980,
1982) и другие предложили подобные гамильтонианы типа Тьюринга в начале
80-х годов. Хотя идеи Бенёва не позволяли провести полный анализ
квантового вычисления, они показывали, что унитарная (единичная)
квантовая эволюция по крайней мере обладает такой же вычислительной
мощностью, что и классический компьютер.
Другого подхода придерживался Feyman (1982, 1986). Он рассматривал
возможность создания не универсального вычисления, а универсальной
имитации - специально созданной квантовой системы, способной имитировать
физическое поведение любой другой системы. Очевидно, что таким имитатором
может быть и универсальный компьютер, поскольку любой компьютер является
физической системой. Фейнман привел доводы, из которых следовало, что
квантовая эволюция может более эффективно, чем любой классический
компьютер, использоваться для решения определенного типа задач. Но его
устройство не могло быть названо компьютером, поскольку схема его
функционирования была определена не полностью: он предположил, что можно
определить порядок любого взаимодействия между смежными системами с двумя
состояниями, но не объяснил, как определить этот порядок.
Следующее важное открытие было сделано Дойчем в 1985 году. Его
предложение можно рассматривать как первую приближенную схему работы
квантового компьютера. Хотя следующее утверждение является спорным, но в
силу своей специфичности и простоты, данная схема может являться схемой
действия реального устройства, а в силу своей гибкости она может
описывать работу и универсального компьютера. По своей сути система Дойча
представляет собой ряд систем с двумя базисными состояниями и больше
похожа на регистровую машину, чем на машину Тьюринга (обе машины являются
универсальными классическими вычислительными машинами). Дойч доказал, что
можно получить любую единичную эволюцию, а следовательно, реализо-
18
Глава 1
вать эволюцию, имитирующую развитие любой физической системы, если
возможно осуществить эволюцию системы с двумя состояниями посредством
определенного малого множества простых операций. Опираясь на
вышеизложенные идеи, Дойч также описал создание режима работы, сходного с
функционированием машины Тьюринга.
Сегодня простые операции, предложенные Дойчем, называются квантовыми
"гейтами", поскольку их назначение аналогично назначению двоичных
комплексных гейтов в классических компьютерах. Разными авторами был
предложен наименьший класс гейтов, достаточный для проведения квантовых
вычислений.
Однако есть два спорных аспекта в проекте Дойча: его производительность
(эффективность) и осуществимость. Вопрос эффективности является
фундаментальным в информатике, и на нем строится понятие
"универсальность". Универсальным компьютером называется такой компьютер,
который не только воспроизводит (имитирует) работу любого другого, но и
делает это достаточно- быстро. Здесь выражение "достаточно быстро"
определяется посредством требуемых для вычисления шагов: их количество не
должно зависеть экспоненциально от размера входных данных (точное
значение будет дано в разделе 3.1). С этой точки зрения имитатор Дойча не
является универсальным. Ллойд показал, что он может быть эффективным при
имитации широкого класса квантовых систем (1996). В своей работе Дойч
