Алгоритм Гровера и его связь с классами сложности?

Я запутался в алгоритме Гровера и его связи с классами сложности.

Алгоритм Гровера находит и элемент в базе данных с (таким, что ) элементов с обращениями к оракулу.$k$$N=2^n$$f(k)=1$

Итак, у нас есть следующая проблема:

Проблема: Найти в базе данных так, чтобы$k$$f(k)=1$

Теперь я знаю, что это не проблема решения, и поэтому наши обычные определения класса сложности , т. Д. На самом деле не применяются. Но мне любопытно узнать, как мы будем определять класс сложности в таком случае - и будет ли это сделано в отношении или ?$\text{P}$$\text{NP}$$N$$n$

Кроме того, алгоритм Гровера может быть использован в качестве подпрограммы. Я читал в нескольких местах, что алгоритм Гровера не меняет класс сложности, это проблема - есть ли эвристический способ увидеть это.

Резюме

• Существует теория сложности поисковых задач (также известная как проблемы отношений). Эта теория включает в себя классы, называемые FP , FNP и FBQP, которые эффективно решают задачи поиска с различными видами ресурсов.
• Из задач поиска вы также можете определить задачи решения, что позволяет связать задачи поиска с обычными классами P , NP и BQP .
• Независимо от того, рассматриваете ли вы поисковую версию решающей версии проблемы, то, как вы учитываете вклад в проблему неструктурированного поиска, определит, какие верхние границы вы можете установить для ее сложности.

Сложность проблем отношений

Как вы заметили, проблема Гровера решает проблему поиска , которая в литературе о сложности иногда также называется проблемой отношений . То есть это проблема следующего вида:

Структура общей поисковой задачи.
Учитывая , вход и бинарное отношение , найти таких , что имеет место.$x$$R$$y$$R(x,y)$

Классы сложности FP и FNP определены в терминах таких задач, где, в частности, интересует случай, когда имеет длину не более чем полиномиальную функцию длины , и где отношение может само по себе вычисляться за время, ограниченное некоторым полиномом от длины .$y$$x$$R(x,y)$$(x,y)$

В частности: пример проблемы «поиск в базе данных», к которой обычно применяется поиск Гровера, можно описать следующим образом.

Неструктурированный поиск.
Имеется входной оракул такой, что для некоторой функции , найдите такой, что .$\mathcal O: \mathcal H_2^{\otimes m+1} \!\to \mathcal H_2^{\otimes m+1}$$\mathcal O \lvert a \rangle \lvert b \rangle = \lvert a \rangle \lvert b \oplus f(a) \rangle$$f: \{0,1\}^m \to \{0,1\}$$y$$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Здесь сам оракул является источником проблемы: он играет роль$x$ , а отношение, которое мы вычисляем, равно

Предположим, что вместо оракула нам предоставляется конкретный вход который описывает, как должна вычисляться функция f , и мы можем затем рассмотреть, к какому классу сложности относится эта задача. Как видно , соответствующий класс сложности, который мы получаем, зависит от того, как предоставляется ввод.$x$$f$pyramids

• Предположим, что функция ввода предоставляется в качестве базы данных (как иногда описывается проблема), где каждая запись в базе данных имеет некоторую длину . Если n - длина строки x, используемой для описания всей базы данных , то в базе данных есть N = n / ℓ записей. Затем можно провести исчерпывающий поиск по всей базе данных, запросив каждую из N записей по порядку, и остановиться, если мы найдем запись y такую, что f ( y ) = 1 . Предположим, что каждый запрос к базе данных занимает что-то вроде O $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$ , эта процедура останавливается во времени O ( N log N ) ⊆ O ( n log n ) , так что проблема вFP.$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$

  Предполагая, что поиск в базе данных может быть выполнен в когерентной суперпозиции, алгоритм Гровера позволяет эту проблему в FBQP . Однако, поскольку FP  ⊆  FBQP , классический исчерпывающий поиск также доказывает, что эта проблема находится в FBQP . Все, что мы получаем (с учетом логарифмических коэффициентов), - это квадратичное ускорение благодаря экономии числа запросов к базе данных.
  
  

