PostBQP

Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com pós-seleção e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas).

Pós-seleção não é considerada uma funcionalidade que um computador realístico (mesmo um quântico) iria conter, mas ainda assim, máquinas pós-seletivas são interessantes sob uma perspectiva teórica.

Remover qualquer uma dessas duas funcionalidades (quanticidade e pós-seleção) de PostBQP resulta em uma das duas seguintes classes, sendo as duas subclasses de PostBQP:

• BQP é a mesma que PostBQP apenas sem pós-seleção
• BPP_path é a mesma que PostBPP exceto que ao invés de quântico, o algoritmo é randômico clássico (com pós-seleção)

Adicionar pós-seleção parece fazer com que Máquinas de Turing Quântica fiquem muito mais poderosas: Scott Aaronson provou que PostBQP é equivalente a PP, uma classe que se acredita ser relativamente poderosa, enquanto que BQP não se sabe se até mesmo contém a classe aparentemente menor NP. Utilizando técnicas similares, Aaronson também provou que pequenas mudanças nas leis da computação quântica teriam efeitos significativos. Como exemplos específicos, sob quaisquer das duas seguintes mudanças, a "nova" versão de BQP se tornaria equivalente a PP:

• se nós ampliarmos a definição de 'porta quântica' para incluir não apenas operações unárias mas também operações lineares, ou
• se a probabilidade de medição de um estado base $|x\rangle$ for proporcional a $|\alpha _{x}|^{p}$ no lugar de $|\alpha _{x}|^{2}$ para qualquer inteiro ímpar p > 2.

Propriedades Básicas

Para descrever algumas das propriedades de PostBQP fixamos uma maneira de descrever pós-seleção quântica. Defina um algoritmo quântico como sendo uma família de circuitos quânticos (especificamente, uma família uniforme de circuitos). Designamos um qubit como o qubit de pós-seleção P e outro como qubit de saída Q. Então PostBQP é definida pela pós-seleção sobre o evento em que o qubit de pós-seleção é |1>. Explicitamente, uma linguagem L está em PostBQP se existe um algoritmo quântico A tal que após rodar A sobre a entrada x e avaliando os dois qubits P e Q,

• P = 1 com probabilidade diferente de zero
• se a entrada x esta em L então Pr[Q = 1|P = 1] ≥ 2/3
• se a entrada x não esta em L então Pr[Q = 0|P = 1] ≥ 2/3.

Pode se provar que permitir um único passo pós-seletivo no final do algoritmo (como descrito acima) ou permitir intermediar passos pós-seletivos durante o algoritmo são equivalentes.

Aqui estão as três propriedades básicas de PostBQP (que também são garantidas para BQP através de provas similares):

1. PostBQP é fechada sobre complemento. Dada uma linguagem L é PostBQP e uma família de circuito decisora correspondente, criar uma nova família de circuito por troca do saída qubit após medição, então, a nova família de circuito prova que o complemento de L esta em PostBQP.

2. Você pode realizar a amplificação de probabilidade em PostBQP. A definição de PostBQP não é modificada se nós substituirmos o valor 2/3 em sua definição por alguma outra constante estritamente 1/2 e 1. Como exemplo, dado um algoritmo PostBQP A com probabilidade de sucesso 2/3, nós podemos construir outro algoritmo que executa três independente cópias de A, resultando um bit pós-seletivo equivalente à conjunção lógica dos três "mais internos" , e resultando em um bit resultado equivalente a maioria dos três "mais internos"; o novo algoritmo será corrigido com probabilidade condicional $(2/3)^{3}+3(1/3)(2/3)^{2}=20/27$, maior que a original 2/3.

3. PostBQP é fechada sobre interseção. Suponha que tenhamos famílias de circuitos PostBQP para duas linguagens L1 e L2, com seus respectivos 'pós-seletivos qubits' e 'saída qubit' P1, P2, Q1, Q2. Nós podemos assumir por probabilística amplificação de que ambas famílias de circuito tem uma probabilidade de sucesso de nó mínimo 5/6. Então, criamos um algoritmo composto onde os circuitos para L1 e L2 são executados independentemente, e nós configuramos P para a conjunção de P1 e P2, e Q para a conjunção de Q1 e Q2. Não é dificilmente reconhecível um limíte de união que esse algoritmo composto corretamente decide pertinência em $L1\cap L2$ com probabilidade (condicional) de no mínimo 2/3.

Mais genericamente, combinações dessas ideias mostram que PostBQP é fechado sobre união e reduções à tabelas-verdade BQP.

PostBQP = PP

