-norma preservación de las máquinas de Turing

Al leer algunos subprocesos recientes sobre computación cuántica ( aquí , aquí y aquí ), me hace recordar una pregunta interesante sobre el poder de algún tipo de máquina de preservación $\ell_p$ -norm.

Para las personas que trabajan en la teoría de la complejidad que van a la complejidad cuántica, un gran texto introductorio es el artículo de Fortnow cuyo enlace fue publicado por Joshua Grochow aquí . En ese artículo, la máquina cuántica de Turing se presenta como una máquina de Turing probabilística generalizada. Básicamente, la máquina probabilístico tiene un estado normalizaron bajo la ℓ 1 -norma, es decir, ∥ s ∥ 1 = 1 . La evolución temporal de la máquina viene dada por la aplicación de una matriz estocástica P tal que ∥ P s ∥ 1 = 1 , es decir, P conserva el$s$$\ell_1$$\parallel s\parallel_1=1$$P$$\parallel Ps\parallel_1=1$$P$ -norm. Entonces, el estado en el tiempo t es P t s (la notación puede no ser precisa porque la multiplicación izquierda o derecha de P depende de si s es un vector de fila o columna o si las filas o columnas de P son los subespacios que preservan la norma). Entonces, en este sentido, la máquina probabilística de Turing es unamáquina de preservación de ℓ 1 -forma denominada M ℓ 1 .$\ell_1$$t$$P^ts$$P$$s$$P$$\ell_1$$M^{\ell_1}$

A continuación, una máquina de Turing cuántica puede ser visto como que tiene un estado con ∥ s ∥ 2 = 1 y unitaria matriz P (que conserva l 2 -norms) tal que P t s es el estado en el tiempo t , donde ∥ P t s ∥ 2 = 1 . Esta es una máquina de preservar ℓ 2 -norm denominada M ℓ 2 .$s$$\parallel s\parallel_2=1$$P$$\ell_2$$P^ts$$t$$\parallel P^ts\parallel_2=1$$\ell_2$$M^{\ell_2}$

Dejar que, en general, un -norma máquina de preservar estar indicados por M ℓ p .$\ell_p$$M^{\ell_p}$

Entonces mis preguntas son:

(1) ¿Cuál es el poder de las máquinas de preservación -norm para p finita ? Más formalmente, podemos demostrar que para cualquier dada p y q , si q > p entonces existe un lenguaje L y la máquina M ℓ q tal que M ℓ q decide de manera eficiente L y no hay máquina M ℓ p que decide de manera eficiente L . Por ejemplo, esto podría ser una generalización de la pregunta, ¿es N P ⊆ B Q P ?$\ell_p$$p$$p$$q$$q>p$$L$$M^{\ell_q}$$M^{\ell_q}$$L$$M^{\ell_p}$$L$$NP \subseteq BQP$

(2) ¿Qué pasa con ? Aquí el valor máximo de los componentes del vector de estado es 1.$p=\infty$

(3) Estas preguntas van más allá de la unitaridad, por lo que no se espera que esté de acuerdo con la mecánica cuántica. En general, ¿qué sucede con la computación si relaja la restricción de unitaridad en las operaciones? Hay trabajos sobre permitir operadores no lineales (ver Aaronson 2005 ).

(4) Quizás lo más importante, ¿es universal? Creo que esto está claro, porque para casos particulares es universal. Pero, ¿qué sucede con la universalidad cuando ?$p=\infty$

Esta no es una respuesta completa a las preguntas, pero es demasiado larga para escribirla como comentario. Expande mi comentario anterior.

La pregunta "¿Qué sucede con la computación si los axiomas de la mecánica cuántica se modifican un poco?" Se aborda con gran detalle en un divertido artículo [Aar04] de Scott Aaronson. Creo que sus preguntas se responden esencialmente en la primera mitad de la Sección 2 de [Aar04].

Aaronson muestra que si p> 0 y p ≠ 2, entonces una matriz que preserva la norma p para todos los vectores es necesariamente una matriz de permutación generalizada (un producto de una matriz de permutación y una matriz diagonal). Afirma que lo mismo ocurre en el caso p = ∞. Todo esto vale tanto para over como para ℂ. Tenga en cuenta que esto incluye el caso de p = 1: las matrices estocásticas conservan la norma 1 para los vectores no negativos, pero no para todos los vectores en general.

Supongo que una máquina de Turing probabilística generalizada como en [For00] tiene una matriz de permutación generalizada como su matriz de transición global solo si es una máquina de Turing determinista, pero no tengo una prueba a mano.

Aaronson discute también varias otras modificaciones de los axiomas de la mecánica cuántica en el documento. Por ejemplo, si cambiamos la regla de medición (en lugar del conjunto de puertas permitidas) para que el resultado x ocurra con probabilidad | α _x |^p / ∑ _y | α _y | ^p , donde α _y es la amplitud de | y⟩, entonces esta "computadora cuántica" puede resolver cualquier problema en PP (incluidos los problemas NP-completos) en tiempo polinómico a menos que p = 2 (Proposición 5).

Referencias

[Aar04] Scott Aaronson. ¿Es la mecánica cuántica una isla en teoryspace? En Actas de la Conferencia de Växjö "Teoría cuántica: reconsideración de fundamentos", 2004. arXiv: quant-ph / 0401062 v2.

[For00] Lance Fortnow. La visión de un teórico de la complejidad de la computación cuántica. In Computing: the Australasian Theory Symposium (CATS 2000), págs. 58–72, enero de 2000. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

Hubo algún artículo de Aaronson en el que se muestra que cuando realidad no hay matrices que preserven la norma. Pero puede considerar matrices que no aumentan la norma ℓ p . Naturalmente, desearía que la regla de Born diera probabilidades | ψ i | p . El problema es que si la norma del vector de estado disminuye, las probabilidades ya no suman uno. Aaronson consideró el caso en el que volvería a normalizar el vector después de cada paso (vea los enlaces en la respuesta de @ Tsuyoshi arriba). Creo que la conclusión fue que estas máquinas tendrían un gran poder.$p \not\in \{1,2\}$$\ell_p$$\left| \psi_i \right|^p$

$\ell_p$$\ell_1$$\ell_2$$\Omega(N^{1/p})$$\ell_\infty$$\ell_p$$\ell_q$$1/p+1/q=1$$\ell_p$$p$