• Предположим, что входная функция кратко описывается алгоритмом полиномиального времени, который принимает спецификацию и аргумент y ∈ { 0 , 1 } m и вычисляет O : H m + 1$x \in \{0,1\}^n$$y \in \{0,1\}^m$$\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$на нормативной основе состояние , где м может быть значительно больше , чем П ( журнал п ) . Примером может служить случай, когда x задает форму CNF некоторой булевой функции f : { 0 , 1 } m → { 0 , 1 } для m ∈ O ( n ) , и в этом случае мы можем эффективно оценить f ( y ) на входе y $\lvert y \rangle\lvert b \rangle$$m$$\Omega(\log n)$$x$$f: \{0,1\}^m \to \{0,1\}$$m \in O(n)$$f(y)$ и тем самым эффективно оценивать O на стандартных базовых состояниях. Это ставит проблему вFNP.$y \in \{0,1\}^m$$\mathcal O$

  Дана процедура оценки из ( x , y ) за время O ( p ( n ) ) для n = | х | Алгоритм Гровера решает проблему неструктурированного поиска O за время O ( p ( n ) $f(y)$$(x,y)$$O(p(n))$$n = \lvert x \rvert$$\mathcal O$$O(p(n) \sqrt{2^m})$ $\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

$n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$$O(\sqrt N)$

Сложность решения из проблем отношений

Существует простой способ получить решение проблем из отношений отношений, что хорошо известно из теории NP- неполных задач: превратить задачу поиска в вопрос о существовании действительного решения.

$x$$R$$\exists y: R(x,y)$

$R$

$x$$x$ решение для неструктурированного поиска, которое делает это без фактического поиска решения, хотя в целом не ясно, как это сделать таким образом, чтобы обеспечить преимущество по сравнению с фактическим поиском решения.

Сложность Oracle

$\mathcal O$$x$$\mathcal O$

$\mathcal O$$n$$\mathcal O$$n$$x$

$\mathcal O$
$x = 11\cdots 1$$n$

• $y \in \{0,1\}^n$

• $y \in \{0,1\}^n$

$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

$\mathsf{NP}^{\mathcal O}$$\mathsf{FNP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$$\mathsf{FBQP}^{\mathcal O}$

$\mathcal O$

Как видно из последнего случая, если мы будем рассматривать ввод только как оракула, ситуация выглядит немного не интуитивно понятной, и это, безусловно, делает невозможным говорить о способах реализации «базы данных». Но одно достоинство рассмотрения релятивизированной версии проблемы с реальным оракулом состоит в том, что мы можем доказать вещи, которые в противном случае мы понятия не имеем, как доказать. Если бы мы могли доказать, что версия решения краткой неструктурированной задачи поиска была в BQP , то мы бы достигли огромного прорыва в практических вычислениях; и если бы мы могли доказать, что проблема решения на самом деле не была в BQP , то мы бы показали, что P ≠ PSPACE$\mathcal O$$\mathcal O$$\mathsf{NP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$

$n$$m$$n$

$m*2^{n/2}$$m*2^{n-1}$

Тем не менее, физики любят апеллировать к мнению, что это все еще экспоненциальное ускорение без какого-либо известного (или действительно легко мыслимого) классического эквивалента. Это наиболее очевидно в примере с базой данных, где функция oracle является поиском в базе данных, а алгоритм Гровера может привести к тому, что потребуется гораздо меньше поисков, чем имеется данных в базе данных. В этом смысле все еще есть существенное преимущество, хотя оно полностью потеряно в картине класса сложности.

$n$

$\text{NP}$

$f(x)$$x\in\{0,1\}^n$$x$$f(x)=1$$p_x$$m\sim\text{poly}(n)$$g(x,p_x)=1$$f(x)=1$$g(x,p_x)$$\text{poly}(n)$

Позвольте мне привести несколько примеров (возможно, это то, что вы просили здесь ?):

• $f(x)$$x$$x$$f(x)$$g(x,p_x)=f(x)$

• $f(x)$$x$$x=72$$p_x=(8,9)$$g(x,p)$$x$

• $G_1$$G_2$$x$$f(x)$$p_x$$G_1$$G_2$$g(x,p_x)$$p_x$$G_1$$G_2$

• $x$$f(x)$$p_x$$g(x,p_x)$

$\text{NP}$$\text{P}$$\text{P}$

$\text{P}$$\text{NP}$$\text{NP}$$\text{P}$$\text{P}\neq\text{NP}$

$\text{NP}$$x$$p_x$$m=\text{poly}(n)$$g(x,p_x)=1$$O(2^m\text{poly}(m))$$g(x,p_x)=1$$p_x$$O(2^{m/2}\text{poly}(m))$, Это значительно быстрее, но не меняет оценку того, является ли время выполнения полиномиальным или что-то хуже; он не стал алгоритмом полиномиального времени. Например, изоморфизм графов должен был бы искать по всем возможным перестановкам. Сапер должен будет искать все возможные назначения мин на открытых площадках.

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

Забудьте о базе данных. Алгоритм Гровера решает проблему булевой удовлетворенности , а именно:

$n$$1$$0$

Известно, что проблема является NP-полной.