Квантовая магия. С. И. Доронин

которых являются суперпозиционные состояния, человечество никогда еще не располагало. Когда они начнут выходить из научных лабораторий в коммерческое производство и в нашу повседневную жизнь, это станет началом второй квантовой революции. По своим масштабам и последствиям она значительно превзойдет «скромные» результаты первой, которая «родила» атомную бомбу и практически все современные электронно-технические устройства.

      Идеи Фейнмана были интересны, но в те годы они не вызвали особого резонанса в научной среде. Ситуация коренным образом изменилась в 1994 году, когда Питер Шор[5] показал, что квантовый алгоритм способен свести задачу факторизации (разложения целого числа на простые множители) к полиномиальному классу сложности, в то время как обычный алгоритм экспоненциально зависит от входных данных.

      Например, обычному компьютеру, выполняющему 10¹⁰ операций в секунду, потребуется около года, чтобы разложить на простые множители число из 34 цифр, а время, необходимое для разложения числа из 60 цифр, уже превысит возраст Вселенной (10¹⁷ с). Используя же квантовый алгоритм, эту задачу можно решить достаточно быстро.

      Результат, полученный П. Шором, с практической точки зрения означает, что квантовый компьютер способен за реальное время «взломать» шифры, используемые, например, в банковской сфере. Там как раз широко применяется криптосистема, основанная на невозможности разложения достаточно большого числа на простые множители за приемлемое для обычных компьютеров время. Осознав ситуацию и на наглядном примере убедившись в возможностях квантового компьютера, финансовый мир, частные фирмы и государственные учреждения многих стран мира направили огромные средства на научные исследования в области квантовых вычислений. В эту же сферу устремились и многие научные коллективы, срочно переориентировав свою тематику. Квантовым вычислениям стало посвящаться наибольшее количество научных публикаций по сравнению с другими разделами физики. В отдельные годы число напечатанных в реферируемых журналах статей на эту тему превышало количество публикаций на все другие темы из области физики вместе взятые. Все это способствовало тому, что достаточно быстро были созданы реальные прототипы квантового компьютера, а теоретические основы, необходимые для его создания, получили очень мощный импульс к развитию. Прежде всего это касается теории запутанных состояний, теории декогеренции и квантовой теории информации.

      Мы не будем касаться вычислительных возможностей квантовых компьютеров. А вывод Фейнмана относительного того, что квантовые компьютеры способны моделировать реальные процессы на фундаментальном уровне, обсудим подробно, но подойдем к этому вопросу с несколько другой стороны.

      Дело в том, что в процессе работы над квантовым компьютером ученым пришлось глубоко вникнуть в эти фундаментальные законы. И это вполне естественно – практическая работа квантово-когерентных устройств

5

Shor P. W. In Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, CA). Р. 124 (1994).