Введение
Алгоритмы, выполняемые на квантовых компьютерах, как правило, используют суперпозицию и/или запутанность.
В квантовых вычислениях квантовый алгоритм — это алгоритм, который выполняется на реалистичной модели квантовых вычислений, наиболее часто используемой моделью является модель квантовой схемы. Классический (или неквантовый) алгоритм — это конечная последовательность инструкций или пошаговая процедура решения задачи, где каждый шаг или инструкция может быть выполнен на классическом компьютере. Аналогично, квантовый алгоритм — это пошаговая процедура, где каждый из этапов может быть выполнен на квантовом компьютере. Хотя все классические алгоритмы также могут быть выполнены на квантовом компьютере, термин «квантовый алгоритм» обычно зарезервирован для алгоритмов, которые по своей сути являются квантовыми или используют существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность. Проблемы, неразрешимые на классических компьютерах, остаются неразрешимыми и на квантовых компьютерах. Квантовые алгоритмы интересны тем, что они могут решать некоторые задачи быстрее, чем классические алгоритмы, поскольку квантовая суперпозиция и квантовая запутанность, используемые в квантовых алгоритмах, обычно не могут быть эффективно смоделированы на классических компьютерах (см. Квантовое превосходство). Наиболее известными алгоритмами являются алгоритм Шора для факторизации и алгоритм Гровера для поиска в неструктурированной базе данных или неупорядоченном списке. Алгоритм Шора работает значительно (почти экспоненциально) быстрее, чем лучший известный классический алгоритм для факторизации — общее решето числового поля. Алгоритм Гровера работает квадратично быстрее, чем лучший возможный классический алгоритм для той же задачи — линейный поиск.
Обзор
Квантовые алгоритмы обычно описываются, в широко используемой модели схемы квантовых вычислений, квантовой схемой, которая воздействует на некоторые входные кубиты и завершается измерением. Квантовая схема состоит из простых квантовых гейтов, каждый из которых воздействует на конечное число кубитов. Квантовые алгоритмы могут также быть представлены в других моделях квантовых вычислений, таких как модель гамильтонова оракула. Квантовые алгоритмы можно классифицировать по основным используемым в них методам. Некоторые из наиболее часто используемых методов и идей в квантовых алгоритмах включают обратное распространение фазы, оценку фазы, кванственное преобразование Фурье, квантовые прогулки, амплитудное усиление и топологическую квантовую теорию поля. Квантовые алгоритмы также могут быть сгруппированы по типу решаемой задачи; см., например, обзор квантовых алгоритмов для алгебраических проблем.
Алгоритмы, основанные на квантовой трансформации Фурье
Квантовое преобразование Фурье является квантовым аналогом дискретного преобразования Фурье и используется в ряде квантовых алгоритмов. Преобразование Адамара также является примером квантового преобразования Фурье над n-мерным векторным пространством над полем F2. Квантовое преобразование Фурье может быть эффективно реализовано на квантовом компьютере, используя лишь полиномиальное количество квантовых гейтов.
Алгоритм Джоззы
Алгоритм Дойча — Йожи решает задачу «черного ящика», для которой любому детерминированному классическому компьютеру требуется экспоненциальное количество запросов к этому ящику, но квантовый компьютер может справиться с ней всего одним запросом. Однако, при сравнении классических и квантовых алгоритмов с допустимой ошибкой, ускорения не наблюдается, поскольку классический вероятностный алгоритм может решить эту задачу с постоянным числом запросов, допускающим небольшую вероятность ошибки. Алгоритм определяет, является ли функция f постоянной (возвращает 0 для всех входных данных или 1 для всех входных данных) или сбалансированной (возвращает 1 для половины области определения и 0 для другой половины).
Алгоритм Бернштейна-Вазирани
Алгоритм Бернштейна — Вазирани — первый квантовый алгоритм, который решает задачу эффективнее, чем наилучший известный классический алгоритм. Он был разработан для демонстрации разделения между классами сложности BQP и BPP с использованием оракула.
Алгоритм Саймона
Алгоритм Саймона решает задачу "черного ящика" экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы с ограниченной ошибкой. Этот алгоритм, обеспечивающий экспоненциальный выигрыш в скорости по сравнению со всеми классическими алгоритмами, которые мы считаем эффективными, послужил основой для алгоритма Шора по факторизации.
Алгоритм оценки квантовой фазы
Алгоритм квантовой оценки фазы используется для определения собственной фазы собственного вектора унитарной операции, при условии наличия квантового состояния, пропорционального этому собственному вектору, и доступа к данной операции. Алгоритм часто применяется в качестве подпрограммы в других алгоритмах.
Алгоритм Шора
Алгоритм Шора решает задачу о дискретном логарифме и задачу факторизации целых чисел за полиномиальное время, в то время как лучшие известные классические алгоритмы требуют времени, растущего быстрее, чем полиномиально. Неизвестно, относятся ли эти задачи к классам P или NP-полных. Это также один из немногих квантовых алгоритмов, решающих задачу, не являющуюся задачей с "черным ящиком", за полиномиальное время, в то время как лучшие известные классические алгоритмы работают за время, растущее быстрее, чем полиномиально.
Проблема скрытых подгрупп
Проблема скрытых подгрупп абелевой группы является обобщением многих задач, которые могут быть решены квантовым компьютером, таких как проблема Саймона, решение уравнения Пелля, проверка главного идеала кольца R и факторизация. Для абелевой проблемы скрытых подгрупп известны эффективные квантовые алгоритмы. Более общая проблема скрытых подгрупп, где группа не обязательно абелева, является обобщением вышеупомянутых задач, а также изоморфизма графов и некоторых задач на решётках. Для определенных неабелевых групп известны эффективные квантовые алгоритмы. Однако для симметрической группы эффективные алгоритмы неизвестны, что позволило бы создать эффективный алгоритм для изоморфизма графов, а для диэдрической группы – решить определенные задачи на решётках.
Оценка гаусовских сумм
Гауссова сумма — это тип экспоненциальной суммы. Наиболее известный классический алгоритм для вычисления этих сумм требует экспоненциального времени. Поскольку задача дискретного логарифмирования сводится к оценке гауссовой суммы, эффективный классический алгоритм для вычисления гауссовых сумм означал бы наличие эффективного классического алгоритма для вычисления дискретных логарифмов, что считается маловероятным. Однако квантовые компьютеры могут вычислять гауссовы суммы с полиномиальной точностью за полиномиальное время.
Алгоритмы, основанные на амплитудной амплификации
Амплитудное усиление — это техника, позволяющая усилить выбранное подпространство квантового состояния. Применение амплитудного усиления обычно обеспечивает квадратичное ускорение по сравнению с соответствующими классическими алгоритмами. Его можно рассматривать как обобщение алгоритма Гровера.
Алгоритм Гровера
Алгоритм Гровера ищет в неструктурированной базе данных (или неупорядоченном списке) с N элементами отмеченный элемент, используя только запросов вместо запросов, необходимых в классическом случае. В классическом случае требуется запросов даже при использовании вероятностных алгоритмов с допустимой ошибкой. Теоретики рассматривали гипотетическое обобщение стандартного квантового компьютера, который мог бы получать доступ к истории скрытых переменных в бо́мской механике. (Такой компьютер является полностью гипотетическим и не был бы стандартным квантовым компьютером, и даже невозможен согласно стандартной теории квантовой механики.) Такой гипотетический компьютер мог бы реализовать поиск в базе данных из N элементов не более чем за шагов. Это немного быстрее, чем шаги, выполняемые алгоритмом Гровера. Однако ни один из методов поиска не позволит ни одной модели квантового компьютера решать NP-полные задачи за полиномиальное время.
Квантовое подсчет
Квантовый подсчет решает обобщение задачи поиска. Он решает задачу подсчета количества отмеченных элементов в неупорядоченном списке, а не просто определения наличия хотя бы одного такого элемента. В частности, он подсчитывает количество отмеченных элементов в списке из *N* элементов с ошибкой не более ε, выполняя только *Q* запросов, где *M* – количество отмеченных элементов в списке. Более точно, алгоритм выдает оценку *E* для *M*, количества отмеченных элементов, с точностью ε.
Алгоритмы на основе квантовых ходок
Квантовая прогулка – это квантовый аналог классической случайной прогулки. Классическую случайную прогулку можно описать распределением вероятностей по некоторым состояниям, а квантовую прогулку – квантовой суперпозицией по состояниям. Известно, что квантовые прогулки обеспечивают экспоненциальное ускорение для некоторых задач типа "чёрного ящика". Они также предоставляют полиномиальное ускорение для многих задач. Существует основа для создания алгоритмов квантовой прогулки, и это универсальный инструмент. Рассматривается ввод бозонов (например, фотонов) умеренного числа, которые случайным образом рассеиваются по большому количеству выходных мод, ограниченных заданной унитарностью. При использовании отдельных фотонов задача изоморфна многофотонной квантовой прогулке. Задача состоит в получении достоверной выборки распределения вероятностей выхода, зависящего от входного расположения бозонов и унитарности. Решение этой задачи классическим компьютерным алгоритмом требует вычисления постоянной (перманента) матрицы унитарного преобразования, что может занять непомерно много времени или оказаться вовсе невозможным. В 2014 году было предложено использовать существующие технологии и стандартные вероятностные методы генерации состояний одиночных фотонов в качестве входа для подходящей квантово-вычислимой линейной оптической сети, и что выборка распределения вероятностей выхода будет существенно превосходить использование квантовых алгоритмов. В 2015 году исследование предсказало, что задача выборки имеет аналогичную сложность для входов, отличных от фотонов в состоянии Фока, и выявило переход в вычислительной сложности – от классически моделируемой до такой же сложной, как задача бозонной выборки, в зависимости от размера когерентных амплитудных входов.
Проблема четкости элементов
Проблема различимости элементов — это задача определения, все ли элементы списка уникальны. Классически для списка размера *n* требуется *n* запросов, однако на квантовом компьютере её можно решить с помощью *O(√n)* запросов. Оптимальный алгоритм был предложен Андрисом Амбаинисом, а Яоюн Ши впервые доказал строгую нижнюю границу при достаточно большом размере диапазона. Амбаинис и Кутин независимо друг от друга (и с использованием различных доказательств) расширили эту работу, чтобы получить нижнюю границу для всех функций.
Проблема поиска треугольника
Проблема поиска треугольника — это задача определения, содержит ли заданный граф треугольник (клику размера 3). Наиболее известная нижняя оценка для квантовых алгоритмов — , но лучший известный алгоритм требует O(N¹․²⁹⁷) запросов, что является улучшением по сравнению с предыдущей лучшей оценкой в O(N¹․³) запросов.
Оценка формулы
Формула — это дерево, в каждом внутреннем узле которого находится логическая операция (gate), а в каждом листе — входной бит. Задача состоит в вычислении значения формулы, которое является выходным значением корневого узла, при наличии доступа к оракулу для получения входных данных. Хорошо изученным примером формулы является сбалансированное двоичное дерево, состоящее только из логических элементов NAND. Для вычисления значения такой формулы требуется запросов с использованием случайности, однако с помощью квантового алгоритма её можно вычислить за запросов. До недавнего времени не было известно квантовых алгоритмов, решающих эту задачу быстрее, чем для нетрадиционной модели гамильтонова оракула. Также существуют быстрые квантовые алгоритмы для более сложных формул.
Коммутативность групп
Проблема состоит в определении, является ли группа «черного ящика», заданная k образующими, коммутативной. Группа «черного ящика» — это группа с функцией-оракулом, которая должна использоваться для выполнения групповых операций (умножение, инверсия и сравнение с единичным элементом). В данном контексте представляет интерес сложность запросов, то есть количество вызовов оракула, необходимых для решения задачи. Детерминированная и рандомизированная сложность запросов равны и соответственно. Квантовый алгоритм требует запросов, а лучший известный классический алгоритм использует запросов.
Проблемы с BQP-комплектом
Класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой) — это множество задач принятия решений, разрешимых квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех экземпляров. Он является квантовым аналогом классического класса сложности BPP. Задача является BQP-полной, если она принадлежит классу BQP и любая задача из BQP может быть сведена к ней за полиномиальное время. Неформально, класс BQP-полных задач включает в себя задачи, которые не проще самых сложных задач в BQP и при этом эффективно разрешимы квантовым компьютером (с ограниченной ошибкой).
Вычисление инвариантов узла
Виттен показал, что топологическая квантовая теория поля Черна — Саймонса (TQFT) может быть решена в терминах полиномов Джонса. Квантовый компьютер может моделировать TQFT и, следовательно, аппроксимировать полином Джонса, который, насколько нам известно, сложно вычислить классически в наихудшем случае.
Квантовая симуляция
Идея о том, что квантовые компьютеры могут превосходить классические по вычислительной мощности, возникла из замечания Ричарда Фейнмана о том, что для моделирования многих квантовых систем частиц классическим компьютерам, по-видимому, требуется экспоненциальное время, в то время как квантовые системы многих тел способны к самоорганизации. С тех пор представление о том, что квантовые компьютеры могут моделировать квантовые физические процессы экспоненциально быстрее, чем классические, получило значительное развитие и детализацию. Были разработаны эффективные (то есть, работающие за полиномиальное время) квантовые алгоритмы для моделирования как бозонных, так и фермионных систем, а также для моделирования химических реакций, которые недоступны современным классическим суперкомпьютерам, используя лишь несколько сотен кубитов. Квантовые компьютеры также способны эффективно моделировать топологические квантовые теории поля. Помимо своего теоретического интереса, этот результат привёл к созданию эффективных квантовых алгоритмов для вычисления квантовых топологических инвариантов, таких как многочлены Джонса и HOMFLY, а также инвариант Тураева-Виро трёхмерных многообразий.
Решение линейной системы уравнений
В 2009 году Арам Харроу, Авинатана Хассидима и Сет Ллойд сформулировали квантовый алгоритм для решения систем линейных уравнений. Алгоритм оценивает результат скалярного измерения над вектором решения заданной системы линейных уравнений. Если система линейных уравнений является разреженной и имеет небольшое число обусловленности, и если пользователя интересует результат скалярного измерения над вектором решения (а не значения самого вектора решения), то время работы алгоритма составляет , где – количество переменных в системе линейных уравнений. Это обеспечивает экспоненциальное ускорение по сравнению с самым быстрым классическим алгоритмом, который работает за (или для положительно полуопределенных матриц).
Гибридные квантово-классические алгоритмы
Гибридные квантово-классические алгоритмы сочетают подготовку и измерение квантового состояния с классической оптимизацией. Эти алгоритмы обычно стремятся определить собственный вектор и собственное значение эрмитова оператора, соответствующие основному состоянию.
КАОА
Алгоритм квантовой приближенной оптимизации вдохновлен квантовым отжигом и реализует дискретизированное приближение квантового отжига с помощью квантовой схемы. Он может быть использован для решения задач теории графов. Алгоритм применяет классическую оптимизацию квантовых операций для максимизации целевой функции.
Вариационный квантовый собственнорешатель
Вариационный квантовый алгоритм собственного решателя (VQE) использует классическую оптимизацию для минимизации среднего значения энергии пробного состояния с целью нахождения основного состояния гермитова оператора, например, гамильтониана молекулы. Его также можно расширить для определения энергий возбужденных состояний молекулярных гамильтонианов.
Контрактный квантовый собственный растворитель
Алгоритм сжатого квантового решателя собственных значений (CQE) минимизирует остаток сжатия (или проекции) уравнения Шредингера на пространство, описываемое двумя (или более) электронами, для нахождения энергии основного или возбужденного состояния и двухелектронной редуцированной матрицы плотности молекулы. Он основан на классических методах решения для энергий и двухелектронных редуцированных матриц плотности непосредственно из антиэрмитова сжатого уравнения Шредингера.