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

Qual a relação entre BQP e NP?

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.

A relação suspeita entre BQP para outros espaços de problemas[1]

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 por um lado, ou exigindo um erro tão pequeno quanto por outro lado, onde é qualquer constante positiva, e é o tamanho da entrada.

Definição editar

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  , tal que

  • Para todo  ,   toma n qubits como entrada e dá como saída 1 bit
  • Para todo   em L,  
  • Para todo   que não esta em L,  

Computação Quântica editar

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  -bits usando apenas   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:

Relacionamento com outras classes de complexidade editar

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 BQPBQP = 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.

 

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 editar

Referências

  1. Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
  2. a b arXiv: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.
  5. a b Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [1]
  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