Разложение n-разрядного целого числа на простые множители.
Квантовый алгоритм Питера Шора решает это за \( \widetilde {O} (n ^ 3) \) [82,125]. Самым быстрым известным классическим алгоритмом для разложения на множители целых чисел является метод решета числового поля, который, как полагают, выполняется за время \( 2 ^ {\widetilde {O}(n ^ {1/3})}\). Наилучшей строго доказанной верхней границей классической сложности факторизации является \( O(2 ^ {n /4 + o(1)}) \) с помощью алгоритма Полларда-Штрассена [252,362]. Алгоритм факторинга Шора угрожает шифрованию с открытым ключом RSA, а тесно связанные квантовые алгоритмы для дискретных логарифмов угрожают схемам с цифровой подписью DSA и ECDSA и протоколу обмена ключами Диффи-Хеллмана. Более быстрый квантовый алгоритм, чем алгоритм Шора, для частного случая разложения на множители “полупростых”, которые широко используются в криптографии, приведен в [271]. Если существуют малые коэффициенты, алгоритм Шора может быть превзойден квантовым алгоритмом, использующим поиск Гровера для ускорения метода факторизации эллиптической кривой [366]. Дополнительные оптимизированные версии алгоритма Шора приведены в работах [384,386,431]. Существуют предложенные классические криптосистемы с открытым ключом, которые, как считается, не могут быть взломаны квантовыми алгоритмами, см. [248]. В основе алгоритма факторинга Шора лежит нахождение порядка, которое может быть сведено к задаче абелевой скрытой подгруппы, которая решается с помощью квантового преобразования Фурье. Известно, что ряд других задач сводится к целочисленной факторизации, включая проблему принадлежности матричных групп над полями нечетного порядка [253] и некоторые диофантовы задачи, относящиеся к синтезу квантовых схем [254].

Дано: три n-разрядных числа a, b и N с обещанием, что \( b = a^s \mod N \) для некоторого s. Найти: s. Как показал Шор [82], это может быть достигнуто на квантовом компьютере за время poly(n) время. Самый быстрый известный классический алгоритм требует суперполиномиального времени в n. С помощью методов, аналогичных описанным в [82], квантовые компьютеры могут решать задачу дискретного логарифмирования на эллиптических кривых, тем самым нарушая криптографию эллиптических кривых [109, 14]. Дальнейшие оптимизации алгоритма Шора приведены в работах [385,432]. Суперполиномиальное квантовое ускорение также было распространено на задачу дискретного логарифмирования полугрупп [203,204]. Смотрите также абелеву скрытую подгруппу.

Уравнение Пелла имеет вид \( x ^ 2 - d y ^ 2 = 1 \), где d - натуральное число, не являющееся квадратом. Для любого такого d существует бесконечно много пар целых чисел (x, y), решающих это уравнение. Пусть \( (x_1,y_1) \) - пара, которая минимизирует \( x+y\sqrt{d} \). Если d является n-разрядным целым числом (т.е. \( 0 \leq d \lt 2^ n \)), то для \( (x_1,y_1) \) в общем случае может потребоваться экспоненциально много битов для записи. Таким образом, в общем случае невозможно найти \( (x_1,y_1) \) за полиномиальное время. Пусть \( R = \log(x_1+y_1 \sqrt{d}) \). \( \lfloor R \rceil \) однозначно идентифицирует \( (x_1,y_1) \). Как показано Халлгреном [49], при заданном n-разрядном числе d квантовый компьютер может найти \( \lfloor R \rceil \) за время poly(n). Классический алгоритм решения этой задачи за полиномиальное время неизвестен. Факторинг сводится к этой проблеме. Этот алгоритм нарушает криптосистему Бухмана-Уильямса. Смотрите также абелеву скрытую подгруппу.

Дано: n-разрядное целое число d и обратимый идеал I кольца \( \mathbb{Z}[\sqrt{d}] \). I является главным идеалом, если существует \( \alpha \in \mathbb{Q}(\sqrt{d}) \) такой, что \( I = \alpha \mathbb{Z}[\sqrt{d}] \). \( \alpha \) может быть экспоненциально большим в d. Следовательно, \( \alpha \) в общем случае даже не может быть записан за полиномиальное время. Однако \( \lfloor \log \alpha \rceil \) однозначно идентифицирует \( \alpha \). Задача: определить, является ли I главным идеалом, и если да, то найти \( \lfloor \log \alpha \rceil \). Как показал Халлгрен, это можно сделать за полиномиальное время на квантовом компьютере [49]. Модифицированный квантовый алгоритм для решения этой задачи, использующий меньшее количество кубитов, был приведен в [131]. Квантовый алгоритм, решающий задачу главного идеала в числовых полях произвольной степени (т.е. полиномиальное масштабирование по степени), был впоследствии приведен в [329]. Разложение на множители сводится к решению уравнения Пелла, которое сводится к решению главного идеала. Таким образом, решение главного идеала, по крайней мере, так же сложна, как разложение на множители, и поэтому, вероятно, не относится к P. Смотрите также абелеву скрытую подгруппу.

Дано: Числовое поле \( \mathbb{Q}(\theta) \) считается имеющим степень d, если многочлен наименьшей степени, корнем которого \( \theta \) является, имеет степень d. Множество \( \mathcal{O} \) элементов \( \mathbb{Q}(\theta) \), которые являются корнями монических многочленов в \( \mathbb{Z}[x] \), образует кольцо, называемое кольцом целых чисел из \( \mathbb{Q}(\theta) \). Множество единиц (обратимых элементов) кольца \( \mathcal{O}\) образуют группу, обозначаемую \( \mathcal{O}^*\). Найти набор генераторов для \( \mathcal{O}^*\) описанное \( \theta\) Как показано Халлгреном [50] и независимо Шмидтом и Воллмером [116], для любого \( \mathbb {Q} (\theta) \) фиксированной степени квантовый компьютер может за полиномиальное время найти набор генераторов для \( \mathcal{O}^*\) описанное \( \theta\). Классический алгоритм решения этой задачи за полиномиальное время неизвестен. Халлгрен и его коллеги впоследствии обнаружили, как добиться полиномиального масштабирования по степени [213]. См. также [329]. Алгоритмы основаны на решении задач абелевой скрытой подгруппы над аддитивной группой вещественных чисел.

Числовое поле \( \mathbb{Q}(\theta) \) считается имеющим степень d, если многочлен наименьшей степени, корнем которого \( \theta \) является, имеет степень d. Множество \( \mathcal{O} \) элементов \( \mathbb{Q}(\theta) \), которые являются корнями монических многочленов в \( \mathbb{Z}[x] \), образует кольцо, называемое кольцом целых чисел из \( \mathbb{Q}(\theta) \), который является доменом Дедекинда. Для дедекиндовой области ненулевые дробные идеалы по модулю ненулевых главных идеалов образуют группу, называемую группой классов. Как показано Халлгреном [50], квантовый компьютер может найти набор генераторов для группы классов кольца целых чисел любой постоянной степени числового поля, учитывая описание \(\ theta\), за время poly(log(\( | \mathcal {O} | \))). Улучшенный квантовый алгоритм, время выполнения которого также является полиномиальным по d, был впоследствии приведен в [329]. Классический алгоритм решения этих задач за полиномиальное время неизвестен. Смотрите также абелеву скрытую подгруппу.

Пусть \( \mathbb{F}_q \) - конечное поле. Элементы, отличные от нуля из \( \mathbb{F}_q\), образуют группу \( \mathbb{F}_q^\times\) при умножении, а элементы \( \mathbb{F}_q\) образуют (абелеву, но не обязательно циклическую) группу \( \mathbb{F}_q^+ \) при добавлении. Мы можем выбрать некоторый символ \( \chi ^\times \) из \( \mathbb{F}_q^\times \) и некоторый символ \( \chi ^ + \) из \( \mathbb{F}_q^+ \). Соответствующая сумма Гаусса является внутренним произведением этих символов: \( \sum_{x \neq 0 \in \mathbb{F}_q} \chi ^ + (x) \chi ^ \times(x) \) Как показали van Dam и Seroussi [90], суммы Гаусса могут быть оценены с полиномиальной точностью на квантовом компьютере за полиномиальное время. Хотя конечное кольцо не образует группу при умножении, а образует набор единиц. Выбирая представление для аддитивной группы кольца и выбирая представление для мультипликативной группы его единиц, можно получить сумму Гаусса по единицам конечного кольца. Они также могут быть оценены с полиномиальной точностью на квантовом компьютере за полиномиальное время [90]. Классического алгоритма оценки сумм Гаусса за полиномиальное время не известно. Дискретный логарифм сводится к оценке суммы Гаусса [90]. Определенные функции разбиения модели Поттса могут быть вычислены с помощью квантового алгоритма за полиномиальное время, связанного с оценкой суммы Гаусса [47].

Дано: n-разрядное число Задача: либо не подтвердить предположение о составности числа, либо точно утверждать его простоту (т.е. провести тест простоты). Самыми быстрыми классическими алгоритмами являются AKS (тест Агравала-Каяла-Саксены), лучшие версии которых [393, 394] имеют по существу квартичную сложность, и ECPP (тест простоты с использованием эллиптических кривых), где эвристическая сложность самой быстрой версии [395] также по существу квартична. Самым быстрым известным квантовым алгоритмом для решения этой задачи является метод Donis-Vela и Garcia-Escartin [396] со сложностью \( O(n^2 (\log \ n)^3 \log \ \log \ n) \). Это улучшает предыдущий основанный на факторинге квантовый алгоритм доказательства простоты [397], который имеет сложность \( O(n^3 \log \ n \ \log \ \log \ n) \). Недавний результат Harvey и Van Der Hoeven [398] может быть использован для повышения сложности квантового алгоритма, основанного на факторинге, для доказательства простоты до \(O (n ^ 3 \ log \ n) \), и может оказаться возможным аналогичным образом уменьшить сложность алгоритма Donis-Vela-Garcia-Escartin для \( O(n ^2 (\log \ n)^3) \) [399].

Нам даны \( a,b,c,f,g \in \mathbb{F}_q \). Найти целые числа \(x,y\) такие, что \( a f ^ x + b g ^ y = c \). Как показано в [111], квантовые компьютеры могут решить эту проблему за \( \widetilde{O}(q^{3/8}) \) время, тогда как наилучший классический алгоритм требует \( \widetilde{O}(q^{9/8}) \) времени. Квантовый алгоритм [111] основан на квантовых алгоритмах дискретных логарифмов и поиска.

Все представления конечных групп и компактных линейных групп могут быть выражены в виде унитарных матриц при соответствующем выборе базиса. Сопряжение регулярного представления группы с помощью схемы квантового преобразования Фурье над этой группой дает прямую сумму неприводимых представлений группы. Таким образом, эффективное квантовое преобразование Фурье над симметричной группой [196] вместе с тестом Адамара дает быстрый квантовый алгоритм для аддитивной аппроксимации отдельных матричных элементов произвольных неприводимых представлений \(S_n\). Аналогично, используя квантовое преобразование Шура [197], можно эффективно аппроксимировать матричные элементы неприводимых представлений SU (n), которые имеют полиномиальный вес. Прямые реализации отдельных неприводимых представлений для групп U (n), SU (n), SO (n) и \(A_n\) с помощью эффективных квантовых схем приведены в [106]. Примеры, которые кажутся экспоненциально сложными для известных классических алгоритмов, также определены в [106].

