BQP - BQP

Na teoria da complexidade computacional , o tempo polinomial quântico de erro limitado ( BQP ) é a classe de problemas de decisão solucionáveis por um computador quântico em tempo polinomial , com uma probabilidade de erro de no máximo 1/3 para todas as instâncias. É o análogo quântico da classe de complexidade BPP .

Um problema de decisão é um membro do BQP se existe um algoritmo quântico (um algoritmo que é executado em um computador quântico) que resolve o problema de decisão com alta probabilidade e tem garantia de execução em tempo polinomial. Uma execução do algoritmo resolverá corretamente o problema de decisão com uma probabilidade de pelo menos 2/3.

Algoritmo BQP (1 execução)
Responder produzido Resposta correta	sim	Não
sim	≥ 2/3	≤ 1/3
Não	≤ 1/3	≥ 2/3
Algoritmo BQP ( k execuções)
Responder produzido Resposta correta	sim	Não
sim	> 1 - 2 ^{- ck}	<2 ^{- ck}
Não	<2 ^{- ck}	> 1 - 2 ^{- ck}
para alguma constante c > 0

Definição

O BQP pode ser visto como as linguagens associadas a certas famílias uniformes de erros limitados de circuitos quânticos . Uma linguagem L está em BQP se e somente se existe uma família uniforme de tempo polinomial de circuitos quânticos , tal que ${\ displaystyle \ {Q_ {n} \ dois pontos n \ in \ mathbb {N} \}}$

Para todos , Q _n leva n qubits como entrada e produz 1 bit ${\ displaystyle n \ in \ mathbb {N}}$
Para todo x em L , ${\ displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 1) \ geq {\ tfrac {2} {3}}}$
Para todo x não em L , ${\ displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 0) \ geq {\ tfrac {2} {3}}}$

Alternativamente, pode-se definir BQP em termos de máquinas de Turing quânticas . Uma linguagem L está em BQP se e somente se existe uma máquina de Turing quântica polinomial que aceita L com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.

Similarmente a outras classes probabilísticas de "erro limitado", a escolha de 1/3 na definição é arbitrária. Podemos executar o algoritmo um número constante de vezes e obter a maioria dos votos para atingir qualquer probabilidade desejada de correção menor que 1, usando o limite de Chernoff . A classe de complexidade é inalterado, permitindo erro tão elevada como 02/01 - n ^{- c} , por um lado, ou requerendo erro tão pequeno como 2 ^{- n ^c} , por outro lado, onde c é uma constante qualquer positivo, e n é o comprimento de entrada.

Um problema de BQP completo

Semelhante à noção de NP-completude e outros problemas completos , podemos definir um problema BQP-completo como um problema que está em BQP e que todo problema em BQP se reduz a ele em tempo polinomial.

Aqui está um problema BQP completo intuitivo, que decorre diretamente da definição de BQP.

Problema com APPROX-QCIRCUIT-PROB

Dada uma descrição de um circuito quântico atuando em qubits com portas, onde é um polinômio em e cada porta atua em um ou dois qubits e dois números , distingue entre os dois casos a seguir: ${\ displaystyle C}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$

medir o primeiro qubit do estado produz com probabilidade ${\ displaystyle C | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle \ geq \ alpha}$
medir o primeiro qubit do estado produz com probabilidade ${\ displaystyle C | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle \ leq \ beta}$

Observe que o problema não especifica o comportamento se uma instância não for coberta por esses dois casos.

Alegar. Qualquer problema de BQP se reduz a APPROX-QCIRCUIT-PROB.

