Почему квантовые компьютеры до сих пор не продаются

Слова «квантовый компьютер» сейчас не написаны разве что на заборе. Правда, я однажды видел именно на заборе надпись «CNOT» – это одна из логических операций, которую выполняет квантовый компьютер. Так что можно считать, что и на этом носителе имеются записи на данную тему. Те, кто читает разные статьи про науку, наверняка слышали про «квантовый компьютер» много раз. По слухам, если его, наконец, построить, он будет работать быстрее всех Пентиумов и Атлонов вместе взятых, а графика на этой платформе будет такая, что «Матрица» может отдыхать.

На самом деле от квантового компьютера ожидают совсем другого. Есть надежда, что он сможет решать действительно трудные задачи. Русское слово «трудные» оказывается в этом случае очень точным. «Трудный» – значит требующий труда. Например: как по найденному утром в кармане номеру телефона определить, кому же Вы обещали позвонить с самого утра? Ответ в этой задаче прост, как палец, но не радует – в худшем случае надо прочитать весь телефонный справочник. Вот он, имена в строгом алфавитном порядке, телефоны – как придется, в нем 1000 страниц, валяйте. На первый взгляд, совершенная глупость, но именно такие задачи решают системы управления базами данных, которые спрятаны за красивыми интерфейсами. Трудные задачи трудны из-за их огромных размеров.

В любой задаче есть некоторые исходные данные. Размер этих данных решающим образом влияет на время выполнения вычислений и необходимый объем памяти. Если в справочнике, о котором мы говорили в первом примере, только трехзначные номера, то никаких проблем при поиске заветного имени не будет – таких номеров всего тысяча, просмотреть их можно за пару минут без всякого компьютера, и Ваша Маша никуда не денется. Все становится плохо, когда размер данных становится большим. Зависимость времени вычисления от размера данных – главный критерий трудности задачи.

Пусть – число, определяющее размер данных, а – время вычисления. Тогда задачи, для которых (растет пропорционально ), будут совсем простыми. Посмотрите на график логарифма в учебнике – он почти горизонтален при больших значениях аргумента. Задачи, для которых ( – положительное число), будут просто простыми, а задачи, для которых – безнадежно трудными. Мы используем 2 вместо 10, как в учебнике алгебры, в качестве основания логарифмической и показательной функции потому, что в компьютере все данные представлены двоичными числами и – это просто количество двоичных цифр в исходных данных. Попробуйте вычислить для и , и у Вас отпадут многие вопросы.

Можно сколько угодно восхищаться скоростью работы современных компьютеров, но задача о разложении 100-значного числа на простые множители решается полгода, а задача о разложении 200-значного числа не будет решена никогда. Если Вам кажется, что такие задачи просто никому не нужны, то «супер-бупер» секретные ЦРУ-шные коды не будут крякнуты!!

В чем тут дело? Пусть имеется какой-нибудь способ, позволяющий ответить на вопрос: «Является ли некоторый вариант входных данных решением задачи?». Назовем этот способ – «Оракул». Те, кто знаком с программированием, могут считать, что Оракул – это функция, получающая некоторое число и возвращающая булевы ДА и НЕТ. Стиль общения с Оракулом можно представить примерно так:

       – О, Всезнающий, будет ли 123456789 решением моей ничтожной задачи?
       – Чего?
       – 1-2-3-4-5-6-7-8-9 !!!
       – Рупь клади.
       Вы выкладываете рубль и слышите в ответ:
       – Не-а.

Полное же решение задачи – ответ на другой вопрос: «Найти все варианты входных данных, являющиеся решением задачи». Самый тупой способ – перебрать все варианты (заплатив за каждый по рублю). Такие алгоритмы называются переборными, и если ширина данных (число двоичных цифр) равна , то необходимо раз обратиться к Оракулу. В приведенной выше сценке разговора с Оракулом используется десятичная система счисления, и нас интересуют девятизначные числа, следовательно, количество описанных диалогов и, соответственно, рублей, по закону «подлости», будет примерно (миллиард, для непонятливых). Понятно, что на наши деньги таким способом можно решить только простенькие (маленькие) задачки, даже учитывая то, что «наш»-то еще недорого берет.