Дано: три \( n \times n \) матрицы A, B и C Задача: проверить матричное произведение, т.е. решить, является ли AB = C. Классически наиболее известный алгоритм достигает этого за время \(O(n ^ 2) \), тогда как наиболее известный классический алгоритм умножения матриц выполняется за время \(O(n ^ {2.373}) \). Ambainis и др. обнаружили квантовый алгоритм для решения этой задачи за время \(O(n^{7/4}) \) [6]. Впоследствии Buhrman и Špalek улучшили это, получив квантовый алгоритм для этой задачи до \(O(n^{5/3}) \) [19]. Этот алгоритм основан на результатах, касающихся квантовых блужданий, которые были доказаны в [85].

Дано: список целых чисел \( x_1,\ldots, x_n \) и целевое целое число s Задача просуммировать подмножества, т.е. определить, равно ли s сумме любого подмножества заданных целых чисел. Эта задача является NP-полной и, следовательно, вряд ли может быть решена классическими или квантовыми алгоритмами с полиномиальной сложностью в наихудшем случае. В сложных случаях заданные целые числа имеют порядок \( 2 ^ n \), и многие исследования по сумме подмножеств фокусируются на средних примерах в этом режиме. В [178] приведен квантовый алгоритм, который решает такие случаи за время \(2 ^ {0,241n}\) с точностью до полиномиальных множителей. Этот квантовый алгоритм работает, применяя вариант алгоритма квантового блуждания Амбайниса (EN) для определения четкости элементов [7], чтобы ускорить сложный классический алгоритм для этой задачи, разработанный Howgrave-Graham и Joux. Самый быстрый известный классический алгоритм для таких случаев суммирования подмножеств выполняется за время \(2 ^ {0.291n}\) с точностью до полиномиальных множителей [404].

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

Хорошо известно, что алгоритмы Шора для разложения на множители и дискретных логарифмов [82,125] полностью разрушают криптосистемы RSA и Диффи-Хеллмана, а также их варианты на основе эллиптических кривых [109, 14]. (Для замены этих примитивов был предложен ряд "постквантовых" криптосистем с открытым ключом, которые, как известно, не могут быть взломаны квантовыми атаками.) Помимо алгоритма Шора, растет объем работ по квантовым алгоритмам, специально разработанным для атаки на криптосистемы. Как правило, они делятся на три категории:

1. квантовые алгоритмы, обеспечивающие полиномиальные или субэкспоненциальные временные атаки на криптосистемы при стандартных предположениях. В частности, алгоритм Childs, Jao и Сухарева для нахождения изогений эллиптических кривых взламывает определенные криптосистемы на основе эллиптических кривых за субэкспоненциальное время, которые еще не были взломаны алгоритмом Шора [283].
2. квантовые алгоритмы, достигающие полиномиального улучшения по сравнению с известными классическими криптоаналитическими атаками за счет ускорения частей этих классических алгоритмов с использованием поиска по Гроверу, обнаружения квантовых столкновений и т.д. Такие атаки на закрытый ключ [284,285,288, 315,316] и примитивы с открытым ключом [262,287], не исключают использования соответствующих криптосистем, но могут влиять на выбор размера ключа.
3. атаки, которые используют квантовую суперпозицию для блокирования шифров. Эти атаки во многих случаях полностью разрушают криптографические примитивы [286, 289, 290,291,292]. Однако в большинстве практических ситуаций такие запросы о наложении вряд ли будут выполнимы.

Нам дан оракул с N разрешенными входными данными. Для одного входа w ("the winner") соответствующий выходной сигнал равен 1, а для всех остальных входов соответствующий выходной сигнал равен 0. Задача состоит в том, чтобы найти w. На классическом компьютере для этого требуются \( \Omega(N) \) запросов. Квантовый алгоритм Гровера достигает этого за \( O(\sqrt{N}) \) [48], что является оптимальным [216]. Этот алгоритм впоследствии был обобщен для поиска при наличии нескольких "winners" [15], вычисления суммы произвольной функции [15,16,73], нахождения глобального минимума произвольной функции [35,75, 255], использования преимуществ альтернативных начальных состояний [100] или неоднородных вероятностных априорных значений [123], работают с оракулами, время выполнения которых варьируется в зависимости от входных данных [138], аппроксимируют определенные интегралы [77] и сходятся к фиксированной точке [208,209,433]. Соображения по оптимизации глубины схем квантового поиска приведены в [405]. Обобщение алгоритма Гровера, известное как оценка амплитуды [17], в настоящее время является важным примитивом в квантовых алгоритмах. Оценка амплитуды составляет ядро большинства известных квантовых алгоритмов, связанных с поиском столкновений и свойствами графов. Одним из естественных применений Grover search является ускорение решения NP-полных задач, таких как 3-SAT. Сделать это нетривиально, потому что лучший классический алгоритм для 3-SAT - это не совсем поиск методом перебора. Тем не менее, усиление амплитуды обеспечивает квадратичное квантовое ускорение по сравнению с лучшим классическим алгоритмом 3-SAT, как показано в [133]. Квадратичные ускорения для других задач удовлетворения ограничений получены в работе [134]. Дополнительные примеры применения поиска по Гроверу и усиления амплитуды приведены в [261,262]. Проблема, тесно связанная с поиском по Гроверу, но более сложная - это пространственный поиск, при котором запросы к базе данных ограничены некоторой графовой структурой. На достаточно хорошо связанных графах \(O(\sqrt{n})\) квантовая сложность запроса все еще достижима [274,275,303,304,305,306,330].

Пусть G - конечно порожденная абелева группа, и пусть H - некоторая подгруппа G такая, что G / H конечна. Пусть f - функция на G такая, что для любого \( g_1,g_2 \ в G \), \( f(g_1) = f(g_2) \) тогда и только тогда, когда \( g_1 \) и \( g_2 \) находятся в одном и том же смежном наборе H. Задача состоит в том, чтобы найти H (т.е. найти набор генераторов для H), выполнив запросы к f. Это решаемо на квантовом компьютере с использованием запросов \( O(\log \vert G\vert) \), тогда как классически требуются запросы \( \Omega(|G|) \). Этот алгоритм был впервые сформулирован в полной общности Боном и Липтоном в работе [14]. Однако правильная атрибуция этого алгоритма затруднена, поскольку, как описано в главе 5 работы [76], он включает в себя многие исторически важные квантовые алгоритмы как частные случаи, включая алгоритм Саймона [108], который послужил источником вдохновения для алгоритма определения периода Шора, который составляет ядро его факторинга и дискретной-логарифмические алгоритмы. Алгоритм абелевой скрытой подгруппы также лежит в основе алгоритмов уравнения Пелла, главного идеала, группы единиц и группы классов. В некоторых случаях проблема абелевой скрытой подгруппы может быть решена с помощью одного запроса, а не order \( \log(\vert G\vert) \), как показано в [30]. Обычно при определении периода предполагается, что функция \(f(x) \neq f(y) \), если только \( x-y = s \), где \( s \) - период. Квантовый алгоритм, который применяется даже при ослаблении этого ограничения, приведен в [388]. Определение периода было обобщено для применения к оракулам, которые предоставляют только несколько наиболее значимых битов о базовой функции в [389].

Пусть G - конечно порожденная группа, и пусть H - некоторая подгруппа G, имеющая конечное число левых смежных групп. Пусть f - функция на G такая, что для любого \( g_1, g_2 \), \( f(g_1) = f(g_2) \) тогда и только тогда, когда \( g_1 \) и \( g_2 \) находятся в одном и том же левом смежном наборе H. Задача состоит в том, чтобы найти H (т.е. найти набор генераторов для H), выполнив запросы к f. Это разрешимо на квантовом компьютере с использованием запросов \( O(\log(|G|) \), тогда как классически требуются запросы \( \Omega(|G|) \) [37,51]. Однако это не квалифицируется как эффективный квантовый алгоритм, поскольку, как правило, для обработки квантовых состояний, полученных в результате этих запросов, может потребоваться экспоненциальное время. Эффективные квантовые алгоритмы для задачи о скрытой подгруппе известны для некоторых конкретных неабелевых групп [81,55,72,53,9,22,56,71,57,43,44,28,126,207,273]. Немного устаревший обзор приведен в [69]. Особый интерес представляют симметричная группа и двугранная группа. Решение для симметричной группы решило бы проблему изоморфизма графов. Решение для двугранной группы решило бы некоторые проблемы с решеткой [78]. Несмотря на большие усилия, решение за полиномиальное время для этих групп неизвестно, за исключением особых случаев [312]. Однако Куперберг [66] нашел алгоритм времени \(2 ^ {O(\sqrt{\log N})}) \) для нахождения скрытой подгруппы двугранной группы \(D_N\). Впоследствии Регев улучшил этот алгоритм таким образом, что он использует не только субэкспоненциальное время, но и полиномиальное пространство [79]. Дальнейшее улучшение асимптотического масштабирования требуемого числа кубитов получено в работе [218]. Ускорения квантовых запросов (хотя и не обязательно эффективные квантовые алгоритмы с точки зрения количества элементов) для несколько более общих задач тестирования на изоморфизм функций в наборах перестановок приведены в [311]

Нам дан оракул, входные данные которого равны n битам, а выходные - одному биту. Учитывая входные данные \( x \in \{0,1\}^n \), выход равен \( x \odot h \), где h - "скрытая" строка из n битов, а \( \odot \) обозначает побитовое внутреннее произведение по модулю 2. Задача состоит в том, чтобы найти h. На классическом компьютере для этого требуется n запросов. Как показали Бернштейн и Вазирани [11], этого можно достичь на квантовом компьютере с помощью одного запроса. Кроме того, можно построить рекурсивные версии этой задачи, называемые рекурсивной выборкой Фурье, таким образом, что квантовым компьютерам требуется экспоненциально меньше запросов, чем классическим компьютерам [11]. Смотрите [256,257] для соответствующей работы по повсеместному использованию квантовых ускорений из универсальных квантовых схем и [258,270] для соответствующей работы по ускорению квантовых запросов для обнаружения корреляций между функцией oracle и преобразованием Фурье другой.

Нам дан оракул, входные данные которого равны n битам, а выходные - одному биту. Нам обещают, что из \( 2 ^ n \) возможных входных данных либо все они, либо ни один из них, либо половина из них дают результат 1. Задача состоит в том, чтобы отличить сбалансированный случай (половина всех входных данных дает результат 1) от постоянного случая (все или ни один из входных данных не дает результата 1). Дойч [32] показал, что при n =1 это может быть решено на квантовом компьютере с помощью одного запроса, тогда как любой детерминированный классический алгоритм требует двух. Исторически это был первый четко определенный квантовый алгоритм, достигающий ускорения по сравнению с классическими вычислениями. (Связанный с этим, более свежий, педагогический пример приведен в [259].) Квантовый алгоритм с одним запросом для произвольного n был разработан Дойчем и Йозсой в [33]. Несмотря на то, что вероятностно легко решается с помощью O (1) запросов, задача Дойча-Йозса классически имеет экспоненциальную детерминированную сложность запроса в наихудшем случае.

