Provas interativas via pós-seleção?

Defina o modelo computacional MPostBQP para ser idêntico ao PostBQP, exceto que permitimos polinomialmente muitas medições de qubit antes da pós-seleção e medição final.

Podemos dar alguma evidência indicando que o MPostBQP é mais poderoso que o PostBQP?

Defina MPostBQP [k] para permitir várias rodadas de medição e pós-seleção antes de fazer a medição final. Escolha a indexação para que MPostBQP [1] = PostBQP e MPostBQP [2] = MPostBQP e assim por diante. (Atualização: Uma definição formal é dada abaixo.)

Considere os jogos Arthur-Merlin. Talvez possamos simulá-los neste modelo de computação: a pós-seleção pode assumir o papel de Merlin de produzir mensagens convincentes e as medições intermediárias podem assumir o papel dos lançamentos públicos de moedas de Arthur. Essa possibilidade me faz perguntar:

Temos AM [k] MPostBQP [k]? $\subset$

Isso é realmente conhecido por , que diz MA PP. Mostrá- lo para significaria MPostBQP = PP somente se AM PP. Como existe um oráculo em relação ao qual o AM não está contido no PP , isso poderia dar uma resposta afirmativa à minha primeira pergunta. $k=1$ $\subset$ $k=2$ $\subset$

Finalmente, para o caso polinomialmente de muitas rodadas,

Nós temos PSPACE MPostBQP [poly]? Se sim, é igualdade? $\subset$

Isso seria filosoficamente interessante (pelo menos para mim), porque nos diria que a classe de problemas "tratável" para um "feiticeiro pós-selecionado" inclui (ou é ) todo o PSPACE.

EDIT: Me pediram uma definição formal do MPostBQP. (Atualizei o que se segue.)

MPostBQP [k] é a classe de idiomas para a qual existe uma família uniforme de circuitos quânticos de tamanho polinomial , para todos entradas de , o procedimento abaixo os rendimentos reais com probabilidade de, pelo menos, , se , e com uma probabilidade de, no máximo, , se . O procedimento, que permite algumas opções que podem depender de (mas não ), é definido da seguinte maneira: $L \subset \{0,1\}^*$ $\{C_n\}_{n \geq 1}$ $x$ $2/3$ $x \in L$ $1/3$ $x \notin L$ $L$ $x$

Procedimento: Etapa 1. Aplique o operador unitário correspondente a ao estado de entrada . Observe que o comprimento do primeiro é no máximo polinomial no comprimento de . Etapa 2. Para : Se for par, meça qualquer número desejado de qubits do primeiro registro (no máximo polinomialmente muitos, considerando o tamanho do registro). Se for ímpar, faça a pós-seleção para que um qubit único escolhido no primeiro registro seja medido como $C_n$ $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$ $\left\vert0\cdots 0\right>$ $x$ $i = 1 \cdots k$ $i$ $i$ $\left\vert 0 \right>$ (e tenha a garantia de que a probabilidade é diferente de zero, para que a pós-seleção seja válida, é claro). Etapa 3. Finalmente, meça um último qubit no primeiro registro e retorne true se medirmos e false caso contrário. $\left \vert 1 \right>$

Temos MPostBQP [0] = BQP, MPostBQP [1] = PostBQP e MPostBQP: = MPostBQP [2]. Estou tentando espelhar as classes Arthur-Merlin, onde AM [0] = BPP, AM [1] = MA e AM [2] = AM.

EDIT (27/03/11 17:00): Parece haver um debate sobre como a pós-seleção deve ser definida neste contexto. Obviamente, quero dizer uma definição que não trivialize minha pergunta! :) A definição que assumi é a seguinte: A seleção posterior no k-ésimo bit significa que projetamos o estado no subespaço no qual o k-ésimo bit é $0$ e normalize. Acontece que, em um esquema no qual selecionamos as postagens antes de realizar as medições, podemos obter as estatísticas finais observando probabilidades condicionais em um esquema no qual as pós-seleções são substituídas por medições. No entanto, afirmo que essa caracterização se decompõe quando medições e pós-seleções são intercaladas. Acho que a confusão decorre de pessoas que usam essa "definição de probabilidade condicional" (que funciona no caso especial do qual estou generalizando) como a definição de pós-seleção, em vez da definição de "medição forçada" que acabei de fornecer, que depende claramente da ordem por falta de comutatividade. Eu espero que isso ajude!