Prova. Suponha que temos um algoritmo que resolve APPROX-QCIRCUIT-PROB, ou seja, dado um circuito quântico atuando em qubits, e dois números , distingue entre os dois casos acima. Podemos resolver qualquer problema no BQP com este oráculo, configurando . ${\ displaystyle A}$ ${\ displaystyle C}$ ${\ displaystyle n}$ ${\ displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$ ${\ displaystyle A}$ ${\ displaystyle \ alpha = 2/3, \ beta = 1/3}$

Para qualquer um , existe uma família de circuitos quânticos tal que, para todos , um estado de qubits, se ; mais se . Fixe uma entrada de qubits e o circuito quântico correspondente . Podemos primeiro construir um circuito assim . Isso pode ser feito facilmente cabeando e aplicando uma sequência de portas CNOT para inverter os qubits. Então podemos combinar dois circuitos para obter , e agora . E, finalmente, necessariamente os resultados de é obtido medindo vários qubits e aplicando algumas portas lógicas (clássicas) a eles. Sempre podemos adiar a medição e redirecionar os circuitos para que, medindo o primeiro qubit de , obtenhamos a saída. Este será o nosso circuito , e decidimos a associação de em concorrendo com . Por definição de BQP, cairemos no primeiro caso (aceitação) ou no segundo caso (rejeição), portanto, reduz-se a APPROX-QCIRCUIT-PROB. ${\ displaystyle L \ in \ mathrm {BQP}}$ ${\ displaystyle \ {Q_ {n} \ dois pontos n \ in \ mathbb {N} \}}$ ${\ displaystyle n \ in \ mathbb {N}}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle n}$ ${\ displaystyle x \ in L, Pr (Q_ {n} (| x \ rangle) = 1) \ geq 2/3}$ ${\ displaystyle x \ notin L, Pr (Q_ {n} (| x \ rangle) = 0) \ geq 2/3}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle n}$ ${\ displaystyle Q_ {n}}$ ${\ displaystyle C_ {x}}$ ${\ displaystyle C_ {x} | 0 \ rangle ^ {\ otimes n} = | x \ rangle}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle C '= C_ {x} Q_ {n}}$ ${\ displaystyle C '| 0 \ rangle ^ {\ otimes n} = Q_ {n} | x \ rangle}$ ${\ displaystyle Q_ {n}}$ ${\ displaystyle C '| 0 \ rangle ^ {\ otimes n} = Q_ {n} | x \ rangle}$ ${\ displaystyle C}$ ${\ displaystyle x}$ ${\ displaystyle L}$ ${\ displaystyle A (C)}$ ${\ displaystyle \ alpha = 2/3, \ beta = 1/3}$ ${\ displaystyle L \ in \ mathrm {BQP}}$

APPROX-QCIRCUIT-PROB é útil quando tentamos provar as relações entre algumas classes de complexidade conhecidas e o BQP.

Relação com outras classes de complexidade

Problema não resolvido na ciência da computação :

Qual é a relação entre e ? ${\ displaystyle {\ mathsf {BQP}}}$ ${\ displaystyle {\ mathsf {NP}}}$

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

A relação suspeita de BQP com outros espaços de problema

BQP em relação a outras classes de complexidade probabilística ( ZPP , RP , co-RP, BPP , PP ), que generalizam P dentro de PSPACE . Não se sabe se alguma dessas restrições é estrita.

BQP é definido para computadores quânticos; a classe de complexidade correspondente para computadores clássicos (ou mais formalmente para máquinas de Turing probabilísticas ) é BPP . Assim como P e BPP , BQP é baixo para si mesmo, o que significa BQP ^BQP = BQP . Informalmente, isso é verdade porque algoritmos de tempo polinomial são fechados sob composição. Se um algoritmo de tempo polinomial chama algoritmos de tempo polinomial como sub-rotinas, o algoritmo resultante ainda é o tempo polinomial.

BQP contém P e BPP e está contido em AWPP , PP e PSPACE . Na verdade, o BQP é baixo para PP , o que significa que uma máquina de PP não obtém nenhum benefício por ser capaz de resolver problemas de BQP instantaneamente, uma indicação da possível diferença de potência entre essas classes semelhantes. As relações conhecidas com classes clássicas de complexidade são:

{\ displaystyle {\ mathsf {P \ subseteq BPP \ subseteq BQP \ subseteq AWPP \ subseteq PP \ subseteq PSPACE \ subseteq EXP}}}

Como o problema de P ≟ PSPACE ainda não foi resolvido, a prova da desigualdade entre o BQP e as classes mencionadas acima é considerada difícil. A relação entre BQP e NP não é conhecida. Em maio de 2018, os cientistas da computação Ran Raz da Universidade de Princeton e Avishay Tal da Universidade de Stanford publicaram um artigo que mostrava que, em relação a um oráculo , o BQP não estava contido no PH .

Adicionar pós - seleção ao BQP resulta na classe de complexidade PostBQP que é igual a PP .

Vamos provar ou discutir alguns desses resultados a seguir.

BQP e EXP

Começamos com uma contenção mais fácil. Para mostrar isso , é suficiente mostrar que APPROX-QCIRCUIT-PROB está em EXP, pois APPROX-QCIRCUIT-PROB é BQP-completo. ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$

Reivindicar - ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Prova -

A ideia é simples. Como temos potência exponencial, dado um circuito quântico $C$ , podemos usar o computador clássico para estimular cada porta em $C$ para obter o estado final.

Mais formalmente, deixe $C$ ser um circuito quântico tamanho polinomial em $n$ qubits e $m$ portas, onde m é polinomial em n. Deixe e seja o estado após a aplicação da $i-$ ésima porta no circuito . Cada estado pode ser representado em um computador clássico como um vetor unitário em . Além disso, cada porta pode ser representada por uma matriz em . Conseqüentemente, o estado final pode ser calculado no tempo e, portanto, todos juntos, temos um algoritmo de tempo para calcular o estado final e, portanto, a probabilidade de que o primeiro qubit seja medido como um. Isso implica isso . ${\ displaystyle | \ psi _ {0} \ rangle = | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle | \ psi _ {i} \ rangle}$ ${\ displaystyle | \ psi _ {i-1} \ rangle}$ ${\ displaystyle | \ psi _ {i} \ rangle}$ ${\ displaystyle \ mathbb {C} ^ {2 ^ {n}}}$ ${\ displaystyle \ mathbb {C} ^ {2 ^ {n} \ vezes 2 ^ {n}}}$ ${\ displaystyle | \ psi _ {m} \ rangle}$ ${\ displaystyle O (m2 ^ {2n})}$ ${\ displaystyle 2 ^ {O (n)}}$ ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Observe que esse algoritmo também requer espaço para armazenar os vetores e as matrizes. Mostraremos na seção seguinte que podemos melhorar a complexidade do espaço. ${\ displaystyle 2 ^ {O (n)}}$

BQP e PSPACE

Para provar , primeiro introduzimos uma técnica chamada soma de histórias. ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PSPACE}}}$

