Квантовые вычислительные устройства уже долгое время вызывают интерес у научного сообщества благодаря своей способности решать некоторые задачи намного быстрее, чем классические компьютеры [10, 13], тем самым демонстрируя так называемое квантовое превосходство. Впервые идея квантовых вычислений была предложена независимо Юрием Маниным и Ричардом Фейнманом в начале 1980-х [15, 17], но исследования в этой области начались ещё раньше [12]. С тех пор и по сей день активно рассматриваются способы создания квантовых компьютеров, а также открываются и изобретаются новые квантовые алгоритмы, то есть алгоритмы, исполняемые квантовым вычислительным устройством.
Одним из первых квантовых алгоритмов, демонстрирующих квантовое превосходство, является алгоритм Дойча-Джозы [5]. Впоследствии был предложен также алгоритм Бернштейна-Вазирани [1]. Несмотря на то что их практическое применение может вызывать сомнения, само их существование бросило вызов научному сообществу искать новые алгоритмы, демонстрирующие квантовое превосходство и решающие при этом более животрепещущие задачи.
Квантовый алгоритм, решающий очень важную задачу факторизации целого числа за полиномиальное время, был открыт американским учёным Питером Шором в 1994-м году [13]. На предположении о том, что такая задача нерешаема за обозримое количество времени, основаны многие даже современные криптосистемы. Отсюда стало ясно, что с помощью квантового компьютера можно взломать любую такую систему, и это открытие вызвало сильный интерес к квантовым компьютерам.
Спустя время в 1996-м году американский математик Лов Гровер изобрёл алгоритм поиска в неотсортированной базе данных [10], имеющий квадратичное ускорение по сравнению с лучшими известными классическими алгоритмами, решающими эту задачу. Алгоритм Гровера может быть использован для решения широкого спектра задач, в
частности, NP-полных задач.
Впоследствии американским физиком-теоретиком Дэвидом П. Ди-Винченцо были сформулированы критерии [4], которым должно соответствовать вычислительное устройство для того, чтобы по праву называться квантовым компьютером. Было предложено множество архитектур квантовых компьютеров: основанные на явлении ядерного магнитного резонанса; использующие электроны, запертые в квантовых точках; основанные на ядерных спинах идентичных молекул; использующие запутанные фотоны.
Идея создать квантовый компьютер на фотонах вызывает особый интерес благодаря тому, что практически все критерии ДиВинченцо выполнимы в этой архитектуре без особых усилий. Единственная трудность остаётся в осуществлении преобразований, запутывающих пару фотонов. Исследования в этой области на текущий момент привели к некоторым любопытным результатам [7, 9, 11], однако, к сожалению, все они не масштабируемы, и задача нахождения запутывающего преобразования остаётся открытой.
В связи с этим возникло предположение о том, что для поиска таких преобразований стоит использовать неочевидные техники. Одним из таких подходов является “выращивание” интересующего преобразования с использованием генетических алгоритмов.
1. Постановка задачи
Целью данной работы является реализация алгоритмов поиска схем запутывающих преобразований в линейной квантовой оптике и нахождение преобразований лучше, чем известные на данный момент.
Для достижения данной цели были поставлены следующие задачи.
• Оптимизировать существующий генетический алгоритм поиска.
• Реализовать алгоритм поиска с помощью градиентного спуска.
• Сравнить два подхода и сделать выводы
В ходе выполнения данной работы были достигнуты следующие результаты.
• Оптимизирован существующий генетический алгоритм поиска.
• Реализован алгоритм поиска с помощью градиентного спуска.
• Произведено сравнение двух подходов и сделаны выводы.
• Расширены возможности поискового фреймворка.
Код доступен в репозитории, размещённом на веб-сервисе GitHub.
По данной работе была подготовлена и отправлена на рецензирование совместная публикация “Heralded gate search with genetic algorithms for quantum computation by A. Chernikov, S. S. Sysoev, E. A. Vashukevich, et al.” в журнал Physical Review A.
