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

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

В квантовых вычислениях квантовый алгоритм — это алгоритм , который работает на реалистичной модели квантовых вычислений , наиболее часто используемой моделью является модель вычислений с квантовой схемой . ^{[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(\varepsilon ^{-1}{\sqrt {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] , что проблема выборки будет иметь аналогичную сложность для входных данных, отличных от фотонов в фоковском состоянии, и выявило переход вычислительной сложности от классически моделируемой к такой же сложной, как проблема выборки бозонов, в зависимости от размера входных когерентных амплитуд. .

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

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

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

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

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

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

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

Известны также быстрые квантовые алгоритмы для более сложных формул. ^[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.