EDIT (27/03/11 21:00): Eu já defini a pós-seleção no formalismo de estado puro. Niel fez uma análise no formalismo da matriz de densidade que discorda da minha no exemplo de 3 qubit. O culpado é, novamente, a definição de pós-seleção. Defina a seleção posterior na configuração da matriz de densidade da seguinte maneira. Dada uma matriz de densidade , reescreva-a como uma mistura de estados separáveis . Seja o resultado da pós-seleção (em alguns qubit) usando o formalismo de estado puro que defini acima. Defina o resultado da seleção de postagem em como . $M$ $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$ $\left\vert A_i \right>$ $M$ $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$

Essa é uma definição mais sensata, pois não nos dá resultados que afirmam que, após a seleção, alteramos as estatísticas dos eventos (medições) que já vimos acontecer. Ou seja, os são probabilidades de moedas que "já jogamos". Não faz sentido para mim dizer que vamos voltar no tempo e influenciar uma troca de moedas que já aconteceu, porque isso tornaria a atual seleção pós-provável mais provável. $p_i$

EDIT (28/03/11 13:00): Niel admite que, com minhas definições, o problema faz sentido e não trivializa - mas com a estipulação de que não devo chamá-lo de pós - seleção . Dada a quantidade de confusão, tenho que concordar com ele. Então, vamos chamar o que eu defini como seleção , que executa uma "medição forçada". Eu provavelmente deveria mudar o nome das classes de complexidade que defini também (para não ter "Post" nelas), então vamos chamá-las de QMS [k] (quantum-measure-select).

cc.complexity-theory complexity-classes quantum-computing interactive-proofs Shaun Harker
fonte

Você pode definir o MPostBQP de maneira mais formal? Se você apenas quer dizer que essa classe tem o poder de pós-selecionar com base no resultado de vários bits, essa classe deve estar contida no PostBQP.

Robin Kothari 26/03

A idéia principal não é pós-selecionar muitos bits de uma vez, porque, como Robin aponta, isso não ajuda. É para intercalar medições e pós-seleções. Não podemos comutar estes; a ordem é importante. Por exemplo, não funcionaria no PostBQP para medir a resposta e, em seguida , selecionar novamente.

Shaun Harker

Veja o comentário na resposta de Niel; podemos adiar as medições e as pós-seleções até depois da evolução quântica. Eu já estou fazendo isso! O mesmo argumento não parece reordenar as pós-seleções após as medidas, no entanto, porque as medidas não são unitárias. Em particular, estou dizendo que as medições e pós-seleções são operações não unitárias no estado quântico que não são comutadas, pelo que sei que não podemos sem perda adiar todas as pós-seleções até depois de todas as medições.

Shaun Harker

@ Shaun Harker: o fato de as medições e as seleções pós-unitárias não serem unitárias, na verdade, não nos fornece mais informações sobre se elas serão comutadas. Talvez você possa identificar por que acha que eles não se deslocam?

Niel de Beaudrap 27/03

Por causa do emaranhado. Aqui está um exemplo. Prepare o estado . Escolha . Se primeiro medimos o primeiro qubit e depois selecionamos o terceiro qubit e depois medimos o segundo qubit para nosso resultado, obtemos ou com igual probabilidade. Se primeiro selecionarmos o terceiro qubit, depois medirmos o primeiro qubit e, finalmente, medirmos o segundo qubit para nosso resultado, obteremos menos frequência do que .

α | 000 ⟩ + \sqrt{1 / 2 - α^{2}} | 011 ⟩ + \sqrt{1 / 2 - β^{2}} | 101 ⟩ + β | 110 ⟩

$\alpha\left\vert 000 \right> + \sqrt{1/2 - \alpha^2} \left\vert 011 \right> + \sqrt{1/2 - \beta^2} \left\vert 101 \right> + \beta\left\vert 110 \right>$

0 < α < β < 1

$0 < \alpha < \beta < 1$

0

$0$

1

$1$

0

$0$

1

$1$

Shaun Harker

Respostas:

Parece pelos comentários que Shaun tem em mente algo diferente do que normalmente é entendido pela pós-seleção. Agora entendo que isso significa que as estatísticas de quaisquer medidas feitas antes de uma determinada seleção posterior não devem ser alteradas pela seleção posterior posterior. Isso é semelhante a ter um operador de projeção em que a normalização é realizada sobre cada ramo da função de onda correspondente a um resultado de medição específico, em vez de sobre a função de onda como um todo.