Scott Aaronson mostrou que classes de complexidade PostBQP (limite de erro quântico pós-selecionado em tempo polinomial) e PP (tempo probabilístico polinomial) são equivalentes. O resultado foi significativo pois essa reformulação quântica de PP deu novas ideias e provas simplificadas das propriedades de PP.

A definição comum de uma família de circuitos PostBQP é uma com dois outbit qubits P (pós-seleção) e Q (resultado) com uma única medição de P e Q no final tal que a probabilidade de medição de P = 1 tem uma probabilidade diferente de zero, a probabilidade condicional Pr[Q = 1|P = 1] ≥ 2/3 se a entrada x esta na linguagem, e Pr[Q = 0|P = 1] ≥ 2/3 se a entrada x não esta na linguagem. Por razões técnicas nós puxamos a definição de PostBQP como o seguinte: requer-se que Pr[P = 1] ≥ 2^−nc para alguma constante c dependendo da família de circuitos. Perceba que essa mudança não afeta as propriedades básicas de PostBQP, e também, é possível mostrar demonstrar qualquer computação consistente de barreiras típicas (ex. Hadamard, Toffoli) tem essa propriedade sempre que Pr[P = 1] > 0.

Provando PostBQP ⊆ PP

Suponhamos que a família de circuitos PostBQP para decidir uma linguagem L. Assume-se que sem perdas de generalidade (ex. ver o propriedades inessenciais dos computadores quânticos) que todas as barreiras tem matrizes de transição que são representadas com números reais, ao custo de adicionar um qubit a mais.

Faça $\Psi$ denotar o estado quântico final do circuito antes da medida pós-seleção ser feita. O objetivo geral da prova é construir um algoritmo PP para decidir L. Mais especificamente é suficiente ter L comparando corretamente a amplitude quadrádica de $\Psi$ nos estados com Q = 1, P = 1 para a amplitude quadrádica de $\Psi$ nos estados com Q = 0, P = 1 para determinar qual maior. A ideia chave é a de que a comparação dessas amplitudes podem ser transformadas em comparar a probabilidade de aceitação de uma máquina PP com 1/2.

Visualização Matricial de Algoritmos PostBQP

Sejam n denotando o tamanho da entrada, B = B(n) denotando o número total de qubits no circuito (entradas, auxiliares, saídas e qubits de pós-seleção), e G = G(n) denotando o número total de portas. Representando a i-ésima porta por sua matriz de transição Aⁱ (uma matriz unária real $2^{B}\times 2^{B}$) e fazendo o estado inicial ser |x> (cercado de zeros). Então $\Psi =A^{G}A^{G-1}\dotsb A^{2}A^{1}|x\rangle$. Definindo S₁ (resp. S₀) como sendo o conjunto dos estados base correspondendo a P = 1, Q = 1 (resp. P = 1, Q = 0) e definindo as probabilidades

$\pi _{1}:={\text{Pr}}[P=1,Q=1]=\sum _{\omega \in S_{1}}\Psi _{\omega }^{2}$

$\pi _{0}:={\text{Pr}}[P=1,Q=0]=\sum _{\omega \in S_{0}}\Psi _{\omega }^{2}.$

A definição de PostBQP garante que tanto $\pi _{1}\geq 2\pi _{0}$ ou $\pi _{0}\geq 2\pi _{1}$ quer x esteja em L ou não.

Nossa máquina PP irá comparar $\pi _{1}$ e $\pi _{0}$. Para que isso seja feito, expandimos a definição da matriz de multiplicação:

$\Psi _{\omega }=\sum _{\alpha _{1},\ldots ,\alpha _{G}}A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}$

onde a soma é tomada sobre todas as listas de vetores $\alpha _{i}$ com base G. Agora $\pi _{1}$ e $\pi _{0}$ podem ser expressas como a soma dos produtos das paridades desses termos. Intuitivamente, nós queremos desenvolver uma máquina cuja probabilidade de aceitação é algo como ${\frac {1}{2}}(1+\pi _{1}-\pi _{0})$, desde que $x\in L$ implicaria que a probabilidade de aceitação é ${\frac {1}{2}}(1+\pi _{1}-\pi _{0})>1/2$, enquanto $x\not \in L$ implicaria que a probabilidade de aceitação é ${\frac {1}{2}}(1+\pi _{1}-\pi _{0})<1/2$.

Tecnicalidade: podemos assumir entradas das matrizes de transição Aⁱ são racionais com denominador $2^{f(n)}$ para algum polinômio f(n).

