Verificação quântica unidirecional

A teoria da computação em estado de cluster já está bem estabelecida, mostrando que qualquer circuito BQP pode ser modificado para usar apenas portas quânticas de qubit único, possivelmente controladas classicamente, desde que haja um amplo fornecimento de um estado conhecido como "estado de cluster" - que é um estado simples de produzir stablizer.

Minha pergunta é: é conhecida uma noção semelhante para verificação quântica - ou seja, é possível substituir os circuitos QMA por portas de 1 qubit com controle clássico, possivelmente usando algum "estado especial"? Pelo menos inicialmente, não estou claro por que o estado do cluster pode funcionar nesse caso.

quantum-computing Lior Eldar
fonte

Se bem entendi, o problema que o QMA Merlin lhe oferece é uma prova quântica que você precisa incorporar ao modelo? Em outras palavras, se fosse QCMA em vez de QMA, onde Merlin apenas fornece uma sequência clássica, poderíamos usar os resultados conhecidos para BQP, certo?

Robin Kothari

Sim esta correto. Obrigado por fazer essa distinção.

Lior Eldar

Para começar, pode-se fazer a mesma pergunta para o BQP: Podemos realizar qualquer cálculo quântico com o poder de realizar medições de 1 qubit e com um suprimento de estados de cluster não confiáveis (ou algum outro estado adequado)?

Norbert Schuch

Respostas:

É possível restringir o verificador QMA a medições de qubit único e pré-processamento e pós-processamento clássicos (com aleatoriedade), mantendo a integridade do QMA.

Para ver o porquê, use qualquer classe de Hamiltonianos locais QMA-completos em qubits. Pela adição de uma constante de ordem e rescaling com um fator, o Hamiltoniano pode ser trazido para a forma onde , , e $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{i} w_{i} h_{i},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, onde

é um produto de Paulis. A estimativa do menor valor próprio de

até a precisão

ainda é difícil para QMA.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

$1/\mathrm{poly}(n)$

Agora podemos construir um circuito que usa apenas medições de qubit único que, dado um estado , aceita com probabilidade (que, por construção é entre e ). Para esse fim, primeiro escolha aleatoriamente um dos de acordo com a distribuição . Em seguida, medir cada uma das Paulis em , e tomar a paridade dos resultados, que agora está relacionado com $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ via O circuito agora saídas, e a saída é, por conseguinte distribuído de acordo com a.

⟨ ψ | h_{i} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

Ou seja, se escolhermos uma instância sim do problema hamiltoniano local (completo com QMA), existe um estado de tal modo que este verificador aceitará com alguma probabilidade , enquanto que de outra forma qualquer estado será rejeitada com uma probabilidade , com . A variante de QMA onde o verificador está restrita a uma medições-qubit é, por conseguinte, QMA-completa para alguns $|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ Gap = Vão. Finalmente, esta versão do QMA pode ser amplificada usando apenas as técnicas de amplificação convencionais para o QMA, o que finalmente prova que ele é completo e independente do intervalo (dentro do mesmo intervalo que o QMA).

Norbert Schuch
fonte

Você poderia dar uma breve explicação ou referência sobre por que o problema de estimar o menor autovalor de

ainda é difícil para o QMA? Obrigado!

H

$H$

Henry Yuen

Começamos com um Hamiltoniano

para o qual esse problema [até

] é completo com QMA, e o transformamos em Hamiltoniano

, onde

, estimando a energia GS de

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$

y = p o l y (n)

$y=\mathrm{poly}(n)$

H

$H$ até a precisão

ainda é difícil para QMA.

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$

Norbert Schuch

Você pode sempre assumir que

é um projetor para um eigenspace de um Pauli hamiltoniano?

h_{i}

$h_i$

Henry Yuen

Bem, cada termo

no hamiltoniano original pode ser escrito como uma soma de

produtos Pauli (

para

) e o prefator de cada Pauli produto

