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

19

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

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

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

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

Дион Дж Дон Киви ван Вреуминген
источник

Ответы:

7

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

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

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

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

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

tparker
источник
Отличный ответ, большое спасибо! Еще одна вещь: что именно вы подразумеваете под «преодолением барьера релятивизации»?
Дион Дж Дон Киви ван Вреуминген
@DonKiwi Это странный теоретический жаргон CS. Часто мы не можем найти доказательства для претензии, но мы можем доказать мета-результат о том, какие доказательства будут или не будут работать для доказательства претензии. «Барьер» относится к результату, что некоторые широкие классы доказательств не достаточно сильны, чтобы доказать утверждение. Например, любое доказательство того, что какой-то конкретный алгоритм поиска для структурированной задачи дает быстрее, чемN
OPO=NPOPNPPEXPTIMEPOEXPTIMEOO
Ах, теперь это имеет смысл. Мне будет действительно интересно увидеть какие-либо события в этой области.
Дион Джей Дон Киви ван Вреуминген
2

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

это действительно может быть быстрее, чем О(N)?

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

user1271772
источник
Интересно, откуда пришло понижение ...
user1271772