A definição de PostBQP nos diz que $\pi _{1}\geq {\frac {2}{3}}(\pi _{0}+\pi _{1})$ se x esta em L, e de outra forma $\pi _{0}\geq {\frac {2}{3}}(\pi _{0}+\pi _{1})$. Substituindo todas as entradas de A pela fração mais próxima com denominador $2^{f(n)}$ por um grande polinômio f(n) que nós descrevemos atualmente. O que será utilizado posteriormente é o novo valor $\pi$ satisfazendo $\pi _{1}>{\frac {1}{2}}(\pi _{0}+\pi _{1})$ se x esta em L, e $\pi _{0}>{\frac {1}{2}}(\pi _{0}+\pi _{1})$ se x não esta em L. Usando o assumido anteriormente tecnicamente e analizando como a 1-norma do estado computacional muda, isso parece ser satisfeito se $(1+2^{-f(n)}2^{B})^{G}-1<{\frac {1}{6}}2^{-n^{c}},$ assim claramente existe um f grande suficiente que é polinomial em in n.

Construindo a Máquina PP

Agora, detalhamos a implementação da nossa máquina PP. Seja $\alpha$ denotando a sequência $\{\alpha _{i}\}_{i=1}^{G}$ e defina a notação prática

$\Pi (A,\omega ,\alpha ,x):=A_{\omega ,\alpha _{G}}^{G}A_{\alpha _{G},\alpha _{G-1}}^{G-1}\dotsb A_{\alpha _{3},\alpha _{2}}^{2}A_{\alpha _{2},\alpha _{1}}^{1}x_{\alpha _{1}}$,

então

$\pi _{1}-\pi _{0}=\sum _{\omega \in S_{1}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)-\sum _{\omega \in S_{0}}\sum _{\alpha ,\alpha '}\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x).$

Nós definimos nossa máquina PP para

• tomar um estado base $\omega$ uniformemente ao aleatório
• se $\omega \not \in S_{0}\cup S_{1}$ então PARE e aceite com probabilidade 1/2, rejeito com probabilidade 1/2
• tome duas sequências $\alpha ,\alpha '$ do estado base G uniformemente ao aleatório
• computar $X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)$ (que é uma fração com denominador $2^{2f(n)G(n)}$ tal que $-1\leq X\leq 1$)
• se $\omega \in S_{1}$ então aceite com probabilidade ${\frac {1+X}{2}}$ e rejeite com probabilidade ${\frac {1-X}{2}}$ (que toma no máximo 2f(n)G(n)+1 jogadas de moeda)
• caso contrário (então $\omega \in S_{0}$) aceite com probabilidade ${\frac {1-X}{2}}$ e rejeite com probabilidade ${\frac {1+X}{2}}$ (que novamente toma no máximo 2f(n)G(n)+1 jogadas de moeda)

Então é diretamente para computador que essa máquina aceita com probabilidade ${\frac {1}{2}}+(\pi _{1}-\pi _{0})/(2^{1+B(n)+2B(n)G(n)}),$ então essa é uma máquina PP para a linguagem L, como desejado.

Provando PP ⊆ PostBQP

Supõe-se que tenhamos uma máquina PP com complexidade de tempo T:=T(n) sobre a entrada x de tamanho n := |x|. Assim, a máquina joga uma moeda no máximo T vezes durante a computação. Pode-se então ver a máquina como uma função determinística f (implementada, ex. por um circuito clássico) que toma duas entradas (x, r) onde r, uma cadeia de caracteres binária de tamanho T, representa o resultado das randômicas jogadas de moeda que são realizadas pelo computador, e o resultado de f é 1 (aceite) ou 0 (rejeite). A definição de PP nos diz que

$x\in L\Leftrightarrow \#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}\geq 2^{T-1}$

Assim, queremos um algoritmo PostBQP que pode determinar se a expressão acima é verdadeira.

Definindo s como sendo o número de cadeias de caracteres randômicas que levam a aceitação,

$s:=\#\{r\in \{0,1\}^{T}\mid f(x,r)=1\}$

e então $2^{T}-s$ é o número de cadeias rejeitadas. É diretamente argumentar que sem perda de generalidade, $s\not \in \{0,2^{T}/2,2^{T}\}$; para detalhamentos, ver um assunção similar sem perda de similaridade na prova de que PP é fechada sobre complemento.

Algoritmo de Aaronson

