¿Pruebas interactivas vía postselección?

Defina que el modelo computacional MPostBQP sea idéntico a PostBQP, excepto que permitimos polinómicamente muchas mediciones de qubit antes de la selección posterior y la medición final.

¿Podemos dar alguna evidencia que indique que MPostBQP es más poderoso que PostBQP?

Defina MPostBQP [k] para permitir múltiples rondas de medición y postselección antes de realizar la medición final. Elija la indexación para MPostBQP [1] = PostBQP y MPostBQP [2] = MPostBQP y así sucesivamente. (Actualización: a continuación se proporciona una definición formal).

Considere los juegos de Arthur-Merlin. Quizás podamos simularlos en este modelo de cómputo: la postelección puede tomar el papel de Merlín de producir mensajes convincentes y las mediciones intermedias pueden tomar el papel de los lanzamientos públicos de monedas de Arthur. Esta posibilidad me hace preguntar:

¿Tenemos AM [k] $\subset$ MPostBQP [k]?

De hecho, esto se conoce para , que dice MA PP. Mostrarlo para significaría MPostBQP = PP solo si AM PP. Como hay un oráculo en relación con el cual AM no está contenido en PP , esto podría dar una respuesta afirmativa para mi primera pregunta. $k=1$ $\subset$ $k=2$ $\subset$

Finalmente, para el caso polinomialmente de muchas rondas,

¿Tenemos PSPACE $\subset$ MPostBQP [poli]? Si es así, ¿es igualdad?

Esto sería filosóficamente interesante (al menos para mí) porque nos diría que la clase de problemas "manejables" para un "hechicero postseleccionador" incluye (o es ) todo PSPACE.

EDITAR: Me han pedido una definición formal de MPostBQP. (He actualizado lo que sigue.)

MPostBQP [k] es la clase de lenguajes para la cual existe una familia uniforme de circuitos cuánticos de tamaño polinomial modo que para todas las entradas , el siguiente procedimiento da como resultado verdadero con probabilidad al menos si , y con probabilidad, como máximo, si . El procedimiento, que permite algunas opciones que pueden depender de (pero no $L \subset \{0,1\}^*$ $\{C_n\}_{n \geq 1}$ $x$ $2/3$ $x \in L$ $1/3$ $x \notin L$ $L$ $x$ ), se define de la siguiente manera:

Procedimiento: Paso 1. Aplicar el operador unitario correspondiente a al estado de entrada . Tenga en cuenta la longitud de la primera registro es a lo sumo polinomio en la longitud de . Paso 2. Para : si es par, mida cualquier número deseado de qubits desde el primer registro (como mucho polinomialmente muchos, dado el tamaño del registro). Si $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$ es impar, luego se selecciona para que un qubit único elegido en el primer registro mida como (y tienen una garantía de que la probabilidad no es cero de modo que el postselección es válido, por supuesto). Paso 3. Finalmente, mida un último qubit en el primer registro y devuelva verdadero si medimos y falso en caso contrario. $\left\vert 0 \right>$ $\left \vert 1 \right>$

Tenemos MPostBQP [0] = BQP, MPostBQP [1] = PostBQP y MPostBQP: = MPostBQP [2]. Estoy tratando de reflejar las clases de Arthur-Merlin donde AM [0] = BPP, AM [1] = MA y AM [2] = AM.

EDITAR (27/03/11 5 PM): Parece haber debate sobre cómo se debe definir la postselección en este contexto. ¡Obviamente, me refiero a una definición que no trivializa mi pregunta! :) La definición que he asumido es la siguiente: la selección posterior en el kth bit significa que proyectamos el estado en el subespacio en el que el kth bit es $0$ y normalizar. Resulta que en un esquema donde posteleccionamos antes de hacer mediciones, entonces podemos obtener las estadísticas finales al observar las probabilidades condicionales en un esquema donde las postselecciones son reemplazadas por mediciones. Sin embargo, afirmo que esta caracterización se rompe cuando las medidas y las postselecciones se intercalan. Creo que la confusión proviene de las personas que usan esta "definición de probabilidad condicional" (que funciona en el caso especial del que estoy generalizando) como la definición de postselección, en lugar de la definición de "medición forzada" que acabo de dar, que claramente depende de orden debido a la falta de conmutatividad. ¡Espero que esto ayude!

