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)

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

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)
• Logaritmo discreto
• 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, PP e PSPACE. 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. A relação entre BQP e NP não é conhecida.

Adicionar postselection à BQP resulta na classe de complexidade PostBQP que é igual à PP.

Ligações externas

• Complexity Zoo link to BQP