Una noción de circuitos cuánticos monótonos

En la complejidad computacional, existe una distinción importante entre los cálculos monótonos y generales, y un famoso teorema de Razborov afirma que 3-SAT e incluso MATCHING no son polinomiales en el modelo de circuitos booleanos monótonos.

Mi pregunta es simple: ¿hay un análogo cuántico para circuitos monótonos (o más de uno)? ¿Existe un teorema cuántico de Razborov?

Realmente haces dos preguntas diferentes y esperas que haya una respuesta única que responda a ambas: (1) ¿Qué nociones naturales de circuitos cuánticos monótonos existen? (2) ¿Cómo sería un resultado cuántico de estilo Razborov basado en celosía?

No es obvio cómo lograr ambas cosas al mismo tiempo, por lo que describiré lo que me parece una noción razonable de circuitos monotónicos cuánticos (sin indicar si existe o no un resultado Razborov correspondiente), y una noción completamente diferente de cómo se vería una conjetura cuántica "natural" de Razborov (sin indicar si es probable que sea cierta).

Lo que queremos del cuanto

Como comento en los comentarios, creo que no es necesario tratar de exprimir la noción de circuitos monotónicos en un molde de unitaridad. Ya sea en el hecho de que la evolución con el tiempo no necesita preservar la base estándar, o en el hecho de que existen múltiples bases de medición en las que los resultados pueden estar enredados, creo que la condición sine qua non de la computación cuántica es el hecho de que La base estándar no es la única base. Incluso entre los estados del producto, en algunas implementaciones se define solo por una elección del marco de referencia.

Lo que debemos hacer es considerar las cosas de tal manera que se elimine la base estándar de su lugar privilegiado tradicional, o, en este caso, tanto como sea posible mientras se conserva una noción significativa de monotonicidad.

Un modelo simple de circuitos monótonos cuánticos.

Considere un modelo de circuito que está implícito en el comentario de Tsuyoshi Ito sobre "canales cuánticos monótonos" (y que es más o menos lo que uno debe hacer si quiere una noción de "un circuito" que no esté restringido a la evolución unitaria).

Sea el espacio de los operadores hermitianos en C 2 (para que contenga todos los operadores de densidad en un qubit). ¿Cómo definiríamos una puerta monótona cuántica G : H$\mathbf H$$\mathbb C^2$ de dos qubits de entrada a , b a un qubit de salida c , de tal manera que no sea efectivamente una puerta monótona clásica? Creo que es sencillo decir que la salida no debe limitarse a | 0 $\mathsf G: \mathbf H_a \otimes \mathbf H_b \to \mathbf H_c$$a,b$$c$o | 1 $|0\rangle\!\langle 0|$, o mezclas de ellos; bu que para ser "monótona", se debe exigir que como ⟨ 1 $|1\rangle\!\langle 1|$y ⟨1$\langle 1 | \,\mathop{\mathrm{Tr}_a}\bigl(\rho_{ab}\bigr) |1\rangle$aumento, el valor de⟨$\langle 1 | \,\mathop{\mathrm{Tr}_b}\bigl(\rho_{ab}\bigr) |1\rangle$ deben ser no decreciente. Para una puerta de qubit de dos entradas, esto significa que G debe ser implementable en principio como$\langle 1 | \mathsf G(\rho_{ab}) | 1 \rangle$$\mathsf G$

1. realizar una medición de dos qubits con respecto a alguna base ortonormal , donde | mu ⟩ , | ν ⟩ abarcar el subespacio de peso Hamming 1, y$\{ |00\rangle, |\mu\rangle, |\nu\rangle, |11\rangle \}$$|\mu\rangle,|\nu\rangle$

2. produciendo como salida un estado correspondiente al resultado se mide, donde ⟨ 1 | ρ 00 | 1 ⟩ ⩽ ⟨ 1 | ρ λ | 1 ⟩ ⩽ ⟨ 1 $\rho \in \{ \rho_{00}, \rho_\mu, \rho_\nu, \rho_{11} \}$ para cada lambda ∈ { μ , ν } .$\langle 1 | \rho_{00} | 1 \rangle \leqslant \langle 1 | \rho_\lambda | 1 \rangle \leqslant \langle 1 | \rho_{11} | 1 \rangle$$\lambda \in \{ \mu, \nu \}$

