BQP

Problema de ciência da computação em aberto:

Qual a relação entre BQP e NP?

(mais problemas em aberto da ciência da computação)

Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias. É a classe quântica análoga da classe de complexidade BPP.

Em outras palavras, existe um algoritmo para um computador quântico (um algoritmo quântico) que resolve o problema de decisão com alta probabilidade e é garantido de executar em tempo polinomial. Em qualquer dada execução do algoritmo, ele tem uma probabilidade de até 1/3 de que vai dar uma resposta errada.

Similarmente a outras classes probabilisticas "de erro limitado", a escolha de 1/3 na definição é arbitrária. Pode-se executar o algoritmo um número constante de vezes e tomar uma maioria para alcançar qualquer probabilidade de corretude menor que 1 desejada, utilizando o limitante de chernoff. Análises detalhadas mostram que a classe de complexidade é inalterada admitindo um erro tão alto quando ${1/2}-{n^{-c}}$ por um lado, ou exigindo um erro tão pequeno quanto $2^{n^{-c}}$ por outro lado, onde $c$ é qualquer constante positiva, e $n$ é o tamanho da entrada.

Definição

BQP pode também ser vista como uma família uniforme de circuitos quânticos de erro limitado. Uma linguagem L está em BQP se e somente se, existe uma família de tempo polinomial de circuitos quânticos $\{Q_{n}:n\in \mathbb {N} \}$ , tal que

Para todo $n\in \mathbb {N}$ , $Q_{n}$ toma n qubits como entrada e dá como saída 1 bit
Para todo $x$ em L, $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
Para todo $x$ que não esta em L, $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

Computação Quântica

O número de qubits no computador é permitido que seja uma função polinomial do tamanho da instância. Por exemplo, algoritmos que são conhecidos por fatorar um inteiro de $n$ -bits usando apenas $2n$ qubits (Algoritmo de Shor).

Normalmente, computação em um computador quântico termina com uma medição. isso leva a um colapso de função de onda do estado quântico a um dos estados base. Pode ser dito que o estado quântico é medido para estar no estado correto com uma probabilidade alta.

Computadores quânticos tem ganho um largo interesse por alguns problemas de interesse prático também sabidos de estar em BQP, mas suspeitos de estarem fora de P. Alguns exemplos proeminentes são:

Fatoração de inteiros (ver Algoritmo de Shor)^[2]
Logaritmo discreto^[2]
Simulação de sistemas quânticos (ver Simulador Quântico)
Computar o Polinômio de Jones em certas raízes de unidade

Relacionamento com outras classes de complexidade

Essa classe é definida por um computador quântico e sua classe correspondente natural para um computador normal (ou uma Máquina de Turing mais uma fonte de aleatoriedade) é $BPP$ . Assim como $P$ e $BPP$ , $BQP$ é de baixa complexidade por si mesmo, que significa $BQP$ ^$BQP$ = $BQP$ . Informalmente, isso é verdadeiro porque algoritmos de tempo polinomial são fechados por composição. Se um algoritmo de tempo polinomial chama como uma subrotina polinomial muitos algoritmos de tempo polinomial, o algoritmo resultante continua executando em tempo polinomial.

$BQP$ contém $P$ e $BPP$ e esta contido em $AWPP$ ,^[3] $PP$ ^[4] e $PSPACE$ .^[5] De fato, $BQP$ é de baixa complexidade para $PP$ , significando que uma máquina $PP$ não conseguem se beneficiar por serem capazes de resolver instantaneamente problemas $BQP$ , um indicativo da possível diferença do poder dessas classes similares.

{\ce {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE}}

Como o problema $P ≟ PSPACE$ ainda não foi resolvido, o problema da diferença entre $BQP$ e as classes mencionadas acima é supostamente difícil.^[5] A relação entre $BQP$ e $NP$ não é conhecida.

Adicionar postselection à $BQP$ resulta na classe de complexidade $PostBQP$ que é igual à $PP$ .^[6]^[7]

Ligações externas

Complexity Zoo link to BQP

Referências

↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
↑ ^a ^b arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor
↑ Fortnow, Lance; Rogers, John (1999). «Complexity limitations on Quantum computation» (PDF). Boston, MA: Academic Press. J. Comput. Syst. Sci. 59 (2): 240–252. ISSN 0022-0000. doi:10.1006/jcss.1999.1651
↑ L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.
↑ ^a ^b Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [1]
↑ Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A. 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546 . Preprint available at [2]
↑ Aaronson, Scott (11 de janeiro de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado em 2 de maio de 2008

[1] Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.

[Shor-2] rXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

[3] Fortnow, Lance; Rogers, John (1999). «Complexity limitations on Quantum computation» (PDF). Boston, MA: Academic Press. J. Comput. Syst. Sci. 59 (2): 240–252. ISSN 0022-0000. doi:10.1006/jcss.1999.1651

[4] L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.

[BernVazi-5] Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [1]

[PostBQP=PP-6] Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A. 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546 . Preprint available at [2]

[7] Aaronson, Scott (11 de janeiro de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado em 2 de maio de 2008

[1]

[2]

[3]

[4]

[5]

[6]

[7]