Логическое выражение называется формулой, если каждая переменная используется только один раз. Формула соответствует схеме без разветвления, которая, следовательно, имеет топологию дерева. Согласно формализму span-программы Райхардта, теперь известно [158], что квантовая сложность запроса любой формулы O(1) фанина для N переменных равна \( \Theta(\sqrt{N}) \). Этот результат является кульминацией долгой работы [27,8,80,159,160], которая началась с открытия Фархи и др. [38] что деревья NAND по переменным \(2 ^ n\) могут быть вычислены на квантовых компьютерах за время \( O(2 ^ {0,5n}) \) с использованием квантового блуждания в непрерывном времени, тогда как классические компьютеры требуют \( \Omega(2^{0,753n}) \) запросы. Во многих случаях алгоритмы вычисления квантовых формул эффективны не только с точки зрения сложности запроса, но и с точки зрения временных затрат. Формализм span-программы также дает нижние границы сложности квантового запроса [149]. Несмотря на то, что первоначально алгоритм Гровера был обнаружен с другой точки зрения, его можно рассматривать как частный случай вычисления формулы, в котором каждый элемент равен OR. Квантовая сложность вычисления небулевых формул также была изучена [29], но изучена не столь полно. Чайлдс и др. обобщили на случай, в котором входные переменные могут повторяться (т.е. первый уровень схемы может включать разветвление) [101]. Они получили квантовый алгоритм, используя запросы \( O(\ min \{N,\sqrt{S},N ^{1/2} G ^{1/4} \}) \), где N - количество входных переменных, не включающих кратности, S - количество входных данных, учитывающих кратности, а G - это количество вентилей в формуле. В ссылках [164], [165] и [269] рассматриваются особые случаи задачи дерева NAND, в которой число элементов NAND, принимающих неравные входные данные, ограничено. Некоторые из этих случаев приводят к суперполиномиальному разделению между квантовой и классической сложностью запроса.

Нам предоставляется доступ oracle к некоторой функции f на \( \mathbb{Z}_N \). Мы знаем, что f(x) = g (x+ s), где g - известная функция, а s - неизвестный сдвиг. Проблема скрытого сдвига состоит в том, чтобы найти s. При сокращении от задачи Гровера становится ясно, что для решения скрытого сдвига в целом необходимы по крайней мере запросы \( \sqrt{N} \). Однако некоторые частные случаи проблемы скрытого сдвига разрешимы на квантовых компьютерах с использованием O(1) запросов. В частности, ван Дам и др. показал, что это может быть сделано, если f является мультипликативным символом конечного кольца или поля [89]. Ранее обнаруженный алгоритм смещенных символов Лежандра [88,86] рассматривается как частный случай этого, поскольку символ Лежандра \( \ left(\frac {x} {p} \right) \) является мультипликативным символом \( \mathbb{F}_p \). Для решения этих задач не известен ни один классический алгоритм, выполняющийся за время O(polylog(N)). Более того, квантовый алгоритм для задачи о сдвинутом символе Лежандра сломал бы определенный криптографический генератор псевдослучайных чисел, учитывая возможность выполнять квантовые запросы к генератору [89]. Квантовое ускорение для задач скрытого сдвига разностных множеств приведено в [312], и это также включает проблему символа Лежандра в качестве частного случая. Реттелер обнаружил экспоненциальное квантовое ускорение для поиска скрытых сдвигов некоторых нелинейных булевых функций [105,130]. Основываясь на этой работе, Гавински, Реттелер и Роланд показали [142], что проблема скрытого сдвига для случайных булевых функций\( f:\mathbb {Z}_2 ^n \to \mathbb{Z}_2 \) имеет O(n) квантовую сложность в среднем случае, тогда как классическая сложность запроса равна \( \Омега(2^{n/2}) \). Результаты в [143], хотя они сформулированы в терминах задачи о скрытой подгруппе для двугранной группы, подразумевают, что сложность квантового запроса задачи о скрытом сдвиге для инъективной функции на \(\mathbb {Z} _N \) равна O(log n), тогда как классический запрос сложность равна \( \Theta(\sqrt{N}) \). Однако наиболее известная сложность квантовой схемы для инъективного скрытого сдвига на \( \ mathbb {Z} _N \) равна \( O (2 ^ {C \ sqrt {\log N}}) \), достигаемая с помощью алгоритма решета Куперберга [66]. Недавний результат, основанный на [408,43], обеспечивает экспоненциальное квантовое ускорение для некоторых обобщений проблемы скрытого сдвига, включая проблему скрытого множественного сдвига, в которой пользователь имеет доступ к запросу \(f_s(x) = f(x-hs) \) в некотором допустимом диапазоне s и хочется сделать вывод о h [407].

Пусть \(p (x) = a_d x ^d + \ldots + a_1 x + a_0 \) - многочлен над конечным полем \( \mathrm{GF}(q) \). Одному предоставляется доступ к оракулу, который, учитывая \( x \in \mathrm{GF}(q) \), возвращает \( p(x) \). Задача полиномиального восстановления состоит в том, чтобы путем выполнения запросов к оракулу определить коэффициенты \( a_d,\ldots,a_0\). Классически запросы \( d + 1 \) являются необходимыми и достаточными. (В некоторых источниках для этой задачи используется термин реконструкция вместо интерполяции.) В количественном отношении необходимы запросы \( d/2 + 1/2 \) и достаточно запросов \( d/2 + 1\) [360,361]. Для многомерных многочленов степени d от n переменных задача интерполяции имеет классическую сложность запроса \( \binom{n+d}{d} \). Как показано в [387], сложность квантового запроса равна \( O \left( \frac{1}{n+1} \binom{n+d}{d} \right) \) над \( \mathbb{R} \) и \( \mathbb{C} \) и это \( O \left( \frac {d}{n+d} \binom{n+d}{d} \right) \) поверх \( \mathbb{F}_q \) для достаточно большого q. Квантовые алгоритмы также были обнаружены для случая, когда оракул возвращает \( \chi(f(x)) \), где \( \chi \) является квадратичным символом \( \mathrm{GF}(q)\) [390], и случая, когда оракул возвращает \( f(x)^e \) [392]. Они обобщают алгоритм скрытого сдвига из [89] и обеспечивают экспоненциальное ускорение по сравнению с классическими вычислениями. Квантовый алгоритм для восстановления рациональных функций над конечными полями при зашумленном и неполном доступе оракула к значениям функций приведен в [391].

Учитывая строки T длины n и P длины m < n, обе из некоторого конечного алфавита, задача сопоставления с образцом состоит в том, чтобы найти вхождение P в качестве подстроки T или сообщить, что P не является подстрокой T. В более общем плане T и P могут быть скорее d-мерными массивами чем одномерные массивы (строки). Тогда проблема сопоставления с образцом состоит в том, чтобы вернуть местоположение P в виде блока \(m \times m \times \ldots \times m\) внутри массива \(n \times n \times \ldots \times n\) или сообщить, что такого местоположения не существует. Нижняя граница запроса \( \Omega(\sqrt{N}) \) для неструктурированного поиска [216] подразумевает, что наихудшая сложность квантового запроса в этой задаче равна \( \Omega ( \sqrt{n} + \sqrt{m} ) \). Квантовый алгоритм, достигающий этого с точностью до логарифмических множителей, был получен в работе [217]. Этот квантовый алгоритм работает за счет использования алгоритма Гровера в сочетании с классическим методом, называемым детерминированной выборкой. Совсем недавно Монтанаро показал, что суперполиномиальное квантовое ускорение может быть достигнуто в среднем случае сопоставления с образцом, при условии, что m больше логарифмического значения в n. В частности, квантовый алгоритм, приведенный в [215], решает задачу сопоставления шаблонов среднего случая за \( \widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2} \sqrt{\log m})})\) время. Этот квантовый алгоритм построен путем обобщения алгоритма квантового сита Куперберга [66] для задач двугранной скрытой подгруппы и скрытого сдвига таким образом, чтобы он мог работать в d-измерениях и учитывать небольшое количество шума, а затем классически сводить проблему сопоставления с образцом к этой зашумленной d-мерной версии скрытого сдвига. Квантовый алгоритм для сопоставления строк со сложностью \(\widetilde{O} (\sqrt{n}) \) приведен в [435] в другой модели ввода, где строки записываются полностью с использованием \(n + m\) кубитов, а не с помощью квантовых запросов к оракул, предоставляющий отдельные биты.

Нам предоставляется доступ oracle к списку из N чисел в порядке от наименьшего к наибольшему. Учитывая число x, задача состоит в том, чтобы выяснить, в какое место в списке оно бы поместилось. Классически наилучшим возможным алгоритмом является двоичный поиск, который принимает запросы \( \log_2 N \). Фархи и др. показал, что квантовый компьютер может достичь этого, используя 0,53 \( \log_2 N\) запросов [39]. В настоящее время наиболее известный детерминированный квантовый алгоритм для решения этой задачи использует 0,433 \( \log_2 N\) запросов [103]. Для этой задачи была доказана нижняя граница квантовых запросов \(\frac{\ln2}{\pi} \log_2 N\) [219,24]. В [10] приведен рандомизированный квантовый алгоритм, ожидаемая сложность запроса которого меньше \( \frac{1}{3} \log_2 N \).