Nesse caso, os argumentos dados em outras respostas por mim e por Neil não se sustentam mais. De fato, é fácil ver que MPostBQP [k], já que MPostBQP pode ser visto como uma máquina BQP que pode fazer consultas a um oracle PP e, portanto, MPostBQP . $P^{PP[k]}\subseteq$ $[k]$ $k$ $P^{\# P}\subseteq$

Então agora temos um limite inferior não trivial, e o limite superior? Bem, claramente o problema está no PSPACE , mas podemos fazer melhor? Na verdade, acho que podemos.

Podemos escrever qualquer cálculo no MPostBQP como uma sequência de camadas da forma: cálculo quântico seguido de uma pós-seleção, seguido de uma única medição de qubit. De fato, essa pode ser uma maneira alternativa de formular o MPostBQP [k], como uma computação composta por tais camadas (isso é um pouco diferente da definição de Shaun, que acredito que se destina a contar apenas o número de pós-seleções), seguida por um camada final do pós-processamento clássico. Usarei esta definição de MPostBQP [k] a seguir, pois ela leva a um resultado esteticamente mais agradável. $k$

O abaixo é atualizado a partir da versão original para corrigir um furo na prova.

Primeiro, queremos calcular o resultado da medição do primeiro qubit medido (não pós-selecionado!). Para fazer isso, primeiro observamos que qualquer cálculo quântico pode ser expresso usando apenas os portões Hadamard e Toffoli, e a amplitude de um determinado estado base computacional na saída pode ser escrita como a soma de no máximo termos , em que é o número total de portas Hadamard, cada uma das quais corresponde a um caminho computacional exclusivo. Claramente, . A probabilidade de obter um estado final é então dada por $\alpha_w$ $|w\rangle$ $2^{H}$ $a_{j,w}$ $H$ $a_{j,w} = \pm 2^{-H/2}$ $|w\rangle$ $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$ . Desejamos calcular a probabilidade total de medir um 1. Seja o conjunto de estados de base computacional que atendem aos critérios de pós-seleção (ou seja, o qubit pós-seleção é 1) e resultam em 0 para o qubit medido e deixe seja o conjunto de estados de base computacional que atendem aos critérios de pós-seleção e resultam em 1 para o qubit medido. Podemos definir e $S_0$ $S_1$

π_{0}^{\pm} = \sum w \in S_{0} \pm \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w}

$\pi_0^\pm = \sum{w \in S_0} \pm \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}$

π_{1}^{\pm} = \pm \sum_{w \in S_{1}} \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w} .

$\pi_1^\pm = \pm \sum_{w \in S_1} \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}.$

Nesse caso, a probabilidade de medir 1 condicionada a 1 para o qubit pós-selecionado é dada por . Como podemos determinar isso com 4 chamadas para um oráculo #P. Usamos isso para produzir um bit aleatório que é 1 com probabilidade , o mesmo que a medição quântica. Assim, o MPostBQP [1] está no . $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$ $b_1$ $X_1$ $BPP^{\# P[4]}$

A seguir, calculamos o resultado da medição do segundo qubit. Para fazer isso, executamos as mesmas consultas #P da primeira camada, mas no circuito obtido ao compor as duas primeiras camadas e onde selecionamos em 1 para cada um dos qubits pós-selecionados, mas também em para o saída da medição 1. Observe que, embora essa seleção seja pós-selecionada nos estados de 3 qubits em vez de 1, é uma modificação trivial nas consultas , simplesmente adicionando uma ancilla que é configurada apenas se os 3 qubits atenderem às condições necessárias e pós-seleção em vez desta ancilla. Isso gera as probabilidades corretas de saída condicional para o resultado do segundo qubit medido, que rotulamos $b_1$ $\# P$ $b_2$ . Observe que agora usamos 8 chamadas para o oracle #P .

