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

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

и хотя бы 1/4 удовлетворяет

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2.}$

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

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

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

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

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

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

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

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

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

Квантовое блуждание — это квантовый аналог классического случайного блуждания , которое можно описать распределением вероятностей по некоторым состояниям. Квантовое блуждание можно описать квантовой суперпозицией состояний. Известно, что квантовые блуждания приводят к экспоненциальному ускорению решения некоторых задач «черного ящика». ^{[19] [20]} Они также обеспечивают полиномиальное ускорение для решения многих задач. Фреймворк для создания алгоритмов квантового блуждания существует и является довольно универсальным инструментом. ^[21]

Проблема выборки бозонов

Проблема отбора бозонов в экспериментальной конфигурации предполагает ^[22] вход бозонов (например, фотонов света) умеренного количества, которые случайным образом рассеиваются в большом количестве выходных мод, ограниченных определенной унитарностью . Когда используются отдельные фотоны света, проблема изоморфна многофотонному квантовому блужданию. ^[23] Тогда проблема состоит в том, чтобы создать адекватную выборку распределения вероятностей выходных данных, которое зависит от входного расположения бозонов и унитарности. ^[24] Решение этой проблемы с помощью классического компьютерного алгоритма требует вычисления перманента матрицы унитарного преобразования, что может быть либо невозможно, либо занять непомерно много времени. В 2014 году было предложено ^[25] , что существующие технологии и стандартные вероятностные методы генерации однофотонных состояний могут быть использованы в качестве входных данных для подходящей квантово-вычислимой линейной оптической сети и что выборка выходного распределения вероятностей будет явно лучше, если использовать квантовые алгоритмы. В 2015 году исследование предсказало ^[26] , что проблема выборки будет иметь аналогичную сложность для входных данных, отличных от фотонов в состоянии Фока , и выявило переход вычислительной сложности от классически моделируемой к такой же сложной, как проблема выборки бозонов, в зависимости от размера входных когерентных амплитуд.

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

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

Задача нахождения треугольника

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

Оценка формулы

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

