Verificación cuántica unidireccional

La teoría del cómputo del estado del clúster ya está bien establecida, lo que demuestra que cualquier circuito BQP puede modificarse de modo que solo use puertas cuánticas de qubit único, posiblemente controladas de forma clásica, que proporcionen un amplio suministro de un estado conocido como "estado del clúster", que es un estado estabilizador simple de producir.

Mi pregunta es: ¿se conoce una noción similar para la verificación cuántica? Al menos inicialmente, no estoy claro por qué el estado del clúster puede funcionar en este caso.

quantum-computing Lior Eldar
fuente

Si entiendo correctamente, ¿es el problema que en QMA Merlin le entrega una prueba cuántica que tiene que incorporar de alguna manera al modelo? En otras palabras, si se tratara de QCMA en lugar de QMA, donde Merlin solo le entrega una cadena clásica, entonces podríamos usar los resultados conocidos para BQP, ¿verdad?

Robin Kothari

Si eso es correcto. Gracias por hacer esta distinción.

Lior Eldar

Para comenzar, uno podría hacer la misma pregunta para BQP: ¿podemos realizar algún cálculo cuántico dada la potencia para realizar mediciones de 1 qubit y un suministro de estados de clúster no confiables (o algún otro estado adecuado)?

Norbert Schuch

Respuestas:

Es posible restringir el verificador QMA a mediciones de un solo qubit y al preprocesamiento y posprocesamiento clásico (con aleatoriedad) mientras se mantiene la integridad de QMA.

Para ver por qué, tome cualquier clase de Hamiltonianos locales QMA-completos en qubits. Al agregar una constante de orden y reescalar con un factor , el hamiltoniano se puede llevar a la forma donde , , y $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$

, donde

es un producto de Paulis. Estimación del valor propio más pequeño de

hasta la precisión

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)$ sigue siendo difícil de QMA.

Ahora podemos construir un circuito que solo utiliza mediciones de un solo qubit que, dado un estado , acepta con probabilidad (que por la construcción es de entre y ). Para este fin, primero elija aleatoriamente una de las 's de acuerdo con la distribución . A continuación, medir cada uno de los Paulis en , y tomar la paridad de los resultados, que ahora se relacionan con $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ a través de El circuito ahora da salida a, y la salida es por lo tanto distribuido de acuerdo con.

⟨ ψ | 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$

Esto es, si elegimos una instancia de sí del problema hamiltoniano local (QMA-complete), hay un estado tal que este verificador aceptará con cierta probabilidad $|\psi\rangle$ , mientras que de lo contrario cualquier estado será rechazada con probabilidad , con . La variante de QMA donde el verificador está restringido a mediciones de un qubit es, por lo tanto, completa de QMA para $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ brecha. Finalmente, esta versión de QMA puede amplificarse utilizando solo las técnicas de amplificación convencionales para QMA, lo que finalmente demuestra que es QMA completa independientemente de la brecha (dentro del mismo rango que QMA).

Norbert Schuch
fuente

¿Podría dar una breve explicación o referencia de por qué el problema de estimar el valor propio más pequeño de

todavía es difícil de QMA? ¡Gracias!

H

$H$

Henry Yuen

Partimos de un Hamiltoniano

para el cual este problema [hasta

] es QMA completo, y lo cambiamos a un Hamiltoniano

, donde

, por lo que se estima la energía 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$ hasta precisión

sigue siendo QMA-hard.

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

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

Norbert Schuch

¿Puedes suponer siempre que

es un proyector en un espacio propio de un Pauli Hamiltoniano?

h_{i}

$h_i$

Henry Yuen

Bueno, cada término

en el hamiltoniano original se puede escribir como una suma de

productos Pauli (

para

), y el prefactor de cada Pauli producto

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

Mi interpretación de la pregunta es: ¿podemos suponer que el circuito verificador para un protocolo QMA usa solo mediciones de un solo qubit? (La idea es que el probador le envíe tanto la prueba cuántica como el estado del grupo cuántico necesarios para implementar el circuito de verificación original mediante "computación cuántica unidireccional").

