¿Cuál es la clase de complejidad para las subrutinas cuánticas que toman estados cuánticos arbitrarios como entradas?

La clase de complejidad BQP corresponde a subrutinas cuánticas de tiempo polinómico que toman entradas clásicas y escupen una salida clásica probabilística. El asesoramiento cuántico modifica eso para incluir copias de algunos estados de asesoramiento cuántico predeterminados pero con entradas clásicas como de costumbre. ¿Cuál es la clase de complejidad para las subrutinas cuánticas de tiempo polinómico que toman estados cuánticos arbitrarios como entradas, con una sola copia debido a que no hay clonación, y escupiendo estados cuánticos como salida?

Creo que lo que quieres saber son los análogos cuánticos de las clases de problemas de funciones. (Gracias a Peter Shor por señalar esta breve descripción en un comentario).

Un proceso abstracto que toma un estado cuántico de tamaño fijo como entrada y produce un estado cuántico de tamaño fijo cuando la salida se llama canal cuántico . En su situación, no queremos fijar el tamaño de entrada o el tamaño de salida, y por lo tanto, naturalmente consideramos una familia de canales cuánticos como el análogo cuántico de funciones de cadenas clásicas a cadenas clásicas.

Es claramente posible definir la clase de familias de canales cuánticos que pueden implementarse / aproximarse por familias de circuitos cuánticos eficientes (con nociones adecuadas de eficiencia, uniformidad y aproximación). No sé si esta clase tiene algún nombre estándar (pero vea el comentario de Peter Shor para una sugerencia).

En mi especulación, las clases de canales cuánticos a menudo no se estudian porque una de las razones para considerar las clases de complejidad es para comparar los poderes de diferentes modelos computacionales, y las clases de canales cuánticos no se pueden usar para comparar modelos computacionales clásicos y cuánticos. Sin embargo, está perfectamente bien definir y hablar sobre tales clases si se puede demostrar algo interesante sobre ellas.

Algo que podría interesarle es la noción de oráculo cuántico presentada por Aaronson y Kuperberg en arXiv: quant-ph / 0604056 . Citando de su papel:

Así como un oráculo clásico modela una subrutina a la que un algoritmo tiene acceso de caja negra, un oráculo cuántico modela una subrutina cuántica, que puede tomar entrada cuántica y producir salida cuántica.

Esto no responde directamente a su pregunta sobre la definición de una clase de complejidad que representa el modelo que describe. Aún así, la noción de oráculo cuántico tiene relevancia en la teoría de la complejidad: en su artículo, Aaronson y Kuperberg usan un oráculo cuántico para dar una separación entre QMA y QCMA .

Creo que una clase de complejidad para problemas de decisión , tomando los estados cuánticos como entrada es probable que tenga una definición frágil. Para los problemas de promesa, la definición será sensible a las elecciones numéricas, o esencialmente resolverá los problemas clásicos de decisión / promesa codificados en alguna base eficientemente decodificable de estados cuánticos.

$\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$- estados de qubit a estados de un solo qubit. Por supuesto, un circuito cuántico es un canal perfectamente bueno; Si vamos a hablar de realizar canales específicos que están limitados computacionalmente, también podríamos hablar de familias de circuitos cuánticos uniformes (o para el caso, cualquier forma uniforme de implementar un mapa CPTP). Para una buena medida, el circuito debe terminar con una medición de base estándar, si queremos conservar la semántica de decidir algo con probabilidad limitada.

$\mathcal L$$\rho'$$\rho \in \mathcal L$$\rho$$\rho'$$\mathcal L$ . Entonces, me parece que una clase QBQP solo contendría "problemas de promesa cuántica", en los que se promete que la entrada pertenece a una clase de instancias SÍ o de instancias NO que no agotan el espacio de todos los estados posibles. (Una clase de decisión de lenguaje cuántico con error ilimitado , una especie de clase QPQP , puede no estar restringida a una formulación de problema prometedor para ser significativa).

$\mathcal L$$\mathcal L$(1), esa es una probabilidad que está más cerca de la certeza a medida que aumenta el tamaño de entrada, y de manera similar, la probabilidad de rechazo de cualquier estado que la rutina de decisión pueda rechazar también debería converger a cero.

Los problemas de promesa cuántica que un circuito QBQP (para entradas de tamaño n ) podrían distinguir serían:

• $\mathcal H_2^{\otimes n}$ , y cualquier mezcla permitida por la promesa;
• Para NO casos, mezclas de estados puros que son ortogonales a ese subespacio (o al menos, todos los estados ortocomplementarios permitidos por la promesa).

$\mathcal L$$\mathcal L^\bot$ problema de decisión o promesa, codificado en estados cuánticos, con error convergente a cero.

Corrígeme si me equivoco, pero me parece que estás interesado en la clase BQP / qpoly . Definición de Complexity Zoo: "La clase de problemas que puede resolver una máquina BQP que recibe un estado cuántico ψn como consejo, que depende solo de la longitud de entrada n".

Si es así, en el sitio web puede encontrar relaciones de esta clase con otras clases de complejidad. Si no es así, este sitio web también contiene información sobre lo que le sucede a BQP cuando utiliza diferentes tipos de consejos.

También hay un trabajo relativamente reciente sobre la " caracterización del asesoramiento cuántico " en el que puede encontrar la siguiente jerarquía:

No sé cuánto de esta información ya está en Complexity Zoo. Si está interesado en el artículo, los autores también han dado una charla al respecto.

Editar Me pregunto si por "arbitrario" te refieres a un estado generado por un proceso cuántico más general que "evolución unitaria que actúa sobre estados computacionales" como evolución disipativa. En este último caso específico, no tiene más potencia computacional que BQP como se muestra en este artículo .

Aquí hay algunas referencias sobre lenguajes cuánticos, es decir, problemas de decisión con entradas cuánticas. Probablemente hay muchos más.

1. NP cuántico y una jerarquía cuántica -Tomoyuki Yamakami
2. Sobre la complejidad de las lenguas cuánticas -Elham Kashefi, Carolina Moura Alves
3. Una prueba eficiente para estados de productos, con aplicaciones a los juegos cuánticos Merlin-Arthur -Aram Harrow, Ashley Montanaro, DOI: 10.1109 / FOCS.2010.66, Resumen: arxiv.org/abs/1001.0017v3