Algoritmo de Grover e sua relação com classes de complexidade?

Estou ficando confuso sobre o algoritmo de Grover e sua conexão com as classes de complexidade.

O algoritmo de Grover encontra e o elemento em um banco de dados de N = 2 n (tal que f ( k ) = 1 ) de elementos com ∼ $k$$N=2^n$$f(k)=1$ chama o oráculo.

Portanto, temos o seguinte problema:

Problema: Encontre um no banco de dados de forma que f ( k ) = $k$$f(k)=1$

Agora estou ciente de que este não é um problema de decisão e, portanto, nossas definições normais de classe de complexidade , NP etc. não se aplicam realmente. Mas estou curioso para saber como definiríamos a classe de complexidade nesse caso - e o clima é feito com relação a N ou n ?$\text{P}$$\text{NP}$$N$$n$

Além disso, o algoritmo de Grover pode ser usado como uma sub-rotina. Li em vários lugares que o algoritmo de Grover não altera a classe da complexidade como um problema - existe uma maneira heurística de ver isso.

Sumário

• Existe uma teoria da complexidade dos problemas de pesquisa (também conhecidos como problemas de relação). Essa teoria inclui classes chamadas FP , FNP e FBQP que são efetivamente sobre a solução de problemas de pesquisa com diferentes tipos de recursos.
• Nos problemas de pesquisa, você também pode definir problemas de decisão, o que permite relacionar os problemas de pesquisa às classes P , NP e BQP usuais .
• Se você considera a versão de pesquisa da versão de decisão do problema, a maneira como você considera a entrada para o problema de Pesquisa Não Estruturada determinará quais limites superiores você pode colocar em sua complexidade.

A complexidade dos problemas de relacionamento

Como você observa, o problema de Grover resolve um problema de pesquisa , que na literatura de complexidade também é conhecido como problema de relação . Ou seja, é um problema do seguinte tipo:

A estrutura de um problema geral de pesquisa.
Dada uma entrada e uma relação binária R , encontre um y tal que R ( x , y ) seja válido.$x$$R$$y$$R(x,y)$

As classes de complexidade FP e FNP são definidas em termos de tais problemas, em que um está particularmente interessado no caso em que tem no máximo uma função polinomial do comprimento de x e onde a relação R ( x , y ) pode ser calculado em uma quantidade de tempo limitada por algum polinômio no comprimento de ( x , y ) .$y$$x$$R(x,y)$$(x,y)$

Em particular: o exemplo do problema de 'pesquisa de banco de dados' para o qual a Pesquisa de Grover é geralmente aplicada pode ser descrito a seguir.

Pesquisa não estruturada.
Dado um oráculo de entrada tal que O | um ⟩ | b ⟩ = | um ⟩ | b ⊕ f ( a ) ⟩ para alguma função f : { 0 , 1 } m → { 0 , 1 } , encontre y tal que O | y ⟩ | 0 ⟩ = | 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$