Soma de Histórias

Soma de histórias é uma técnica introduzida pelo físico Richard Feynman para a formulação de integrais de caminho . Aplicamos essa técnica à computação quântica para resolver o APPROX-QCIRCUIT-PROB.

Árvore de soma de histórias

Considere um circuito quântico $C$ , que consiste em $t$ portas, onde cada uma vem de um conjunto de portas universal e atua em no máximo dois qubits. Para entender o que é a soma das histórias, visualizamos a evolução de um estado quântico dado um circuito quântico como uma árvore. A raiz é a entrada e cada nó na árvore possui filhos, cada um representando um estado em . O peso numa borda árvore de um nó em $j$ nível -ésimo que representa um estado de um nó em nível -ésimo representando um estado é , a amplitude de após a aplicação em . A amplitude de transição de um caminho da raiz para a folha é o produto de todos os pesos nas bordas ao longo do caminho. Para obter a probabilidade do estado final ser , somamos as amplitudes de todos os caminhos da raiz para a saída que terminam em um nó que representa . ${\ displaystyle g_ {1}, g_ {2}, \ cdots, g_ {m}}$ ${\ displaystyle g_ {j}}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle \ mathbb {C} ^ {n}}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle j + 1}$ ${\ displaystyle | y \ rangle}$ ${\ displaystyle \ langle y | g_ {j + 1} | x \ rangle}$ ${\ displaystyle | y \ rangle}$ ${\ displaystyle g_ {j + 1}}$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle | \ psi \ rangle}$ ${\ displaystyle | \ psi \ rangle}$

Mais formalmente, para o circuito quântico $C$ , sua árvore de soma sobre histórias é uma árvore de profundidade $m$ , com um nível para cada porta além da raiz, e com fator de ramificação . ${\ displaystyle g_ {i}}$ ${\ displaystyle 2 ^ {n}}$

Definir - um histórico é um caminho na árvore de soma de históricos. Vamos denotar uma história por uma sequência para algum estado final $x$ . ${\ displaystyle (u_ {0} = | 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m} = x)}$

Definir - Let . Seja a amplitude da aresta no $j-$ ésimo nível da soma sobre a árvore de histórias . Para qualquer história , a amplitude de transição da história é o produto . ${\ displaystyle u, v \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle (| u \ rangle, | v \ rangle)}$ ${\ displaystyle \ alpha _ {j} (u \ rightarrow v) = \ langle v | g_ {j} | u \ rangle}$ ${\ displaystyle h = (u_ {0} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m})}$ ${\ displaystyle \ alpha _ {h} = \ alpha _ {1} (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1}) \ alpha _ {2} (u_ {1} \ rightarrow u_ {2 }) \ cdots \ alpha _ {m} (u_ {m-1} \ rightarrow x)}$

Reivindicação - Para uma história . A amplitude de transição do histórico é computável em tempo polinomial. ${\ displaystyle (u_ {0} \ rightarrow \ cdots \ rightarrow u_ {m})}$

Prova -

