Физикам успешно удалось применить алгоритм Гровера к масштабируемому квантовому компьютеру

Квантовые алгоритмы поиска могут теперь изменить область вычислений, после успешной демонстрации вычислений на масштабируемом устройстве. Еще в 1996 году, программист Лов Гровер из Bell Labs в штате Нью Джерси предложил необычный алгоритм поиска по базам данных. Алгоритмы поиска являются одной из самых важных областей в информатике. С их помощью становятся возможны такие повседневные задачи, такие как поиск в телефонной книге, но также и более экзотические задачи, такие как взлом криптографических кодов. Этот тип алгоритмов повсеместно распространен в информатике.

Получается что любой способ с помощью которого удается ускорить решение какой-либо задачи имеет огромную ценность. Стандартный поиск — алгоритм линейного поиска занимает период времени, который примерно пропорционален количество элементов в массиве данных. То есть это самый худший сценарий, когда для того чтобы найти один элемент необходимо перебрать все элементы массива. Но алгоритм Гровера отличается от такого поиска. Время, которое требуется для нахождения элемента, пропорционально квадратному корню из числа элементов. Программисты называют это квадратичным ускорением. И в мире, где даже скорость поиска увеличивается на несколько процентов от процента, такой алгоритм оказывается чрезвычайно ценным. А квадратичное ускорение — это огромное достижение.

Гровер решил использовать странные но мощные идеи квантовой механики. В классическом мире бит может быть равен 1 либо 0. Но в квантовом мире, один квантовый бил или кубит, может быть 1 и 0 одновременно. То есть хранить в себе все значения сразу. Физики говорят в таком случае, что кубит находится в суперпозиции состояний.

Суперпозиция — это ключ. В этом состоянии алгоритм может искать значение для 0 так и для 1 в один и тот же момент времени. Поскольку он может искать одновременно несколько элементов, то квантовый алгоритм может искать в списке намного быстрее информацию, чем классический аналог. Квантовые алгоритмы должны быть реализованы на квантовом компьютере, и в 1996 году, когда Гровер только выполнял свою работу, это были лишь отдаленные мечты. Но прорыв произошел быстро. Физики продемонстрировали первый примитивный квантовый компьютер в 1998 году и показали, как он может выполнить алгоритм Гровера в том же году. Но такой вид квантовых вычислений ограничен. Алгоритм может работать на нескольких кубитах, но не более того. Это происходит из-за сложности масштабирования кубитов — увеличения количества кубитов.

Но теперь, спустя практически 20 лет, физики начинают создавать квантовые компьютеры, которые имеют потенциал для масштабирования, и следовательно, способны проводить более мощные вычисления. Кэролайн Фиджэт и соавторы из университета Мэрилэнда сообщили, что они использовали алгоритм Гровера на масштабируемом квантовом компьютере впервые. Продемонстрированные результаты открывают путь для амбициозной работы с алгоритмом, который уже можно использовать для дешифрирования кодов. Квантовый компьютер, с которым работает Фиджэт и ее команда, состоит из нити, которая представляет собой пять ионов иттербия подвешенных в электромагнитном поле на одной оси. Каждый ион похож на крошечный магнит, который может быть ориентирован вверх или вниз, манипулировать этими состояниями — спинами можно с помощью лазера. Таким образом, каждый ион может хранить следующую информацию: 1 для вращения вверх и 0 для вращения вниз, например. Поскольку ионы являются квантовыми объектами, то они могут существовать в суперпозиции этих состояний.

Ионы также взаимодействуют друг с другом посредством сил отталкивания, связанных с их положительным зарядом. Это взаимодействие позволяет одному кубиту взаимодействовать с другим кубитом для обработки информации. В этом суть квантовых вычислений. Порядок шагов в этом вычислении — это квантовый алгоритм, в данном случае алгоритм Гровера. Фриджэт и соавторы использовали свою систему для создания трехкубитного квантового компьютера, который может хранить до восьми элементов в базе данных. Затем они использовали алгоритм Гровера, для того чтобы показать, что в среднем можно найти элемент значительно быстрее, по-сравнению с классическим компьютером, для которого требуется по меньшей мере 8 бит информации.

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

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

