Поводом для этой темы стала новость о том, что физикам из MIT удалось впервые реализовать квантовый алгоритм Шора в масштабируемой системе. На наши вопросы о том, что это значит, отвечал сотрудник РКЦ, заведующий лабораторией сверхпроводящих материалов Национального исследовательского технологического университета «МИСиС» и профессор Технологического института Карлсруэ Алексей Устинов.

Что такое квантовые вычисления и чем они отличаются от классических?

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

В квантовых алгоритмах используется обычная логика, которой пользуются люди со времен Аристотеля или какая-то своя, квантовая?

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

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

Квантовый компьютер всегда быстрее обычного? Для каких задач квантовый компьютер непригоден и проще использовать обычный?

Например, для наибольшего числа привычных нам задач: сложение, умножение, деление. Это довольно простые задачи, которые быстро и эффективно решаются на обычном компьютере и нет необходимости что-либо усложнять. Сделать то же самое на квантовом компьютере можно, но не нужно. Все существующие сейчас реализации квантового компьютера имеют тактовую частоту намного меньше, чем обычные компьютеры. Будет ли когда-то в будущем реализовано что-то квантовое, что сравнимо по частоте – вопрос трудно прогнозируемый, тут можно только гадать.

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

Как работает алгоритм Шора?

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

Алгоритм Шора в квантовых системах уже реализовывали, но в этот раз его речь идет о том, что это сдалано в масштабируемой системе. Почему это важно?

Масштабирование означает в данном случае то, что хотя алгоритм был продемонстрирован на простом устройстве, в принципе его можно «безболезненно» усложнить добавлением новых кубитов. Объясню, почему это важно. Любимая задача, которую до сих пор решали экспериментаторы заключалась в том, чтобы разложить на множители совсем небольшое число, например число 15. Именно оно было очень популярно во многих экспериментах с квантовыми системами. Раскладывалось оно, понятное дело, на 5×3=15. Были эксперименты и с числом 21. Однако, чтобы двигаться дальше, необходимо сделать масштабирование системы, т.е. сделать устройство, в котором можно будет разумными усилиями делать разложение больших чисел, а для этого необходимо использовать много кубитов. Сложность в том, что все они должны работать вместе, а заставить их это делать непросто. Это с одной стороны. С другой стороны, должны быть очень эффективные устройства контроля и управления, которые будут работать независимо от сложности системы. Все это вызывает массу физических и инженерных проблем, которые надо решать.

Читать дальше.