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

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

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

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

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

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

Недавний препринт Аруначалама и де Вольфа предоставляет новый алгоритм для решения проблемы поиска с одним отмеченным элементом со сложностью запроса и только ворота (из набора ворот Тоффоли + все однобитовые ворота).O($O(\sqrt{N})$$O(\sqrt{N}\log(\log^* N))$

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