Пусть G - граф из n вершин. Нам предоставляется доступ к оракулу, который, учитывая пару целых чисел в {1,2,...,n}, сообщает нам, соединены ли соответствующие вершины ребром. Основываясь на предыдущей работе [35,52,36], Дюрр и др. [34] показывают, что сложность квантового запроса для нахождения минимального связующего дерева взвешенных графов и определения связности для направленных и неориентированных графов имеет \(\ Theta (n ^ {3/2}) \) сложность квантового запроса, и что нахождение пути с наименьшим весом имеют \( O(n ^{3/2}\log ^ 2 n) \) квантовую сложность запроса. Определение того, является ли граф двудольным, обнаружение циклов и принятие решения о том, может ли данная вершина быть достигнута из другой (st-связность), - все это может быть достигнуто с помощью ряда запросов и квантовых элементов, которые масштабируются как \( \widetilde {O}(n ^ {3/2}) \), и только логарифмически много кубитов, как показано в [317], основываясь на [13,272,318]. Основанный на span-программе квантовый алгоритм для обнаружения деревьев заданного размера как младших за \( \widetilde{O}(n) \) время приведен в [240]. Свойство графа является разреженным, если существует константа c, такая, что каждый граф со свойством имеет отношение ребер к вершинам не более c. Чайлдс и Котари показали, что все свойства разреженного графа имеют сложность запроса \( \ Theta (n ^ {2/3}) \), если они не могут быть охарактеризованы по списку запрещенных подграфов и \( o(n ^{2/3}) \) (little-o), если они могут [140]. Первый алгоритм основан на поиске по Гроверу, второй - на формализме квантового блуждания [141]. Согласно теореме Мадера, свойства разреженного графа включают в себя все нетривиальные свойства малой замкнутости. К ним относятся плоскостность, являющаяся лесом и не содержащая пути заданной длины. Согласно широко распространенной гипотезе Аандераа-Карпа-Розенберга, все вышеперечисленные задачи имеют \( \ Omega (n ^ 2) \) классическую сложность запроса. Другой интересной вычислительной задачей является нахождение подграфа H в заданном графе G. Простейший случай такого нахождения - треугольник, то есть клика третьего размера. Самый быстрый известный квантовый алгоритм для этого находит треугольник в \( O(n ^ {5/4}) \) квантовых запросах [319], улучшая [276,175,171,70,152,21]. Более высокие верхние границы сложности квантового запроса известны, когда графики достаточно разрежены [319, 320]. Классически для нахождения треугольника требуются запросы \( \Omega(n ^ 2) \) [21]. В более общем плане квантовый компьютер может найти произвольный подграф из k вершин, используя запросы \( O(n ^ {2-2/k-t}) \), где \(t=(2k-d-3)/(k(d+1)(m+2)) \) а d и m таковы, что H имеет вершину степени d и m + d ребер [153]. Это улучшает предыдущий алгоритм из [70]. В некоторых случаях сложность этого запроса превосходит квантовый алгоритм [140], который находит H, используя \( \widetilde{O}\left( n^{\frac{3}{2}-\frac{1}{\mathrm{vc}(H)+1}} \right) \) запросы, при условии, что G является разреженным, где vc(H) - размер минимального вершинного покрытия H. Квантовый алгоритм для нахождения подграфов постоянного размера над 3-однородными гиперграфами в запросах \( O(n ^{1.883}) \) приведен в [241].

Пусть G - граф из N вершин, M ребер и степени d. Нам предоставляется доступ к оракулу, который при запросе с меткой вершины и \( j \in \{1,2,\ldots,d\}\) выводит j-го соседа вершины или null, если вершина имеет степень меньше d. Предположим, нам дано обещание, что G либо двудольно, либо далеко не двудольно в том смысле, что для достижения двудольности необходимо было бы удалить постоянную долю ребер. Тогда, как показано в [144], квантовая сложность определения двудольности равна \( \widetilde{O}(N ^{1/3}) \). Также в [144] показано, что отличие графов-расширителей от графов, которые далеки от того, чтобы быть расширителями, имеет квантовую сложность \( \widetilde {O} (N ^ {1/3}) \) и \( \widetilde{\Omega}(N^{1/4}) \), тогда как классическая сложность равна \( \widetilde{\Theta}(\sqrt{N}) \). Ключевым инструментом квантовой алгоритмики является алгоритм Амбайниса для определения четкости элементов. В [34] показано, что поиск минимального остовного дерева имеет квантовую сложность запроса \( \Theta(\sqrt{NM}) \), определение связности графа имеет квантовую сложность запроса \( \Theta(N) \) в неориентированном случае и \( \widetilde{\Theta} (\sqrt{NM}) \) в направленном случае, и вычисление пути с наименьшим весом от заданного источника ко всем другим вершинам взвешенного графа имеет квантовую сложность запроса \( \widetilde{\Theta}(\sqrt{NM}) \). В [317] приведены квантовые алгоритмы для st-связности, определения двудольности и определения того, является ли граф лесом, которые выполняются за \( \widetilde {O}(N \ sqrt{d}) \) время и используют только логарифмически много кубитов.

Некоторые вычислительные задачи можно сформулировать в терминах сложности запроса, связанного с поиском пути в лабиринте. То есть, существует некоторый граф G, к которому предоставляется доступ oracle. При запросе с меткой данного узла oracle возвращает список меток всех соседних узлов. Задача состоит в том, чтобы, начиная с некоторого исходного узла (т.е. его метки), найти метку определенного помеченного конечного узла. Как показали Чайлдс и др. [26], квантовые компьютеры могут экспоненциально превосходить классические компьютеры в решении этой задачи, по крайней мере, для некоторых графиков. В частности, рассмотрим граф, полученный путем соединения двух бинарных деревьев глубиной n случайным "сварным швом" таким образом, что все узлы, кроме двух корней, имеют третью степень. Начиная с одного корня, квантовый компьютер может найти другой корень, используя poly (n) запросы, тогда как это доказуемо невозможно с помощью классических запросов.

Предположим, нам предоставлен доступ oracle к функции два к одному f в домене размера N. Проблема столкновения состоит в том, чтобы найти пару \(x,y \ в \{1,2,\ldots,N\} \) такую, что f(x) = f(y). Классическая сложность рандомизированного запроса для этой задачи составляет \( \ Theta(\sqrt{N}) \), тогда как, как показано Брассардом и др., квантовый компьютер может достичь этого, используя \(O(N ^ {1/3}) \) запросов [18]. (См. также [315].) Удаление обещания о том, что f равно два к одному, приводит к проблеме, называемой различимостью элементов, которая имеет \( \ Theta(N) \) классическую сложность запроса. Улучшая [21], Амбайнис дает квантовый алгоритм со сложностью запроса \( O(N ^ {2/3}) \) для различимости элементов, что является оптимальным [7,374]. Проблема определения того, существуют ли какие-либо k-кратные столкновения, называется k-отчетливостью. Улучшая [7,154], наилучшая сложность квантового запроса для k-отчетливости равна \( O(n^{3/4 - 1/(4(2^ к-1))}) \) [172,173]. Для k=2,3 это также временная сложность, с точностью до логарифмических множителей, по [7]. Для \(k > 3\) самый быстрый известный квантовый алгоритм имеет временную сложность \(O(n ^ {(k-1)/k}) \) [363]. Учитывая две функции f и g, в областях размера N и M, соответственно, коготь представляет собой пару x, y, такую, что f(x) = g (y). В случае, когда N = M, алгоритм из [7] решает задачу поиска когтей в \(O(N ^ {2/3}) \) запросах, улучшая предыдущий \(O(N ^ {3/4} \log N) \) квантовый алгоритм из [21]. Дальнейшая работа позволяет повысить сложность запросов для различных режимов параметров, в которых \(N \neq M\) [364,365]. В более общем плане проблема, связанная с различимостью элементов, заключается в том, чтобы при наличии доступа oracle к последовательности оценить \(k ^ {\ mathrm {th}}\) частотный момент \(F_k = \sum_j n_j ^k \), где \(n_j\) - количество повторений что j встречается в последовательности. Приблизительно квадратичное ускорение для этой задачи получено в работе [277]. Смотрите также столкновение графиков.

Нам дан неориентированный граф из n вершин и доступ oracle к обозначению вершин 1 и 0. Проблема столкновения графов состоит в том, чтобы, запросив этот оракул, решить, существует ли пара вершин, соединенных ребром, обе из которых помечены как 1. Можно внедрить задачу неструктурированного поиска Гровера в качестве примера столкновения графов, выбрав звездообразный граф, пометив центр 1 и пометив остальные вершины записями базы данных. Следовательно, эта проблема имеет квантовую сложность запроса \( \Omega(\sqrt{n}) \) и классическую сложность запроса \( \Theta (n) \). В [70] Магниез, Наяк и Сегеди дали квантовый алгоритм \( O (N ^ {2/3}) \)-запроса для столкновения графов на общих графах. Это остается наилучшей верхней границей сложности квантового запроса для этой задачи на общих графах. Однако для нескольких специальных классов графов были получены более строгие верхние границы. В частности, сложность квантового запроса на графе G равна \( \widetilde{O}(\sqrt{n} + \sqrt{l}) \), где l - количество не-ребер в G [161], \(O(\sqrt{n} \alpha^{1/6}) \) где \(\alpha\) - размер наибольшего независимого набора G [172], \(O(\sqrt{n} + \sqrt{\alpha^*})\) где \( \alpha^*\) - максимальный общая степень любого независимого множества G [200] и \(O(\sqrt{n} t ^{1/6}) \), где t - ширина дерева G [201]. Кроме того, сложность квантового запроса составляет \(\widetilde{O}(\sqrt{n}) \) с высокой вероятностью для случайных графов, в которых наличие или отсутствие ребра между каждой парой вершин выбирается независимо с фиксированной вероятностью (т.е. графы Эрдеша-Реньи) [200]. Краткое изложение этих результатов, а также новые верхние границы для двух дополнительных классов графов, которые слишком сложны для описания здесь, приведены в [201].

Нам предоставляется доступ oracle к k матрицам, каждая из которых равна \( n \times на n \). Учитывая целые числа \( i,j \in \{1,2,\ldots,n\} \) и \( x \in \{1,2,\ldots,k\} \), оракул возвращает элемент матрицы ij из \( x^{\mathrm{th}} \) матрица. Задача состоит в том, чтобы решить, коммутируют ли все эти k матриц. Как показал Итакура [54], этого можно достичь на квантовом компьютере, используя запросы \( O(k ^ {4/5} n ^{9/5}) \), тогда как классически для этого требуются запросы \( \Omega(k n ^ 2 ) \).

Нам предоставляется список из k генераторов для группы G и доступ к черному ящику, реализующему групповое умножение. Запрашивая этот черный ящик, мы хотим определить, является ли группа коммутативной. Наиболее известный классический алгоритм основан на Pak и требует O(k) запросов. Магниез и Наяк показали, что квантовая сложность запроса для этой задачи равна \( \widetilde{\Theta}(k^{2/3}) \) [139].

Любую абелеву группу G можно визуализировать в виде решетки. Подгруппа H из G является подрешеткой, а смежные группы H - это все сдвиги этой подрешетки. Проблема абелевой скрытой подгруппы обычно решается путем получения суперпозиции по случайному смежному набору скрытой подгруппы, а затем с использованием преобразования Фурье для выборки из двойной решетки. Вместо того чтобы обобщать на неабелевы группы (см. неабелеву скрытую подгруппу), вместо этого можно обобщить на проблему идентификации скрытых подмножеств, отличных от решеток. Как показали Чайлдс и соавт. [23] эта задача эффективно разрешима на квантовых компьютерах для определенных подмножеств, определяемых многочленами, таких как сферы. Декер и др. показал, как эффективно решать некоторые связанные с этим проблемы в работах [31,212].

Нам дан оракул, который вычисляет функцию f из \( \mathbb {R} ^ d \) в некоторое произвольное множество S, где f сферически симметрично. Мы хотим определить местоположение центра симметрии с некоторой точностью. (Для простоты пусть точность будет фиксированной.) В [110] Лю приводит квантовый алгоритм, основанный на криволинейном преобразовании, который решает эту проблему, используя постоянное число квантовых запросов, независимых от d. Это представляет собой полиномиальное ускорение по сравнению с классической нижней границей, которая представляет собой запросы \( \Omega(d) \). Алгоритм работает, когда функция f колеблется в достаточно малых масштабах, например, когда наборы уровней f представляют собой достаточно тонкие сферические оболочки. Показано, что квантовый алгоритм работает в идеализированной непрерывной модели, и нестрогие аргументы предполагают, что эффекты дискретизации должны быть небольшими.