Иногда удается придумать способ, как вступать в контакт с Оракулом меньшее количество раз. Например, мы можем очень лихо выведать у него номер выигрышного лотерейного билета следующим образом. Разобьем весь интервал номеров пополам и спросим, в какой половине выигрыш. Если он ответит «в верхней», тогда разобьем пополам верхнюю половину и снова спросим, где выигрыш. Действуя таким образом, мы всё узнаем, задав вопросов. Например, если – это миллион, то вопросов будет только 20. Такие алгоритмы называют эффективными. Каждый эффективный алгоритм – большая ценность. Найденный Джимом Кули и Джоном Тьюки алгоритм преобразования Фурье (пока не важно, что это такое), требующий только умножений и сложений (обращений к Оракулу) вместо бесхитростных , породил «мобилы» и «плееры», Шрека и Терминатора, Quake и Counterstrike.

Изо всего этого балагана с Оракулом, логарифмами и Шреком необходимо понять главное: в классическом компьютере в каждый момент времени выполняется вычисление только с одним экземпляром данных. Вычисления с несколькими экземплярами данных можно выполнить только последовательно на одном компьютере, или, если возможно, одновременно на нескольких компьютерах. Конечной причиной такой ситуации является то, что каждый бит в процессоре в каждый момент времени может быть только в одном состоянии («0» или «1») а регистр (группа битов) может хранить и обрабатывать только одно число (слово). Таковы законы поведения объектов классической физики, а бит в компьютере – это не понятие, а устройство.

Последнее заявление, с одной стороны, звучит, как приговор, но, с другой стороны, заставляет вспомнить квантовую механику, в которой работает совсем другое правило – оно называется «принцип суперпозиции». Если результатами измерения состояния некоторой системы могут быть либо ДА либо НЕТ, то, вместе с ними, ее состоянием может быть ДАНЕТ, где и – любые числа, которые удовлетворяют условию . Правда, когда мы попытаемся узнать, каково состояние этой системы (произведем измерение), мы все равно получим либо ДА, либо НЕТ, но вероятность каждого исхода зависит от и . С вероятностью мы получим ДА, а с вероятностью – НЕТ.

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

КОТ В ЯЩИКЕЖИВОЙ КОТМЁРТВЫЙ КОТ.

Будем состояния ДА и НЕТ, ЖИВОЙ КОТ и МЁРТВЫЙ КОТ читать как «0» и «1», а систему, обладающую такими свойствами, называть квантовым битом (кубитом).

Вот тут и возникает самое интересное – группа из таких систем (квантовый регистр) может хранить любое двоичное -разрядное число, а может хранить и ВСЕ ДВОИЧНЫЕ ЧИСЛА СРАЗУ. Под влиянием внешних воздействий коэффициенты при 0 и 1 в каждом квантовом бите (кубите) будут изменяться, и если мы исхитримся организовать эти воздействия (программу) правильно, то финальное состояние квантового регистра будет решением нашей задачи для всех входных данных сразу. Это явление называется массовым квантовым параллелизмом. Это объяснение о-о-очень сильно упрощено, подробности – в университетской аудитории, в специальных лекционных курсах.

После такого захватывающего дух заявления начинаются сплошные оговорки и преодоления разных трудностей, которые начались с 90-х годов и продолжаются до сих пор.

Во-первых, такой компьютер будет эффективно решать далеко не любую задачу. Под квантовый стиль вычислений были придуманы несколько задач, которые плохо решает обычный, даже очень быстрый компьютер, а квантовый, даже очень медленный, решает их быстро, потому что ему требуется не , а просто , или даже один раз повторить вычисления. Но эти задачи были не слишком актуальными. На этом этапе интерес к квантовым вычислениям был чисто академическим, и количество энтузиастов, занимавшихся квантовыми вычислениями, было невелико.

