Квантовый алгоритм - Quantum algorithm

В квантовых вычислениях , А квантовый алгоритм является алгоритмом , который работает на реалистичную модели квантовых вычислений , наиболее часто используемая моделью является квантовой схема моделью вычислений. Классический (или неквантовый) алгоритм - это конечная последовательность инструкций или пошаговая процедура решения проблемы, в которой каждый шаг или инструкция могут выполняться на классическом компьютере . Точно так же квантовый алгоритм - это пошаговая процедура, в которой каждый из шагов может быть выполнен на квантовом компьютере . Хотя все классические алгоритмы также могут выполняться на квантовом компьютере, термин квантовый алгоритм обычно используется для тех алгоритмов, которые кажутся по своей сути квантовыми или используют некоторые существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность .

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

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

Обзор

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

Квантовые алгоритмы можно разделить на категории по основным методам, используемым в алгоритме. Некоторые часто используемые методы / идеи в квантовых алгоритмов включают фазы кик-обратно , оценку фазы , то квант преобразование Фурье , квантовое ходит , амплитуды усиления и топологической квантовой теории поля . Квантовые алгоритмы также могут быть сгруппированы по типу решаемой проблемы, например, см. Обзор квантовых алгоритмов для алгебраических задач.

Алгоритмы на основе квантового преобразования Фурье

Квантового преобразования Фурье является квантовый аналог дискретного преобразования Фурье , и используется в нескольких квантовых алгоритмов. Преобразование Адамара также является примером квантового преобразования Фурье в n-мерном векторном пространстве над полем F ₂ . Квантовое преобразование Фурье может быть эффективно реализовано на квантовом компьютере, используя только полиномиальное количество квантовых вентилей .

Алгоритм Дойча – Йожи

Алгоритм Дойча – Йоже решает проблему черного ящика, которая, вероятно, требует экспоненциально большого числа запросов к черному ящику для любого детерминированного классического компьютера, но может быть выполнена с помощью ровно одного запроса на квантовом компьютере. Если мы допускаем и квантовые алгоритмы с ограниченной ошибкой, и классические алгоритмы, то ускорения не будет, поскольку классический вероятностный алгоритм может решить проблему с постоянным числом запросов с малой вероятностью ошибки. Алгоритм определяет, является ли функция f постоянной (0 на всех входах или 1 на всех входах) или сбалансированной (возвращает 1 для половины входной области и 0 для другой половины).

Алгоритм Бернштейна – Вазирани

Алгоритм Бернштейна – Вазирани - это первый квантовый алгоритм, который решает проблему более эффективно, чем самый известный классический алгоритм. Он был разработан, чтобы создать оракульное разделение между BQP и BPP .

Алгоритм Саймона

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

Алгоритм квантовой оценки фазы

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

Алгоритм Шора

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

Проблема скрытой подгруппы

Абелева скрытые проблемы подгруппа является обобщением многих проблем , которые могут быть решены с помощью квантового компьютера, такие как проблема Саймона, решая уравнение Пелля , испытывая главный идеал в виде кольца R и факторинга . Для решения проблемы скрытых абелевых подгрупп известны эффективные квантовые алгоритмы. Более общая проблема скрытых подгрупп, когда группа не обязательно абелева, является обобщением ранее упомянутых проблем, изоморфизма графов и некоторых решеточных проблем . Для некоторых неабелевых групп известны эффективные квантовые алгоритмы. Однако для симметрической группы не известны эффективные алгоритмы , которые давали бы эффективный алгоритм для изоморфизма графов и диэдральной группы , которая решала бы определенные решеточные задачи.

Проблема взятия проб бозона