Aqui, o próprio oráculo é a entrada para o problema: ele desempenha o papel de , e a relação que estamos computando é R ( O , y $x$

Suponha que, em vez de um oráculo, recebamos uma entrada específica que descreve como a função f deve ser calculada, e então podemos considerar a qual classe de complexidade esse problema pertence. Como indica , a classe de complexidade apropriada que obtemos depende de como a entrada é fornecida.$x$$f$pyramids

• Suponha que a função de entrada seja fornecida como um banco de dados (como o problema às vezes é descrito), em que cada entrada no banco de dados tem algum comprimento . Se n for o comprimento da cadeia x usada para descrever o banco de dados inteiro , o banco de dados terá N = n / ℓ entradas. É então possível pesquisar exaustivamente todo o banco de dados consultando cada uma das N entradas em sequência e parar se encontrarmos uma entrada y tal que f ( y ) = 1 . Supondo que cada consulta ao banco de dados tenha algo como O $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$ , este procedimento pára no tempo O ( N log N ) ⊆ O ( n log n ) , de modo que o problema está noFP.$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$

  Supondo que a pesquisa de banco de dados possa ser feita em superposição coerente, o algoritmo de Grover permite que esse problema esteja no FBQP . No entanto, como FP  ⊆  FBQP , a pesquisa exaustiva clássica também prova que esse problema está no FBQP . Tudo o que obtemos (até os fatores de log) é uma aceleração quadrática devido a uma economia no número de consultas ao banco de dados.
  
  

• Suponha-se que a função de entrada é descrito sucintamente, por um algoritmo de tempo polinomial que tem uma especificação e um argumento y ∈ { 0 , 1 } m e calcula ó : 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}\!$em um estado de base padrão , onde m pode ser muito maior do que Ω ( log n ) . Um exemplo seria onde x especifica a forma CNF de alguma função booleana f : { 0 , 1 } m → { 0 , 1 } para m ∈ O ( n ) ; nesse caso, podemos avaliar eficientemente f ( y ) em uma entrada 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)$ e, assim, avaliar eficientemente ó em estados da base padrão. Isso coloca o problema noFNP.$y \in \{0,1\}^m$$\mathcal O$

  Dado um procedimento para avaliar de ( x , y ) no tempo O ( p ( n ) ) para n = | x | , O algoritmo de Grover resolve o problema da pesquisa não estruturada de O no tempo O ( p ( n ) $f(y)$$(x,y)$$O(p(n))$$n = \lvert x \rvert$$\mathcal O$⊆O(p(n)$O(p(n) \sqrt{2^m})$ . Isso não é polinomial emne, portanto, não é suficiente para colocar esse problema noFBQP: obtemos apenas uma aceleração quadrática - embora essa ainda seja uma economia potencialmente enorme de tempo de computação, assumindo que a vantagem oferecida pelo algoritmo de Grover não seja perdida. a sobrecarga necessária para o cálculo quântico tolerante a falhas.$\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

Em ambos os casos, a complexidade é determinada em termos do comprimento da cadeia de x * que especifica a forma de calcular a oráculo ó . No caso em que x representa uma tabela de consulta, temos N = n / ℓ ; nesse caso, o desempenho em função de N é semelhante ao desempenho em função de n ; mas no caso em que x especifica sucintamente O e N ∈ O ( 2 n / 2 ) , a mensagem geral de que Grover resolve o problema em $n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$consultas obscurecem a mensagem mais refinada de que esse algoritmo ainda é de tempo exponencial para um computador quântico.$O(\sqrt N)$

Complexidade de decisão de problemas de relacionamento

Há uma maneira simples para obter problemas de decisão de problemas de relacionamento, que é bem conhecido da teoria da NP -completo problemas: para transformar o problema de pesquisa a uma pergunta sobre a existência de uma solução válida.

A versão de decisão de um problema de pesquisa geral.
Dada uma entrada e uma relação binária R , determinar se ∃ y : R ( x , y ) se mantém.$x$$R$$\exists y: R(x,y)$

A classe de complexidade NP pode ser essencialmente definida em termos de tais problemas, quando o relacionamento é eficientemente computável: os problemas mais famosos de NP (CNF-SAT, HAMCYCLE, 3-COLORING) referem-se à mera existência de uma solução válida para um problema de relacionamento eficientemente verificável. Essa mudança de produzir soluções para simplesmente afirmar a existência de soluções é também o que nos permite descrever versões de fatoração inteira que estão no BQP (perguntando se existem fatores não triviais, em vez de solicitar os valores de fatores não triviais) .$R$

$x$$x$ uma solução para a pesquisa não estruturada que o faz sem realmente encontrar uma solução, embora não esteja claro, em geral, como fazê-lo de uma maneira que proporcione uma vantagem sobre a localização de uma solução.

Complexidade do 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$

Como podemos ver no último caso, se tratarmos a entrada apenas como um oráculo, a situação parecerá pouco intuitiva e certamente tornará impossível falar sobre as maneiras pelas quais o "banco de dados" pode ser realizado. Mas uma virtude de considerar a versão relativizada do problema, com um oráculo real, é que podemos provar coisas que, do contrário, não temos idéia de como provar. Se pudéssemos provar que a versão decisória do problema de pesquisa não estruturado e sucinto estava no BQP , teríamos uma enorme inovação na computação prática; e se pudéssemos provar que o problema de decisão não estava realmente no BQP , teríamos mostrado que 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}$

No entanto, os físicos gostam de apelar para a noção de que essa ainda é uma aceleração exponencial sem um equivalente clássico conhecido (ou realmente facilmente concebível). Isso é mais aparente no exemplo do banco de dados, onde a função oracle é uma pesquisa no banco de dados e o algoritmo de Grover pode fazer com que seja necessário muito menos pesquisas do que os dados no banco de dados. Nesse sentido, ainda há uma vantagem significativa, embora esteja completamente perdida no quadro da classe de complexidade.

$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)$

Deixe-me dar alguns exemplos (talvez seja o que você estava pedindo aqui ?):

• $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))$. Isso é massivamente mais rápido, mas não altera a avaliação de se o tempo de execução é polinomial ou algo pior; não se tornou um algoritmo de tempo polinomial. Por exemplo, o isomorfismo gráfico teria que pesquisar todas as permutações possíveis. O caça-minas teria que procurar todas as atribuições possíveis de minas em quadrados descobertos.

Obviamente, algumas vezes, uma estrutura adicional no problema permite soluções diferentes que não exigem a pesquisa de todas as provas possíveis. Lá, a pesquisa de Grover é de pouca ou nenhuma utilidade para nós, mas pode ser que possamos criar um algoritmo de tempo polinomial de outra maneira. Por exemplo, o caso do teste composto: classicamente, encontrar os fatores de um número parece difícil: não podemos fazer muito melhor do que testar todos os fatores possíveis; portanto, usar essa forma de prova não ajuda muito, mas , como já mencionado, a questão pode ser resolvida com eficiência por outra rota, o teste de primalidade da AKS.

Esqueça o banco de dados. O algoritmo de Grover resolve o problema de satisfação booleana , a saber:

$n$$1$$0$

O problema é conhecido por ser NP-completo.