Могут ли адиабатические квантовые вычисления быть быстрее, чем алгоритм Гровера?

Было доказано, что адиабатические квантовые вычисления эквивалентны «стандартным» или квантовым вычислениям модели затвора. Адиабатические вычисления, однако, показывают перспективы для задач оптимизации, где цель состоит в том, чтобы минимизировать (или максимизировать) функцию, которая каким-то образом связана с проблемой, то есть найти экземпляр, который минимизирует (или максимизирует) эту функцию, немедленно решает проблема.

Теперь мне кажется, что алгоритм Гровера, по сути, может делать то же самое: путем поиска в пространстве решений он найдет одно решение (возможно, из множества решений), которое удовлетворяет критерию оракула, который в этом случае приравнивается к условию оптимальности, во время , где$O(\sqrt N)$$N$ - размер пространства решений.

Этот алгоритм оказался оптимальным: как Bennett et al. (1997) сформулировал это так: «класс не может быть решен на квантовой машине Тьюринга за время o ( 2 n / 2 ) ». В моем понимании это означает, что нет способа построить какой-либо квантовый алгоритм, который находит решение путем поиска в пространстве быстрее, чем O ( $\rm NP$$o(2^{n/2})$, гдеNмасштабируется с размером проблемы.$O(\sqrt N)$$N$

Итак, мой вопрос: хотя адиабатические квантовые вычисления часто представляются превосходящими, когда речь идет о задачах оптимизации, могут ли они действительно быть быстрее, чем ? Если да, то это, кажется, противоречит оптимальности алгоритма Гровера, поскольку любой адиабатический алгоритм может быть смоделирован квантовой схемой. Если нет, то какой смысл разрабатывать адиабатические алгоритмы, если они никогда не будут быстрее, чем то, что мы можем систематически строить с помощью схем? Или что-то не так с моим пониманием?$O(\sqrt N)$

Хороший вопрос. Для неструктурированного поиска адиабатические квантовые вычисления действительно дают точно такой же ускорение, что делает стандартный алгоритм Гровера на основе шлюза, как доказано вэтом$\sqrt{N}$ важной статье Роландом и Серфом. Это согласуется с упомянутой вами эквивалентностью между адиабатическими и квантовыми вычислениями на основе затвора.

(Одно небольшое исправление в вашем вопросе: вы правы в том, что при настройке проблемы поиска оракула вам нужно сформулировать свой поисковый запрос как вопрос «да / нет», на который оракул может ответить. Но вопрос на самом деле не был принят чтобы быть «делает extremize функции F ( х ) ?», как вы предложили. Вместо этого, «является е ( х ) меньше или равно M ?» См слайдов 9 и 10 здесь . это потому , что оракул для последнего Вопрос считается более реалистичной моделью для физической установки, где онМожно предположить, что можно было непосредственно вычислить или измерить f ( x ) для данного $x$$f(x)$$f(x)$$M$$f(x)$$x$, но .)$f(x) - f_\text{min}$

Тем не менее, у адиабатического контроля качества есть два потенциальных преимущества, оба из которых трудно изучать теоретически. Первое практично: на самом деле построить большие когерентные квантовые схемы гораздо сложнее, чем просто нарисовать их в журнальной статье. Даже при том, что адиабатический контроль качества не имеет каких-либо фундаментальных преимуществ по сравнению с традиционной настройкой, его может быть гораздо проще реализовать экспериментально.

Во-вторых, то же самое предостережение относится к AQC, как и к стандартному алгоритму Гровера: это относится только к неструктурированным или «черному ящику» поиска, где мы полностью игнорируем любые корреляции между ответами, которые дает оракул, когда он подается в «похожих» или « связанные "запросы. Любая реальная проблема поиска, о которой мы заботимся, по определению будет иметь определенную структуру, хотя эта структура может быть слишком сложной для нашего анализа. Например, если мы думаем о функции, которая должна быть экстремальной, как о энергетическом ландшафте, то кажется разумным, что система может легче туннелировать между «соседними» локальными минимумами, чем между «далекими».

$\subset$ , хотя это считается очень маловероятным.

Адиабатические квантовые вычисления не могут делать ничего быстрее, чем квантовые вычисления на основе схем с точки зрения сложности вычислений. Это потому, что есть математическое доказательство того, что квантовые вычисления на основе схем могут эффективно моделировать адиабатические квантовые вычисления [см. Раздел 5 этой статьи ].

это действительно может быть быстрее, чем $\mathcal{O}(\sqrt{N})$?

Ответ - нет. Это потому, что если AQC может сделать это, скажем,$\mathcal{O}(\log{N})$, то QC на основе схем также может сделать это в $\mathcal{O}(\log{N})$по алгоритму в разделе 5 статьи, которую я связал выше. Это нарушит оптимальность$\mathcal{O}(\sqrt{N})$ для неструктурированного поиска.