h^{'}

$h'$

4^{k}

$4^k$

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$

k = O (\log (n))

$k=O(\log(n))$

P_{i}

$P_i$

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$

Norbert Schuch

Minha interpretação da pergunta é a seguinte: podemos assumir que o circuito verificador de um protocolo QMA usa apenas medições de qubit único? (A ideia é que o provador envie a você a prova quântica e o estado do cluster quântico necessário para implementar o circuito de verificação original pela "computação quântica unidirecional".)

O problema, é claro, é que o provador pode não enviar a você um estado de cluster válido. Portanto, o verificador precisaria testar o estado recebido para garantir que realmente seja um estado de cluster. O verificador faz isso fazendo medições de um qubit único e verificando as correlações que atendem às verificações necessárias do estabilizador. Como esse teste é destrutivo para o estado, seria necessário um procedimento no qual o verificador recebe muitas cópias do estado, verifica a maioria deles e usa um aleatório para o cálculo. Polinomialmente muitas cópias são suficientes?

Não acho que esse seja um teorema conhecido. Não vejo um contra-exemplo óbvio (com um minuto de reflexão), por isso pode ser crível. A tecnologia de prova conhecida nos estados de teste parece ser suficiente para verificar isso. Por exemplo, veja o artigo de Matthew McKague arXiv: 1010.1989 [quant-ph]. Se você conseguir uma prova, envie o artigo para o QIP (prazo de 5 de outubro)!

Anônimo
fonte

Talvez eu esteja entendendo mal essa pergunta. Se você está perguntando se pode implementar o circuito verificador para um problema no QMA usando um cálculo baseado em medição, em que Merlin fornece a camada de entrada e Arthur fornece todos os qubits adicionais no estado do recurso e envolve ambos os conjuntos de qubits antes do início das medições. a resposta é trivialmente sim. Isso resulta diretamente do fato de que qualquer circuito quântico pode ser implementado como um cálculo baseado em medição, independentemente de você se importar com entradas clássicas ou quânticas.

Você notará que na maioria dos trabalhos sobre sites de entrada de cálculo baseados em medidas geralmente são identificados separadamente dos outros sites, e é por isso (ou seja, especificamente para lidar com o caso de entrada quântica).

Joe Fitzsimons
fonte

Na verdade, não estou claro sobre este ponto. Nos documentos de computação baseada em medição que eu observei, a transformação é de qualquer circuito BQP com entrada clássica, em um circuito de computação unidirecional a partir do estado do cluster. Ou seja, NÃO é descrito como uma transformação que leva qualquer circuito unitário arbitrário U para um circuito U_1 baseado em medição, independentemente da entrada. Embora a questão da complexidade que eu fiz agora esteja resolvida após a resposta de Norbert, eu ainda gostaria de entender esse ponto.

Lior Eldar

@LiorEldar: Então você deve olhar o artigo original de Raussendorf e Briegel ou o artigo de Raussendorf, Browne e Briegel. Eles explicitamente constroem circuitos um portão por vez, mostrando que cada padrão de medição implementa um determinado portão na camada de entrada, que pode estar em um estado arbitrário. Definitivamente, você pode implementar circuitos arbitrários em entradas arbitrárias.

Joe Fitzsimons

Lior estava por aqui em Aachen quando discutimos isso, e uma maneira de entender a pergunta é baseada nesta idéia: Merlin poderia fornecer a prova incorporada em um estado de cluster (não confiável) e Arthur usa suas medições de um qubit para verificar o cluster ou verifique a prova usando o MBQC? (Talvez alguém possa usar idéias semelhantes às da composição cega, onde a correção de erros é usada?) Infelizmente, não é necessário ter essa boa idéia para provar a dureza do QMA. ;-( No entanto, acredito que ainda é uma questão interessante para entender se isso iria funcionar, e você seria o especialista para mostrar isso :-)

Norbert Schuch

@ Lior: Se você deseja usar o MBQC para verificar a entrada, é claro que também precisa de portas de 2 qubit, além das medições de um qubit (já que você precisa envolver a entrada com o estado do cluster).

Norbert Schuch

@ Joe: BTW, a mesma pergunta para o BQP (podemos executar o BQP usando medições de 1 qubit usando um estado de cluster não confiável) é claro que ainda está aberta, e parece-me que as idéias usadas na computação cega podem ser o caminho a percorrer .

Norbert Schuch