Repetimos esse processo de forma iterativa, para que, em uma camada , seja selecionada em 1 para todos os qubits pré-selecionados e em para todas as medições anteriores, e rotule o resultado do máquina . No total, isso exigiu consultas Oracle. $j$ $j$ $b_{i<j}$ $P^{\# P}$ $b_j$ $4j$

Portanto, temos MPostBQP [k] , que combinado com o resultado anterior que MPostBQP , implica que MPostBQP [k] e, portanto, MPostBQP . $\subseteq P^{\# P[4k]}$ $P^{PP[k]}\subseteq$ $[k]$ $P^{PP[k]} \subseteq$ $\subseteq BPP^{\# P[4k]}$ $= P^{\# P}$

Joe Fitzsimons
fonte

[Revisado.] Revisei minha resposta com base nas suas revisões de sua pergunta. Mantive o conteúdo da minha resposta original, mas a reduzi. A descrição mais elaborada do processo de "simulação" foi substituída, mas suponho que isso possa ser visto visualizando o histórico de edição deste post.

A maioria das pessoas entenderá "pós-seleção" no sentido de uma probabilidade condicional. De fato, a versão atual do artigo da Wikipedia no PostBQP a descreve dessa maneira; e visto como uma operação em operadores de densidade (em que se aplica um mapa de rastreamento sem aumento completamente positivo Φ, de modo que Φ ² = Φ e renormaliza o rastreamento), recupera-se essa definição.

Dada esta definição de pós-seleção , sua definição de um algoritmo MPostBQP [ k ] pode ser simulada por um algoritmo PostBQP , adiando as pós-seleções e realizando-as simultaneamente, de maneira adequada. Isso é observado mais ou menos explicitamente na página 3 do artigo de Aaronson, Quantum Computing, Postselection e Probabilistic Polynomial-Time, que apresenta a classe PostBQP .

Isso pode ser demonstrado explicitamente, observando que, para que uma sequência de bits P ₁ , P ₂ , ... seja pós-selecionada ( por exemplo, no 1estado, o que é usual), não há diferença entre condicionar o fato de eles estarem 1no meio de a computação e o condicionamento neles estando 1no final da computação, desde que os valores desses bits não sejam alterados nesse ínterim. Então, em vez de pós-selecionar cada um deles individualmente 1, podemos calcular o AND lógico antes da pós-seleção e, em seguida, selecionar novamente o conjunto1. Além disso, a computação do AND pode ser realizada a qualquer momento entre a última transformação do bit e sua pós-seleção. Isso não afetará de maneira alguma as estatísticas conjuntas de nenhuma das propriedades do estado.

Assim, usando a definição comum de pós-seleção em termos de probabilidades condicionais, teríamos MPostBQP [ k ] = PostBQP para todos os k > 0.

Como observei nos comentários acima, não acho que a operação que você descreve no estado vetores - especificamente, envolvendo a renormalização de vetores de estado independentemente em cada ramo da distribuição de probabilidade sobre os resultados da medição- corresponde à pós-seleção, pois muitas pessoas no campo (especialmente experimentalistas) descreveriam o conceito. Pode até dar origem a algumas propriedades "não-físicas", se estendidas a um mapeamento em operadores de densidade. No entanto, é um meio possível de construir algo como árvores de decisão cujos nós são rotulados por vetores de estado e, portanto, é, em princípio, um processo razoável de estudo por si só. Eu simplesmente não chamaria esse processo de 'pós-seleção'.

[Edit.] Por uma questão de organização, removi o exemplo calculado. Suponho que isso possa ser visto visualizando o histórico de edições deste post.

Niel de Beaudrap
fonte

O argumento parece incompleto. O comentário no artigo de Aaronson aponta que não ganhamos poder ao intercalar as seleções pós-postas com as evoluções unitárias, assim como não ajuda a intercalar medições com as evoluções unitárias. Mas eu não estou fazendo nenhum; Estou intercalando pós-seleção e medição. Responder a minha pergunta de maneira negativa exigiria provar que sempre podemos solicitar as pós-seleções após as medições sem perda de potência. (Não é óbvio para mim.) O restante da resposta explica apenas por que eu defini a classe para selecionar apenas uma coluna a cada rodada.

Shaun Harker

C_{j}

$C_j$

C_{j}

$C_j$

C_{j}

$C_j$

Parece que você está argumentando que obtemos as mesmas estatísticas se reordenarmos as seleções e medições. Mas se medirmos alguns bits antes de uma pós-seleção, mediremos a partir de uma distribuição diferente , teríamos se medíssemos esses mesmos bits após a pós-seleção. Portanto, as estatísticas não são as mesmas.

Shaun Harker

Para fins de coleta de estatísticas, uma seleção pós-seleção pode ser implementada fisicamente (embora de maneira ineficiente), simplesmente rejeitando tentativas nas quais a pós-condição desejada não se mantém. O status de uma pós-condição se manter ( por exemplo, "este bit único está no estado | 1⟩" ou "esses cinco bits estão no estado | 1⟩") não é afetado pela ordem de medição, desde que as operações não sejam aplicado para alterar os bits que armazenam os resultados. Como o fato de uma avaliação ser rejeitada ou não é independente da ordem de medição no PostBQP , podemos adiar a seleção pós-final até o fim.

Niel de Beaudrap 27/03

Essa caracterização da pós-seleção só se aplica quando executamos a pós-seleção antes das medições. O exemplo de três qubit que eu já dei demonstrou isso. Se eu estiver errado sobre isso, responda refutando diretamente este exemplo, que fornece estatísticas diferentes, dependendo da ordem das medições e das seleções pós-seleções.

Shaun Harker

Parece que você definiu MPostBQP , que é simplesmente PostBQP em fantasia. Em vez de tentar convencê-lo de que as medições podem ser reordenadas, talvez você ache mais convincente provar MPostBQP = PP , pois é sabido que PostBQP = PP (consulte quant-ph / 0412187 ). Para provar isso, separamos em duas tarefas:

$\subseteq$
$\subseteq$

$\subseteq$

O seguinte é adaptado do esboço de prova da Wikipedia para PostBQP = PP .

$|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$ $P_i^1$ $i$ $|1\rangle$ $A^{ij}$ $A^{ij}$

$\{p_i\}$ $q$ $\pi_0 = \sum_{w \in S_0} \psi_w^2$ $\pi_1 = \sum_{w \in S_1} \psi_w^2$ $S_0$ $S_1$ $p_i = 1 \forall i$ $q=0$ $q=1$ $\pi(1) \geq 2\pi(0)$ $\pi_0 \geq 2\pi_1$ $\pi_0$ $\pi_1$ $\psi_w$ $\psi$ $w$ $i$ $j$ $A^{ij}$ $k$ $G$ $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$

$\frac{1}{2}(1+C(\pi_1-\pi_0))$ $C>0$ $x \in L$ $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ $x \notin L$

$\alpha = \{\alpha_i\}$ $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$ $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$

Essa máquina PP pode então ser definida da seguinte forma:

$w$
$w \notin S_0 \cup S_1$ $1/2$
$\alpha$ $\alpha'$ $G$
$X = F(A,w,\alpha,x)F(A,w,\alpha',x)$
$w\in S_1$ $\frac{1+X}{2}$ $w\in S_0$ $\frac{1-X}{2}$

$\subseteq$ $k$

Joe Fitzsimons
fonte

Esse argumento mostra que intercalar várias seleções de postagens com evoluções unitárias não nos dá nada além de PP. Eu concordo totalmente. Sem perda de poder, podemos adiá-los até o fim e precisamos apenas de um. Não vejo que esse argumento me diga mais do que isso. Mas minha pergunta faz algo diferente; diz respeito à evolução unitária seguida de rodadas de medição e seleção (com probabilidades finais calculadas por esse método de árvore de decisão). Portanto, não vejo que isso resolva minha pergunta.

Shaun Harker

Para não dizer que não (extremamente) aprecio o esforço que você coloca em sua resposta. Só não vejo que isso atenda ao que eu realmente tentava alcançar, o que eu reconhecidamente não fiz muito bem em explicar.

Shaun Harker

@ Shaun: Eu não vejo a distinção. Você está sugerindo que a adição de medidas altera a potência? Certamente não é esse o caso, pois as medições são sempre equivalentes à evolução unitária em um espaço maior de Hilbert.

21811 Joe Fitzsimons

@ Shaun: Meu argumento é que matematicamente a situação com medições e a situação sem (mas com um espaço Hilbert adequadamente aumentado) são idênticas. Não estou tentando fazer nenhum tipo de argumento filosófico ou favorecendo uma interpretação da mecânica quântica, estou apenas apontando que a adição de medidas não faz diferença para o poder computacional devido a um resultado (matemático) bem estabelecido.

21811 Joe Fitzsimons

@ Shaun: Parece-me que você está implementando a pós-seleção incorretamente. Se você implementá-lo da maneira normal (ou seja, considerando quais estatísticas você obtém se considerar apenas os resultados que atendem a um critério específico), obtém PostBQP = MPostBQP, como Niel e eu mostramos. Você também obtém estatísticas idênticas, independentemente da ordem das medições do estado que você deu nos comentários. É importante ressaltar que o primeiro qubit não fornece 0 e 1 com igual probabilidade. (a ser continuado)

Joe Fitzsimons