BQP
Em Teoria da Complexidade Computacional, BQP é 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.
Imagem: Christian Junker | Photography · BY-NC-ND · Openverse
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 ∈ N } {\displaystyle \{Q_{n}:n\in \mathbb {N} \}} , tal que
Imagem: Christian Junker | Photography · BY-NC-ND · Openverse
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 {\displaystyle n} -bits usando apenas 2 n {\displaystyle 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:
Imagem: Vasilyev Serge · BY · Openverse
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, 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. 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.
