Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
Именно таким образом недавно открытый Ловом Гровером из AT&T Белл лаборатории в Нью-Джерси [120] замечательный алгоритм достигает поразительного результата, производя поиск в неупорядоченном списке из N элементов за время всего лишь порядка vN шагов. Рассмотрим, например, поиск определенного телефонного номера в адресной книге, содержащей миллион записей, хранящихся в памяти компьютера в алфавитном порядке. Легко доказать (и это очевидно), что ни один классический алгоритм не может улучшить метод прямого перебора записей одна за одной, пока данный номер не будет найден, что в среднем потребует 500000 обращений в память. Квантовый компьютер может проверить все эти записи одновременно, путем одного обращения в память. Однако, если просто запрограммировать его выдать результат в этом месте, то никакого улучшения по сравнению с классическим алгоритмом не получится: только в одном из миллиона вычислительных путей (т.е. в одной из миллиона вселенных) была проверена запись, которую мы ищем, так что вероятность того, что мы получим эту информацию при измерении состояния компьютера есть всего лишь одна миллионная. Но если мы оставим эту квантовую информацию в компьютере не измеренной, последующая квантовая операция может привести к тому, что эта информация повлияет на другие пути - так же как в описанном выше простом интерференционном эксперименте. Таким образом информация об интересующей нас записи распространяется с помощью квантовой интерференции на другие «вселенные». Оказывается, что если повторить эту порождающую интерференцию процедуру около 1000 раз (в общем случае, раз), то информация о том, какая запись содержит данный номер, будет доступна для измерения с вероятностью 0.5, - то есть она распространится на более чем половину «вселенных». Поэтому повторение всего алгоритма еще несколько раз позволит найти искомую запись с вероятностью, чрезвычайно близкой к 1.
В дополнение к нахождению записи с заданным свойством, вариации алгоритма поиска Гровера могут также находить наименьшее или
Введение в квантовые вычисления 133
наибольшее число в списке, модальное значение и т.д., так что это очень гибкий инструмент. Тем не менее, на практике поиск в физической базе данных вряд ли будет основным применением алгоритма Гровера - по крайней мере до тех пор, пока классическая память будет оставаться дешевле квантовой памяти. Поскольку операция переноса базы данных из классической в квантовую память (биты в кубиты) сама потребует 0(N) шагов, алгоритм Гровера в лучшем случае ускорит время поиска на постоянный множитель, чего можно достигнуть с помощью использования классических параллельных процессоров. По-настоящему алгоритм Гровера найдет применение только в алгоритмических поисках, - то есть, поисках в списках, которые не хранятся в памяти, а сами на ходу генерируются компьютерной программой. Например, играющий в шахматы квантовый компьютер может использовать его для исследования триллионов возможных продолжений из текущей позиции за примерно то же число шагов, которое потребуется классическому компьютеру (использующему слепой поиск «в лоб») для исследования всего миллиона продолжений. Несмотря на большие возможности по «отсечению ветвей дерева» в классических шахматных алгоритмах, это должно привести к очень существенному улучшению.
Как недавно показал Жиль Брассар из университета Монреаля [121], другим важным применением алгоритма Гровера будет использование его в криптоанализе для атаки классических криптографических схем, таких как DES (the Data Encryption Standard, см. главу 2 по квантовой криптографии). Взлом DES по существу требует поиска среди 256=7х1016 возможных ключей. Если их перебирать со скоростью, скажем, в один миллион ключей в секунду, то классическому компьютеру потребуется около тысячи лет для отыскания правильного ключа, в то время как квантовый компьютер использующий алгоритм Гровера сделает это менее чем за 4 минуты!
По странному совпадению, несколько основных свойств квантовых компьютеров имеют приложения в криптографии. Одно из них -это алгоритм Гровера. Другое - это квантовый алгоритм для эффективной факторизации больших целых чисел, открытый в 1991 году Питером Шором, также из AT&T Белл лаборатории в Нью Джерси [36]. Здесь различие в производительности между квантовым и классическими алгоритмами еще более впечатляющее. Математики верят (твердо, хотя они на самом деле это не доказали), что для факторизации числа с N десятичными знаками любому классическому компьютеру требуется число шагов, которое растет экспоненциально с N. Иначе говоря, добавление одного десятичного знака к числу в общем случае умножает время, необходимое для его факторизации, на постоянный множитель (см. раздел 4.2). Таким образом, при уве-
134 Концепция квантовых вычислений
личении числа знаков задача быстро становится нереальной. Наибольшее число, которое было разложено на простые множители в качестве математического соревнования, т.е. число, чьи простые множители были втайне выбраны математиками, чтобы составить задачу для других математиков, состояло из 129 знаков. Никто не может даже представить себе, как можно факторизовать с помощью классического алгоритма число, скажем, из тысячи знаков; вычисление займет время во много раз большее, чем возраст вселенной. Напротив, квантовые компьютеры могут факторизовать число с тысячью знаками за долю секунды - и время расчета будет расти только как куб числа знаков.
