PostBQP

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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
  • BPPpath é 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 for proporcional a no lugar de para qualquer inteiro ímpar p > 2.

Propriedades Básicas[editar | editar código-fonte]

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 , 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 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[editar | editar código-fonte]

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] ≥ 2nc 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[editar | editar código-fonte]

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 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 nos estados com Q = 1, P = 1 para a amplitude quadrádica de 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[editar | editar código-fonte]

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 Ai (uma matriz unária real ) e fazendo o estado inicial ser |x> (cercado de zeros). Então . Definindo S1 (resp. S0) como sendo o conjunto dos estados base correspondendo a P = 1, Q = 1 (resp. P = 1, Q = 0) e definindo as probabilidades

A definição de PostBQP garante que tanto ou quer x esteja em L ou não.

Nossa máquina PP irá comparar e . Para que isso seja feito, expandimos a definição da matriz de multiplicação:

onde a soma é tomada sobre todas as listas de vetores com base G. Agora e 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 , desde que implicaria que a probabilidade de aceitação é , enquanto implicaria que a probabilidade de aceitação é .

Tecnicalidade: podemos assumir entradas das matrizes de transição Ai são racionais com denominador para algum polinômio f(n).[editar | editar código-fonte]

A definição de PostBQP nos diz que se x esta em L, e de outra forma . Substituindo todas as entradas de A pela fração mais próxima com denominador por um grande polinômio f(n) que nós descrevemos atualmente. O que será utilizado posteriormente é o novo valor satisfazendo se x esta em L, e 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 assim claramente existe um f grande suficiente que é polinomial em in n.

Construindo a Máquina PP[editar | editar código-fonte]

Agora, detalhamos a implementação da nossa máquina PP. Seja denotando a sequência e defina a notação prática

,

então

Nós definimos nossa máquina PP para

  • tomar um estado base uniformemente ao aleatório
  • se então PARE e aceite com probabilidade 1/2, rejeito com probabilidade 1/2
  • tome duas sequências do estado base G uniformemente ao aleatório
  • computar (que é uma fração com denominador tal que )
  • se então aceite com probabilidade e rejeite com probabilidade (que toma no máximo 2f(n)G(n)+1 jogadas de moeda)
  • caso contrário (então ) aceite com probabilidade e rejeite com probabilidade (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 então essa é uma máquina PP para a linguagem L, como desejado.

Provando PP ⊆ PostBQP[editar | editar código-fonte]

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

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,

e então é o número de cadeias rejeitadas. É diretamente argumentar que sem perda de generalidade, ; para detalhamentos, ver um assunção similar sem perda de similaridade na prova de que PP é fechada sobre complemento.

Algoritmo de Aaronson[editar | editar código-fonte]

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 . 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

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

.

Onde são números reais positivos a serem escolhidos depois com , computa-se o estado 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 onde denota-se

.

Visualizando os estados possíveis de um qubit como um círculo, vê-se que se , (isto é se ) então fica no quadrante aberto enquanto se , (isto é se ) então fica no quadrante aberto . De fato, para qualquer x fixado (e seu correspondente s), conforme varia-se a proporção em , percebe-se que a imagem de é 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[editar | editar código-fonte]

Seja , que é o centro de , e seja ortogonal à . Qualquer qubit em , quando medido nas bases , dado o valor menor que 1/2 do tempo. Por outro lado, se e nós tivermos tomado então medindo na base daria o valor 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 buscando conseguir um que seja "próximo" de r*.

Especificamente, perceba e deixe sucetivamente configurar para qualquer valor da forma para . Então os cálculos elementares mostram que para um desses valores de i, a probabilidade de medição de sobre a base de mede é ao menos

Geralmente, o algoritmo PostBQP é descrito como se segue. Seja k ser uma constante estritamente entre 1/2 e . Faz-se o seguinte experimento para cada : constói-se e mede-se sobre as bases de um total de vezes onde C é uma constante. Se a proporção de 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 tem uma probabilidade de pós-seleção e então a probabilidade total é .

Implicações[editar | editar código-fonte]

Referências

  1. Y. Han and Hemaspaandra, L. and Thierauf, T. (1997). «Threshold computation and cryptographic security». SIAM Journal on Computing. 26: 59–78. doi:10.1137/S0097539792240467 
  2. a b Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A. 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546 . Preprint available at [1]
  3. Aaronson, Scott (11 de janeiro de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado em 2 de maio de 2008 
  4. Ethan Bernstein & Umesh Vazirani (1997). «Quantum Complexity Theory». SIAM Journal on Computing. 26: 11–20. doi:10.1137/s0097539796300921 
  5. Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187Acessível livremente. doi:10.1098/rspa.2005.1546