Mostrar código-fonte de PostBQP

Em [[Complexidade computacional|teoria da complexidade computacional]], '''PostBQP''' é uma [[classe de complexidade]] que consiste de todos os [[Problema computacional|problemas computacionais]]  solúveis em [[Complexidade de Tempo|tempo polinomial]] em uma [[Máquina de Turing quântica]] com [[postselection|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<sub>path</sub>''' é a mesma que '''PostBPP''' exceto que ao invés de quântico, o algoritmo é randômico clássico (com pós-seleção)<ref>{{citar periódico|ano=1997|título=Threshold computation and cryptographic security|periódico= [[SIAM Journal on Computing]] | volume=26 |páginas=59–78 | doi = 10.1137/S0097539792240467 |autor =Y. Han and Hemaspaandra, L. and Thierauf, T.}}</ref>

Adicionar [[pós-seleção]] parece fazer com que Máquinas de Turing Quântica fiquem muito mais poderosas: [[Scott Aaronson]] provou<ref name="PostBQP = PP">{{citar periódico |título=Quantum computing, postselection, and probabilistic polynomial-time |periódico=[[Proceedings of the Royal Society A]] |número=2063 |último=Aaronson |primeiro=Scott |ano=2005 |páginas=3473–3482 |doi=10.1098/rspa.2005.1546 |volume=461}}.  Preprint available at [http://arxiv.org/abs/quant-ph/0412187]</ref><ref>{{Citar web|url=http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html|título=Complexity Class of the Week: PP|último=Aaronson|primeiro=Scott|data=2004-01-11|obra=Computational Complexity Weblog|acessodata=2008-05-02}}</ref> 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 (complexidade)|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 (complexidade)|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 <math>|x\rangle</math> for proporcional a  <math>|\alpha_x|^p</math> no lugar de  <math>|\alpha_x|^2</math> 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 [[Circuito Quântico|circuitos quântico]]s (especificamente, uma  [[Complexidade de circuitos|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''&nbsp;=&nbsp;1|''P''&nbsp;=&nbsp;1]&nbsp;≥&nbsp;2/3
* se a entrada ''x'' não esta em ''L'' então Pr[''Q''&nbsp;=&nbsp;0|''P''&nbsp;=&nbsp;1]&nbsp;≥&nbsp;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.<ref name="PostBQP = PP" /><ref>{{citar periódico|título= Quantum Complexity Theory|periódico= SIAM Journal on Computing|ano= 1997|
    volume = 26|páginas= 11–20|autor1 =Ethan Bernstein  |autor2 =Umesh Vazirani
 |lastauthoramp=yes |doi=10.1137/s0097539796300921
}}</ref>

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 <math>(2/3)^3 + 3(1/3)(2/3)^2 = 20/27</math>, 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 <math>L1 \cap L2</math> 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<ref>{{citar periódico| doi = 10.1098/rspa.2005.1546 |último1 = Aaronson |primeiro1 = Scott|autor9 = Aaronson, Scott |ano= 2005 |título= Quantum computing, postselection, and probabilistic polynomial-time|periódico= Proceedings of the Royal Society A | volume = 461 |número= 2063 |páginas= 3473–3482 | arxiv = quant-ph/0412187}}</ref> que classes de complexidade  '''PostBQP''' (limite de erro quântico pós-selecionado em tempo polinomial) e '''[[PP (complexidade)|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''&nbsp;=&nbsp;1 tem uma probabilidade diferente de zero, a probabilidade condicional  Pr[''Q''&nbsp;=&nbsp;1|''P''&nbsp;=&nbsp;1]&nbsp;≥&nbsp;2/3 se a entrada&nbsp;''x'' esta na linguagem, e Pr[''Q''&nbsp;=&nbsp;0|''P''&nbsp;=&nbsp;1]&nbsp;≥&nbsp;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''&nbsp;=&nbsp;1]&nbsp;≥&nbsp;2<sup>&minus;''n''<sup>''c''</sup></sup> para alguma constante ''c'' dependendo da família de circuitos. Perceba que essa mudança não afeta as  [[PostBQP#Propriedades Básicas|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''&nbsp;=&nbsp;1]&nbsp;>&nbsp;0.

== Provando PostBQP &sube; PP ==
Suponhamos que a família de circuitos '''PostBQP''' para decidir uma linguagem&nbsp;''L''. Assume-se que sem perdas de generalidade (ex. ver o [[Computador quântico#A estrutura dos computadores quânticos|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 <math>\Psi</math> 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 <math>\Psi</math> nos estados com ''Q''&nbsp;=&nbsp;1,&nbsp;''P''&nbsp;=&nbsp;1 para a amplitude quadrádica de <math>\Psi</math> nos estados com ''Q''&nbsp;=&nbsp;0,&nbsp;''P''&nbsp;=&nbsp;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&nbsp;1/2.

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

: <math>\pi_1 := \text{Pr}[P=1,Q=1]=\sum_{\omega \in S_1} \Psi^2_\omega</math>

: <math>\pi_0 := \text{Pr}[P=1,Q=0]=\sum_{\omega \in S_0} \Psi^2_\omega.</math>

A definição de '''PostBQP''' garante que tanto <math>\pi_{1} \ge 2\pi_0</math> ou <math>\pi_0 \ge 2\pi_1</math> quer ''x'' esteja em ''L'' ou não.

Nossa máquina '''PP''' irá comparar <math>\pi_{1}</math> e <math>\pi_{0}</math>. Para que isso seja feito, expandimos  a definição da matriz de multiplicação:
:: <math>\Psi_\omega = \sum_{\alpha_1, \ldots, \alpha_{G}}A^{G}_{\omega,\alpha_{G}}A^{G-1}_{\alpha_G,\alpha_{G-1}}\dotsb A^2_{\alpha_3,\alpha_2} A^1_{\alpha_2,\alpha_1} x_{\alpha_1}</math>

onde a soma é tomada sobre todas as listas de vetores  <math>\alpha_i</math> com base ''G''. Agora <math>\pi_1</math> e <math>\pi_0</math> 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 <math>\frac{1}{2}(1+\pi_1-\pi_0)</math>, desde que <math>x \in L</math> implicaria que a probabilidade de aceitação é <math>\frac{1}{2}(1+\pi_{1}-\pi_{0})>1/2</math>, enquanto <math>x \not\in L</math> implicaria que a probabilidade de aceitação é  <math>\frac{1}{2}(1+\pi_1-\pi_0)<1/2</math>.

====Tecnicalidade: podemos assumir entradas das matrizes de transição ''A<sup>i</sup>'' são racionais com denominador  <math>2^{f(n)}</math> para algum polinômio ''f(n)''.====
A definição de '''PostBQP''' nos diz que <math>\pi_{1} \ge \frac{2}{3}(\pi_0+\pi_1)</math> se ''x'' esta em ''L'', e de outra forma <math>\pi_{0} \ge \frac{2}{3}(\pi_0+\pi_1)</math>. Substituindo todas as entradas de ''A'' pela fração mais próxima com denominador <math>2^{f(n)}</math> por um grande polinômio ''f(n)'' que nós descrevemos atualmente. O que será utilizado posteriormente é o ''novo'' valor  <math>\pi</math> satisfazendo <math>\pi_1 > \frac{1}{2}(\pi_0+\pi_1)</math> se ''x'' esta em ''L'', e <math>\pi_0 > \frac{1}{2}(\pi_0+\pi_1)</math> 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 <math>(1+2^{-f(n)}2^{B})^{G}-1 < \frac{1}{6}2^{-n^c},</math> assim claramente existe um ''f'' grande suficiente que é polinomial em in&nbsp;''n''.

===Construindo a Máquina PP===
Agora, detalhamos a implementação da nossa máquina '''PP'''. Seja <math>\alpha</math> denotando a sequência <math>\{\alpha_i\}_{i=1}^G</math> e defina a notação prática
:: <math>\Pi(A, \omega, \alpha, x) := A^{G}_{\omega,\alpha_{G}}A^{G-1}_{\alpha_{G},\alpha_{G-1}}\dotsb A^2_{\alpha_3,\alpha_2} A^1_{\alpha_2,\alpha_1} x_{\alpha_1}</math>,
então
:: <math>\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).</math>
Nós definimos nossa máquina '''PP''' para
* tomar um estado base <math>\omega</math> uniformemente ao aleatório
* se <math>\omega \not\in S_0 \cup S_1</math> então PARE e aceite com probabilidade 1/2, rejeito com probabilidade 1/2
* tome duas sequências <math>\alpha,\alpha'</math> do estado base ''G'' uniformemente ao aleatório
* computar <math>X = \Pi(A, \omega, \alpha, x)\Pi(A, \omega, \alpha', x)</math> (que é uma fração com denominador <math>2^{2f(n)G(n)}</math> tal que <math>-1 \le X \le 1</math>)
* se <math>\omega \in S_1</math> então aceite com probabilidade <math>\frac{1+X}{2}</math> e rejeite com probabilidade <math>\frac{1-X}{2}</math> (que toma no máximo  ''2f(n)G(n)+1'' jogadas de moeda)
* caso contrário (então <math>\omega \in S_0</math>) aceite com probabilidade <math>\frac{1-X}{2}</math> e rejeite com probabilidade <math>\frac{1+X}{2}</math> (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
<math>\frac{1}{2}+(\pi_{1}-\pi_{0})/(2^{1+B(n)+2B(n)G(n)}),</math>
então essa é uma máquina '''PP''' para a linguagem ''L'', como desejado.

== Provando PP &sube; 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
:: <math>x \in L \Leftrightarrow \#\{r \in \{0,1\}^T\mid f(x, r)=1\} \ge 2^{T-1}</math>
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,
:: <math>s := \#\{r \in \{0,1\}^T\mid f(x, r)=1\}</math>
e então <math>2^T-s</math> é o número de cadeias rejeitadas.
É diretamente argumentar que sem perda de generalidade, <math>s \not\in \{0, 2^T/2, 2^T\}</math>; para detalhamentos, ver um assunção similar [[sem perda de similaridade]] na [[PP (complexidade)#Prova de que PP é fechada sob complemento|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 <math>\sum_{x \in \{0,1\}^T} |x \rangle |f(x) \rangle</math>. Segundo, aplica-se [[Transformação de Hadamard|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
:: <math> |\psi \rangle := (2^T-s)|0 \rangle + s|1 \rangle. </math>
Onde ''H'' denota a porta de Hadamard, nós computamos o estado
:: <math> H |\psi\rangle = (2^T |0\rangle + (2^T - 2s)|1 \rangle)/\sqrt{2} </math>.
Onde <math>\alpha, \beta</math> são números reais positivos a serem escolhidos depois com <math>\alpha^2+\beta^2=1</math>, computa-se o estado <math>\alpha |0\rangle|\psi\rangle+\beta |1\rangle|H\psi\rangle</math> 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 <math>\beta/\alpha</math> onde denota-se
:: <math> | \phi_{\beta/\alpha} \rangle := \alpha s |0\rangle + \frac{\beta}{\sqrt{2}}(2^T-2s)|1\rangle</math>.

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

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

Geralmente, o algoritmo '''PostBQP''' é descrito como se segue. Seja ''k'' ser uma constante estritamente entre 1/2 e <math>(3+2\sqrt{2})/6</math>.
Faz-se o seguinte experimento para cada <math>-T \leq i \leq T</math>: constói-se e mede-se <math>| \phi_{2^i} \rangle</math> sobre as bases de <math>\{|+\rangle, |-\rangle\}</math> um total de <math>C \log T</math> vezes onde ''C'' é uma constante. Se a proporção de  <math>|+\rangle</math> 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 <math>| \phi_{2^i} \rangle</math> tem uma probabilidade de pós-seleção <math>1/2^{O(T)}</math> e então a probabilidade total é <math>1/2^{O(T^2 \log T)}</math>.

== Implicações ==
* Ver [[PP (complexidade)#Prova de que PP é fechada sob complemento|Reformulação de '''PP''' em computação quântica]]

{{Referências}}

{{DEFAULTSORT:Postbqp}}
[[Categoria:Computação quântica]]
[[Categoria:Complexidade]]