Предположим, что конечная группа G задана оракулярно следующим образом. Каждому элементу в G присваивается соответствующая метка. Учитывая упорядоченную пару меток элементов группы, oracle возвращает метку их продукта. Существует несколько классически сложных проблем, связанных с такими группами. Один из них заключается в том, чтобы найти порядок группы, учитывая метки набора генераторов. Другая задача состоит в том, чтобы, получив битовую строку, решить, соответствует ли она элементу group. Конструктивная версия этой проблемы принадлежности требует, в случае "да", разложения данного элемента как произведения групповых генераторов. Классически эти проблемы не могут быть решены с помощью запросов polylog (| G |), даже если G является абелевым. Для абелевых групп квантовые компьютеры могут решать эти задачи, используя запросы polylog (|G|) путем редукции к задаче абелевой скрытой подгруппы, как показано Моской [74]. Более того, как показал Уотроус [91], квантовые компьютеры могут решать эти задачи, используя запросы polylog(|G|) для любой разрешимой группы. Для групп, заданных в виде матриц над конечным полем, а не оракулярно, задачи определения порядка и конструктивной принадлежности могут быть решены за полиномиальное время с использованием квантовых алгоритмов дискретного логарифмирования и факторинга [124]. Смотрите также групповой изоморфизм.

Пусть G - конечная группа. Каждому элементу G присваивается произвольная метка (битовая строка). Учитывая упорядоченную пару меток элементов группы, групповой оракул возвращает метку их продукта. Имея доступ к групповым оракулам для двух групп G и G" и список генераторов для каждой группы, мы должны решить, являются ли G и G" изоморфными. Для абелевых групп мы можем решить эту проблему, используя poly (log | G|, log | G"|) запросы к oracle, применив квантовый алгоритм [127], который разлагает любую абелеву группу на каноническое прямое произведение циклических групп. Квантовый алгоритм [128] решает проблему группового изоморфизма, используя запросы poly (log |G|, log |G"|) для определенного класса неабелевых групп. В частности, группа G относится к этому классу, если G имеет нормальную абелеву подгруппу A и элемент y порядка, взаимно простого с | A |, такой, что G = A, y. Затлукал недавно дал экспоненциальное квантовое ускорение для некоторых случаев проблемы, тесно связанной с групповым изоморфизмом, а именно для проверки эквивалентности групповые расширения [202].

Предположим, нам даны два черных ящика A и B, областью действия которых являются целые числа от 1 до T, а диапазоном - целые числа от 1 до N. Выбирая равномерно случайным образом среди разрешенных входных данных, мы получаем распределение вероятностей по возможным выходным данным. Мы хотим аппроксимировать с постоянной точностью расстояние L1 между распределениями вероятностей, определенными A и B. Классически количество необходимых запросов масштабируется по существу линейно с N. Как показано в [117], квантовый компьютер может достичь этого, используя запросы \( O(\sqrt{N}) \). Приблизительная однородность и ортогональность распределений вероятностей также могут быть определены на квантовом компьютере с помощью запросов \( O(N ^ {1/3}) \). Основным инструментом является алгоритм квантового подсчета из [16]. Еще более усовершенствованный квантовый алгоритм для решения этой задачи получен в работе [265].

Предположим, нам даны черные ящики, реализующие операции сложения и умножения на конечном кольце R, не обязательно коммутативном, вместе с набором образующих для R. Что касается сложения, R образует конечную абелеву группу (R, +). Как показано в [119], на квантовом компьютере можно найти за поли(log |R|) время набор аддитивных генераторов \( \{h_1,\ldots,h_m\} \subset R \) такой, что \( (R,+) \simeq \langle h_1 \rangle \times \ldots \times \langle h_M \rangle\) и m является полилогарифмическим в |R|. Это позволяет эффективно вычислять тензор умножения для R. Как показано в [118], аналогичным образом можно найти аддитивное порождающее множество для любого идеала в R. Это позволяет найти пересечение двух идеалов, найти их частное, доказать, принадлежит ли данный кольцевой элемент данному идеалу, доказать, является ли данный элемент единицей, и если да, то найти его обратное, найдите аддитивные и мультипликативные тождества, вычислите порядок идеала, решите линейные уравнения над кольцами, решите, является ли идеал максимальным, найдите аннигиляторы и проверьте инъективность и сюръективность кольцевых гомоморфизмов. Как показано в [120], можно также использовать квантовый компьютер, чтобы эффективно решить, является ли данный многочлен тождественно нулевым на заданном конечном кольце черного ящика. Известные классические алгоритмы для решения этих задач масштабируются как poly(|R|).

Предположим, нам дали N монет, k из которых поддельные. Все настоящие монеты имеют одинаковый вес, а поддельные монеты имеют какой-то другой одинаковый вес. У нас есть общий баланс, и мы можем сравнить вес любой пары подмножеств монет. Классически, нам нужны взвешивания \( \ Omega(k \log(N / k)) \), чтобы идентифицировать все поддельные монеты. Мы можем ввести оракул таким образом, что, учитывая пару подмножеств монет равной мощности, он выводит один бит, указывающий на сбалансированный или несбалансированный. Основываясь на предыдущей работе Терхала и Смолина [137], Ивама и др. показали [136], что на квантовом компьютере можно идентифицировать все поддельные монеты, используя запросы \( O(k ^{1/4}) \). Основными методами, лежащими в основе квантового ускорения, являются усиление амплитуды и алгоритм Бернштейна-Вазирани.

Предположим, нам предоставлен доступ oracle к (целочисленным) записям матрицы A ( n умножить на m). Мы хотим определить ранг матрицы. Классически для этого требуется упорядочивать запросы nm. Основываясь на [149], Беловс [150] дает квантовый алгоритм, который может использовать меньшее количество запросов, учитывая обещание, что ранг матрицы равен как минимум r. В частности, алгоритм Беловса использует \( O(\sqrt{r(n-r+1)}LT) \) запросы, где L - среднеквадратичное значение обратных величин r наибольших сингулярных значений A, а T - коэффициент, зависящий от разреженности матрицы. Для общего A, \( T = O(\sqrt{nm}) \). Если A имеет не более k ненулевых записей в любой строке или столбце, то \( T = O(k \log(n+m)) \). (Чтобы достичь соответствующей сложности запроса в случае k-разреженности, oracle должен принять индекс столбца в качестве входных данных и предоставить список ненулевых элементов матрицы из этого столбца в качестве выходных данных.) В качестве важного частного случая можно использовать эти квантовые алгоритмы для решения задачи определения того, является ли квадратная матрица сингулярной, которую иногда называют задачей детерминанта. Для общего случая A сложность квантового запроса задачи определения не ниже сложности классического запроса [151]. Однако [151] не исключает квантового ускорения, учитывая обещание на A, такое как разреженность или отсутствие малых сингулярных значений.

Полукольцо - это множество, наделенное операциями сложения и умножения, которые подчиняются всем аксиомам кольца, за исключением существования аддитивных обратных. Умножение матриц на различные полукольца имеет множество применений для решения графических задач. Умножение матриц по полукольцам может быть ускорено путем простых улучшений Гровера по сравнению с умножением в школьных учебниках, что дает квантовый алгоритм, который умножает пару \(n \ умножить на n \) матриц за \( \ widetilde {O} (n ^ {5/2}) \) время. Для некоторых полуколец этот алгоритм превосходит самые быстрые известные классические алгоритмы, а для некоторых полуколец - нет [206]. Особый интерес представляет булево полукольцо, в котором OR служит сложением, а AND - умножением. Не известен ни один квантовый алгоритм для умножения булевой матрицы полукольца в общем случае, который превзошел бы лучший классический алгоритм, имеющий сложность \( n ^ {2.373} \). Однако для разреженных входных данных на выходе известны квантовые ускорения. В частности, пусть A,B равны n по n булевым матрицам. Пусть C=AB, и пусть l - количество записей в C, которые равны 1 (т.е. TRUE). Улучшая [19, 155, 157], наиболее известной верхней границей сложности квантового запроса является \(\widetilde{O}(n \sqrt{l}) \), как показано в [161]. Если вместо этого входные матрицы разрежены, то в определенном режиме также было обнаружено квантовое ускорение по сравнению с самым быстрым известным классическим алгоритмом [206]. Подробное сравнение с классическими алгоритмами приведено в работах [155,206]. Было обнаружено, что квантовые алгоритмы выполняют умножение матриц по (максимальному, минимальному) полукольцу за \(\widetilde{O}(n ^{2.473})\) время и по полукольцу доминирования расстояния за \(\widetilde{O}(n^{2.458})\) время [206]. Самый быстрый известный классический алгоритм для решения обеих этих задач имеет \(\widetilde {O}(n ^ {2.687})\) сложность.

Мы получаем доступ oracle к функции \( f:D \to R \), где D и R - конечные множества. Указано некоторое свойство \( P \subset (D \times R)^k \), например, в виде явного списка. Наша задача состоит в том, чтобы найти подмножество D размером k, удовлетворяющее P, т.е. \( ((x_1,f(x_1)),\ldots,(x_k,f(x_k))) \in P \), или отклонить, если такового не существует. Как обычно, мы хотим сделать это с минимальным количеством запросов к f. Обобщая результат [7], в [162] было показано, что этого можно достичь с помощью \(O(|D|^{k/(k+1)}) \) квантовых запросов. В качестве примечательного частного случая этот алгоритм решает задачу о сумме k-подмножеств, заключающуюся в нахождении k чисел из списка с некоторой желаемой суммой. Соответствующая нижняя граница сложности квантового запроса доказана в [163].

Проблема поиска с подстановочными знаками заключается в идентификации скрытой n-разрядной строки x путем выполнения запросов к oracle f. Учитывая \( S \subseteq \{1,2,\ldots,n\} \) и \( y \in \{0,1\}^{|S|} \), f возвращает единицу, если подстрока x, указанная S, равна y, и возвращает ноль в противном случае. Классически эта проблема имеет сложность запроса \(\Theta(n)\). Как показано в [167], сложность квантового запроса в этой задаче равна \( \Theta(\sqrt{n}) \). Интересно, что это квадратичное ускорение достигается не за счет усиления амплитуды или квантовых блужданий, а скорее за счет использования так называемого довольно хорошего измерения. В статье [167] также дается квантовое ускорение для связанной с этим задачи комбинаторного группового тестирования. Этот результат и последующие более быстрые квантовые алгоритмы для группового тестирования обсуждаются в статье о тестировании Junta и групповом тестировании.