Задача дискретизации бозона в экспериментальной конфигурации предполагает вход бозонов (например, фотонов света) умеренного числа, которые случайным образом рассеиваются в большое количество выходных мод, ограниченных определенной унитарностью . Тогда задача состоит в том, чтобы получить точную выборку распределения вероятностей выхода, которое зависит от входной конфигурации бозонов и Унитарности. Решение этой проблемы с помощью классического компьютерного алгоритма требует вычисления перманента унитарной матрицы преобразования, что может быть либо невозможно, либо занять слишком много времени. В 2014 году было предложено использовать существующие технологии и стандартные вероятностные методы генерации однофотонных состояний в качестве входных данных в подходящую квантово-вычислимую линейную оптическую сеть и что выборка выходного вероятностного распределения будет явно лучше при использовании квантовых алгоритмов. В 2015 году исследование предсказало, что проблема дискретизации имеет аналогичную сложность для входов, отличных от фотонов состояния Фока, и выявило переход вычислительной сложности от классической моделируемой к такой же сложной, как проблема дискретизации бозона, в зависимости от размера когерентных входных амплитуд.

Оценка сумм Гаусса

Гаусс сумма представляет собой тип экспоненциальной суммы . Самый известный классический алгоритм оценки этих сумм требует экспоненциального времени. Поскольку проблема дискретного логарифма сводится к оценке суммы Гаусса, эффективный классический алгоритм для оценки сумм Гаусса будет предполагать эффективный классический алгоритм для вычисления дискретных логарифмов, что считается маловероятным. Однако квантовые компьютеры могут оценивать суммы Гаусса с полиномиальной точностью за полиномиальное время.

Фурье-рыбалка и проверка Фурье

У нас есть оракул, состоящий из n случайных логических функций, отображающих n-битные строки в логическое значение. Нам требуется найти n n-битных строк z ₁ , ..., z _n таких, что для преобразования Адамара-Фурье по крайней мере 3/4 строк удовлетворяют

${\ displaystyle | {\ тильда {f}} (z_ {i}) | \ geqslant 1}$

и по крайней мере 1/4 удовлетворяет

${\ displaystyle | {\ тильда {f}} (z_ {i}) | \ geqslant 2.}$

Это можно сделать за квантово-полиномиальное время с ограниченной ошибкой (BQP).

Алгоритмы, основанные на усилении амплитуды

Усиление амплитуды - это метод, который позволяет усиление выбранного подпространства квантового состояния. Применение амплитудного усиления обычно приводит к квадратичному ускорению по сравнению с соответствующими классическими алгоритмами. Его можно рассматривать как обобщение алгоритма Гровера.

Алгоритм Гровера

Алгоритм Гровера ищет в неструктурированной базе данных (или неупорядоченном списке) с N записями отмеченную запись, используя только запросы вместо запросов, требуемых классически. Как правило , запросы требуются даже при использовании вероятностных алгоритмов с ограниченной ошибкой. ${\ displaystyle O ({\ sqrt {N}})}$${\ displaystyle O ({N})}$${\ displaystyle O ({N})}$

Теоретики рассмотрели гипотетическое обобщение стандартного квантового компьютера, который мог бы получить доступ к истории скрытых переменных в бомовской механике . (Такой компьютер является полностью гипотетическим и не может быть стандартным квантовым компьютером или даже невозможным в рамках стандартной теории квантовой механики.) Такой гипотетический компьютер мог бы осуществлять поиск в базе данных из N элементов не более чем поэтапно. Это немного быстрее, чем шаги, предпринимаемые алгоритмом Гровера . Ни один из методов поиска не позволил бы ни одной модели квантового компьютера решать NP-полные задачи за полиномиальное время. ${\ Displaystyle О ({\ sqrt [{3}] {N}})}$${\ displaystyle O ({\ sqrt {N}})}$

Квантовый счет