O algoritmo de Aaronson para resolver esse problema é a seguir descrito. For simplicidade, vamos descrever todos os estados quânticos como não-normalizados. Primeiro, prepara-se o estado $\sum _{x\in \{0,1\}^{T}}|x\rangle |f(x)\rangle$. Segundo, aplica-se porta de Hadamard ao primeiro registrador (cada um dos primeiros qubits T), mede-se o primeiro registrador e pós-seleção nele sendo toda string composta unicamente por zeros. É facilmente verificável que isso deixa o último registrador (o último qubit) no estado residual

$|\psi \rangle :=(2^{T}-s)|0\rangle +s|1\rangle .$

Onde H denota a porta de Hadamard, nós computamos o estado

$H|\psi \rangle =(2^{T}|0\rangle +(2^{T}-2s)|1\rangle )/{\sqrt {2}}$.

Onde $\alpha ,\beta$ são números reais positivos a serem escolhidos depois com $\alpha ^{2}+\beta ^{2}=1$, computa-se o estado $\alpha |0\rangle |\psi \rangle +\beta |1\rangle |H\psi \rangle$ e mede-se o segundo qubit, pos-selecionando em seu valor sendo igual a 1, o que deixa o primeiro qubit em um estado residual dependendo de $\beta /\alpha$ onde denota-se

$|\phi _{\beta /\alpha }\rangle :=\alpha s|0\rangle +{\frac {\beta }{\sqrt {2}}}(2^{T}-2s)|1\rangle$.

Visualizando os estados possíveis de um qubit como um círculo, vê-se que se $s>2^{T-1}$, (isto é se $x\in L$) então $\phi _{\beta /\alpha }$ fica no quadrante aberto $Q_{acc}:=(-|1\rangle ,|0\rangle )$ enquanto se $s<2^{T-1}$, (isto é se $x\not \in L$) então $\phi _{\beta /\alpha }$ fica no quadrante aberto $Q_{rej}:=(|0\rangle ,|1\rangle )$. De fato, para qualquer x fixado (e seu correspondente s), conforme varia-se a proporção $\beta /\alpha$ em $(0,\infty )$, percebe-se que a imagem de $|\phi _{\beta /\alpha }\rangle$ é precisamente o quadrante aberto correspondente. No restante da prova, faz-se precisa a idéia de que nós podemos distinguir entre esses dois quadrantes.

Análise

Seja $|+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}$, que é o centro de $Q_{rej}$, e seja $|-\rangle$ ortogonal à $|+\rangle$. Qualquer qubit em $Q_{acc}$, quando medido nas bases $\{|+\rangle ,|-\rangle \}$, dado o valor $|+\rangle$ menor que 1/2 do tempo. Por outro lado, se $x\not \in L$ e nós tivermos tomado $\beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)$ então medindo $|\phi _{\beta /\alpha }\rangle$ na base $\{|+\rangle ,|-\rangle \}$ daria o valor $|+\rangle$ todo o tempo. Desde que não seja sabido s também não seja sabido o valor preciso r*, mas pode-se tentar vários (polinomialmente muito) valores diferentes para $\beta /\alpha$ buscando conseguir um que seja "próximo" de r*.

Especificamente, perceba $2^{-T}<r*<2^{T}$ e deixe sucetivamente configurar $\beta /\alpha$ para qualquer valor da forma $2^{i}$ para $-T\leq i\leq T$. Então os cálculos elementares mostram que para um desses valores de i, a probabilidade de medição de $|\phi _{2^{i}}\rangle$ sobre a base de $\{|+\rangle ,|-\rangle \}$ mede $|+\rangle$ é ao menos $(3+2{\sqrt {2}})/6\approx 0.971.$

Geralmente, o algoritmo PostBQP é descrito como se segue. Seja k ser uma constante estritamente entre 1/2 e $(3+2{\sqrt {2}})/6$. Faz-se o seguinte experimento para cada $-T\leq i\leq T$: constói-se e mede-se $|\phi _{2^{i}}\rangle$ sobre as bases de $\{|+\rangle ,|-\rangle \}$ um total de $C\log T$ vezes onde C é uma constante. Se a proporção de $|+\rangle$ medições é maior que k, então rejeite. Se não rejeitar para qualquer i, aceite. Limite de Chernoff então mostra ue para uma constante C universal suficientemente grande, nós classificamos corretamente x com probabilidade de no mínimo 2/3.

Observa-se que esse algoritmo satisfaz a assunção técnica de que a probabilidade de pós-seleção não é muito pequena: cada medição individual de $|\phi _{2^{i}}\rangle$ tem uma probabilidade de pós-seleção $1/2^{O(T)}$ e então a probabilidade total é $1/2^{O(T^{2}\log T)}$.

Implicações

• Ver Reformulação de PP em computação quântica