Сеть - это ориентированный граф, ребра которого помечены числами, указывающими на их пропускную способность, и две вершины которого обозначены как источник и приемник. Поток в сети - это распределение потоков по ребрам таким образом, чтобы ни один поток не превышал пропускную способность этого ребра, и для каждой вершины, кроме источника и приемника, общий приток равен общему оттоку. Проблема сетевого потока состоит в том, чтобы при наличии сети найти поток, который максимизирует общий поток, идущий от источника к приемнику. Для сети с n вершинами, m ребрами и целыми емкостями максимальной величины U, [168] дает квантовый алгоритм для нахождения максимального потока во времени \( O(\min \{n ^{7/6} \sqrt{m} \ U ^{1/3}, \sqrt{nU}m\} \times \log n) \). Проблема сетевого потока тесно связана с проблемой нахождения максимального соответствия графа, то есть подмножества ребер максимального размера, которое соединяет каждую вершину не более чем с одной другой вершиной. В статье [168] приведены алгоритмы нахождения максимальных совпадений, которые выполняются за время \( O(n \sqrt{m+n} \log n) \), если граф двудольный, и \( O(n^ 2 ( \sqrt{m/n} + \log n) \log n) \) в общем случае. Ядром этих алгоритмов является поиск по Гроверу. Известные верхние границы классической сложности сетевого потока и задач согласования сложно сформулировать, поскольку разные классические алгоритмы предпочтительнее в разных режимах параметров. Однако в определенных режимах вышеупомянутые квантовые алгоритмы превосходят все известные классические алгоритмы. (Подробности см. в [168].)

Нам предоставляется доступ oracle к взвешенному графу из n вершин и максимальной степени d, веса ребер которого следует интерпретировать как электрические сопротивления. Наша задача состоит в том, чтобы вычислить сопротивление между выбранной парой вершин. Ванг привел два квантовых алгоритма в [210] для этой задачи, которые выполняются во времени \(\mathrm{poly}(\log n, d, 1/\phi, 1/\epsilon) \), где \( \phi \) - расширение графа, а ответ должно быть задано с точностью до коэффициента \( 1+\epsilon \). Известные классические алгоритмы для решения этой задачи являются полиномиальными по n, а не \( \log n \). Один из алгоритмов Вана основан на новом использовании квантовых блужданий. Другой основан на квантовом алгоритме [104] для решения линейных систем уравнений. Первые верхние границы сложности квантового запроса для задачи об электрическом сопротивлении в модели запроса смежности приведены в [280] с использованием программ approximate span.

Функция \(f:\{0,1\}^n \to \{0,1\}\) является k-junta, если она зависит не более чем от k своих входных битов. Задача тестирования k-junta состоит в том, чтобы решить, является ли данная функция k-junta или \( \epsilon \) - далекой от любой k-junta. Хотя это и не очевидно, эта проблема тесно связана с групповым тестированием. Задача группового тестирования определяется функцией \(f:\{1,2,\ldots,n\} \to \{0,1\}\). Некому Оракулу дается доступ к F, который принимает в качестве входных данных подмножества \( \{1,2,\ldots,n\} \). F(S) = 1, если существует \(x \in S \) такое, что f(x) = 1 и F(S) = 0 в противном случае. В [266] приведен квантовый алгоритм решения задачи k-junta с использованием запросов \(\widetilde {O}(\sqrt{k/\epsilon}) \) и \( \widetilde{O}(n \sqrt{k/\epsilon}) \) времени. Это квадратичное ускорение по сравнению с классической сложностью и улучшает предыдущий квантовый алгоритм для тестирования k-junta, приведенный в [267]. Полиномиальное ускорение для ограниченной (т.е. аппроксимационной) версии группового тестирования также приведено в [266], улучшая более ранние результаты [167,268].

Считается, что для любого физически реалистичного гамильтониана H с n степенями свободы соответствующий оператор временной эволюции \( e ^ {-i H t} \) может быть реализован с использованием элементов poly(n, t). Если BPP=BQP, то эта задача вообще не разрешима на классическом компьютере за полиномиальное время. Многие методы квантового моделирования были разработаны для общих классов гамильтонианов [25,95,92,5,12,170,205,211,244,245,278,293,294,295,372,382], химической динамики [63,68,227,310,375], физики конденсированных сред [1,99,145], релятивистской квантовой механики (уравнения Дирака и Клейна-Гордона). [367,369,370,371], открытые квантовые системы [376,377,378,379] и квантовое поле теория [107,166,228,229,230,368]. Экспоненциальная сложность классического моделирования квантовых систем привела Фейнмана к первому предположению, что квантовые компьютеры могут превосходить классические компьютеры в решении определенных задач [40]. Хотя задача нахождения основных энергий локальных гамильтонианов является QMA-полной и поэтому, вероятно, требует экспоненциального времени на квантовом компьютере в худшем случае, были разработаны квантовые алгоритмы для аппроксимации основных [102,231,232,233,234,235,308,321,322,380,381], а также тепловых состояний [132,121,281,282,307] для некоторых классов гамильтонианов и состояний равновесия для некоторых классов гамильтонианов. основные уравнения [430]. Были также получены эффективные квантовые алгоритмы для подготовки определенных классов состояний тензорной сети [323,324,325,326,327,328]. Интересно, что моделирование эволюции гамильтонова времени, а также некоторые задачи подготовки основного и теплового состояний - все это может быть выполнено как частные случаи квантового преобразования сингулярных значений [433].

Как показано Фридманом [42, 41] и др., нахождение определенного аддитивного приближения к многочлену Джонса замыкания косы в точке \(e ^ {i 2 \ pi / 5} \) является задачей, полной BQP. Этот результат был переформулирован и расширен до \( e ^ {i 2 \ pi / k} \) для произвольного k Аароновым и др. [4,2]. Вочьян и Ярд далее обобщили это, получив квантовый алгоритм для оценки многочлена ХОМФЛИ [93], частным случаем которого является многочлен Джонса. Ааронов и др. впоследствии было показано, что квантовые компьютеры могут за полиномиальное время оценить определенное аддитивное приближение к еще более общему многочлену Тутте для плоских графов [3]. Не до конца понятно, для какого диапазона параметров аппроксимация, полученная в [3], является BQP-жесткой. (Смотрите также функции разбиения на разделы.) Квантовые алгоритмы с полиномиальным временем также были открыты для аддитивной аппроксимации инвариантов связей, возникающих из квантовых двойников конечных групп [174]. (Известно, что эта задача не является BQP-трудной.) Как показано в [83], задача нахождения некоторого аддитивного приближения к многочлену Джонса замыкания следа косы в точке \( e ^ {i 2 \ pi /5} \) является DQC1-полной.

Инвариант Тураева-Виро - это функция, которая принимает трехмерные многообразия в качестве входных данных и выдает действительное число в качестве выходных данных. Гомеоморфные многообразия дают одинаковое число. Учитывая трехмерное многообразие, заданное расщеплением Хегаарда, квантовый компьютер может эффективно найти определенное аддитивное приближение к своему инварианту Тураева-Виро, и это приближение является BQP-полным [129]. Ранее, в [114], был приведен квантовый алгоритм за полиномиальное время для аддитивной аппроксимации инварианта Виттена-Решитихина-Тураева (WRT) многообразия, заданного представлением операции. Возведение в квадрат инварианта WRT дает инвариант Тураева-Виро. Однако неизвестно, является ли аппроксимация, достигнутая в [114], BQP-полной. Предположение о возможной связи между квантовыми вычислениями и инвариантами трех многообразий также было высказано в работе [115].

Для классической системы с конечным набором состояний S функция распределения равна \( Z = \sum_{s \in S} e^{-E(s)/kT} \), где T - температура, а k - постоянная Больцмана. По существу, каждая термодинамическая величина может быть вычислена путем получения соответствующей частной производной от функции распределения. Функция разбиения модели Поттса является частным случаем многочлена Тутте. Квантовый алгоритм аппроксимации многочлена Тутте приведен в [3]. Некоторые связи между этими подходами обсуждаются в работе [67]. Дополнительные алгоритмы для оценки функций разбиения на квантовых компьютерах приведены в [112,113,45,47]. Результат BQP-полноты (где "энергиям" разрешается быть комплексными) также приведен в [113]. Метод аппроксимации функций распределения путем моделирования процессов термализации приведен в [121]. Квадратичное ускорение для аппроксимации общих функций разбиения приведено в [122]. Метод, основанный на квантовых блужданиях, обеспечивающий полиномиальное ускорение вычисления функций разбиения, приведен в [265].

Для многих задач комбинаторной оптимизации нахождение точного оптимального решения является NP-полным. Существуют также результаты с высокой степенью точности аппроксимации, доказывающие, что нахождение аппроксимации с достаточно малой границей погрешности является NP-полным. Для определенных задач существует разрыв между наилучшей оценкой погрешности, достигаемой классическим алгоритмом аппроксимации за полиномиальное время, и оценкой погрешности, доказавшей свою NP-трудность. В этом режиме существует потенциал для экспоненциального ускорения за счет квантовых вычислений. В [242] был предложен новый квантовый алгоритмический метод, называемый квантовым алгоритмом приближенной оптимизации (QAOA), для нахождения приближенных решений задач комбинаторной оптимизации. В [243] впоследствии было показано, что QAOA решает задачу комбинаторной оптимизации под названием Max E3LIN2 с лучшим коэффициентом аппроксимации, чем любой классический алгоритм с полиномиальным временем, известный в то время. Однако впоследствии был обнаружен эффективный классический алгоритм, достигающий еще лучшего коэффициента аппроксимации (фактически, коэффициент аппроксимации, превышающий предел, установленный жесткостью аппроксимации) [260]. В настоящее время возможности QAOA по сравнению с классическими вычислениями являются активной областью исследований [300,301,302,314].

Учитывая список из m + 1 эрмитовых \(n \times n \) матриц \(C, A_1, A_2, \ ldots, A_m \) и m чисел \(b_1, \ ldots, b_m \), задача полуопределенного программирования состоит в том, чтобы найти положительное полуопределенное \( n \times n \) матрицу X, которая максимизирует tr(CX) с учетом ограничений \( \mathrm{tr} (A_j X) \leq b_j \) для \( j = 1,2,\ldots, m \). Полуопределенное программирование имеет множество применений в исследовании операций, комбинаторной оптимизации и квантовой информации, и оно включает линейное программирование как частный случай. Введенные в [313] и впоследствии улучшенные в [383,425], квантовые алгоритмы теперь известны, которые могут приблизительно решать полуопределенные программы с точностью до \( \pm \epsilon \) за время \( O (\sqrt{m} \log m \cdot \mathrm{poly}(\log n, r, \epsilon^{-1})) \), где r - ранг полуопределенной программы. Это представляет собой квадратичное ускорение по сравнению с самыми быстрыми классическими алгоритмами, когда r мало по сравнению с n. Квантовый алгоритм основан на усилении амплитуды и квантовой выборке Гиббса [121,307]. В модели, в которой входные данные предоставляются в виде квантовых состояний, квантовый алгоритм для полуопределенного программирования может достигать суперполиномиального ускорения, как обсуждалось в [383], хотя недавние результаты деквантования [421] очерчивают ограничения на контекст, в котором возможно суперполиномиальное квантовое ускорение для полуопределенных программ.