Квантовый счет решает обобщение проблемы поиска. Он решает проблему подсчета количества отмеченных записей в неупорядоченном списке вместо простого определения того, существует ли он. В частности, он подсчитывает количество отмеченных записей в списке -элементов, при этом ошибка делает только запросы, где - количество отмеченных элементов в списке. Точнее, алгоритм выводит оценку для , количество помеченных со следующей точностью: . ${\ displaystyle N}$${\ displaystyle \ varepsilon}$${\ displaystyle \ Theta \ left ({\ frac {1} {\ varepsilon}} {\ sqrt {\ frac {N} {k}}} \ right)}$${\ displaystyle k}$${\ displaystyle k '}$${\ displaystyle k}$${\ Displaystyle | к-к '| \ leq \ varepsilon k}$

Алгоритмы на основе квантовых блужданий

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

Проблема отличимости элементов

Проблема различимости элементов - это проблема определения, все ли элементы списка различны. Как правило, для списка размером N требуются запросы Ω ( N ) . Однако ее можно решить с помощью запросов на квантовом компьютере. Оптимальный алгоритм - Андрис Амбайнис . Яоюнь Ши впервые доказал, что нижняя граница достаточно велика. Амбаинис и Кутин независимо (и с помощью различных доказательств) расширили его работу, чтобы получить нижнюю оценку для всех функций. ${\ Displaystyle \ Theta (N ^ {2/3})}$

Задача поиска треугольника

Задача поиска треугольника - это проблема определения, содержит ли данный граф треугольник ( клику размера 3). Самая известная нижняя граница для квантовых алгоритмов - это Ω ( N ), но самый лучший известный алгоритм требует O ( N ^1,297 ) запросов, что является улучшением по сравнению с предыдущими лучшими запросами O ( N ^1,3 ).

Формула оценки

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

Хорошо изученной формулой является сбалансированное двоичное дерево только с вентилями NAND. Для этого типа формулы требуется Θ ( N ^c ) запросов с использованием случайности, где . Однако с помощью квантового алгоритма ее можно решить за Θ ( N ^0,5 ) запросов. Лучшего квантового алгоритма для этого случая не было, пока он не был найден для нетрадиционной гамильтоновой модели оракула. Вскоре последовал тот же результат для стандартных настроек. ${\ displaystyle c = \ log _ {2} (1 + {\ sqrt {33}}) / 4 \ приблизительно 0,754}$

Известны также быстрые квантовые алгоритмы для более сложных формул.

Групповая коммутативность

Проблема состоит в том, чтобы определить, является ли группа черного ящика , заданная k генераторами, коммутативной . Группа черного ящика - это группа с функцией оракула, которая должна использоваться для выполнения групповых операций (умножения, инверсии и сравнения с идентичностью). Нас интересует сложность запроса, то есть количество вызовов оракула, необходимых для решения проблемы. Сложности детерминированного и рандомизированного запроса равны и соответственно. Квантовый алгоритм требует запросов, но самый известный алгоритм использует запросы. ${\ Displaystyle \ Theta (к ^ {2})}$${\ Displaystyle \ Theta (к)}$${\ Displaystyle \ Омега (к ^ {2/3})}$${\ Displaystyle О (к ^ {2/3} \ журнал к)}$

BQP-Complete проблемы

Класс сложности BQP (квантово-полиномиальное время с ограниченной ошибкой) - это набор задач решения, решаемых квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех случаев. Это квантовый аналог классического класса сложности BPP .

Проблема является BQP- полной, если она находится в BQP, и любая проблема в BQP может быть сведена к ней за полиномиальное время . Неформально класс BQP- полных задач - это те, которые столь же сложны, как и самые сложные проблемы в BQP, и сами по себе эффективно решаются на квантовом компьютере (с ограниченной ошибкой).

Вычисление инвариантов узлов

Виттен показал, что топологическая квантовая теория поля (ТКТП) Черна-Саймонса может быть решена в терминах полиномов Джонса . Квантовый компьютер может моделировать TQFT и тем самым аппроксимировать многочлен Джонса, который, насколько нам известно, трудно вычислить классическим способом в худшем случае.

Квантовое моделирование