Все радикально изменилось, когда Питер Шор изобрел эффективный квантовый алгоритм разложения числа на простые множители, а Лов Гровер – алгоритм поиска в неупорядоченной базе данных (это как раз пример с телефонным справочником). Если актуальность второй задачи очевидна, поскольку главным применением компьютера является управление базами данных, то актуальность первой задачи сомнительна. На первый взгляд, вряд ли кому-то позарез понадобится представлять большое число в виде произведения двух простых сомножителей, но оказывается, что на сложности этой операции держится один из наиболее надежных методов криптографии – криптографическая система Ривеста, Шамира и Альдемана (RSA). В настоящее время нет вопроса о возможности расшифровки перехваченного сообщения – конечно расшифруют. Вот только когда? Стандартным требованием к криптосистеме является примерно 30-летний срок сохранности информации. Это надо понимать буквально – декодирование должно занимать не менее 30 лет непрерывной работы самого лучшего компьютера. На криптосистемы, подобные RSA, «заложились» многие организации, где шутить не принято, и алгоритм Шора стал серьезной угрозой для их секретов.

Для квантового компьютера уже готовы многие программы, существуют даже языки программирования и компиляторы для них, но сами квантовые компьютеры пока уж больно просты, и не могут соперничать даже со стиральной машиной. Создание полномасштабного квантового компьютера с количеством кубитов порядка тысячи – это самый крутой вызов технологии. Именно поэтому недавнее заявление руководства канадской инновационной компании «D-wave Systems» о создании коммерческого 16-кубитного процессора «Orion», и готовности до конца 2007 года создать 1000-кубитный процессор произвело впечатление разорвавшейся бомбы. Дрожи, шпион и банкир!!!

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

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

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

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

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

Далее – легко сказать: «договоримся не пинать атом слишком сильно», но соседние атомы будут его пинать и «слишком», и «не слишком», и как угодно, не спрашивая нашего разрешения. Как защитить «наших» от «не наших»?

Переходы из одного состояния в другое мы будем осуществлять, освещая атом светом точно известного цвета. Где взять такой фонарь? Многие скажут «Мы знаем! Мы знаем!! Мы возьмем лазер!!!». Как попасть лучом лазера в нужный атом, не задев остальных? Кто заставит лазер светить на строго фиксированной волне, включаться и выключаться после излучения семи с половиной волн? Или – еще круче – как заставить лазер излучить один фотон, а не целый «паровоз» фотонов? Для любопытных – задачка: Как отличить фотон от вспышки света?

Для выполнения вычислений нам необходимо изменять или не изменять состояние одного кубита в зависимости от того, в каком состоянии находится другой. Как заставить взаимодействовать два атома, которые находятся на расстоянии хотя бы 1 микрометр (для атомов это огромное расстояние)?

И, наконец, когда вычисления закончились, как узнать, что получилось? Как узнать состояние отдельного атома?

Чтобы понять, что представляют собой и другие возможные варианты кубитов, а также проблемы, которые возникают при попытке их реализации, нужны знания, немного большие, чем в школе, поэтому хотя бы назовем некоторые из направлений:

• Атом в электромагнитной ловушке или оптической решетке.
• Ядерный спин (много вариантов).
• Поляризационное состояние фотона. «Летающий кубит».
• Зарядовое состояние квантовой точки.
• Сверхпроводящие структуры (вариант, в котором преуспела «D-wave Systems»).
• Атом в оптическом резонаторе.

В книгах по квантовой механике много диковинных слов, можно, например, прочитать главы про квантовую телепортацию (телепортация не запрещена и даже реализована), квантовое запутывание, сверхплотное кодирование, и т.д. Если Вы их (не слова, а книги) внимательно прочтете – то, может быть, придумаете какое-нибудь свое слово. Желаю Вам успеха.

М.В. Лоханин

Старший преподаватель кафедры микроэлектроники ЯрГУ