Время выполнения алгоритма Гровера

19

Какова временная сложность (не сложность запросов) алгоритма Гровера? Мне кажется ясным, что это поскольку существуют итерации и каждая итерация требует использования операции отражения, которая в свою очередь требует времени с использованием любого стандартного набора универсальных ворот.Ω(Ω(log(N)N)Ω(log(N))Ω(N)Ω(log(N))

Проблема в том, что я не могу найти ни одной ссылки, которая говорит, что временная сложность алгоритма Гровера - . Википедия и некоторые другие веб-страницы говорят, что сложность времени. В работе Гровера утверждается, что "шаги".O(Ω(log(N)N)O(O(N)O(N)

Я что-то пропустил? Возможно, люди определяют операцию отражения, чтобы занять единицу времени. Но это не имеет смысла для меня, потому что если мы сможем сыграть в игру, позволяющую произвольным унитарным элементам занимать единичное время, то не будет никакой разницы между сложностью запроса и сложностью времени.

Дэн Шталке
источник
11
Я не могу вспомнить ссылку, которая говорит о временной сложности алгоритма Гровера, но то, что вы написали, верно. Фактически, для любого конечного набора вентилей операции, выполняемые между запросами в алгоритме Гровера, требуют как минимум , поскольку каждый вентиль имеет конечную ширину, но нам нужно выполнить вентиль, который влияет на все кубитыlog NΩ(logN)logN
Робин Котари

Ответы:

11

Вопрос обычно считается спорным по следующей причине. Алгоритм Гровера - это комбинаторный алгоритм поиска для поиска решения произвольного предиката. Хотя да, - это сложность квантовых ворот на каждом этапе алгоритма черного ящика, предикат также должен быть вычислен. Сложность квантовых ворот - это , потому что в противном случае он не прочитал бы весь ввод, и вы могли бы отбросить некоторые входные биты из поиска. С другой стороны, интересный предикат может занять гораздо больше времени, чем это. Следовательно, количество обращений к предикату считается стандартной монетой, так же как и для классического аналога алгоритма Гровера, а именно случайного угадывания.Ω ( log N )Θ(logN)Ω(logN)

Грег Куперберг
источник
6

Оказывается, есть способ реализовать алгоритм Гровера с меньшим, чем воротами! Вот почему вы не смогли найти ссылку, утверждающую, что необходимы ворота . По крайней мере, в случае, когда есть один отмеченный пункт, это можно сделать лучше.Ω(O(NlogN)Ω(NlogN)

Недавний препринт Аруначалама и де Вольфа предоставляет новый алгоритм для решения проблемы поиска с одним отмеченным элементом со сложностью запроса и только ворота (из набора ворот Тоффоли + все однобитовые ворота).O(O(N)O(Nlog(logN))

Обратите внимание, что функция растет настолько медленно, что даже если - число атомов во вселенной, - не более 3.N log ( log N )log(logN)Nlog(logN)

Робин Котари
источник