Идея о том, что квантовые компьютеры могут быть более мощными, чем классические, возникла из наблюдения Ричарда Фейнмана о том, что классическим компьютерам, похоже, требуется экспоненциальное время для моделирования многочастичных квантовых систем. С тех пор идея о том, что квантовые компьютеры могут моделировать квантовые физические процессы экспоненциально быстрее, чем классические компьютеры, была значительно переработана и конкретизирована. Эффективные (то есть полиномиальные) квантовые алгоритмы были разработаны для моделирования как бозонных, так и фермионных систем, и, в частности, для моделирования химических реакций, выходящих за рамки возможностей современных классических суперкомпьютеров, требуется всего несколько сотен кубитов. Квантовые компьютеры также могут эффективно моделировать топологические квантовые теории поля. Помимо внутреннего интереса, этот результат привел к созданию эффективных квантовых алгоритмов для оценки квантовых топологических инвариантов, таких как полиномы Джонса и ХОМФЛИ , а также инвариант Тураева-Виро трехмерных многообразий.

Решение линейной системы уравнений

В 2009 году Арам Харроу , Авинатан Хассидим и Сет Ллойд сформулировали квантовый алгоритм для решения линейных систем . Алгоритм оценивает результат скалярного измерения на векторе решения для заданной линейной системы уравнений.

При условии, что линейная система является разреженной и имеет низкое число условий , и что пользователя интересует результат скалярного измерения вектора решения, а не значения самого вектора решения, тогда время выполнения алгоритма составляет , где - количество переменных в линейной системе. Это обеспечивает экспоненциальное ускорение по сравнению с самым быстрым классическим алгоритмом, который работает в (или для положительных полуопределенных матриц). ${\ displaystyle \ kappa}$${\ Displaystyle О (\ журнал (N) \ каппа ^ {2})}$${\ displaystyle N}$${\ Displaystyle О (N \ каппа)}$${\ displaystyle O (N {\ sqrt {\ kappa}})}$

Гибридные квантовые / классические алгоритмы

Гибридные квантовые / классические алгоритмы сочетают подготовку и измерение квантового состояния с классической оптимизацией. Эти алгоритмы обычно нацелены на определение собственного вектора основного состояния и собственного значения эрмитова оператора.

QAOA

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

Вариационный квантовый собственный преобразователь

Алгоритм VQE применяет классическую оптимизацию, чтобы минимизировать математическое ожидание состояния анзаца, чтобы найти энергию основного состояния молекулы. Это также можно расширить, чтобы найти возбужденные энергии молекул.

Контрактный квантовый собственный преобразователь

Алгоритм CQE минимизирует остаток сжатия (или проекции) уравнения Шредингера на пространство двух (или более) электронов, чтобы найти энергию основного или возбужденного состояния и двухэлектронную матрицу приведенной плотности молекулы. Он основан на классических методах решения энергий и двухэлектронных редуцированных матриц плотности непосредственно из антиэрмитова сжатого уравнения Шредингера.

Смотрите также

• Квантовое машинное обучение
• Алгоритмы квантовой оптимизации
• Квантовая сортировка
• Тест на первичность

использованная литература

внешние ссылки

• Quantum Алгоритм Zoo : Полный список квантовых алгоритмов , которые обеспечивают ускорение над самым быстрыми известными классическими алгоритмами.
• Конспект лекций Эндрю Чайлдса о квантовых алгоритмах
• Алгоритм квантового поиска - перебор .

Обзоры

• Smith, J .; Моска, М. (2012). «Алгоритмы для квантовых компьютеров». Справочник по естественным вычислениям . п. 1451. DOI : 10.1007 / 978-3-540-92910-9_43 . ISBN 978-3-540-92909-3. S2CID  16565723 .
• Чайлдс, AM; Ван Дам, В. (2010). «Квантовые алгоритмы для алгебраических задач». Обзоры современной физики . 82 (1): 1–52. arXiv : 0812.0380 . Bibcode : 2010RvMP ... 82 .... 1С . DOI : 10.1103 / RevModPhys.82.1 . S2CID  119261679 .