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

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

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

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

Обзор [ править ]

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

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

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

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

Алгоритм Дойча – Йожи [ править ]

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

Алгоритм Бернштейна – Вазирани [ править ]

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

Алгоритм Саймона [ править ]

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

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

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

Алгоритм Шора [ править ]

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

Проблема со скрытой подгруппой [ править ]

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

Проблема с взятием проб бозона [ править ]

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

Оценка сумм Гаусса [ править ]

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

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

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

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

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

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

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

Алгоритмы на основе амплитудного усиления [ править ]

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

Алгоритм Гровера [ править ]

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

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

Квантовый счет [ править ]

Квантовый счет решает обобщение проблемы поиска. Он решает проблему подсчета количества отмеченных записей в неупорядоченном списке, вместо того, чтобы просто определять, существует ли он. В частности, он подсчитывает количество отмеченных записей в списке -элементов, при этом ошибка делает только запросы, где - количество отмеченных элементов в списке. ^[20]^[21] Более точно, алгоритм выводит оценку для , количество отмеченных записей, со следующей точностью: . ${\ 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}$

Алгоритмы, основанные на квантовых прогулках [ править ]

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

Проблема отличимости элементов [ править ]

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

Проблема поиска треугольника [ править ]

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

Формула оценки [ править ]

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

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

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

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

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

BQP-Complete проблемы [ править ]

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

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

Вычисление инвариантов узлов [ править ]

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

Квантовая симуляция [ править ]

Идея о том, что квантовые компьютеры могут быть более мощными, чем классические, возникла из наблюдения Ричарда Фейнмана о том, что классическим компьютерам, похоже, требуется экспоненциальное время для моделирования многочастичных квантовых систем. ^[39] С тех пор идея о том, что квантовые компьютеры могут моделировать квантовые физические процессы экспоненциально быстрее, чем классические компьютеры, была значительно переработана и переработана. Эффективные (то есть полиномиальные) квантовые алгоритмы были разработаны для моделирования как бозонных, так и фермионных систем ^[40], и, в частности, для моделирования химических реакций, выходящих за рамки возможностей современных классических суперкомпьютеров, требуется всего несколько сотен кубитов. ^[41]Квантовые компьютеры также могут эффективно моделировать топологические квантовые теории поля. ^[42] В дополнении к своему собственному интересу, этот результат привело к эффективным квантовым алгоритмам для оценки квантовых топологических инвариантов , таких как Джонс ^[43] и HOMFLY полиномов , ^[44] и инвариант Тураев-Виро трехмерных многообразий. ^[45]

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

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

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

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

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

