Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
(4.3)
(4.4)
144 Концепция квантовых вычислений
общее (перепутанное) состояние п кубитов может входить экспоненциально большое число частей суперпозиции. В этом смысле, квантовая система может содержать экспоненциально больше информации, чем классическая. Эта черта - не следствие того факта, что квантовые амплитуды могут принимать непрерывный набор значений, - она сохраняется, даже если мы ограничим амплитуды некоторым простым дискретным множеством значений. Например, состояние (л+1) кубитов |/ ) в (4.4) содержит информацию обо всем экспоненциально большом наборе значений вида ноль/один для функции f Заметим, что информация, необходимая для описания неперепутанного состояния (т.е. произведения независимых состояний) п кубитов, растет линейно с ростом п, и она в п раз больше информации, необходимой для описания одного единственного состояния.
Формализм квантовой механики позволяет эффективно обрабатывать обширную информацию, содержащуюся в квантовом состоянии, со скоростью, которую нельзя достичь никакими классическими средствами. Это замечательное свойство квантовой теории было впервые отмечено Фейнманом в работе [123]. Предположим, что у нас есть физическая система из п кубитов в некотором перепутанном состоянии |\j/), и мы действуем одно-кубитной операцией U на первый кубит. Это считалось бы в квантовом вычислении одним шагом (или, точнее, постоянным числом шагов, независимым от п - если U надо составлять из других базовых операций, заложенных в компьютере). Рассмотрим теперь классическое вычисление, соответствующее этому преобразованию информации в квантовом состоянии. Можно описать |vy) покомпонентно (относительно базиса п битов) амплитудами, где каждый индекс равен 0 или 1, и U представляется унитарной матрицей 2x2 Uf. Применение U соответствует умножению на матрицу
Таким образом, необходимо выполнить умножение на матрицу 2x2 2Л'/ раз, по одному разу для каждой возможной строки /2.../я, что потребует вычислительных ресурсов, которые будут экспоненциально расти с ростом п. На квантовом же компьютере, благодаря пере-путыванию, эти 2Л'/ повторений не нужны. В этом состоит наш «принцип локальных операций»: единственная локальная операция, действующая на подсистему большой перепутанной системы, перерабатывает информацию в таком объеме, который потребовал бы, в общем случае, экспоненциально больших ресурсов в классическом вычислении.
В вышеуказанном смысле, п кубитов обладают экспоненциально большей емкостью, чем п битов. Однако, у потенциально огромной информации, заключенной в квантовом состоянии, есть еще одно при-
(4.5)
j
Квантовые алгоритмы 145
мечательное свойство: большая ее часть никоим образом не доступна для чтения! Теория квантового измерения накладывает строгие ограничения на количество информации, которое можно получить о неизвестном квантовом состоянии. Эту изначальную недоступность информации можно описать количественно [135, 136] в терминах теории информации Шеннона [137]. В случае общего состояния п кубитов, несущего объем информации порядка 0(2"), оказывается,, что из одной копии такого состояния с помощью каких бы то ни было физических средств может быть получено не более, чем и классических битов информации. Это совпадает с максимальной информационной емкостью п битов.
Полное (в основном, недоступное) информационное содержание данного неизвестного квантового состояния называется квантовой информацией. Естественную квантовую физическую эволюцию можно считать обработкой квантовой информации. Таким образом, взгляд на мир с точки зрения сложности вычислений открывает новое необычное различие между классической и квантовой физикой: чтобы осуществлять естественную квантовую эволюцию, Природа должна обрабатывать огромное количество информации со скоростью, которую нельзя достичь никакими классическими средствами, и, в то же время, большая часть этой обрабатываемой информации держится скрытой от нас! Надо, однако, отметить, что внутренне ей присущая недоступность квантовой информации не отменяет возможности использовать эти огромные возможности по обработке информации для полезных вычислительных целей. Ибо, можно получать небольшие объемы информации о полном виде конечного состояния, для получения которого все равно потребовались бы экспоненциально большие классические ресурсы. Можно это проиллюстрировать примером из описанной выше техники параллельного вычисления: полная квантовая информация состояния \f) в (4.4) включает в себя информацию обо всех отдельных значениях функции f{x), но ее нельзя выяснить никаким измерением. Однако, можно определить некоторые глобальные черты собрания всех значений функции с помощью соответствующих измерений над состоянием f), недиагональных в стандартном базисе (| х>| у)}. Например, если/- периодическая функция, то мы можем определить значение периода, которое, конечно, есть далеко не полная характеристика всей функции, но для оценки которого с помощью классических средств все равно потребовалось бы экспоненциально большое количество раз вычислить значение функции. Этот факт будет ключевым в работе алгоритма Шора (раздел 4.2,6).