Пусть f (x,y) - многочлен степени d над конечным полем \( \mathbb {F}_p \). Пусть \( N_r \) - число проективных решений f(x,y = 0 по полю расширения \( \mathbb {F}_{p^r} \). Дзета-функция для f определена как \(Z_f(T) = \exp \left( \sum_{r=1}^\infty \frac{N_r}{r} T^r\right) \). Примечательно, что \(Z_f(T) \) всегда имеет вид \(Z_f(T) = \frac{Q_f(T)}{(1-pT)(1-T)} \), где \( Q_f(T) \) - многочлен степени 2g и \(g = \frac{1}{2} (d-1) (d-2) \) называется родом f. Учитывая \(Z_f(T) \), можно легко вычислить количество нулей f в любом поле расширения \( \mathbb {F}_{p^r} \). Аналогично можно определить дзета-функцию, когда исходное поле, над которым определено значение f, не имеет простого порядка. Как показано Кедлайей [64], квантовые компьютеры могут определять дзета-функцию кривой рода g над конечным полем \( \mathbb {F}_ {p^ r} \) за \( \mathrm{poly}(\log p, r, g) \) время. Все самые быстрые известные классические алгоритмы являются экспоненциальными либо по log(p), либо по g. В другом, но несколько связанном контексте ван Дам предположил, что благодаря связи между нулями дзета-функций Римана и собственными значениями определенных квантовых операторов квантовые компьютеры могли бы эффективно аппроксимировать число решений уравнений над конечными полями [87].

Пусть C - код на n битах, т.е. подмножество \( \mathbb{Z}_2^n \). Весовой счетчик C равен \(S_C(x,y) = \sum_ {c \в C} x ^ {|c |} y ^ {n- |c |} \), где |c| обозначает вес Хэмминга c. Весовые счетчики имеют множество применений в исследовании из классических кодов. Если C - линейный код, он может быть определен с помощью \( C = \{c: Ac = 0\} \), где A - матрица над \( \mathbb{Z}_2 \) В этом случае \( S_C(x,y) = \sum_{c:Ac=0} x^{|c|} y^{n-|c|} \). Весовые счетчики с квадратичным знаком (QWGT) являются обобщением этого: \(S(A,B,x,y) = \sum_{c:Ac=0} (-1)^{c ^ T B c} x ^{|c|} y^{n-|c|} \). Теперь рассмотрим следующий частный случай. Пусть A - матрица \( n \ умноженная на n \) над \( \mathbb{Z}_2 \) такая, что diag(A)=I. Пусть lwtr(A) - нижняя треугольная матрица, полученная в результате установки всех элементов выше диагонали в A равными нулю. Пусть l,k - целые положительные числа. Учитывая обещание, что \( |S(A,\mathrm{lwtr}(A),k,l)| \geq \frac{1}{2} (k ^ 2+l ^ 2)^{n/2} \) проблема определения знака \( S(A,\mathrm {lwtr} (A), k, l) \) является BQP-полным, как показано Книллом и Лафламмом в [65]. Оценка QWGTS также тесно связана с оценкой функций разбиения моделей Изинга и Поттса [67,45,46].

При моделировании отжига имеется серия цепей Маркова, определяемых стохастическими матрицами \( M_1, M_2,\ldots,M_n\). Они медленно изменяются в том смысле, что их предельные распределения \( pi_1, \pi_2, \ldots, \pi_n \) удовлетворяют \( |\pi_ {t+1} -\pi_t | \lt \epsilon \) для некоторого малого \( \epsilon\). Эти распределения часто можно рассматривать как тепловые распределения при последовательно понижающихся температурах. Если \( \pi_1 \) можно легко подготовить, то, применив эту серию цепей Маркова, можно выполнить выборку из \( \pi_n\). Как правило, требуется, чтобы \( \pi_n \) было распределением по хорошим решениям некоторой задачи оптимизации. Пусть \( \delta_i \) - промежуток между наибольшим и вторым по величине собственными значениями \( M_i \). Пусть \( \delta = \min_i \delta_i \). Время выполнения этого классического алгоритма пропорционально \( 1/\delta \). Основываясь на результатах Сегеди [135,85], Соммы и др. показали [84,177], что квантовые компьютеры могут выполнять выборку из \( \pi_n\) со временем выполнения, пропорциональным \( 1/\sqrt{\delta}\). Дополнительные методы, с помощью которых классические алгоритмы Монте-Карло с цепочкой Маркова могут быть ускорены с помощью квантовых блужданий, приведены в [265].

Перезапись строк - это довольно общая модель вычислений. Системы перезаписи строк (иногда называемые грамматиками) определяются списком правил, по которым определенные подстроки разрешается заменять определенными другими подстроками. Например, контекстно-свободные грамматики эквивалентны автоматам pushdown. В [59] Янцинг и Вочьян показали, что определенная проблема перезаписи строк является PromiseBQP-завершенной. Таким образом, квантовые компьютеры могут решить эту задачу за полиномиальное время, но классические компьютеры, вероятно, не могут. Учитывая три строки s, t, t" и набор правил перезаписи строк, удовлетворяющих определенным обещаниям, проблема состоит в том, чтобы найти определенное приближение к разнице между количеством способов получения t из s и количеством способов получения t" из s. Аналогично, некоторые задачи аппроксимации разницы в количестве путей между парами вершин в графе и разницы в вероятностях перехода между парами состояний при случайном блуждании также являются BQP-полными [58].

Квантовые компьютеры обладают экспоненциальным преимуществом в аппроксимации матричных элементов степеней экспоненциально больших разреженных матриц. Предположим, у нас есть \( N \ умноженная на N \) симметричная матрица A, такая, что в каждой строке имеется не более полилога (N) ненулевых записей, и, учитывая индекс строки, набор ненулевых записей может быть эффективно вычислен. Задача состоит в том, чтобы для любого 1 < i < N и любого m полилогарифмического числа в N аппроксимировать \( (A ^ m) _ {ii} \) по \( i^{\mathrm{th}} \) диагональному матричному элементу \( A ^ m \). Приближение является аддитивным с точностью до \( b ^ m \ epsilon \), где b - заданная верхняя граница для |A|, а \( b^m \epsilon \) имеет порядок 1/ полилог(N). Как показали Янцинг и Вочьян, эта задача является многообещающе QP-полной, как и соответствующая задача для недиагональных матричных элементов [60]. Таким образом, квантовые компьютеры могут решить эту задачу за полиномиальное время, но классические компьютеры, вероятно, не могут.

Проблемы удовлетворения ограничений, многие из которых являются NP-сложными, широко распространены в информатике, каноническим примером является 3-SAT. Если кто-то хочет удовлетворить как можно большему числу ограничений, а не всем из них, это становится задачей комбинаторной оптимизации. (Смотрите также адиабатические алгоритмы.) Решение задач удовлетворения ограничений методом грубой силы может быть квадратично ускорено с помощью алгоритма Гровера. Однако большинство проблем с выполнением ограничений разрешимы с помощью классических алгоритмов, которые (хотя и по-прежнему с экспоненциальным временем) выполняются более чем в квадратичном масштабе быстрее, чем проверка всех возможных решений методом перебора. Тем не менее, полиномиальное квантовое ускорение по сравнению с самым быстрым известным классическим алгоритмом для 3-SAT приведено в [133], а полиномиальные квантовые ускорения для некоторых других задач удовлетворения ограничений приведены в [134,298]. В [423] квадратичное квантовое ускорение для приближенных решений однородных задач КУБО / Изинга получено путем построения квантового алгоритма для полуопределенного программирования. Обычно используемым классическим алгоритмом для удовлетворения ограничений является обратный поиск, и для некоторых задач этот алгоритм является самым быстрым из известных. Общее квантовое ускорение алгоритмов обратного отслеживания приведено в [264] и дополнительно улучшено в [422].

В адиабатических квантовых вычислениях человек начинает с начального гамильтониана, основное состояние которого легко подготовить, и медленно изменяет гамильтониан на тот, основное состояние которого кодирует решение некоторой вычислительной задачи. Согласно адиабатической теореме, система будет отслеживать мгновенное основное состояние при условии, что изменение гамильтониана происходит достаточно медленно. Время выполнения адиабатического алгоритма в худшем случае масштабируется как \(1/ \gamma ^ 3\), где \( \gamma \) - минимальный промежуток между собственным значением основного состояния и первым возбужденным состоянием [185]. Если гамильтониан изменяется достаточно плавно, можно улучшить это до \( \widetilde {O}(1/\gamma ^ 2) \) [247]. Адиабатическое квантовое вычисление было впервые предложено Фархи и др. как метод решения NP-полных задач комбинаторной оптимизации [96,186]. Адиабатические квантовые алгоритмы для задач оптимизации обычно используют "стохастические" гамильтонианы, которые не страдают от проблемы знака. Такие алгоритмы иногда называют квантовым отжигом. Адиабатические квантовые вычисления с нестоквастическими гамильтонианами столь же мощны, как и модель квантовой схемы [97]. Адиабатические алгоритмы, использующие стохастические гамильтонианы, вероятно, менее мощные [183], но, вероятно, более мощные, чем классические вычисления [429]. Асимптотическое время выполнения алгоритмов адиабатической оптимизации, как известно, трудно поддается анализу, но был достигнут некоторый прогресс [179,180,181,182,187,188,189,190,191,226]. (Также уместна более ранняя литература по квантовому отжигу, в которой первоначально упоминался классический алгоритм оптимизации, который работает путем моделирования квантового процесса, подобно тому, как имитированный отжиг - это классический алгоритм оптимизации, который работает путем моделирования теплового процесса. См., например, [199, 198].) Адиабатические квантовые компьютеры могут выполнять процесс, в некоторой степени аналогичный поиску Гровера, за \(O(\sqrt{N}) \) время [98]. Адиабатические квантовые алгоритмы, достигающие квадратичного ускорения для более общего класса задач, построены в [184] путем адаптации методов из [85]. Адиабатические квантовые алгоритмы были предложены для нескольких конкретных задач, включая PageRank [176], машинное обучение [192,195], поиск матриц Адамара [406] и задачи с графами [193,194]. Некоторые алгоритмы квантового моделирования также используют подготовку адиабатического состояния.

Предположим, нам дан оракул для вычисления некоторой гладкой функции\( f:\mathbb {R}^d \to \mathbb{R} \). Входные и выходные данные для f передаются оракулу с конечным числом битов точности. Задача состоит в том, чтобы оценить \( \nabla f \) в некоторой заданной точке \( \mathbf{x}_0 \in \mathbb{R}^d \). Как показано в [61], квантовый компьютер может достичь этого с помощью одного запроса, тогда как классическому компьютеру требуется по крайней мере d+1 запросов. В работе [20] Балджер предложил потенциальные приложения для задач оптимизации. Как показано в приложении D к [62], квантовый компьютер может использовать градиентный алгоритм для нахождения минимума квадратичной формы в d измерениях с использованием O (d) запросов, тогда как, как показано в [94], классическому компьютеру требуется по крайней мере \( \Omega(d ^ 2) \) запросы. Квантовые алгоритмы с одним запросом для нахождения минимумов бассейнов на основе расстояния Хэмминга были приведены в [147,148,223]. Квантовый алгоритм [62] также может извлекать все \( d ^ 2 \) матричные элементы квадратичной формы, используя O(d) запросов, и, в более общем плане, все \(d ^ n \) n-е производные гладкой функции d переменных в \(O(d ^{n-1}) \) запросов. Удивительно общие результаты в [418,419,420] дают квантовое ускорение для выпуклой оптимизации и оценки объема выпуклых тел, а также нижние границы сложности запроса. Грубо говоря, эти результаты показывают, что для выпуклой оптимизации и оценки объема в d измерениях достигается квадратичное ускорение в d точно так же, как было обнаружено ранее для частного случая минимизации квадратичных форм. Как показано в [130,146], квадратичные формы и полилинейные многочлены от d переменных над конечным полем могут быть извлечены с коэффициентом d меньшего количества квантовых запросов, чем требуется классически.

Нам предоставлен Оракул с доступом к матрице A размера \( n \times n \) и некоторому описанию вектора b. Мы хотим найти некоторое свойство f (A)b для некоторой эффективно вычислимой функции f. Предположим, что A - эрмитова матрица с O(polylog n) ненулевыми элементами в каждой строке и номером условия k. Как показано в [104], квантовый компьютер может за время \(O(k ^ 2 \ log n) \) вычислить с полиномиальной точностью различные математические ожидания операторов относительно вектора f(A) b (при условии, что квантовое состояние, пропорциональное b, эффективно конструируется). Для определенных функций, таких как f(x) =1/x, эта процедура может быть распространена на неэрмитовы и даже неквадратные A. Время выполнения этого алгоритма впоследствии было улучшено до \( O(k \log^3 k \log n) \) в [138]. Экспоненциально улучшенное масштабирование времени выполнения с точностью было получено в работе [263]. Были предложены некоторые методы расширения этого алгоритма для применения к не разреженным матрицам [309,402], хотя они требуют предварительного вычисления определенных частичных сумм элементов матрицы. Расширения этого квантового алгоритма были применены к задачам оценки сечений электромагнитного рассеяния [249] (см. также [369] для другого подхода), решения линейных дифференциальных уравнений [156,296], оценки электрического сопротивления сетей [210], подгонки кривой наименьших квадратов [169], решения Системы Теплица [297] и машинное обучение [214,222,250,251,309]. Однако основанные на линейных системах квантовые алгоритмы для рекомендательных систем [309] и анализа главных компонент [250] впоследствии были "деквантованы" Тангом [400,401]. То есть Танг получил классические рандомизированные алгоритмы для этих задач за полиномиальное время, доказав тем самым, что предложенные квантовые алгоритмы для этих задач не достигают экспоненциального ускорения. Некоторые ограничения алгоритмов квантового машинного обучения, основанных на линейных системах, хорошо обобщены в [246]. В [220] было показано, что квантовые компьютеры могут инвертировать хорошо обусловленные матрицы \(n \times n\), используя только кубиты \( O( \log n) \), тогда как лучший классический алгоритм использует биты порядка \( \log ^ 2 n\). Последующие усовершенствования этого квантового алгоритма приведены в [279]. Варианты задачи о линейных системах, включая вычисление псевдоинверсий Мура-Пенроуза, могут быть получены как частные случаи квантового преобразования сингулярных значений [433].

Машинное обучение охватывает широкий спектр вычислительных задач и может быть реализовано с помощью широкого спектра алгоритмических методов. Здесь кратко излагаются квантовые алгоритмические методы для улучшения машинного обучения. Многие из приведенных здесь квантовых алгоритмов перекрестно перечислены под другими заголовками. В [214,222,250,251,309,338,339,359,403] квантовые алгоритмы для решения линейных систем [104] применяются для ускорения поиска кластеров, анализа главных компонент, бинарной классификации, обучения нейронных сетей и различных форм регрессии, при условии, что данные удовлетворяют определенным условиям. [433] для последующих улучшений квантового анализа главных компонент. Ряд алгоритмов квантового машинного обучения, основанных на линейных системах, впоследствии были "деквантованы". В частности, Тан показал в [400,401], что проблемы рекомендательных систем и анализа главных компонент, решаемые квантовыми алгоритмами [251,309], на самом деле также могут быть решены с помощью классических рандомизированных алгоритмов за полиномиальное время. Метод поиска кластеров, не основанный на алгоритме линейных систем из [104], приведен в [336]. В работах [192,195,344,345,346,348] исследуется использование методов адиабатической оптимизации для ускорения обучения классификаторов. В работе [221] предложен метод обучения машин Больцмана путем манипулирования когерентными квантовыми состояниями с амплитудами, пропорциональными весам Больцмана. В [358,340,341,342,343 за полиномиальное ускорение может быть получено путем применения поиска Гровера и связанных с ним методов, таких как усиление амплитуды, к поддающимся обработке подпрограммам современных классических алгоритмов машинного обучения.. Другие алгоритмы квантового машинного обучения, не подпадающие ни под одну из вышеперечисленных категорий, включают [337,349]. Некоторые ограничения алгоритмов квантового машинного обучения хорошо обобщены в [246]. [146,23,11,31,212] - Многие другие алгоритмы квантовых запросов, которые извлекают скрытую структуру функции черного ящика, могут быть использованы в качестве алгоритмов машинного обучения. В [224] приведены алгоритмы запросов для изучения функций большинства и "линкора". В работах [236,237] приведены большие квантовые преимущества для обучения у шумных оракулов. В [428] оценка квантового ядра используется для реализации классификатора опорных векторов, решающего задачу обучения, которая доказуемо так же сложна, как дискретный логарифм. Доступно несколько недавних обзорных статей [299,332,333] и книга [331], в которых кратко описывается состояние дел в этой области. Существует связанный с этим объем работы, не входящий строго в стандартные рамки квантовых алгоритмов, касающийся квантового обучения в том случае, если сами данные являются квантово когерентными. Смотрите, например, [350,334,335,351,352,353,354,355,356,357].

В [424] приведен квантовый алгоритм для идеализированной задачи, мотивированной приложениями машинного обучения на многомерных наборах данных. Рассмотрим \(T = \ lambda v_{\mathrm{sig}}^{\ otimes p} + G \), где G - тензор p-индексов гауссовских случайных величин, симметричный по всем перестановкам индексов, а \(v_{\mathrm{sig}}\) - это N-мерный вектор величины \(\sqrt{N}\). Задача состоит в том, чтобы восстановить \(v_{\mathrm{sig}}\). Рассмотрим \( \лямбда = \альфа N ^{-p/4}\). Лучшие классические алгоритмы успешны при \( \alpha \gg 1\) и имеют временную и пространственную сложность, которая экспоненциально масштабируется в \( \alpha ^{-1}\). Квантовый алгоритм из [424] решает эту проблему в полиномиальном пространстве и с масштабированием во время выполнения в квартальном масштабе лучше в \( \ alpha ^ {-1} \), чем классический спектральный алгоритм. Квантовый алгоритм работает путем кодирования задачи в собственный спектр многочастичного гамильтониана и применения оценки фазы вместе с усилением амплитуды.c

Рассмотрим линейное дифференциальное уравнение первого порядка \( \frac{d}{dt} \mathbf{x} = A(t) \mathbf{x} + \mathbf{b}(t) \), где \( \mathbf{x} \) и \( \mathbf{b} \) - N-мерные векторы, а A - матрица \(N \умноженная на N\). Учитывая начальное условие \( \mathbf{x}(0) \), требуется вычислить решение \( \mathbf{x}(t) \) в некоторое более позднее время t с некоторой точностью \( \эпсилон \) в том смысле, что нормализованный вектор \(x(t)/\|x(t) \|\) полученное значение имеет расстояние не более \( \эпсилон \) от точного решения. В [156] Берри дает квантовый алгоритм для этой задачи, который выполняется за время \( O(t ^ 2 \mathrm{poly}(1/\epsilon) \ mathrm{poly log} N) \), тогда как самые быстрые классические алгоритмы выполняются за время \( O (t \mathrm{poly} N ) \). Конечный результат получается в виде состояния квантовой суперпозиции на \( O(log N) \) кубитах, амплитуды которых содержат компоненты \( \mathbf{x}(t) \). Алгоритм работает путем сведения задачи к линейной алгебре с помощью метода конечных разностей высокого порядка и применения примитива квантовой линейной алгебры из [104]. В [410] был приведен улучшенный квантовый алгоритм для этой задачи, который сводит эпсилон-зависимость к \( \mathrm {poly log}(1/\epsilon)\). Квантовый алгоритм для решения нелинейных дифференциальных уравнений (опять же в смысле получения решения, закодированного в амплитудах) описан в [411], который имеет экспоненциальное масштабирование в t. В [426,427,434] приведены квантовые алгоритмы для решения нелинейных дифференциальных уравнений, которые масштабируются как \( O(t ^ 2) \). Они применимы к ограниченному классу нелинейных дифференциальных уравнений. В частности, их решения не должны слишком быстро увеличиваться или уменьшаться в размерах. Уравнения в частных производных могут быть сведены к обыкновенным дифференциальным уравнениям путем дискретизации, а дифференциальные уравнения более высокого порядка могут быть сведены к первому порядку путем добавления вспомогательных переменных. Следовательно, эти более общие проблемы могут быть решены с помощью методов [156,104]. Однако квантовые алгоритмы, предназначенные для непосредственного решения этих задач, могут быть более эффективными (и для конкретных задач можно проанализировать сложность задач, которые не определены в более общей формулировке, такой как подготовка соответствующих начальных состояний). В [249] приведен квантовый алгоритм, который решает волновое уравнение, применяя методы конечных элементов, чтобы свести его к линейной алгебре, а затем применяя алгоритм квантовой линейной алгебры из [104] с предварительным кондиционированием. В [369] приведен квантовый алгоритм для решения волнового уравнения путем дискретизации его с конечными разностями и преобразования в форму уравнения Шредингера, которое затем моделируется с использованием метода [245]. Задача, решаемая в [369], не эквивалентна задаче, решаемой в [249], поскольку в [249] задача сводится к не зависящей от времени, предполагая синусоидальную зависимость от времени и применяя разделение переменных, тогда как [369] решает зависящую от времени задачу. Квантовое ускорение, достигаемое по сравнению с классическими методами решения волнового уравнения в d-измерениях, является полиномиальным для фиксированного d, но экспоненциальным в d. Конкретные оценки ресурсов квантовых алгоритмов для решения дифференциальных уравнений приведены в работах [412,413,414]. Квантовый алгоритм решения линейных уравнений в частных производных с использованием квантовых вычислений с непрерывной переменной приведен в [415]. В [296] квантовые методы конечных элементов анализируются в общих чертах. Квантово-спектральный метод решения дифференциальных уравнений приведен в работе [416]. Квантовый алгоритм решения уравнения Власова приведен в работе [417].