Цифровой журнал «Компьютерра» № 169

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

Квантовый компьютер позволяет факторизовать число, состоящее из N разрядов, за N² операций. Это означает, что появление достаточно мощных квантовых компьютеров сделает непригодными для использования многие популярные криптоалгоритмы.

Другой интересный пример — алгоритм Гровера, позволяющий найти нужный элемент в неотсортированном списке из N элементов, выполнив лишь N^1/2 сравнений. На обычном компьютере для решения той же задачи потребовалось бы N сравнений.

Для наглядности предположим, что в списке миллион элементов. Обычному компьютеру, чтобы отыскать один из них, необходимо выполнить миллион сравнений. Квантовый компьютер, использующий алгоритм Гровера, обойдётся тысячью. Это не экспоненциальное ускорение, как в случае алгоритма Шора, но прибавка всё равно ощутима.

Суровая реальность

_{Три атома бериллия, используемые в качестве кубитов}

Квантовым алгоритмам требуется заметно меньше шагов для поиска ответа, чем их аналогам, работающим на традиционном компьютере. Кое-кто предполагает, что с помощью квантовых компьютеров удастся эффективно решать даже NP-полные задачи, но такое мнение нельзя назвать популярным. Впрочем, даже без NP-полных задач преимущества квантовых компьютеров очевидны. За чем же дело стало?

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

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

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

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

Ренегаты и шарлатаны

В 2007 году канадский стартап D-Wave объявил о намерении выпустить первый коммерческий квантовый компьютер. Намерение подкрепили демонстрацией машины, которая, по уверениям разработчиков, насчитывала шестнадцать кубит.

На глазах у зрителей она решила головоломку судоку, вычислила идеальную комбинацию гостей на гипотетической свадьбе и обработала SQL-запрос в специальной версии MySQL. С этими задачами прекрасно справился бы и обычный компьютер, но презентация и не должна была потрясать воображение.

Воображение потрясало другое: наполеоновские планы D-Wave. К концу года компания намеревалась довести число кубит до 32, а к середине 2008 года впустить квантовый компьютер с 1024 кубитами.

Обещания D-Wave отличались от суровой реальности, хорошо знакомой всем, кто занимался исследованиями в области квантовых вычислений, как небо и земля. Скачок таких масштабов был бы чудом, а чудес, как известно, не бывает.

Скептицизм специалистов столкнулся с полным нежеланием D-Wave рассказывать, каким образом были достигнуты такие успехи. Напрашивается вопрос: а был ли мальчик? Действительно ли устройство, которым хвасталась компания, — это квантовый компьютер? Никаких доказательств этому не было. Развеять сомнения могли бы публикации разработчиков D-Wave в академических журналах, но их не было.

К D-Wave приклеился ярлык «шарлатаны», но компания продолжала работать. Чересчур оптимистичный план пришлось скорректировать. Машина, использующая, если верить D-Wave, 128 кубитов, появилась не в 2008, а лишь в 2011 году. Несколько месяцев назад разрядность довели до 512.

В 2009 году D-Wave и Google провели совместную презентацию. Хартмут Невен, видный специалист в области распознавания лиц, работающий в Google, рассказал об испытании самообучающегося алгоритма для выделения автомобилей на снимках Street View. По утверждению Невена, квантовое устройство D-Wave справилось с задачей лучше, чем традиционные компьютеры в дата-центрах Google.

Такое развитие событий немного озадачило скептиков. Результаты, которые обнародовал Невен, не доказывали, что в D-Wave построили настоящий квантовый компьютер, однако отмести их тоже было нельзя. Если D-Wave — это мошенники, то как же им удалось переманить на свою сторону совсем не глупых людей из Google?