Los circuitos son solo composiciones de estos de manera sensata. También podríamos permitir el despliegue, en forma de circuitos que incrustan unitariamente y | 1 ⟩ ↦ | 11 ⋯ 1 ⟩ ; al menos deberíamos permitir estos mapas en la entrada, para permitir que se copie cada bit de entrada (nominalmente clásico).$|0\rangle \mapsto |00\cdots 0\rangle$$|1\rangle \mapsto |11\cdots 1\rangle$

Parece razonable considerar todo el continuo de tales puertas, o restringir a alguna colección finita de tales puertas. Cualquier elección da lugar a una "base de puerta monótona cuántica" diferente para los circuitos; Uno puede considerar qué propiedades tienen las diferentes bases monótonas. Los estados se pueden elegir de forma completamente independiente, sujeto a la restricción de monotonicidad; indudablemente sería interesante (y probablemente práctico para vincular el error) establecer ρ 00 = | 0 $\rho_{00}, \rho_\mu, \rho_\nu, \rho_{11}$y ρ 11 = | 1 $\rho_{00} = |0\rangle\!\langle 0|$, aunque no veo ninguna razón para exigir esto en la teoría. Obviamente, AND y OR son puertas de este tipo, donde ρ μ = ρ ν = | 0 $\rho_{11} = |1\rangle\!\langle 1|$y ρ μ = ρ ν = | 1 $\rho_\mu = \rho_\nu = |0\rangle\!\langle 0|$respectivamente, lo que uno elija | mu ⟩ o | nu ⟩ ser.$\rho_\mu = \rho_\nu = |1\rangle\!\langle 1|$$|\mu\rangle$$|\nu\rangle$

Para cualquier k constante , también se pueden considerar bases de compuerta, incluidas las compuertas k -input-one-output. El enfoque más simple en este caso probablemente sería permitir las puertas que pueden implementarse como anteriormente, permitiendo cualquier descomposición de los subespacios V w ⩽ H ⊗ k 2 de cada peso de Hamming 0 $\mathsf G: \mathbf H^{\otimes k} \to \mathbf H$$\mathcal V_w \leqslant \mathcal H_2^{\otimes k}$ , y exigir que max | Psi ⟩ ∈ V$0 \leqslant w \leqslant k$ para cada 0 ⩽ w < k . No está claro cuánta potencia computacional adicional le daría esto (ni siquiera en el caso clásico).

$$\max_{|\psi\rangle \in \mathcal V_w}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle \;\;\leqslant\;\; \min_{|\psi\rangle \in \mathcal V_{w+1}}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle$$ $0 \leqslant w < k$

No sé si hay algo interesante que decir sobre tales circuitos más allá del caso clásico, pero esta me parece la definición candidata más prometedora de un "circuito monótono cuántico".

Una variante cuántica del resultado de Razborov

Considere la exposición de Tim Gowers de los resultados de Alon y Boppana (1987), Combinatorica 7 pp. 1–22 que fortalecen los resultados de Razborov (y hace explícitas algunas de sus técnicas) para la complejidad monótona de CLIQUE. Gowers presenta esto en términos de una construcción recursiva de una familia de conjuntos, mirando desde los "medios espacios" del cubo booleano para cada 1 ⩽ j ⩽ n . Si eliminamos la posición privilegiada de la base estándar en los conjuntos de bases, en analogía con elLema Local de Quantum Lovász, podemos considerar un subespacio de H ⊗ n 2 que corresponde a una proposición binaria (ya sea que un estado pertenezca al subespacio, o es, en cambio, ortogonal) que podría surgir de la medición Por ejemplo, podemos considerar n subespacios A j ⩽ H ⊗ n 2 dado por