QAOA [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ Нильсен, Майкл А .; Чуанг, Исаак Л. (2000). Квантовые вычисления и квантовая информация . Издательство Кембриджского университета . ISBN 978-0-521-63503-5.
Перейти ↑ Mosca, M. (2008). «Квантовые алгоритмы». arXiv : 0808.0369 [ квант-ф ].
^ Ланзагорта, Марко; Ульманн, Джеффри К. (1 января 2009 г.). Квантовая информатика . Издатели Morgan & Claypool. ISBN 9781598297324.
^ Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3.
^ https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
^ а б Фархи, Э .; Goldstone, J .; Гутманн, С. (2007). «Квантовый алгоритм для гамильтонова NAND-дерева». arXiv : квант-ph / 0702144 .
^ Чайлдс, Эндрю М .; ван Дам, В. (2010). «Квантовые алгоритмы для алгебраических задач». Обзоры современной физики . 82 (1): 1–52. arXiv : 0812.0380 . Bibcode : 2010RvMP ... 82 .... 1С . DOI : 10.1103 / RevModPhys.82.1 . S2CID 119261679 .
Перейти ↑ Shor, PW (1997). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". Журнал SIAM по научным и статистическим вычислениям . 26 (5): 1484–1509. arXiv : квант-ph / 9508027 . Bibcode : 1995quant.ph..8027S . DOI : 10.1137 / s0097539795293172 . S2CID 2337707 .
^ Boneh, D .; Липтон, Р.Дж. (1995). «Квантовый криптоанализ скрытых линейных функций». В Копперсмит, Д. (ред.). Труды 15-й Ежегодной Международной конференции по криптологии по достижениям в криптологии . Springer-Verlag . С. 424–437. ISBN 3-540-60221-6.
^ Мур, К .; Russell, A .; Шульман, LJ (2005). «Симметричная группа бросает вызов строгой выборке Фурье: Часть I». arXiv : квант-ph / 0501056 .
^ Регев, О. (2003). «Квантовые вычисления и решеточные задачи». arXiv : cs / 0304005 .
^ Ральф, TC "Рисунок 1: Проблема отбора бозонов" . Природа Фотоника . Природа . Проверено 12 сентября 2014 года .
^ Лунд, AP; Laing, A .; Рахими-Кешари, С .; Рудольф, Т .; О'Брайен, JL; Ральф, ТК (5 сентября 2014 г.). «Отбор проб бозонов из гауссовских состояний». Phys. Rev. Lett . 113 (10): 100502. arXiv : 1305.4346 . Bibcode : 2014PhRvL.113j0502L . DOI : 10.1103 / PhysRevLett.113.100502 . PMID 25238340 . S2CID 27742471 .
^ «Квантовая революция на шаг ближе» . Phys.org . Omicron Technology Limited . Проверено 12 сентября 2014 года .
^ Seshadreesan, Kaushik P .; Олсон, Джонатан П .; Motes, Keith R .; Роде, Питер П .; Доулинг, Джонатан П. (2015). «Выборка бозона со смещенными однофотонными состояниями Фока по сравнению с когерентными состояниями с добавлением однофотонов: квантово-классическое разделение и переходы вычислительной сложности в линейной оптике». Physical Review . 91 (2): 022334. arXiv : 1402.0531 . Bibcode : 2015PhRvA..91b2334S . DOI : 10.1103 / PhysRevA.91.022334 . S2CID 55455992 .
^ Ван Дам, Вт .; Серусси, Г. (2002). «Эффективные квантовые алгоритмы для оценки гауссовых сумм». arXiv : квант-ph / 0207131 .
^ Ааронсон, С. (2009). «BQP и полиномиальная иерархия». arXiv : 0910.4698 [ квант-ф ].
^ Гровер, Лов К. (1996). «Быстрый квантово-механический алгоритм поиска по базам данных». arXiv : квант-ph / 9605043 .
^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .
^ Brassard, G .; Hoyer, P .; Тэпп, А. (1998). Квантовый счет . Конспект лекций по информатике. 1443 . С. 820–831. arXiv : квант-ph / 9805082 . DOI : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2. S2CID 14147978 .
^ Brassard, G .; Hoyer, P .; Моска, М .; Тэпп, А. (2002). «Квантовое амплитудное усиление и оценка». В Сэмюэле Дж. Ломонако младшем (ред.). Квантовые вычисления и квантовая информация . AMS Contemporary Mathematics. 305 . С. 53–74. arXiv : квант-ph / 0005055 . Bibcode : 2000quant.ph..5055B .
^ Чайлдс, AM; Умная.; Deotto, E .; Farhi, E .; Gutmann, S .; Спилман, Д.А. (2003). «Экспоненциальное алгоритмическое ускорение квантовым блужданием». Материалы 35-го симпозиума по теории вычислений . Ассоциация вычислительной техники . С. 59–68. arXiv : квант-ph / 0209131 . DOI : 10.1145 / 780542.780552 . ISBN 1-58113-674-9.
^ Чайлдс, AM; Schulman, LJ; Вазирани, УФ (2007). «Квантовые алгоритмы для скрытых нелинейных структур». Материалы 48-го ежегодного симпозиума IEEE по основам компьютерных наук . IEEE . С. 395–404. arXiv : 0705.2784 . DOI : 10.1109 / FOCS.2007.18 . ISBN 978-0-7695-3010-9.
^ a b Magniez, F .; Nayak, A .; Roland, J .; Сантха, М. (2007). «Поиск через квантовую прогулку». Материалы 39-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 575–584. arXiv : квант-ph / 0608026 . DOI : 10.1145 / 1250790.1250874 . ISBN 978-1-59593-631-8.
^ Ambainis, A. (2007). «Алгоритм квантового блуждания для определения различимости элементов». SIAM Journal on Computing . 37 (1): 210–239. arXiv : квант-ph / 0311001 . DOI : 10,1137 / S0097539705447311 . S2CID 6581885 .
Перейти ↑ Shi, Y. (2002). Квантовые нижние оценки проблемы столкновения и различимости элементов . Материалы 43-го симпозиума по основам информатики . С. 513–519. arXiv : квант-ph / 0112086 . DOI : 10.1109 / SFCS.2002.1181975 .
^ Ambainis, A. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым радиусом действия» . Теория вычислений . 1 (1): 37–46. DOI : 10.4086 / toc.2005.v001a003 .
^ Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновений с малым радиусом действия» . Теория вычислений . 1 (1): 29–36. DOI : 10.4086 / toc.2005.v001a002 .
^ Александр Беловс (2011). «Программы Span для функций с постоянным размером 1-сертификатов». arXiv : 1105,4024 [ квант-ф ].
^ Magniez, F .; Santha, M .; Сегеди, М. (2007). «Квантовые алгоритмы для задачи треугольника». SIAM Journal on Computing . 37 (2): 413–424. arXiv : квант-ph / 0310134 . DOI : 10.1137 / 050643684 . S2CID 594494 .
Перейти ↑ Aaronson, S. (3 февраля 2007 г.). «NAND теперь для чего-то совершенно другого» . Штетл-Оптимизированный . Проверено 17 декабря 2009 года .
^ Сакс, Мэн; Вигдерсон, А. (1986). «Вероятностные булевы деревья решений и сложность оценки игровых деревьев» (PDF) . Материалы 27-го ежегодного симпозиума по основам информатики . IEEE . С. 29–38. DOI : 10.1109 / SFCS.1986.44 . ISBN 0-8186-0740-8.
^ Ambainis, A. (2007). «Практически оптимальный дискретный квантовый алгоритм запроса для вычисления формул NAND». arXiv : 0704.3628 [ квант-ф ].
^ Райхардт, BW; Спалек, Р. (2008). «Квантовый алгоритм вычисления формул на основе Span-программы». Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 103–112. arXiv : 0710.2630 . DOI : 10.1145 / 1374376.1374394 . ISBN 978-1-60558-047-0.
↑ Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации» . Журнал вычислений и математики LMS . 15 : 38–43. DOI : 10.1112 / S1461157012000046 .
^ Magniez, F .; Наяк, А. (2007). «Квантовая сложность проверки групповой коммутативности». Алгоритмика . 48 (3): 221–232. arXiv : квант-ph / 0506265 . DOI : 10.1007 / s00453-007-0057-8 . S2CID 3163328 .
^ Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN 0-521-63503-9 .
^ Ааронов, Д .; Джонс, В .; Ландау, З. (2006). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 427–436. arXiv : квант-ph / 0511096 . DOI : 10.1145 / 1132516.1132579 .
Перейти ↑ Feynman, RP (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Bibcode : 1982IJTP ... 21..467F . CiteSeerX 10.1.1.45.9310 . DOI : 10.1007 / BF02650179 . S2CID 124545445 .
^ Абрамс, DS; Ллойд, С. (1997). «Моделирование многочастичных ферми-систем на универсальном квантовом компьютере». Письма с физическим обзором . 79 (13): 2586–2589. arXiv : квант-ph / 9703054 . Bibcode : 1997PhRvL..79.2586A . DOI : 10.1103 / PhysRevLett.79.2586 . S2CID 18231521 .
^ Kassal, I .; Jordan, SP; Любовь, ПиДжей; Мохсени, М .; Аспуру-Гузик, А. (2008). «Полиномиальный квантовый алгоритм для моделирования химической динамики» . Труды Национальной академии наук Соединенных Штатов Америки . 105 (48): 18681–86. arXiv : 0801.2986 . Bibcode : 2008PNAS..10518681K . DOI : 10.1073 / pnas.0808245105 . PMC 2596249 . PMID 19033207 .
^ Freedman, M .; Китаев, А .; Ван, З. (2002). "Моделирование топологических теорий поля на квантовых компьютерах". Сообщения по математической физике . 227 (3): 587–603. arXiv : квант-ph / 0001071 . Bibcode : 2002CMaPh.227..587F . DOI : 10.1007 / s002200200635 . S2CID 449219 .
^ Ааронов, Д .; Джонс, В .; Ландау, З. (2009). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Алгоритмика . 55 (3): 395–421. arXiv : квант-ph / 0511096 . DOI : 10.1007 / s00453-008-9168-0 . S2CID 7058660 .
^ Wocjan, P .; Ярд, Дж. (2008). «Полином Джонса: квантовые алгоритмы и приложения в квантовой теории сложности». Квантовая информация и вычисления . 8 (1): 147–180. arXiv : квант-ph / 0603069 . Bibcode : 2006quant.ph..3069W .
^ Alagic, G .; Jordan, SP; König, R .; Райхардт, Б.В. (2010). «Аппроксимация инвариантов трехмерного многообразия Тураева-Виро универсальна для квантовых вычислений». Physical Review . 82 (4): 040302. arXiv : 1003.0923 . Bibcode : 2010PhRvA..82d0302A . DOI : 10.1103 / PhysRevA.82.040302 . S2CID 28281402 .
^ Харроу, Арам W; Хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма с физическим обзором . 103 (15): 150502. arXiv : 0811.3171 . Bibcode : 2009PhRvL.103o0502H . DOI : 10.1103 / PhysRevLett.103.150502 . PMID 19905613 . S2CID 5187993 .
^ Молл, Николай; Баркуцос, Панайотис; Епископ Лев С .; Чоу, Джерри М .; Крест, Андрей; Эггер, Дэниел Дж .; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М .; Ганжорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рис, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на краткосрочных квантовых устройствах». Квантовая наука и технологии . 3 (3): 030503. arXiv : 1710.01022 . DOI : 10.1088 / 2058-9565 / aab822 . S2CID 56376912 .
^ Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (14 ноября 2014 г.). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411,4028 [ квант-ф ].
^ Перуццо, Альберто; МакКлин, Джаррод; Шедболт, Питер; Юнг, Ман-Хонг; Чжоу, Сяо-Ци; С любовью, Питер Дж .; Аспуру-Гузик, Алан; О'Брайен, Джереми Л. (23 июля 2014 г.). «Вариационный решатель собственных значений на фотонном квантовом процессоре» . Nature Communications . 5 (1): 4213. arXiv : 1304.3061 . Bibcode : 2014NatCo ... 5E4213P . DOI : 10.1038 / ncomms5213 . ISSN 2041-1723 . PMC 4124861 . PMID 25055053 .
^ Хигготт, Оскар; Ван, Даочэнь; Бриерли, Стивен (2019). «Вариационный квантовый расчет возбужденных состояний». Quantum . 3 : 156. arXiv : 1805.08138 . DOI : 10,22331 / д-2019-07-01-156 . S2CID 119185497 .

Внешние ссылки [ править ]

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 .

[1] Нильсен, Майкл А .; Чуанг, Исаак Л. (2000). Квантовые вычисления и квантовая информация . Издательство Кембриджского университета . ISBN 978-0-521-63503-5.

[2] Перейти ↑ Mosca, M. (2008). «Квантовые алгоритмы». arXiv : 0808.0369 [ квант-ф ].

[3] Ланзагорта, Марко; Ульманн, Джеффри К. (1 января 2009 г.). Квантовая информатика . Издатели Morgan & Claypool. ISBN 9781598297324.

[nielchuan-4] Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3.

[5] ttps://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm

[Hamiltonian_NAND_Tree-6] а б Фархи, Э .; Goldstone, J .; Гутманн, С. (2007). «Квантовый алгоритм для гамильтонова NAND-дерева». arXiv : квант-ph / 0702144 .

[7] Чайлдс, Эндрю М .; ван Дам, В. (2010). «Квантовые алгоритмы для алгебраических задач». Обзоры современной физики . 82 (1): 1–52. arXiv : 0812.0380 . Bibcode : 2010RvMP ... 82 .... 1С . DOI : 10.1103 / RevModPhys.82.1 . S2CID 119261679 .

[8] Перейти ↑ Shor, PW (1997). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". Журнал SIAM по научным и статистическим вычислениям . 26 (5): 1484–1509. arXiv : квант-ph / 9508027 . Bibcode : 1995quant.ph..8027S . DOI : 10.1137 / s0097539795293172 . S2CID 2337707 .

[9] Boneh, D .; Липтон, Р.Дж. (1995). «Квантовый криптоанализ скрытых линейных функций». В Копперсмит, Д. (ред.). Труды 15-й Ежегодной Международной конференции по криптологии по достижениям в криптологии . Springer-Verlag . С. 424–437. ISBN 3-540-60221-6.

[10] Мур, К .; Russell, A .; Шульман, LJ (2005). «Симметричная группа бросает вызов строгой выборке Фурье: Часть I». arXiv : квант-ph / 0501056 .

[11] Регев, О. (2003). «Квантовые вычисления и решеточные задачи». arXiv : cs / 0304005 .

[12] Ральф, TC "Рисунок 1: Проблема отбора бозонов" . Природа Фотоника . Природа . Проверено 12 сентября 2014 года .

[13] Лунд, AP; Laing, A .; Рахими-Кешари, С .; Рудольф, Т .; О'Брайен, JL; Ральф, ТК (5 сентября 2014 г.). «Отбор проб бозонов из гауссовских состояний». Phys. Rev. Lett . 113 (10): 100502. arXiv : 1305.4346 . Bibcode : 2014PhRvL.113j0502L . DOI : 10.1103 / PhysRevLett.113.100502 . PMID 25238340 . S2CID 27742471 .

[14] «Квантовая революция на шаг ближе» . Phys.org . Omicron Technology Limited . Проверено 12 сентября 2014 года .

[15] Seshadreesan, Kaushik P .; Олсон, Джонатан П .; Motes, Keith R .; Роде, Питер П .; Доулинг, Джонатан П. (2015). «Выборка бозона со смещенными однофотонными состояниями Фока по сравнению с когерентными состояниями с добавлением однофотонов: квантово-классическое разделение и переходы вычислительной сложности в линейной оптике». Physical Review . 91 (2): 022334. arXiv : 1402.0531 . Bibcode : 2015PhRvA..91b2334S . DOI : 10.1103 / PhysRevA.91.022334 . S2CID 55455992 .

[16] Ван Дам, Вт .; Серусси, Г. (2002). «Эффективные квантовые алгоритмы для оценки гауссовых сумм». arXiv : квант-ph / 0207131 .

[17] Ааронсон, С. (2009). «BQP и полиномиальная иерархия». arXiv : 0910.4698 [ квант-ф ].

[18] Гровер, Лов К. (1996). «Быстрый квантово-механический алгоритм поиска по базам данных». arXiv : квант-ph / 9605043 .

[19] Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .

[20] Brassard, G .; Hoyer, P .; Тэпп, А. (1998). Квантовый счет . Конспект лекций по информатике. 1443 . С. 820–831. arXiv : квант-ph / 9805082 . DOI : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2. S2CID 14147978 .

[21] Brassard, G .; Hoyer, P .; Моска, М .; Тэпп, А. (2002). «Квантовое амплитудное усиление и оценка». В Сэмюэле Дж. Ломонако младшем (ред.). Квантовые вычисления и квантовая информация . AMS Contemporary Mathematics. 305 . С. 53–74. arXiv : квант-ph / 0005055 . Bibcode : 2000quant.ph..5055B .

[22] Чайлдс, AM; Умная.; Deotto, E .; Farhi, E .; Gutmann, S .; Спилман, Д.А. (2003). «Экспоненциальное алгоритмическое ускорение квантовым блужданием». Материалы 35-го симпозиума по теории вычислений . Ассоциация вычислительной техники . С. 59–68. arXiv : квант-ph / 0209131 . DOI : 10.1145 / 780542.780552 . ISBN 1-58113-674-9.

[23] Чайлдс, AM; Schulman, LJ; Вазирани, УФ (2007). «Квантовые алгоритмы для скрытых нелинейных структур». Материалы 48-го ежегодного симпозиума IEEE по основам компьютерных наук . IEEE . С. 395–404. arXiv : 0705.2784 . DOI : 10.1109 / FOCS.2007.18 . ISBN 978-0-7695-3010-9.

[Search_via_quantum_walk-24] Magniez, F .; Nayak, A .; Roland, J .; Сантха, М. (2007). «Поиск через квантовую прогулку». Материалы 39-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 575–584. arXiv : квант-ph / 0608026 . DOI : 10.1145 / 1250790.1250874 . ISBN 978-1-59593-631-8.

[25] Ambainis, A. (2007). «Алгоритм квантового блуждания для определения различимости элементов». SIAM Journal on Computing . 37 (1): 210–239. arXiv : квант-ph / 0311001 . DOI : 10,1137 / S0097539705447311 . S2CID 6581885 .

[26] Перейти ↑ Shi, Y. (2002). Квантовые нижние оценки проблемы столкновения и различимости элементов . Материалы 43-го симпозиума по основам информатики . С. 513–519. arXiv : квант-ph / 0112086 . DOI : 10.1109 / SFCS.2002.1181975 .

[27] Ambainis, A. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым радиусом действия» . Теория вычислений . 1 (1): 37–46. DOI : 10.4086 / toc.2005.v001a003 .

[28] Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновений с малым радиусом действия» . Теория вычислений . 1 (1): 29–36. DOI : 10.4086 / toc.2005.v001a002 .

[29] Александр Беловс (2011). «Программы Span для функций с постоянным размером 1-сертификатов». arXiv : 1105,4024 [ квант-ф ].

[30] Magniez, F .; Santha, M .; Сегеди, М. (2007). «Квантовые алгоритмы для задачи треугольника». SIAM Journal on Computing . 37 (2): 413–424. arXiv : квант-ph / 0310134 . DOI : 10.1137 / 050643684 . S2CID 594494 .

[31] Перейти ↑ Aaronson, S. (3 февраля 2007 г.). «NAND теперь для чего-то совершенно другого» . Штетл-Оптимизированный . Проверено 17 декабря 2009 года .

[32] Сакс, Мэн; Вигдерсон, А. (1986). «Вероятностные булевы деревья решений и сложность оценки игровых деревьев» (PDF) . Материалы 27-го ежегодного симпозиума по основам информатики . IEEE . С. 29–38. DOI : 10.1109 / SFCS.1986.44 . ISBN 0-8186-0740-8.

[33] Ambainis, A. (2007). «Практически оптимальный дискретный квантовый алгоритм запроса для вычисления формул NAND». arXiv : 0704.3628 [ квант-ф ].

[34] Райхардт, BW; Спалек, Р. (2008). «Квантовый алгоритм вычисления формул на основе Span-программы». Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 103–112. arXiv : 0710.2630 . DOI : 10.1145 / 1374376.1374394 . ISBN 978-1-60558-047-0.

[35] Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации» . Журнал вычислений и математики LMS . 15 : 38–43. DOI : 10.1112 / S1461157012000046 .

[36] Magniez, F .; Наяк, А. (2007). «Квантовая сложность проверки групповой коммутативности». Алгоритмика . 48 (3): 221–232. arXiv : квант-ph / 0506265 . DOI : 10.1007 / s00453-007-0057-8 . S2CID 3163328 .

[Chuang2000-37] Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN 0-521-63503-9 .

[38] Ааронов, Д .; Джонс, В .; Ландау, З. (2006). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . С. 427–436. arXiv : квант-ph / 0511096 . DOI : 10.1145 / 1132516.1132579 .

[39] Перейти ↑ Feynman, RP (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Bibcode : 1982IJTP ... 21..467F . CiteSeerX 10.1.1.45.9310 . DOI : 10.1007 / BF02650179 . S2CID 124545445 .

[40] Абрамс, DS; Ллойд, С. (1997). «Моделирование многочастичных ферми-систем на универсальном квантовом компьютере». Письма с физическим обзором . 79 (13): 2586–2589. arXiv : квант-ph / 9703054 . Bibcode : 1997PhRvL..79.2586A . DOI : 10.1103 / PhysRevLett.79.2586 . S2CID 18231521 .

[41] Kassal, I .; Jordan, SP; Любовь, ПиДжей; Мохсени, М .; Аспуру-Гузик, А. (2008). «Полиномиальный квантовый алгоритм для моделирования химической динамики» . Труды Национальной академии наук Соединенных Штатов Америки . 105 (48): 18681–86. arXiv : 0801.2986 . Bibcode : 2008PNAS..10518681K . DOI : 10.1073 / pnas.0808245105 . PMC 2596249 . PMID 19033207 .

[42] Freedman, M .; Китаев, А .; Ван, З. (2002). "Моделирование топологических теорий поля на квантовых компьютерах". Сообщения по математической физике . 227 (3): 587–603. arXiv : квант-ph / 0001071 . Bibcode : 2002CMaPh.227..587F . DOI : 10.1007 / s002200200635 . S2CID 449219 .

[43] Ааронов, Д .; Джонс, В .; Ландау, З. (2009). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Алгоритмика . 55 (3): 395–421. arXiv : квант-ph / 0511096 . DOI : 10.1007 / s00453-008-9168-0 . S2CID 7058660 .

[44] Wocjan, P .; Ярд, Дж. (2008). «Полином Джонса: квантовые алгоритмы и приложения в квантовой теории сложности». Квантовая информация и вычисления . 8 (1): 147–180. arXiv : квант-ph / 0603069 . Bibcode : 2006quant.ph..3069W .

[45] Alagic, G .; Jordan, SP; König, R .; Райхардт, Б.В. (2010). «Аппроксимация инвариантов трехмерного многообразия Тураева-Виро универсальна для квантовых вычислений». Physical Review . 82 (4): 040302. arXiv : 1003.0923 . Bibcode : 2010PhRvA..82d0302A . DOI : 10.1103 / PhysRevA.82.040302 . S2CID 28281402 .

[Quantum_algorithm_for_solving_linear_systems_of_equations_by_Harrow_et_al.-46] Харроу, Арам W; Хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма с физическим обзором . 103 (15): 150502. arXiv : 0811.3171 . Bibcode : 2009PhRvL.103o0502H . DOI : 10.1103 / PhysRevLett.103.150502 . PMID 19905613 . S2CID 5187993 .

[47] Молл, Николай; Баркуцос, Панайотис; Епископ Лев С .; Чоу, Джерри М .; Крест, Андрей; Эггер, Дэниел Дж .; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М .; Ганжорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рис, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на краткосрочных квантовых устройствах». Квантовая наука и технологии . 3 (3): 030503. arXiv : 1710.01022 . DOI : 10.1088 / 2058-9565 / aab822 . S2CID 56376912 .

[48] Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (14 ноября 2014 г.). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411,4028 [ квант-ф ].

[49] Перуццо, Альберто; МакКлин, Джаррод; Шедболт, Питер; Юнг, Ман-Хонг; Чжоу, Сяо-Ци; С любовью, Питер Дж .; Аспуру-Гузик, Алан; О'Брайен, Джереми Л. (23 июля 2014 г.). «Вариационный решатель собственных значений на фотонном квантовом процессоре» . Nature Communications . 5 (1): 4213. arXiv : 1304.3061 . Bibcode : 2014NatCo ... 5E4213P . DOI : 10.1038 / ncomms5213 . ISSN 2041-1723 . PMC 4124861 . PMID 25055053 .

[50] Хигготт, Оскар; Ван, Даочэнь; Бриерли, Стивен (2019). «Вариационный квантовый расчет возбужденных состояний». Quantum . 3 : 156. arXiv : 1805.08138 . DOI : 10,22331 / д-2019-07-01-156 . S2CID 119185497 .

[1]