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)^[1]

Adicionar pós-seleção parece fazer com que Máquinas de Turing Quântica fiquem muito mais poderosas: Scott Aaronson provou^[2][3] 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 ${\displaystyle |x\rangle }$ for proporcional a ${\displaystyle |\alpha _{x}|^{p}}$ no lugar de ${\displaystyle |\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.^[2][4]

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 ${\displaystyle (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 ${\displaystyle 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^[5] 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 ${\displaystyle \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 ${\displaystyle \Psi }$ nos estados com Q = 1, P = 1 para a amplitude quadrádica de ${\displaystyle \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 ${\displaystyle 2^{B}\times 2^{B}}$) e fazendo o estado inicial ser |x> (cercado de zeros). Então ${\displaystyle \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

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

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

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

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

${\displaystyle \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 ${\displaystyle \alpha _{i}}$ com base G. Agora ${\displaystyle \pi _{1}}$ e ${\displaystyle \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 ${\displaystyle {\frac {1}{2}}(1+\pi _{1}-\pi _{0})}$, desde que ${\displaystyle x\in L}$ implicaria que a probabilidade de aceitação é ${\displaystyle {\frac {1}{2}}(1+\pi _{1}-\pi _{0})>1/2}$, enquanto ${\displaystyle x\not \in L}$ implicaria que a probabilidade de aceitação é ${\displaystyle {\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 ${\displaystyle 2^{f(n)}}$ para algum polinômio f(n).

A definição de PostBQP nos diz que ${\displaystyle \pi _{1}\geq {\frac {2}{3}}(\pi _{0}+\pi _{1})}$ se x esta em L, e de outra forma ${\displaystyle \pi _{0}\geq {\frac {2}{3}}(\pi _{0}+\pi _{1})}$. Substituindo todas as entradas de A pela fração mais próxima com denominador ${\displaystyle 2^{f(n)}}$ por um grande polinômio f(n) que nós descrevemos atualmente. O que será utilizado posteriormente é o novo valor ${\displaystyle \pi }$ satisfazendo ${\displaystyle \pi _{1}>{\frac {1}{2}}(\pi _{0}+\pi _{1})}$ se x esta em L, e ${\displaystyle \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 ${\displaystyle (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 ${\displaystyle \alpha }$ denotando a sequência ${\displaystyle \{\alpha _{i}\}_{i=1}^{G}}$ e defina a notação prática

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \omega }$ uniformemente ao aleatório
• se ${\displaystyle \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 ${\displaystyle \alpha ,\alpha '}$ do estado base G uniformemente ao aleatório
• computar ${\displaystyle X=\Pi (A,\omega ,\alpha ,x)\Pi (A,\omega ,\alpha ',x)}$ (que é uma fração com denominador ${\displaystyle 2^{2f(n)G(n)}}$ tal que ${\displaystyle -1\leq X\leq 1}$)
• se ${\displaystyle \omega \in S_{1}}$ então aceite com probabilidade ${\displaystyle {\frac {1+X}{2}}}$ e rejeite com probabilidade ${\displaystyle {\frac {1-X}{2}}}$ (que toma no máximo 2f(n)G(n)+1 jogadas de moeda)
• caso contrário (então ${\displaystyle \omega \in S_{0}}$) aceite com probabilidade ${\displaystyle {\frac {1-X}{2}}}$ e rejeite com probabilidade ${\displaystyle {\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 ${\displaystyle {\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

${\displaystyle 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,

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

e então ${\displaystyle 2^{T}-s}$ é o número de cadeias rejeitadas. É diretamente argumentar que sem perda de generalidade, ${\displaystyle 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 ${\displaystyle \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

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

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

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

Onde ${\displaystyle \alpha ,\beta }$ são números reais positivos a serem escolhidos depois com ${\displaystyle \alpha ^{2}+\beta ^{2}=1}$, computa-se o estado ${\displaystyle \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 ${\displaystyle \beta /\alpha }$ onde denota-se

${\displaystyle |\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 ${\displaystyle s>2^{T-1}}$, (isto é se ${\displaystyle x\in L}$) então ${\displaystyle \phi _{\beta /\alpha }}$ fica no quadrante aberto ${\displaystyle Q_{acc}:=(-|1\rangle ,|0\rangle )}$ enquanto se ${\displaystyle s<2^{T-1}}$, (isto é se ${\displaystyle x\not \in L}$) então ${\displaystyle \phi _{\beta /\alpha }}$ fica no quadrante aberto ${\displaystyle Q_{rej}:=(|0\rangle ,|1\rangle )}$. De fato, para qualquer x fixado (e seu correspondente s), conforme varia-se a proporção ${\displaystyle \beta /\alpha }$ em ${\displaystyle (0,\infty )}$, percebe-se que a imagem de ${\displaystyle |\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 ${\displaystyle |+\rangle =(|1\rangle +|0\rangle )/{\sqrt {2}}}$, que é o centro de ${\displaystyle Q_{rej}}$, e seja ${\displaystyle |-\rangle }$ ortogonal à ${\displaystyle |+\rangle }$. Qualquer qubit em ${\displaystyle Q_{acc}}$, quando medido nas bases ${\displaystyle \{|+\rangle ,|-\rangle \}}$, dado o valor ${\displaystyle |+\rangle }$ menor que 1/2 do tempo. Por outro lado, se ${\displaystyle x\not \in L}$ e nós tivermos tomado ${\displaystyle \beta /\alpha =r^{*}:={\sqrt {2}}s/(2^{T}-2s)}$ então medindo ${\displaystyle |\phi _{\beta /\alpha }\rangle }$ na base ${\displaystyle \{|+\rangle ,|-\rangle \}}$ daria o valor ${\displaystyle |+\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 ${\displaystyle \beta /\alpha }$ buscando conseguir um que seja "próximo" de r*.

Especificamente, perceba ${\displaystyle 2^{-T}<r*<2^{T}}$ e deixe sucetivamente configurar ${\displaystyle \beta /\alpha }$ para qualquer valor da forma ${\displaystyle 2^{i}}$ para ${\displaystyle -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 ${\displaystyle |\phi _{2^{i}}\rangle }$ sobre a base de ${\displaystyle \{|+\rangle ,|-\rangle \}}$ mede ${\displaystyle |+\rangle }$ é ao menos ${\displaystyle (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 ${\displaystyle (3+2{\sqrt {2}})/6}$. Faz-se o seguinte experimento para cada ${\displaystyle -T\leq i\leq T}$: constói-se e mede-se ${\displaystyle |\phi _{2^{i}}\rangle }$ sobre as bases de ${\displaystyle \{|+\rangle ,|-\rangle \}}$ um total de ${\displaystyle C\log T}$ vezes onde C é uma constante. Se a proporção de ${\displaystyle |+\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 ${\displaystyle |\phi _{2^{i}}\rangle }$ tem uma probabilidade de pós-seleção ${\displaystyle 1/2^{O(T)}}$ e então a probabilidade total é ${\displaystyle 1/2^{O(T^{2}\log T)}}$.

Implicações

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

Referências