$$E_j = \Bigl\{ \mathbf x \in \{0,1\}^n \;:\; x_j = 1 \Bigr\}$$ $1 \leqslant j \leqslant n$$\mathcal H_2^{\otimes n}$$n$$\mathcal A_j \leqslant \mathcal H_2^{\otimes n}$ Permitimos losanálogos delógica cuánticade conjunción y disyunción de subespacios: A ∧ B = A ∩ B ; A ∨ B = A + B = { a + $$\begin{align*} \mathcal A_j = U_j \mathcal E_j \;, & \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where } &\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\ &U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}. \end{align*}$$ Luego preguntamos por cuánto tiempo se requiere una construcción recursiva de conjunciones y disyunciones de espacios para obtener un espacioC, de modo que el proyectorΠCenCdifiera solo ligeramente del proyectorΠK(r)en el espacio abarcado por las funciones indicadoras de gráficos que tienen camarillas de tamañor; por ejemplo, para que‖ΠC-ΠK( $$\begin{gather*} \mathcal A \wedge \mathcal B = \mathcal A \cap \mathcal B ; \\ \mathcal A \vee \mathcal B = \mathcal A + \mathcal B = \Bigl\{ \mathbf a + \mathbf b \,:\, \mathbf a \in \mathcal A\;,\; \mathbf b \in \mathcal B \Bigr\} . \end{gather*}$$ $C$$\Pi_C$$C$$\Pi_{K(r)}$$r$ . La parte monotónica está involucrada en las operaciones lógicas cuánticas, y las proposiciones primitivas sobre la entrada también son cuánticas.$\| \Pi_C - \Pi_{K(r)} \|_\infty <\; 1/\mathrm{poly}(n)$

En el caso general, existe un problema al tratar esto como un problema computacional: la disyunción no corresponde a ningún conocimiento que pueda obtenerse con certeza mediante mediciones en un número finito de copias utilizando mediciones de recuadro negro para y B solo , a menos que sean imágenes de proyectores de conmutación. Este problema general aún puede tratarse como un resultado interesante sobre la complejidad geometrico-combinatoria, y puede dar lugar a resultados relacionados con los frustrados locales de Amistad. Sin embargo, podría ser más natural simplemente requerir que los subespacios $\mathcal A$$\mathcal B$ surjan de proyectores de conmutación, en cuyo caso la disyunción es solo el OR clásico de los resultados de medición de esos proyectores. Entonces podemos exigir que los unitarios$\mathcal A_j$ todo sea la misma, y esto se convierte en un problema sobre un circuito unitario (que da lugar a los "eventos primitivos") con monótona clásica post-procesamiento (que realiza las operaciones lógicas en esos eventos).$U_j$

Tenga en cuenta también que si no imponemos más restricciones en los espacios , puede ser un subespacio con una superposición muy alta con algún espacio E ⊥ k abarcado por los estados básicos estándar x ∈ ˉ E k , que son aquellas cadenas binarias en las que x k = $\mathcal A_j$$\mathcal E_k^\bot$$\mathbf x \in \bar E_k$$x_k = 0$ .

• Si esta posibilidad te hace aprensivo, siempre puedes requerir que tenga un ángulo de separación de cualquier E ⊥ k de al menos $\mathcal A_j$$\mathcal E_k^\bot$(de modo que nuestros subespacios primitivos son, en el peor de los casos, aproximadamente insesgados de los subespacios en los que uno de los bits se establece en 1).$\frac{\pi}{2} - 1/\mathrm{poly}(n)$

• Si no imponemos tal restricción, me parece que admitir subespacios con alta superposición con sería un obstáculo para aproximarse a CLIQUE (r) de todos modos; o estaríamos más o menos restringidos a considerar la ausencia de un borde particular (en lugar de su presencia), o nos veríamos obligados a ignorar uno de los bordes por completo. Por lo tanto, no creo que sea tan importante imponer restricciones a A$\mathcal E_k^\bot$$\mathcal A_j$ , excepto posiblemente que todas son imágenes de un conjunto de proyectores de conmutación, si el objetivo de uno es considerar cómo "evaluar monótonamente CLIQUE a partir de proposiciones cuánticas simples" . En el peor de los casos, equivaldría clásicamente a permitir NO puertas en la entrada (y hacer que todo el despliegue ocurra después de la negación).

Nuevamente, no me queda claro si la sustitución de los conjuntos base con subespacios arbitrarios de da lugar a un problema más interesante que el simple uso de los subespacios E j ; aunque si nos limitamos al caso de las fórmulas CNF (ya sea en el caso de los desplazamientos o no), los resultados que obtenemos corresponderían a alguna noción de complejidad de un hamiltoniano libre de frustración cuya variedad de estado fundamental consistía en una base estándar estados que representan camarillas.$\mathcal H_2^{\otimes n}$$\mathcal E_j$

Como lo demuestran los comentarios de Robin y Tsuyoshi, la noción de circuitos monótonos parece ser fácilmente extensible a los circuitos cuánticos.

Para tener una definición significativa del circuito monótono cuántico, necesitamos elegir un orden en los estados cuánticos con respecto a los cuales se define la monotonicidad. Clásicamente, una opción razonable (y una que conduce a la noción normal de circuitos monotónicos), es el peso de Hamming, pero consideremos un orden dado por una función arbitraria $f$ .

Dado que la evolución de un sistema cuántico cerrado es unitaria (que podemos suponer que viene dada por ), entonces para cada estado | Psi ⟩ que tal f ( U | Psi ⟩ ) > f ( | Psi ⟩ ) existe un estado alternativo | phi ⟩ tal que f ( | phi ⟩ ) > f ( | Psi ⟩ ) , pero para los que f ( T | Psi ⟩ f $U$$|\psi\rangle$$f(U|\psi\rangle)>f(|\psi\rangle)$$|\phi\rangle$$f(|\phi\rangle) > f(|\psi\rangle)$ , y por lo tanto la evolución T no es monótona.$f(U|\psi\rangle)>f(U|\phi\rangle)$$U$

Por lo tanto los únicos circuitos que son monotónica con respecto a son los que f ( U | Psi ⟩ ) = f ( | Psi ⟩ ) para todos | Psi ⟩ . Por lo tanto, cualquier conjunto de compuerta que sea monótono con respecto a f está compuesto por compuertas que conmutan con f .$f$$f(U|\psi\rangle)=f(|\psi\rangle)$$|\psi\rangle$$f$$f$

Obviamente, los conjuntos de puertas que pueden satisfacer esto dependen de la definición de . Si f es constante, entonces todos los conjuntos de puertas son monótonos con respecto a él. Sin embargo, si elegimos f como el peso de los estados de Hamming en la base computacional (una extensión algo natural de la $f$$f$$f$$f$ utilizada en el caso clásico), obtenemos una estructura interesante. La restricción impuesta requiere que el peso de Hamming permanezca sin cambios. Las operaciones que preservan esta cantidad son operaciones diagonales o SWAP parciales, o combinaciones de estos. Esta estructura aparece con bastante frecuencia en física (en modelos de encuadernación apretada, etc.), y es similar al problema de dispersión de Boson estudiado por Aaronson y Arkhipov, aunque no idéntico (es un problema de dispersión ligeramente diferente). Además, contiene circuitos para IQP , y por lo tanto no debería ser eficientemente simulable de manera clásica.

básicamente hace dos preguntas de dificultad muy divergente, en la frontera de dos grandes campos, es decir, circuitos booleanos y computación QM, sobre la posibilidad de lo que a veces se llama un "teorema de puente" en matemáticas:

• análogo cuántico de circuitos monótonos

• análogo cuántico de Razborovs thm

la respuesta sincera corta es no o no hasta ahora .

para (1), una pregunta no tan difícil, pero aparentemente raramente considerada, apareció la siguiente referencia que podría tomarse como un caso relacionado en la literatura.

Dureza de aproximación para problemas cuánticos por Gharibian y Kempe

consideran algunos problemas "monótonos" en un contexto cuántico, por ejemplo, QMSA, "Asignación mínima satisfactoria de monótono cuántico, QMSA", es decir, un análogo SAT QM; (también otro problema Palabra de peso mínimo monótono cuántico, QMW) y muestra algunos resultados de dureza de aproximación, es decir, límites inferiores. no consideran los circuitos cuánticos monótonos per se, pero una idea podría ser que un circuito cuántico o algoritmo que resuelva la función monótona QMSA pueda tomarse como un análogo QM.

en cuanto a (2) sería un resultado muy avanzado si existiera, lo que no parece "hasta ahora". El THM de Razborov es básicamente un resultado de tipo "cuello de botella" de límite inferior considerado un avance distintivo y un resultado casi inigualable en la teoría de circuitos (monótono).

en términos generales, sí, por supuesto, se encuentran algunos cuellos de botella en el cómputo QM, por ejemplo, relacionados con los teoremas del producto directo, para una encuesta, ver por ejemplo

Algoritmos cuánticos, límites inferiores y compensaciones espacio-temporales de Spalek

sin embargo, podría decirse que un mejor límite inferior de computación QM análoga pondría un límite inferior en el número de operaciones qubit o posiblemente basado en puertas "completas" como las puertas Toffoli para una función monótona. No conozco pruebas de este tipo.

otro enfoque podría limitar el análisis a puertas cuánticas especiales AND y OR con bits adicionales "ancilla" añadidos para hacer que las puertas sean reversibles.