Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
универсальность, т. е. показать, что он функционирует в соответствии с
законом Чёрча-Тьюринга. Доказательство состоит из двух шагов и само по
себе очень простое. Во-первых, состояние любой квантовой системы есть
вектор в гильбертовом пространстве. Таким образом, оно может быть
представлено как угодно точно с помощью конечного числа кубитов. Во-
вторых, эволюция любой квантовой системы есть единичное преобразование и,
таким образом, она может быть сымитирована на квантовом компьютере,
который способен создавать новое единичное преобразование с произвольной
точностью.
Принципиальный вопрос был затронут Мейерсом (1997), когда он определил,
что вычислительные задачи, для которых не определено количество шагов до
завершения, представляют определенные трудности. В противоположность
классическому компьютеру нельзя определить останов квантового компьютера.
Однако в дальнейшем будут рассматриваться либо задачи, у которых можно
прогнозировать число шагов до завершения, либо задачи, об останове
которых квантовый компьютер сообщает с помощью специально
предназначенного для этого кубита, не задействованного в вычислениях
(Deutsch 1985).
Несмотря на вышеуказанные условия, остается очень широкий круг задач для
рассмотрения. Нильсен и Чуанг (Nielsen and Chuang 1997) рассмотрели
применение массива фиксированных квантовых гейтов и показали, что если с
помощью массива можно оперировать кубитами, являющимися одновременно
информацией и программой, то невозможно посредством этого же массива
осуществлять единичное преобразование информации. Однако ниже будут
рассмотрены устройст-
6.2. Закон Чёрча - Тьюринга
67
ва, в которых классический компьютер управляет квантовыми гейтами,
действующими на квантовый регистр. Таким образом, с помощью классической
программы можно "определять" любой массив (любую последовательность)
гейтов и направлять его в квантовый компьютер.
Без сомнения, квантовый компьютер является познавательным теоретическим
инструментом. Но рядом с ним до сих пор стоит большой знак вопроса,
требующий ознакомиться с его неидеальностью. Описания квантового
компьютера, указанные выше, относятся к случаю, когда при выполнении
измерений или применении гейтов может быть достигнута любая точность.
Данные случаи, как и четвертое требование (отсутствие эволюции извне),
являются физически некорректными. Описание квантового компьютера будет
реалистичным, если к каждому их четырех требований добавить положение
относительно допустимой степени точности. Данный вопрос является
предметом сегодняшних исследований, которые будут рассмотрены в разделе
9. Пока же необходимо более подробно изучить возможности тщательно
спроектированного квантового компьютера.
Глава 7 Квантовые алгоритмы
Общеизвестно, что классические компьютеры способны рассчитать поведение
квантовых систем, однако до сих пор не было показано, что квантовый
компьютер может работать с задачами, неразрешимыми для классического
компьютера. Действительно, поскольку физические теории содержат
уравнения, которыми можно оперировать, то кажется очень маловероятным тот
факт, что квантовая механика или какая-либо физическая теория, которая
может появиться в будущем, смогут допустить существование вычислительных
задач, неразрешимых в принципе с помощью довольно большой классической
машины Тьюринга. Однако, как было показано в разделе 3.2, определения
"довольно большая" и "достаточно быстрая" играют ключевую роль в
информатике. Задачи, "сложные" с точки зрения вычислений, на практике
могут оказаться просто неразрешимыми. Говоря более строго, до тех пор,
пока квантовые вычисления не расширят множество решаемых задач (по
сравнению с классическими вычислениями) можно говорить о возможности
появления нового класса сложности. Другими словами, задачи, которые не
могут быть адресованы классическому компьютеру по причине его медленной
работы, могут быть решены с помощью квантового компьютера.
7.1. Имитация физических систем
Первым и наиболее очевидным применением квантовых компьютеров является
имитация каких-либо других квантовых систем. Для имитации вектора
состояния в 2п-мерном гильбертовом пространстве классическому компьютеру
необходимо оперировать векторами, содержащими порядка 2" комплексных
чисел. Для той же цели квантовому компьютеру требуется лишь п кубитов,
что делает его более эффективным с точки зрения необходимого объема
памяти. Однако в общем случае и квантовый, и классический компьютеры
неэффективны для
7.2. Алгоритм, поиска периода функции. Алгоритм Шора 69
имитации эволюции системы. Классический компьютер должен оперировать
матрицами, содержащими 22" элементов, при этом число операций (умножение,
сложение) экспоненциально зависит от п. В свою очередь число элементарных
квантовых логических гейтов экспоненциально зависит от числа единичных
операций квантового компьютера, осуществляемых в 2"-мерном гильбертовом
пространстве. Таким образом, квантовый компьютер не может гарантировать