Эта работа также дает интересный взгляд на гонку по созданию мощных квантовых компьютеров. Победитель этой гонки, скорее всего, получит огромное финансовое вознаграждение, но никто не уверен, какая технология лучше. Недавно был анонсирован апдейт канадских квантовых компьютеров от компании D-Wave Systems, которые уже продается для таких компаний как Google и Lockheed Martin. Эти компьютеры работают с 1000 кубитами, это больше чем с использованием любой другой технологии. Но многие теоретики утверждают, что заявления D-Wave преувеличены и что их машины не могут производить вычислительную мощь, которой могут обладать другие квантовые компьютеры. Именно поэтому многие исследовательские группы пытаются коммерциализировать другие квантовые технологии, которые резко отличаются друг от друга тем, как они хранят и обрабатывают квантовую информацию. Они по-разному манипулируют фотонами, атомами, ионами и молекулами чтобы осуществлять свои квантовые взаимодействия. Из всех этих методов одним из старейших является использование ионной ловушки, для осуществления квантовых вычислений. Исследовательская группа из университет штата Мэриленд является мировым лидером в этой области. Крис Монро, лидер исследовательской группы, основал стартап под названием IonQ, целью которого является коммерциализация этой технологии. Таким образом, демонстрация масштабируемого квантового компьютера, который может реализовать алгоритм Гровера, хоть и с тремя кубитами, является серьезным прогрессом.

В 1998 году, после первой реализации алгоритма Гровера, существовал ряд мнений о том, сколько времени потребуется физикам для того чтобы сделать следующий шаг к масштабируемым квантовым компьютерам. Ряд стартапов должным образом сформировался и рухнул на основе оптимистических прогнозов. В итоге большую часть времени из 20 лет превалировали пессимистические прогнозы. Но тот факт, что это заняло так много времени, ставит под сомнение сложность задачи. Контролировать Вселенную на квантовом масштабе трудно. Интересный вопрос для технологов и венчурных капиталистов заключается в том, можно ли значительно ускорить темпы технологического прогресса.

Пояснения к изображениям:

На изображении 55_1, FIG. 1., на области (а) показана эволюция относительных амплитуд для каждого состояния в алгоритме поиска Гровера. Стадия инициализации создает равную суперпозицию всех возможных входных состояний, таким образом амплитуда alpha_i = 1 для всех базисных состояний |x_i>. Стадия оракула обозначает желаемое состояние, поэтому амплитуда alpha_m маркированного состояния |x_,> приобретает отрицательное значение в то время как амплитуда alpha_b немаркированного состояния |x_i>, x_i != x_m остается без изменений. Стадия усиления выполняет отображение относительно среднего вектора Sigma_x_i |x_i>, который имеет амплитуду A = 1/N Sigma_i_alpha_i, для усиления маркированного состояния. Соответствующее количество итераций шагов оракула и усиления будет максимизировать амплитуду правильного ответа. Все состояния кубита нормированы множителем 1/sqrt(N). Алгоритм также может быть обобщен для маркировки и усиления амплитуды t выбранных состояний. На области (b) показана общая принципиальная схема алгоритма поиска Гровера с использованием логического оракула, изображенного с использованием стандартного изображения квантовой схемы. Последний кубит q_a является замыкающим. На области (с) показан пример булева оракула с одним решением, обозначающим состояние |011>. На области (d) показана общая принципиальная схема алгоритма поиска Гровера с использованием фазового оракула. На области (е) показан пример двухфазного выбора фазы оракулом, который маркирует состояния |011> и |101>.

На изображении 55_2, FIG. 2., на области (а) показано распределения вероятностей для трехкубитных состояний. Средняя значение доверительной вероятности составляет 89,6(2)%, с поправкой на среднее значение ошибки в среднем 1,5%. На области (b) показана квантовая схема для трехкубитной логики (см. статью 55). На области (с) показаны значения вероятностей для четырехкубитных состояний с тремя контроллерами и одной мишенью и одним кубитом оракула. Среднее значение точности процесса составляет 70,5(3)%, с поправкой в 1,9% для средней ошибки.

На изображении 55_3, FIG. 3., показаны результаты для одной итерации алгоритма поиска Гровера с одним решением, выполненным в базе данных с 3 кубитами. Данные для булевой формулы оракула показаны слева, а данные для формулировки фазового оракула показаны справа. На графиках показана вероятность обнаружения каждого выходного состояния. Все приведенные значения представлены в процентном соотношении, при этом теоретический ASP составляет 78,1% и теоретический SSO 100%. Данные скорректированы для средней ошибки со значением 1%.

На изображении 55_4, FIG. 4., показаны результаты выполнения алгоритма поиска Гровера с двумя решениями, выполненными на базе данных с 3 кубитами. Данные для булевой формулы оракула показаны слева, а данные для фазовых значений оракула показаны справа. На графиках показана вероятность обнаружения каждого из состояний. Все значения показаны в процентном соотношении. ASP представляет собой сумму вероятностей каждого из двух маркированных состояний. В результатах учтено среднее значение ошибки 1%.

Источник: www.technologyreview.com

Комментарии: