Страница 2 из 16
Чтобы вы могли более наглядно представить себе, что такое экспоненциальный рост, напомню известную легенду о том, как индийский правитель решил отблагодарить изобретателя шахмат за новую интересную игру. Тот попросил выдать ему в качестве награды зерна пшеницы: на первую клетку шахматной доски следовало положить одно зернышко, на вторую — два, на третью — четыре, помещая на каждую следующую клетку в два раза больше зернышек, чем было
на
С квантовым компьютером ситуация та же самая: добавление каждой новой ячейки памяти к уже существующему регистру вдвое увеличивает общую эффективность устройства.
Число различных состояний ячеек памяти у классического компьютера такое же, как у квантового.
кубитом
с
от
кубитах
В квантовом CD имеет место суперпозиционное состояние кубитов, которое содержит в себе сразу все возможные дискретные последовательности из 0 и 1.
исходного
С теоретической точки зрения, создание квантового компьютера особых сложностей не представляет — достаточно того, чтобы ячейки памяти (кубиты) взаимодействовали друг с другом, и мы умели бы целенаправленно манипулировать их состоянием. Однако на практике все оказывается гораздо сложнее — и об этом мы поговорим более подробно в одной из следующих глав.
А сейчас — немного о том, что предшествовало работе по созданию квантового компьютера. Одним из первых, кто обратил внимание на возможную перспективу создания таких компьютеров, был Ричард Фейнман [4].
В 1982 году он задался вопросом, каким должен быть компьютер, позволяющий моделировать природу. Причем имелось в виду не простое моделирование, основанное на хорошо известных законах классической физики, которые отражают ограниченную часть реальности. Фейнман говорил о моделировании физики на фундаментальном уровне, «когда компьютер делает точно то же, что и природа», о более полном и глубоком описании реальности, при котором классическая реальность и ее законы получались бы в классическом приближении как предельный случай (упрощенный вариант квантового описания). Ученый пришел к выводу, что такой компьютер должен быть квантовым.
Но речь шла не о том, что он должен работать по законам квантовой механики — на их основе сейчас и так разрабатывается вся электроника, а о том, что, если в настоящее время все современные приборы и компьютеры работают по квантовым законам, но в классическом режиме, то квантовый компьютер и работать должен в квантовом режиме.
Идеи Фейнмана были интересны, но в те годы они не вызвали особого резонанса в научной среде. Ситуация коренным образом изменилась в 1994 году, когда Питер Шор [5]показал, что квантовый алгоритм способен свести задачу факторизации (разложения целого числа на простые множители) к полиномиальному классу сложности, в то время как обычный алгоритм экспоненциально зависит от входных данных.
Например, обычному компьютеру, выполняющему 10 10операций в секунду, потребуется около года, чтобы разложить на простые множители число из 34 цифр, а время, необходимое для разложения числа из 60 цифр, уже превысит возраст Вселенной (10 17с). Используя же квантовый алгоритм, эту задачу можно решить достаточно быстро.
Результат, полученный П.
Шором
всего
Мы не будем касаться вычислительных возможностей квантовых компьютеров. А вывод Фейнмана относительного того, что квантовые компьютеры способны моделировать реальные процессы на фундаментальном уровне, обсудим подробно, но подойдем к этому вопросу с несколько другой стороны.
Дело в том, что в процессе работы над квантовым компьютером ученым пришлось глубоко вникнуть в эти фундаментальные законы. И это вполне естественно — практическая работа квантово-когерентных устройств на фундаментальном уровне реальности предполагает более глубокое понимание законов этого уровня. Фейнман говорил об этом так: «Если предположить, что мы знаем все физические законы в совершенстве, то, конечно, нам не надо уделять никакого внимания компьютерам. И все же, если задуматься, нам есть что узнать о физических законах, и, если уж быть совсем откровенным, я признаю, что мы многого не понимаем». И действительно, при работе над квантовым компьютером удалось узнать очень много нового о фундаментальных законах, о процессах, с которыми раньше физика никогда не имела дела — таких как декогеренция и рекогеренция, о которых мы еще будем говорить подробно. В результате в науке возникли новые прикладные направления: теория запутанных состояний, теория декогеренции, квантовая теория информации и другие современные разделы квантовой теории, которые часто объединяют под общим названием «физика квантовой информации».
3
Более подробно см. главу 2, раздел 2.4.
4
Feynman R. Simulating physics with computers // International Journal of Theoretical Physics.
Vol. 21.
No. 6/7.
Vol
. 16.
5
Shor
In Proceedings of the 35th A
Goldwasser
Alamitos