El problema, por supuesto, es que el probador podría no enviarle un estado de clúster válido. Por lo tanto, el verificador tendría que probar el estado recibido para asegurarse de que realmente sea un estado de clúster. El verificador hace esto haciendo mediciones de un solo qubit y verificando que las correlaciones satisfagan las verificaciones necesarias del estabilizador. Dado que tales pruebas son destructivas para el estado, necesitaría un procedimiento en el que el verificador reciba muchas copias del estado, verifique la mayoría de ellas y use una aleatoria para el cálculo. ¿Bastan polinómicamente muchas copias?

No creo que este sea un teorema conocido. No veo un contraejemplo obvio (con un minuto de reflexión), por lo que podría ser creíble. La tecnología de prueba conocida en los estados de prueba parece que debería ser suficiente para verificar esto. Por ejemplo, vea el artículo de Matthew McKague arXiv: 1010.1989 [quant-ph]. Si obtiene una prueba que funciona, envíe el documento a QIP (fecha límite el 5 de octubre).

Anónimo
fuente

Quizás estoy malinterpretando esta pregunta. Si está preguntando si puede implementar el circuito verificador para un problema en QMA usando un cálculo basado en la medición, donde Merlin suministra la capa de entrada, y Arthur suministra todos los qubits adicionales en el estado del recurso y enreda ambos conjuntos de qubits antes de que comiencen las mediciones, entonces La respuesta es trivialmente sí. Esto se deduce directamente del hecho de que cualquier circuito cuántico puede implementarse como un cálculo basado en la medición, ya sea que le interese la entrada clásica o cuántica.

Notarás que en la mayoría de los documentos sobre sitios de entrada de cómputo basados en mediciones generalmente se identifican por separado de los otros sitios, y esta es la razón (es decir, específicamente para tratar el caso de la entrada cuántica).

Joe Fitzsimons
fuente

En realidad no estoy claro sobre este punto. En los documentos de computación basada en medidas que he visto, la transformación es de cualquier circuito BQP con entrada clásica, a un circuito de computación unidireccional que comienza desde el estado del clúster. Es decir, NO se describe como una transformación que toma cualquier circuito unitario arbitrario U a un circuito basado en medidas U_1, independientemente de la entrada. Si bien la pregunta de complejidad que hice, ahora se resuelve siguiendo la respuesta de Norbert, todavía me gustaría entender este punto.

Lior Eldar

@LiorEldar: Entonces deberías mirar el artículo original de Raussendorf y Briegel o el de Raussendorf, Browne y Briegel. Construyen explícitamente circuitos una puerta a la vez, lo que muestra que cada patrón de medición implementa una puerta dada en la capa de entrada, que puede estar en un estado arbitrario. Definitivamente puede implementar circuitos arbitrarios en entradas arbitrarias.

Joe Fitzsimons

Lior estaba realmente por aquí en Aquisgrán cuando discutimos esto, y una forma de entender la pregunta se basa en esta idea: ¿podría Merlín proporcionar la prueba integrada en un estado de clúster (no confiable), y Arthur usa sus mediciones de un qubit para verificar el clúster o verificar la prueba usando MBQC? (Tal vez uno podría usar ideas similares a las de la compilación a ciegas. ¿Dónde se usa la corrección de errores?) Desafortunadamente, uno no necesita esta buena idea para probar la dureza de QMA. ;-( Sin embargo, creo que todavía es una pregunta interesante para entender si esto funcionaría, y usted sería el experto para mostrar esto :-)

Norbert Schuch

@Lior: si desea utilizar MBQC para verificar la entrada, por supuesto, también necesita puertas de 2 qubits además de las mediciones de un qubit (ya que necesita enredar la entrada con su estado de clúster).

Norbert Schuch

@ Joe: Por cierto, la misma pregunta para BQP (¿podemos ejecutar BQP usando mediciones de 1 qubit usando un estado de clúster no confiable) por supuesto todavía está abierta, y creo que las ideas utilizadas en el cálculo ciego podrían ser el camino a seguir .

Norbert Schuch