Хорошо изученная формула — это сбалансированное двоичное дерево, состоящее только из вентилей И-НЕ. ^[33] Этот тип формулы требует Θ( N ^c ) запросов с использованием случайности, ^[34] где . Однако с помощью квантового алгоритма ее можно решить за Θ( N ^0,5 ) запросов. Лучшего квантового алгоритма для этого случая не было известно, пока не был найден алгоритм для нетрадиционной гамильтоновой модели оракула. ^[7] Вскоре последовал тот же результат и для стандартной настройки. ^[35] ${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$

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

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

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

BQP-полные проблемы

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

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

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

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

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

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

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

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

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

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

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

КАОА

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

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

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

Сокращенный квантовый собственный решатель

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

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

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

Рекомендации

1. Нильсен, Майкл А .; Чуанг, Исаак Л. (2000). Квантовые вычисления и квантовая информация . Издательство Кембриджского университета . ISBN 978-0-521-63503-5.
2. Моска, М. (2008). «Квантовые алгоритмы». arXiv : 0808.0369 [квант-ph].
3. Ланзагорта, Марко; Ульманн, Джеффри К. (1 января 2009 г.). Квантовая информатика. Издательство Морган и Клейпул. ISBN 9781598297324.
4. Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3.
5. "Алгоритм Шора".
6. «Руководство пользователя квантового композитора IBM: алгоритм Гровера» . Quantum-Computing.ibm.com . Проверено 7 июня 2022 г.
7. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (2008). «Квантовый алгоритм для гамильтонова дерева NAND». Теория вычислений . 4 : 169–190. arXiv : Quant-ph/0702144 . дои : 10.4086/toc.2008.v004a008 .
8. Чайлдс, Эндрю М .; Ван Дам, В. (2010). «Квантовые алгоритмы решения алгебраических задач». Обзоры современной физики . 82 (1): 1–52. arXiv : 0812.0380 . Бибкод : 2010РвМП...82....1С. doi : 10.1103/RevModPhys.82.1. S2CID  119261679.
9. Шор, PW (1997). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». Журнал SIAM по научным и статистическим вычислениям . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . Бибкод : 1995quant.ph..8027S. дои : 10.1137/s0097539795293172. S2CID  2337707.
10. Боне, Д.; Липтон, Р.Дж. (1995). «Квантовый криптоанализ скрытых линейных функций». В Копперсмите, Д. (ред.). Материалы 15-й ежегодной международной конференции по криптологии, посвященной достижениям в криптологии . Спрингер-Верлаг . стр. 424–437. ISBN 3-540-60221-6.
11. Мур, К .; Рассел, А.; Шульман, ЖЖ (2005). «Симметричная группа бросает вызов строгой выборке Фурье: Часть I». arXiv : Quant-ph/0501056 .
12. Регев, О. (2003). «Квантовые вычисления и проблемы решетки». arXiv : cs/0304005 .
13. Ван Дам, В.; Серусси, Г. (2002). «Эффективные квантовые алгоритмы для оценки сумм Гаусса». arXiv : Quant-ph/0207131 .
14. Ааронсон, С. (2009). «BQP и полиномиальная иерархия». arXiv : 0910.4698 [квант-ph].
15. Гровер, Лов К. (1996). «Быстрый квантовомеханический алгоритм поиска в базе данных». arXiv : Quant-ph/9605043 .
16. Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .
17. Брассар, Г.; Хойер, П.; Тэпп, А. (1998). «Квантовый счет». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 1443. стр. 820–831. arXiv : Quant-ph/9805082 . дои : 10.1007/BFb0055105. ISBN 978-3-540-64781-2. S2CID  14147978.
18. Брассар, Г.; Хойер, П.; Моска, М.; Тэпп, А. (2002). «Квантовое амплитудное усиление и оценка». В Сэмюэле Дж. Ломонако-младшем (ред.). Квантовые вычисления и квантовая информация . AMS Современная математика. Том. 305. стр. 53–74. arXiv : Quant-ph/0005055 . Бибкод : 2000quant.ph..5055B. doi : 10.1090/conm/305/05215. ISBN 9780821821404. S2CID  54753.
19. Чайлдс, AM; Умный.; Деотто, Э.; Фархи, Э.; Гутманн, С.; Спилман, Д.А. (2003). «Экспоненциальное алгоритмическое ускорение за счет квантового блуждания». Материалы 35-го симпозиума по теории вычислений . Ассоциация вычислительной техники . стр. 59–68. arXiv : Quant-ph/0209131 . дои : 10.1145/780542.780552. ISBN 1-58113-674-9.
20. Чайлдс, AM; Шульман, LJ; Вазирани, У.Ф. (2007). «Квантовые алгоритмы для скрытых нелинейных структур». Материалы 48-го ежегодного симпозиума IEEE по основам информатики . ИИЭЭ . стр. 395–404. arXiv : 0705.2784 . дои : 10.1109/FOCS.2007.18. ISBN 978-0-7695-3010-9.
21. Манье, Ф.; Наяк, А.; Роланд, Дж.; Санта, М. (2007). «Поиск с помощью квантовой прогулки». Материалы 39-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 575–584. arXiv : Quant-ph/0608026 . дои : 10.1145/1250790.1250874. ISBN 978-1-59593-631-8.
22. Ральф, TC (июль 2013 г.). «Рисунок 1: Проблема выборки бозонов». Природная фотоника . Природа. 7 (7): 514–515. дои : 10.1038/nphoton.2013.175. S2CID  110342419 . Проверено 12 сентября 2014 г.
23. Перуццо, Альберто; Лобино, Мирко; Мэтьюз, Джонатан CF; Мацуда, Нобуюки; Полити, Альберто; Пулиос, Константинос; Чжоу, Сяо-Ци; Лахини, Йоав; Исмаил, Нур; Вёрхофф, Керстин; Бромберг, Ярон; Зильберберг, Ярон; Томпсон, Марк Г.; О'Брайен, Джереми Л. (17 сентября 2010 г.). «Квантовые блуждания коррелированных фотонов». Наука . 329 (5998): 1500–1503. arXiv : 1006.4764 . Бибкод : 2010Sci...329.1500P. дои : 10.1126/science.1193515. ISSN  0036-8075. PMID  20847264. S2CID  13896075.
24. Лунд, AP; Лэнг, А.; Рахими-Кешари, С.; Рудольф, Т.; О'Брайен, JL; Ральф, TC (5 сентября 2014 г.). «Выборка бозонов из гауссовских состояний». Физ. Преподобный Летт . 113 (10): 100502. arXiv : 1305.4346 . Бибкод : 2014PhRvL.113j0502L. doi : 10.1103/PhysRevLett.113.100502. PMID  25238340. S2CID  27742471.
25. «Квантовая революция — на шаг ближе» . Физика.орг . Омикрон Технолоджи Лимитед . Проверено 12 сентября 2014 г.
26. Сешадрисан, Кошик П.; Олсон, Джонатан П.; Моутс, Кейт Р.; Роде, Питер П.; Даулинг, Джонатан П. (2015). «Выборка бозонов со смещенными однофотонными состояниями Фока по сравнению с когерентными состояниями с добавлением одиночных фотонов: квантово-классическое разделение и переходы сложности вычислений в линейной оптике». Физический обзор А. 91 (2): 022334. arXiv : 1402.0531 . Бибкод : 2015PhRvA..91b2334S. doi : 10.1103/PhysRevA.91.022334. S2CID  55455992.
27. Амбайнис, А. (2007). «Алгоритм квантового блуждания для различения элементов». SIAM Journal по вычислительной технике . 37 (1): 210–239. arXiv : Quant-ph/0311001 . дои : 10.1137/S0097539705447311. S2CID  6581885.
28. Ши, Ю. (2002). «Квантовые нижние оценки столкновений и проблемы различия элементов». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы . Материалы 43-го симпозиума по основам информатики . стр. 513–519. arXiv : Quant-ph/0112086 . дои : 10.1109/SFCS.2002.1181975. ISBN 0-7695-1822-2.
29. Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном». Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .
30. Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном». Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .
31. Александр Белов (2011). «Программы Span для функций с 1-сертификатами постоянного размера». arXiv : 1105.4024 [квант-ph].
32. Манье, Ф.; Санта, М.; Сегеди, М. (2007). «Квантовые алгоритмы решения проблемы треугольника». SIAM Journal по вычислительной технике . 37 (2): 413–424. arXiv : Quant-ph/0310134 . дои : 10.1137/050643684. S2CID  594494.
33. Ааронсон, С. (3 февраля 2007 г.). «NAND теперь для чего-то совершенно другого». Shtetl-Оптимизированный . Проверено 17 декабря 2009 г.
34. Сакс, МЭ; Вигдерсон, А. (1986). «Вероятностные логические деревья решений и сложность оценки игровых деревьев» (PDF) . Материалы 27-го ежегодного симпозиума по основам информатики . ИИЭЭ . стр. 29–38. дои : 10.1109/SFCS.1986.44. ISBN 0-8186-0740-8.
35. Амбайнис, А. (2007). «Почти оптимальный квантовый алгоритм дискретных запросов для оценки формул NAND». arXiv : 0704.3628 [квант-ph].
36. Райхардт, BW; Спалек, Р. (2008). «Квантовый алгоритм вычисления формул на основе Span-программы». Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 103–112. arXiv : 0710.2630 . дои : 10.1145/1374376.1374394. ISBN 978-1-60558-047-0.
37. Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации». LMS Журнал вычислений и математики . 15 : 38–43. дои : 10.1112/S1461157012000046 .
38. Манье, Ф.; Наяк, А. (2007). «Квантовая сложность проверки групповой коммутативности». Алгоритмика . 48 (3): 221–232. arXiv : Quant-ph/0506265 . дои : 10.1007/s00453-007-0057-8. S2CID  3163328.
39. Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN 0-521-63503-9 . 
40. Ааронов, Д.; Джонс, В.; Ландау, З. (2006). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 427–436. arXiv : Quant-ph/0511096 . дои : 10.1145/1132516.1132579. ISBN 1595931341.
41. Фейнман, Р.П. (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Бибкод : 1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310 . дои : 10.1007/BF02650179. S2CID  124545445. 
42. Абрамс, Д.С.; Ллойд, С. (1997). «Моделирование ферми-систем многих тел на универсальном квантовом компьютере». Письма о физических отзывах . 79 (13): 2586–2589. arXiv : Quant-ph/9703054 . Бибкод : 1997PhRvL..79.2586A. doi : 10.1103/PhysRevLett.79.2586. S2CID  18231521.
43. Кассал, И.; Джордан, СП; С любовью, Пи Джей; Мохсени, М.; Аспуру-Гузик, А. (2008). «Квантовый алгоритм полиномиального времени для моделирования химической динамики». Труды Национальной академии наук Соединенных Штатов Америки . 105 (48): 18681–86. arXiv : 0801.2986 . Бибкод : 2008PNAS..10518681K. дои : 10.1073/pnas.0808245105 . ПМК 2596249 . ПМИД  19033207. 
44. Фридман, М.; Китаев А.; Ван, З. (2002). «Моделирование топологических теорий поля с помощью квантовых компьютеров». Связь в математической физике . 227 (3): 587–603. arXiv : Quant-ph/0001071 . Бибкод : 2002CMaPh.227..587F. дои : 10.1007/s002200200635. S2CID  449219.
45. Ааронов, Д.; Джонс, В.; Ландау, З. (2009). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». Алгоритмика . 55 (3): 395–421. arXiv : Quant-ph/0511096 . дои : 10.1007/s00453-008-9168-0. S2CID  7058660.
46. Воцян, П.; Ярд, Дж. (2008). «Полином Джонса: квантовые алгоритмы и приложения в квантовой теории сложности». Квантовая информация и вычисления . 8 (1): 147–180. arXiv : Quant-ph/0603069 . Бибкод : 2006quant.ph..3069W. дои : 10.26421/QIC8.1-2-10. S2CID  14494227.
47. Алагич, Г.; Джордан, СП; Кениг, Р.; Райхардт, BW (2010). «Аппроксимация инвариантов трехмерного многообразия Тураева-Виро универсальна для квантовых вычислений». Физический обзор А. 82 (4): 040302. arXiv : 1003.0923 . Бибкод : 2010PhRvA..82d0302A. doi : 10.1103/PhysRevA.82.040302. S2CID  28281402.
48. Харроу, Арам В.; хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма о физических отзывах . 103 (15): 150502. arXiv : 0811.3171 . Бибкод : 2009PhRvL.103o0502H. doi : 10.1103/PhysRevLett.103.150502. PMID  19905613. S2CID  5187993.
49. Молл, Николай; Баркуцос, Панайотис; епископ Лев С.; Чоу, Джерри М.; Кросс, Эндрю; Эггер, Дэниел Дж.; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М.; Ганцхорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рисс, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на квантовых устройствах ближайшего будущего». Квантовая наука и технология . 3 (3): 030503. arXiv : 1710.01022 . Бибкод : 2018QS&T....3c0503M. дои : 10.1088/2058-9565/aab822. S2CID  56376912.
50. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (14 ноября 2014 г.). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411.4028 [квант-ph].
51. Перуццо, Альберто; МакКлин, Джаррод; Шедболт, Питер; Юнг, Ман-Хонг; Чжоу, Сяо-Ци; С любовью, Питер Дж.; Аспуру-Гузик, Алан; О'Брайен, Джереми Л. (23 июля 2014 г.). «Вариационный решатель собственных значений фотонного квантового процессора». Природные коммуникации . 5 (1): 4213. arXiv : 1304.3061 . Бибкод : 2014NatCo...5.4213P. doi : 10.1038/ncomms5213. ISSN  2041-1723. ПМЦ 4124861 . ПМИД  25055053. 
52. Хигготт, Оскар; Ван, Даочэнь; Брирли, Стивен (2019). «Вариационные квантовые вычисления возбужденных состояний». Квантовый . 3 : 156. arXiv : 1805.08138 . Бибкод : 2019Количество...3..156H. doi : 10.22331/кв-2019-07-01-156. S2CID  119185497.
53. Смарт, Скотт; Мацциотти, Дэвид (18 февраля 2021 г.). «Квантовый решатель сокращенных уравнений на собственные значения для масштабируемого молекулярного моделирования на квантовых вычислительных устройствах». Физ. Преподобный Летт . 125 (7): 070504. arXiv : 2004.11416 . Бибкод : 2021PhRvL.126g0504S. doi : 10.1103/PhysRevLett.126.070504. PMID  33666467. S2CID  216144443.
54. Мацциотти, Дэвид (6 октября 2006 г.). «Антиэрмитово сокращенное уравнение Шредингера: прямое определение двухэлектронных приведенных матриц плотности многоэлектронных молекул». Физ. Преподобный Летт . 97 (14): 143002. Бибкод : 2006PhRvL..97n3002M. doi : 10.1103/PhysRevLett.97.143002. ПМИД  17155245.

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

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

Опросы

• Далзелл, Александр М.; и другие. (2023). «Квантовые алгоритмы: обзор приложений и сквозных сложностей». arXiv : 2310.03011 [квант-ph].
• Смит, Дж.; Моска, М. (2012). «Алгоритмы для квантовых компьютеров». Справочник по естественным вычислениям . стр. 1451–1492. дои : 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 . Бибкод : 2010РвМП...82....1С. doi : 10.1103/RevModPhys.82.1. S2CID  119261679.