EDITAR (27/03/11 9 PM): Ya definí la postselección en el formalismo de estado puro. Niel dio un análisis en el formalismo de la matriz de densidad que no está de acuerdo con el mío para el ejemplo de 3 qubits. El culpable es, nuevamente, la definición de postselección. Defina la selección posterior en la configuración de la matriz de densidad de la siguiente manera. Dada una matriz de densidad , reescríbala como una mezcla de estados separables . Dejar ser el resultado de postselección (en algunos qubit), utilizando el formalismo-estado puro I definida anteriormente. Defina el resultado de la postselección en 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$

Esta es una definición más sensata, porque no nos da resultados que digan que después de la selección posterior, alteramos las estadísticas de eventos (mediciones) que ya vimos suceder. Es decir, las 's son probabilidades de monedas que "ya volteamos". No tiene sentido para mí decir que vamos a retroceder en el tiempo y sesgar un lanzamiento de moneda que ya sucedió porque eso haría más probable la actual selección posterior. $p_i$

EDITAR (28/03/11 1 PM): Niel reconoce que con mis definiciones el problema tiene sentido y no es trivial, pero con la estipulación de que no debería llamarlo postselección . Dada la cantidad de confusión, tengo que estar de acuerdo con él. Así que llamemos a lo que definí como selección , que realiza una "medición forzada". Probablemente debería cambiar también el nombre de las clases de complejidad que definí (para no tener "Post" en ellas), así que llamémoslas QMS [k] (quantum-measure-select).

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

¿Puedes definir MPostBQP más formalmente? Si solo quiere decir que esta clase tiene el poder de realizar una selección posterior basada en el resultado de varios bits, entonces esta clase debería estar contenida en PostBQP.

Robin Kothari

La idea clave no es la selección posterior en muchos bits a la vez, porque como Robin señala, esto no ayuda. Es para intercalar medidas y postselecciones. No podemos conmutar estos; El orden importa. Por ejemplo, no funcionaría en PostBQP para medir la respuesta, y luego postselect.

Shaun Harker

Vea el comentario sobre la respuesta de Niel; Podemos diferir tanto las mediciones como las post-selecciones hasta después de la evolución cuántica. Estoy ya de hacer eso! Sin embargo, el mismo argumento no parece reordenar las postselecciones después de las mediciones, porque las mediciones no son unitarias. En particular, digo que las mediciones y las postselecciones son operaciones no unitarias en el estado cuántico que no se conmutan, por lo que puedo decir, no podemos perder sin pérdida todas las postselecciones hasta después de todas las mediciones.

Shaun Harker

@Shaun Harker: el hecho de que las mediciones y las postselecciones no sean unitarias en realidad no nos dan más información sobre si van a viajar. ¿Quizás podrías identificar por qué crees que no viajan?

Niel de Beaudrap

Por enredos. Aquí hay un ejemplo. Prepara el estado

. Elija

. Si primero medimos el primer qubit y luego seleccionamos el tercer qubit y luego medimos el segundo qubit para nuestro resultado, entonces obtenemos

con igual probabilidad. Si primero posteleccionamos en el tercer qubit, luego medimos el primer qubit y finalmente medimos el segundo qubit para nuestro resultado, obtenemos

menos frecuencia de la que obtenemos

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

Respuestas:

Según los comentarios, Shaun tiene en mente algo diferente de lo que normalmente se entiende por selección posterior. Ahora entiendo que esto significa que las estadísticas de cualquier medición realizada antes de una selección posterior en particular no deben ser alteradas por la posterior selección posterior. Esto es similar a tener un operador de proyección donde la normalización se lleva a cabo sobre cada rama de la función de onda correspondiente a un resultado de medición particular, en lugar de sobre la función de onda en su conjunto.

