Что такое квантовый компьютер?

ДОПОЛНЕНИЕ № 1.

* * *

Что такое квант и зачем он нужен
Микромир - атомы, электроны, фотоны и другие частицы - живет по особым законам. Там не просто все очень маленькое, там все совсем другое, и многие явления микромира не имеют аналогов в привычном нам макромире, из-за чего кажутся фантастическими. В классической физике величины могут изменяться равномерно и непрерывно, принимая любые значения. Физика микромира дискретна: у величин есть ряд фиксированных значений, которые они могут принимать. Если пытаться вообразить такую ситуацию в макромире, то можно представить, например, что предметы имеют температуру, которая выражается только целым числом градусов. То есть 10, 20, 31, 36 градусов - может быть, а вот 36,6 - просто невозможно. Нагревать и охлаждать предметы можно, но при этом температура будет скакать туда-сюда сразу на градус. Примерно таким свойством обладают многие характеристики микромира. В частности, энергия электромагнитного поля излучается только в виде дискретных неделимых порций. Вот такая порция и называется квантом.

ДОПОЛНЕНИЕ № 2.

* * *
Как из этого сделать компьютер
Ученые быстро поняли, что рассчитывать напрямую состояние изменяющихся квантовых систем чрезвычайно сложно. Представим себе, что у нас есть система из 30 электронов в ограниченном пространстве, мы знаем все параметры, какие только можем знать, и хотим предсказать, как будет вести себя система в будущем (грубо говоря, какой электрон куда переместится). Даже имея в своем распоряжении суперкомпьютер, в оперативной памяти которого больше битов, чем атомов в видимой области Вселенной, мы не сможем просчитать будущее системы. Между тем мы можем его выяснить, просто поставив эксперимент (разумеется, одно из возможных - но мы ведь можем поставить эксперимент несколько раз). В 1980 году советский математик Юрий Манин задумался: а нельзя ли посмотреть на задачу с другой стороны и, раз квантовая система может то, чего не могут наши компьютеры, использовать эти ее возможности с пользой, а именно - заставить ее производить вычисления? Эту идею поддержали физики, в частности, Нобелевский лауреат Ричард Фейнман. В 90-е годы были найдены конкретные приложения для теоретической квантовой мощи, а в 2001 - создан первый прототип квантового компьютера

ДОПОЛНЕНИЕ № 3.

* * *

Как устроен квантовый компьютер
В обычном компьютере информация хранится в битах, которые принимают значения 0 или 1. Ячейками памяти управляет логический вентиль, выполняющий элементарные логические операции. Ячейкой хранения информации в квантовом компьютере является квантовый бит (quantum bit, qubit), или кубит. Это квантовая частица, которая может иметь два состояния (одно принимается за 0, другое - за 1). Физически кубит может быть устроен по-разному: это может быть атом, имеющий два энергетических состояния (чаще используется квантовая точка, или искусственный атом: маленький фрагмент проводника или полупроводника), атомное ядро или электрон, имеющий два возможных значения спина - вниз и вверх, сверхпроводящее кольцо, в котором ток может течь в двух направлениях, и т.п. N кубит (по данным словарей, надо говорить пять бит, но много битов, логично склонять кубит так же) могут, как и N бит, иметь 2N возможных состояний, однако принципиальное отличие состоит в том, что кубиты могут находиться в суперпозиции этих состояний и быть при этом запутанными между собой. Это значит, что система из нескольких кубитов (квантовый регистр) находится в каждом из состояний с некоторой вероятностью, а самое главное, это значит, что за счет запутанности можно изменить сразу все 2N состояний. В классическом компьютере такая операция потребовала бы 2N шагов. Это обеспечивает беспрецедентный параллелизм вычислений, и именно это является основой мощности квантовых компьютеров. В классическом компьютере за один такт процессор может изменить одно состояние, которое хранят N бит памяти. В квантовом компьютере за один такт можно изменить N кубит, которые находятся в состоянии, являющемся суперпозицией всех базовых состояний, а следовательно, все 2N базовых состояний. Таким образом, квантовый компьютер отчасти является не цифровым, а аналоговым устройством.

ДОПОЛНЕНИЕ № 4.

* * *

Что могут квантовые компьютеры
Пока что самое сложное действие, доступное реально существующим квантовым компьютерам: разработке IBM 2001 года и двум недавним разработкам - это разложение числа 15 на простые множители. Но потенциально они могут гораздо больше. Первый алгоритм для квантовых компьютеров - разложение числа на простые множители - был разработан в 1994 году Питером Шором. Эту задачу умеют решать и классические компьютеры, но времени они на это требуют неизмеримо больше (квантовые же справляются с разложением за время, полиномиальное от раскладываемого числа). Алгоритм Шора имеет большое значение для современной криптографии. Если удастся создать достаточно мощные квантовые компьютеры, то часть использующихся систем шифрования с открытым ключом (например, RSA) станет уязвима для взлома: для подбора тайного ключа необходимо разложить открытый на простые множители. При достаточно длинном ключе даже современным суперкомпьютерам на это нужны сотни лет, а вот перед квантовыми он не устоит. Разрабатываются и применения квантовых компьютеров для противоположной задачи: не взлома, а усиления защиты информации. Еще одним известным алгоритмом является алгоритм Гровера: алгоритм поиска в неструктурированной базе данных.