Cada porta pode ser decomposta em para algum operador unitário agindo em dois qubits, que sem perda de generalidade podem ser considerados os dois primeiros. Portanto, que pode ser calculado em tempo polinomial em $n$ . Como $m$ é polinomial em $n$ , a amplitude de transição do histórico pode ser calculada em tempo polinomial. ${\ displaystyle g_ {j}}$ ${\ displaystyle g_ {j} = I \ otimes {\ tilde {g}} _ {j}}$ ${\ displaystyle {\ tilde {g}} _ {j}}$ ${\ displaystyle \ langle v | g_ {j} | u \ rangle = \ langle v_ {1}, v_ {2} | {\ tilde {g}} _ {j} | u_ {1}, u_ {2} \ rangle \ langle v_ {3}, \ cdots, v_ {n} | u_ {3}, \ cdots, u_ {n} \ rangle}$

Reivindicação - Let ser o estado final do circuito quântico. Para alguns , a amplitude pode ser calculada por . ${\ displaystyle C | 0 \ rangle ^ {\ otimes n} = \ sum _ {x \ in \ {0,1 \} ^ {n}} \ alpha _ {x} | x \ rangle}$ ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle \ alpha _ {x}}$ ${\ displaystyle \ alpha _ {x} = \ sum _ {h = (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)} \ alpha _ {h}}$

Prova -

Nós temos . O resultado vem diretamente inserindo entre , e e assim por diante e, em seguida, expanda a equação. Então, cada termo corresponde a um , onde ${\ displaystyle \ alpha _ {x} = \ langle x | C | 0 \ rangle ^ {\ otimes n} = \ langle x | g_ {t} g_ {t-1} \ cdots g_ {1} | C | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle I = \ sum _ {x \ in \ {0,1 \} ^ {n}} | x \ rangle \ langle x |}$ ${\ displaystyle g_ {1}, g_ {2}}$ ${\ displaystyle g_ {2}, g_ {3}}$ ${\ displaystyle \ alpha _ {h}}$ ${\ displaystyle h = (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)}$

Reivindicar - ${\ displaystyle {\ text {APPROX-QCIRCUIT-PROB}} \ in {\ mathsf {PSPACE}}}$

Observe que no algoritmo de soma sobre histórias para calcular alguma amplitude , apenas uma história é armazenada em qualquer ponto da computação. Conseqüentemente, o algoritmo de soma sobre os históricos usa espaço para calcular qualquer $x,$ uma vez que os bits são necessários para armazenar os históricos, além de algumas variáveis do espaço de trabalho. ${\ displaystyle \ alpha _ {x}}$ ${\ displaystyle O (nm)}$ ${\ displaystyle \ alpha _ {x}}$ ${\ displaystyle O (nm)}$

Portanto, no espaço polinomial, podemos calcular sobre todo $x$ com o primeiro qubit sendo ${\ displaystyle \ sum _ {x} | \ alpha _ {x} | ^ {2}}$ 1 , que é a probabilidade de que o primeiro qubit seja medido como 1 no final do circuito.

Observe que, em comparação com a simulação fornecida para a prova disso , nosso algoritmo aqui ocupa muito menos espaço, mas ao invés disso, muito mais tempo. Na verdade, leva tempo para calcular uma única amplitude! ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$ ${\ displaystyle O (m2 ^ {mn})}$

BQP e PP

Um argumento similar de soma sobre histórias pode ser usado para mostrar isso . ${\ displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PP}}}$

BQP, P e NP

Em primeiro lugar, sabemos , uma vez que todo circuito clássico pode ser simulado por um circuito quântico. ${\ displaystyle {\ mathsf {P}} \ subseteq {\ mathsf {BQP}}}$

É conjecturado que BQP resolve problemas difíceis fora de P, especificamente, problemas em NP. A afirmação é indefinida porque não sabemos se P = NP, então não sabemos se esses problemas estão realmente em P. Abaixo estão algumas evidências da conjectura:

Fatoração de inteiros (veja o algoritmo de Shor )
Logaritmo discreto
Simulação de sistemas quânticos (ver simulador quântico universal )
Aproximando o polinômio de Jones em certas raízes de unidade
Algoritmo Harrow-Hassidim-Lloyd (HHL)

No entanto, também conhecemos um análogo no sentido de "caixa preta". Considere o problema da busca não estruturada: dado um acesso oráculo a uma função desconhecida , encontre $x$ tal que . Este problema está claramente no NP. O algoritmo quântico ótimo para este problema, por outro lado, é o algoritmo de Grover , que tem uma complexidade de apenas se tiver permissão para acessar $f$ por meio desse oráculo. ${\ displaystyle {\ mathsf {NP}} \ not \ subseteq {\ mathsf {BQP}}}$ ${\ displaystyle f: \ {0,1 \} ^ {n} \ a \ {0,1 \}}$ ${\ displaystyle f (x) = 1}$ ${\ displaystyle O ({\ sqrt {2 ^ {n}}})}$