En este caso, los argumentos dados en otras respuestas por mí y Neil ya no son válidos. De hecho, se ve fácilmente que MPostBQP [k], ya que MPostBQP puede verse como una máquina BQP que puede hacer consultas a un oráculo PP, y por lo tanto MPostBQP . $P^{PP[k]}\subseteq$ $[k]$ $k$ $P^{\# P}\subseteq$

Entonces, ahora tenemos un límite inferior no trivial, ¿qué pasa con un límite superior? Bueno, claramente el problema está en PSPACE , pero ¿podemos hacerlo mejor? En realidad, creo que podemos.

Podemos escribir cualquier cálculo en MPostBQP como una secuencia de capas de la forma: cálculo cuántico seguido de una selección posterior, seguida de una medición de un solo qubit. De hecho, esta podría ser una forma alternativa de formular MPostBQP [k], como un cálculo compuesto por tales capas (esto es ligeramente diferente de la definición de Shaun que creo que pretende contar solo el número de post-selecciones), seguido de un capa final de postprocesamiento clásico. Usaré esta definición de MPostBQP [k] a continuación, ya que conduce a un resultado más estéticamente agradable. $k$

Lo siguiente se actualiza desde la versión original para arreglar un agujero en la prueba.

Primero deseamos calcular el resultado de la medición del primer qubit medido (¡no seleccionado posteriormente!). Para hacer esto, primero notamos que cualquier cálculo cuántico puede expresarse usando solo puertas Hadamard y puertas Toffoli, y la amplitud de un estado de base computacional particular en la salida se puede escribir como la suma de a lo sumo términos , donde es el número total de puertas de Hadamard, cada uno de los cuales corresponde a un camino computacional único. Claramente, $\alpha_w$ $|w\rangle$ $2^{H}$ $a_{j,w}$ $H$ $a_{j,w} = \pm 2^{-H/2}$ . La probabilidad de obtener un estado final viene dada por . Deseamos calcular la probabilidad total de medir un 1. Sea el conjunto de estados de base computacional que cumplan con los criterios de post-selección (es decir, el qubit de post-selección es 1) y resulte en 0 para el qubit medido, y dejemos que $|w\rangle$ $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$ $S_0$ $S_1$ sea el conjunto de estados de base computacional que cumplan con los criterios de selección posterior y den como resultado 1 para el qubit medido. Podemos definir y

π_{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}.$

En este caso, la probabilidad de medir un 1 condicionado a un 1 para el qubit post-seleccionado viene dada por . Como podemos determinar esto con 4 llamadas a un oráculo #P. Usamos esto para producir un bit aleatorioque es 1 con probabilidad, lo mismo que la medición cuántica. Porlotanto,MPostBQP[1] está en $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$ $b_1$ $X_1$ $BPP^{\# P[4]}$ .

Luego calculamos el resultado de la medición del segundo qubit. Para hacer esto, ejecutamos las mismas consultas #P que para la primera capa, pero en el circuito obtenido al componer las dos primeras capas, y donde post-seleccionamos en 1 para cada uno de los qubits post-seleccionados, pero también en para el resultado de la medición 1. Tenga en cuenta que aunque esto es una selección posterior en los estados de 3 qubits en lugar de 1, esta es una modificación trivial a las consultas , simplemente agregando un ancilla que se establece solo si los 3 qubits cumplen las condiciones requeridas y post-selección en su lugar en esta ancilla. Esto genera las probabilidades de salida condicionales correctas para el resultado del segundo qubit medido, que denominamos $b_1$ $\# P$ $b_2$ . Tenga en cuenta que ahora hemos utilizado 8 llamadas al oráculo #P .

Repetimos este proceso de manera iterativa, de manera que en una capa que postselect en 1 para todos los precede qubits seleccionado de postes y en para todos la medición anterior, y la etiqueta de los resultados de la correspondiente máquina . En total esto ha requerido consultas de Oracle. $j$ $j$ $b_{i<j}$ $P^{\# P}$ $b_j$ $4j$

Así tenemos MPostBQP [k] , que combinado con el resultado anterior que MPostBQP , implica que MPostBQP [k] , y por lo tanto MPostBQP . $\subseteq P^{\# P[4k]}$ $P^{PP[k]}\subseteq$ $[k]$ $P^{PP[k]} \subseteq$ $\subseteq BPP^{\# P[4k]}$ $= P^{\# P}$

Joe Fitzsimons
fuente

[Revisado.] Revisé mi respuesta en función de sus revisiones a su pregunta, conservé el contenido de mi respuesta original, pero lo hice más breve. Se ha reemplazado la descripción más elaborada del proceso de "simulación", pero supongo que se puede ver al ver el historial de edición de esta publicación.

La mayoría de la gente entenderá "postselección" en el sentido de una probabilidad condicional. De hecho, la versión actual del artículo de Wikipedia sobre PostBQP lo describe de esa manera; y visto como una operación en operadores de densidad (en la que se aplica un mapa de traza no creciente completamente positivo Φ, tal que Φ ² = Φ, y luego renormaliza la traza) uno recupera esta definición.

Dada esta definición de postselección, su definición de un algoritmo MPostBQP [ k ] puede ser simulada por un algoritmo PostBQP , diferiendo las post-selecciones y realizándolas simultáneamente, de manera adecuada. Esto se observa más o menos explícitamente en la página 3 del artículo de Aaronson, Quantum Computing, Postselection y Probabilistic Polynomial-Time, que presenta la clase PostBQP .

Esto se puede mostrar explícitamente señalando que, para una secuencia de bits P ₁ , P ₂ , ... que se postseleccionan ( p . Ej., En el 1estado, lo cual es habitual), no hay diferencia entre condicionar que estén 1en el medio de el cálculo y el condicionamiento de ellos se encuentran 1al final del cálculo, siempre y cuando los valores de estos bits no se modifiquen en el ínterin. Entonces, en lugar de post-seleccionar en cada uno de ellos individualmente1 , podemos calcular su AND lógico antes de la selección posterior y luego seleccionar posteriormente en esa conjunción1. Además, calcular el AND se puede realizar en cualquier punto entre la última transformación del bit y su post-selección. Esto de ninguna manera afectará las estadísticas conjuntas de ninguna de las propiedades del estado.

Por lo tanto, utilizando la definición común de postselección en términos de probabilidades condicionales, tendríamos MPostBQP [ k ] = PostBQP para todo k > 0.

Como he señalado en los comentarios anteriores, no creo que la operación que usted describe en el estado vectores: específicamente, que implican la renormalización de vectores de estado independiente en cada rama de la distribución de probabilidad sobre los resultados de medición- corresponde a la post-selección, ya que muchas personas en el campo (especialmente experimentalistas) describirían el concepto. Incluso puede dar lugar a algunas propiedades 'no físicas', si se extiende a un mapeo en operadores de densidad. Sin embargo, es un medio posible de construir algo como árboles de decisión cuyos nodos están etiquetados por vectores de estado, por lo que, en principio, es un proceso de estudio razonable por derecho propio. Simplemente no llamaría a ese proceso 'postselección'.

[Editar.] En aras de la limpieza, he eliminado el ejemplo calculado. Supongo que se puede ver viendo el historial de edición de esta publicación.

Niel de Beaudrap
fuente

El argumento parece incompleto. El comentario en el artículo de Aaronson señala que no ganamos poder intercalando postselecciones con las evoluciones unitarias, así como no ayuda a intercalar mediciones con evoluciones unitarias. Pero yo tampoco lo estoy haciendo; Estoy intercalando postelección y medición. Para responder a mi pregunta de forma negativa de esta manera, sería necesario probar que siempre podemos ordenar las selecciones posteriores después de las mediciones sin pérdida de potencia. (No es obvio para mí en absoluto). El resto de la respuesta solo explica por qué definí la clase para postseleccionar solo en un bit cada ronda.

Shaun Harker

@Shaun Harker: Independientemente de si el artículo de Aaronson responde a su pregunta, mi respuesta anterior debería. El efecto de la postselección es esencialmente permitir que las mediciones realicen probabilidades condicionales en lugar de probabilidades "no condicionales". La selección posterior en los bits

es esencialmente lo mismo que seleccionar conjunciones de condiciones para probabilidades condicionales. Esas probabilidades condicionales en los bits

no cambian, simplemente difiriendo la evaluación de si la condición se cumple, siempre que los bits

se molesten.

C_{j}

$C_j$

C_{j}

$C_j$

C_{j}

$C_j$

Niel de Beaudrap

Parece que está argumentando que obtenemos las mismas estadísticas si reordenamos las selecciones y mediciones posteriores. Pero si medimos algunos bits antes de una selección posterior, entonces medimos desde una distribución diferente que tendríamos si medimos esos mismos bits después de la selección posterior. Entonces las estadísticas no son las mismas.

Shaun Harker

Con el fin de recopilar estadísticas, una postselección puede implementarse físicamente (aunque de manera ineficiente) simplemente rechazando los ensayos en los que no se cumple la poscondición deseada. El estado de si se cumple una condición posterior ( por ejemplo, "este único bit está en el estado | 1⟩" o "estos cinco bits están todos en el estado | 1⟩") no se ve afectado por el orden de medición, siempre que las operaciones no estén aplicado para cambiar bits que almacenan los resultados. Como el hecho de si un ensayo será rechazado o no es independiente del orden de medición en PostBQP , podemos diferir la selección posterior hasta el final.

Niel de Beaudrap

Esta caracterización de la postselección solo se aplica cuando realizamos la postselección antes de las mediciones. El ejemplo de tres qubits que di ya lo demostró. Si me equivoco al respecto, responda directamente refutando este ejemplo, que proporciona estadísticas diferentes según el orden de las mediciones y las subselecciones.

Shaun Harker

Parecería de su definición de MPostBQP , que esto es simplemente PostBQP en disfraces. En lugar de tratar de convencerlo de que las medidas se pueden reordenar, tal vez le resulte más convincente probar MPostBQP = PP , ya que se sabe que PostBQP = PP (ver quant-ph / 0412187 ). Para probar esto, lo separamos en dos tareas:

$\subseteq$
$\subseteq$

$\subseteq$

Lo siguiente está adaptado del boceto de prueba de 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)$

Tal máquina PP se puede definir de la siguiente manera:

$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
fuente

Este argumento muestra que intercalar múltiples postselecciones con evoluciones unitarias no nos da más que PP. Estoy totalmente de acuerdo. Podemos, sin pérdida de poder, aplazarlos hasta el final y solo necesitamos uno. No veo que este argumento me diga nada más que eso. Pero mi pregunta hace algo diferente; se refiere a la evolución unitaria seguida de rondas de medición y selección (con probabilidades finales calculadas mediante este método de árbol de decisión). Así que no veo que esto aborde mi pregunta.

Shaun Harker

Por no decir que no aprecio (extremadamente) el esfuerzo que pones en tu respuesta. Simplemente no veo que aborde lo que realmente estaba tratando de alcanzar, lo que ciertamente no hice un gran trabajo de explicar.

Shaun Harker

@Shaun: No veo la distinción. ¿Está sugiriendo que agregar medidas cambia el poder? Ciertamente, este no es el caso, ya que las mediciones son siempre equivalentes a la evolución unitaria en un espacio de Hilbert más grande.

Joe Fitzsimons

@Shaun: Mi punto es que matemáticamente la situación con las mediciones y la situación sin (pero con un espacio de Hilbert adecuadamente ampliado) son idénticas. No estoy tratando de hacer ningún tipo de punto filosófico, ni estoy a favor de una interpretación de la mecánica cuántica, simplemente estoy señalando que agregar medidas no hace ninguna diferencia en el poder computacional debido a un resultado bien establecido (matemático).

Joe Fitzsimons

@Shaun: Me parece que está implementando la post-selección incorrectamente. Si lo implementa de la manera normal (es decir, considerando qué estadísticas obtiene si considera solo aquellos resultados que se ajustan a un criterio particular), entonces obtiene PostBQP = MPostBQP, como lo hemos demostrado tanto Niel como yo. También obtiene estadísticas idénticas, independientemente del orden de las mediciones del estado que proporcionó en los comentarios. Es importante destacar que el primer qubit no da 0 y 1 con la misma probabilidad. (continuará)

Joe Fitzsimons