BQP

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{P}\mathrm{r}(Q_{|x|}(x)=1)\ge \frac{2}{3}$
• Para todo $x$ que não esta em L, $\mathrm{P}\mathrm{r}(Q_{|x|}(x)=0)\ge \frac{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) é Predefinição:Math. Assim como Predefinição:Math e Predefinição:Math, Predefinição:Math é de baixa complexidade por si mesmo, que significa Predefinição:Math^{Predefinição:Math} = Predefinição:Math. 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.

Predefinição:Math contém Predefinição:Math e Predefinição:Math e esta contido em Predefinição:Math, Predefinição:Math e Predefinição:Math. De fato, Predefinição:Math é de baixa complexidade para Predefinição:Math, significando que uma máquina Predefinição:Math não conseguem se beneficiar por serem capazes de resolver instantaneamente problemas Predefinição:Math, um indicativo da possível diferença do poder dessas classes similares.

$\mathrm{P}\subseteq \mathrm{B}\mathrm{P}\mathrm{P}\subseteq \mathrm{B}\mathrm{Q}\mathrm{P}\subseteq \mathrm{A}\mathrm{W}\mathrm{P}\mathrm{P}\subseteq \mathrm{P}\mathrm{P}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$

Como o problema Predefinição:Math ainda não foi resolvido, o problema da diferença entre Predefinição:Math e as classes mencionadas acima é supostamente difícil. A relação entre Predefinição:Math e Predefinição:Math não é conhecida.

Adicionar postselection à Predefinição:Math resulta na classe de complexidade Predefinição:Math que é igual à Predefinição:Math.

Ligações externas

• Complexity Zoo link to BQP