En la teoría de la complejidad computacional , el tiempo polinomial cuántico de error acotado ( BQP ) es la clase de problemas de decisión que puede resolver una computadora cuántica en tiempo polinomial , con una probabilidad de error de como máximo 1/3 para todos los casos. [1] Es el análogo cuántico de la clase de complejidad BPP .
Un problema de decisión es un miembro de BQP si existe un algoritmo cuántico (un algoritmo que se ejecuta en una computadora cuántica) que resuelve el problema de decisión con alta probabilidad y se garantiza que se ejecute en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3.
Algoritmo BQP (1 ejecución) | ||
---|---|---|
Respuesta producido Respuesta correcta | sí | No |
sí | ≥ 2/3 | ≤ 1/3 |
No | ≤ 1/3 | ≥ 2/3 |
Algoritmo BQP ( k ejecuciones) | ||
Respuesta producido Respuesta correcta | sí | No |
sí | > 1-2 - ck | <2 - ck |
No | <2 - ck | > 1-2 - ck |
para alguna constante c > 0 |
Definición
BQP puede verse como los lenguajes asociados con ciertas familias uniformes de circuitos cuánticos de error acotado . [1] Un lenguaje L está en BQP si y solo si existe una familia uniforme de circuitos cuánticos en tiempo polinómico, tal que
- Para todos , Q n toma n qubits como entrada y salidas 1 bit
- Para todo x en L ,
- Para todo x no en L ,
Alternativamente, se puede definir BQP en términos de máquinas cuánticas de Turing . Un lenguaje L está en BQP si y solo si existe una máquina de Turing cuántica polinomial que acepta L con una probabilidad de error de como máximo 1/3 para todas las instancias. [2]
De manera similar a otras clases probabilísticas de "error acotado", la elección de 1/3 en la definición es arbitraria. Podemos ejecutar el algoritmo un número constante de veces y obtener un voto mayoritario para lograr cualquier probabilidad de corrección deseada menor que 1, utilizando el límite de Chernoff . La clase de complejidad no cambia al permitir un error tan alto como 1/2 - n - c por un lado, o al requerir un error tan pequeño como 2 - n c por otro lado, donde c es cualquier constante positiva y n es la longitud de entrada. [3]
Un problema completo de BQP
Similar a la noción de NP-completitud y otros problemas completos , podemos definir un problema BQP-completo como un problema que está en BQP y que cada problema en BQP se reduce a él en tiempo polinomial.
Aquí hay un problema completo intuitivo de BQP, que se deriva directamente de la definición de BQP.
Problema de APPROX-QCIRCUIT-PROB
Dada una descripción de un circuito cuántico actuando qubits con puertas, donde es un polinomio en y cada puerta actúa sobre uno o dos qubits, y dos números , distinguir entre los dos casos siguientes:
- midiendo el primer qubit del estado rendimientos con probabilidad
- midiendo el primer qubit del estado rendimientos con probabilidad
Tenga en cuenta que el problema no especifica el comportamiento si una instancia no está cubierta por estos dos casos.
Afirmar. Cualquier problema de BQP se reduce a APROX-QCIRCUIT-PROB.
Prueba. Supongamos que tenemos un algoritmo que resuelve APPROX-QCIRCUIT-PROB, es decir, dado un circuito cuántico actuando qubits y dos números , distingue entre los dos casos anteriores. Podemos resolver cualquier problema en BQP con este oráculo, configurando.
Para cualquier , existe una familia de circuitos cuánticos tal que para todos , un estado de qubits, si ; si no. Corregir una entrada de qubits, y el circuito cuántico correspondiente . Primero podemos construir un circuito tal que . Esto se puede hacer fácilmente mediante cableadoy aplique una secuencia de puertas CNOT para voltear los qubits. Entonces podemos combinar dos circuitos para obtener, y ahora . Y finalmente, necesariamente los resultados dese obtiene midiendo varios qubits y aplicándoles algunas puertas lógicas (clásicas). Siempre podemos diferir la medición [4] [5] y desviar los circuitos de modo que midiendo el primer qubit de, obtenemos la salida. Este será nuestro circuito, y decidimos la membresía de en mediante la ejecución con . Por definición de BQP, caeremos en el primer caso (aceptación) o en el segundo caso (rechazo), por lo que se reduce a APROX-QCIRCUIT-PROB.
APPROX-QCIRCUIT-PROB es útil cuando intentamos probar las relaciones entre algunas clases de complejidad conocidas y BQP.
Relación con otras clases de complejidad
¿Cuál es la relación entre BQP y NP ?
BQP se define para computadoras cuánticas; la clase de complejidad correspondiente para las computadoras clásicas (o más formalmente para las máquinas probabilísticas de Turing ) es BPP . Al igual que P y BPP , BQP es bajo por sí mismo, lo que significa BQP BQP = BQP . [2] De manera informal, esto es cierto porque los algoritmos de tiempo polinomial están cerrados bajo composición. Si un algoritmo de tiempo polinomial llama como subrutina polinomialmente a muchos algoritmos de tiempo polinomial, el algoritmo resultante sigue siendo tiempo polinomial.
BQP contiene P y BPP y está incluido en AWPP , [6] PP [7] y PSPACE . [2] De hecho, BQP es bajo para PP , lo que significa que una máquina de PP no logra ningún beneficio al poder resolver problemas de BQP instantáneamente, una indicación de la posible diferencia de potencia entre estas clases similares. Las relaciones conocidas con las clases de complejidad clásicas son:
Como el problema de P ≟ PSPACE aún no se ha resuelto, se supone que la prueba de desigualdad entre BQP y las clases mencionadas anteriormente es difícil. [2] No se conoce la relación entre BQP y NP , aunque sí sabemos que NP no está contenido en BQP. En mayo de 2018, los informáticos Ran Raz de la Universidad de Princeton y Avishay Tal de la Universidad de Stanford publicaron un artículo [8] que mostraba que, en relación con un oráculo , el PH no contenía BQP .
Agregar postselección a BQP da como resultado la clase de complejidad PostBQP que es igual a PP . [9] [10]
Probaremos o discutiremos algunos de estos resultados a continuación.
BQP y EXP
Comenzamos con una contención más fácil. Para mostrar que, es suficiente para mostrar que APPROX-QCIRCUIT-PROB está en EXP ya que APPROX-QCIRCUIT-PROB es BQP-completo.
Afirmar.
Prueba. La idea es sencilla. Dado que tenemos potencia exponencial, dado un circuito cuántico, podemos usar una computadora clásica para estimular cada puerta en para obtener el estado final.
Más formalmente, dejemos ser un circuito cuántico de tamaño polinomial en qubits y puertas, donde m es polinomio en n. Dejar y ser el estado después de la -th puerta en el circuito se aplica a . Cada Estado se puede representar en una computadora clásica como un vector unitario en . Además, cada puerta se puede representar mediante una matriz en. Por lo tanto, el estado final se puede calcular en tiempo, y por lo tanto todos juntos, tenemos un algoritmo de tiempo para calcular el estado final y, por lo tanto, la probabilidad de que el primer qubit se mida como uno. Esto implica que.
Tenga en cuenta que este algoritmo también requiere espacio para almacenar los vectores y las matrices. Mostraremos en la siguiente sección que podemos mejorar la complejidad del espacio.
BQP y PSPACE
Probar , primero presentamos una técnica llamada suma de historias.
Suma de historias [11]
La suma de historias es una técnica introducida por el físico Richard Feynman para la formulación integral de Path . Aplicamos esta técnica a la computación cuántica para resolver APPROX-QCIRCUIT-PROB.
Considere un circuito cuántico , que consiste en puertas , donde cada proviene de un conjunto de puertas universal y actúa como máximo en dos qubits. Para comprender cuál es la suma de historias, visualizamos la evolución de un estado cuántico dado un circuito cuántico como un árbol. La raíz es la entrada, y cada nodo del árbol tiene niños, cada uno representando un estado en . El peso en el borde de un árbol de un nodo en-th nivel que representa un estado a un nodo en -th nivel que representa un estado es , la amplitud de después de aplicar en . La amplitud de transición de un camino de raíz a hoja es el producto de todos los pesos en los bordes a lo largo del camino. Para obtener la probabilidad de que el estado final sea, sumamos las amplitudes de todas las rutas de raíz a salida que terminan en un nodo que representa .
Más formalmente, para el circuito cuántico , su árbol de suma sobre historias es un árbol de profundidad , con un nivel para cada puerta además de la raíz, y con factor de ramificación .
Definir. Una historia es un camino en el árbol de suma de historias. Denotaremos una historia por una secuencia para un estado final .
Definir. Dejar. Deje que la amplitud del borde en el -th nivel del árbol de suma sobre historias sea . Por cualquier historia, la amplitud de transición de la historia es el producto .
Afirmar. Por una historia. La amplitud de transición de la historia se puede calcular en tiempo polinomial.
Prueba. Cada puerta se puede descomponer en para algun operador unitario actuando sobre dos qubits, que sin pérdida de generalidad pueden tomarse como los dos primeros. Por eso, que se puede calcular en tiempo polinomial en . Desde es polinomio en , la amplitud de transición del historial se puede calcular en tiempo polinomial.
Afirmar. Dejarser el estado final del circuito cuántico. Para algunos, la amplitud puede ser calculado por .
Prueba. Tenemos. El resultado viene directamente insertando Entre , y , y así sucesivamente, y luego expanda la ecuación. Entonces cada término corresponde a un, dónde
Afirmar.
Observe en el algoritmo de suma sobre historias para calcular alguna amplitud , solo se almacena un historial en cualquier punto del cálculo. Por lo tanto, el algoritmo de suma sobre historias utiliza espacio para calcular para cualquier desde Se necesitan bits para almacenar los historiales además de algunas variables del espacio de trabajo.
Por lo tanto, en el espacio polinomial, podemos calcular general siendo el primer qubit , que es la probabilidad de que el primer qubit se mida como 1 al final del circuito.
Nótese que en comparación con la simulación dada para la prueba de que , nuestro algoritmo aquí ocupa mucho menos espacio pero, en cambio, mucho más tiempo. De hecho se necesita ¡Es hora de calcular una sola amplitud!
BQP y PP
Se puede usar un argumento similar de suma sobre historias para demostrar que . [12]
BQP, P y NP
Primero que nada, sabemos , ya que cada circuito clásico puede ser simulado por un circuito cuántico. [13]
Se conjetura que BQP resuelve problemas difíciles fuera de P, específicamente, problemas en NP. La afirmación es indefinida porque no sabemos si P = NP, por lo que no sabemos si esos problemas están realmente en P. A continuación se muestran algunas pruebas de la conjetura:
- Factorización de enteros (consulte el algoritmo de Shor ) [14]
- Logaritmo discreto [14]
- Simulación de sistemas cuánticos (ver simulador cuántico universal )
- Aproximación del polinomio de Jones en ciertas raíces de la unidad
- Algoritmo de Harrow-Hassidim-Lloyd (HHL)
Sin embargo, también conocemos un análogo de en un sentido de "caja negra". Considere el problema de la búsqueda no estructurada: dado un acceso de Oracle a una función desconocida, encontrar tal que . Este problema está claramente en NP. El algoritmo cuántico óptimo para este problema, por otro lado, es el algoritmo de Grover , que tiene una complejidad de si solo se le permite acceder a través de ese oráculo. [15]
Ver también
- Problema de subgrupo oculto
- Jerarquía polinomial (PH)
- Teoría de la complejidad cuántica
- QMA , el equivalente cuántico de NP .
Referencias
- ↑ a b c Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN 0-521-63503-9 .
- ^ a b c d Bernstein, Ethan; Vazirani, Umesh (octubre de 1997). "Teoría de la complejidad cuántica". Revista SIAM de Computación . 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186 . doi : 10.1137 / S0097539796300921 .
- ^ Barak, Sanjeev Arora, Boaz (2009). Complejidad computacional: un enfoque moderno / Sanjeev Arora y Boaz Barak . Cambridge. pag. 122 . Consultado el 24 de julio de 2018 .
- ^ Michael A. Nielsen; Isaac L. Chuang (9 de diciembre de 2010). "4.4 Medición". Computación cuántica e información cuántica: Edición del décimo aniversario . Prensa de la Universidad de Cambridge. pag. 186. ISBN 978-1-139-49548-6.
- ^ Odel A. Cross (5 de noviembre de 2012). "5.2.2 Medición diferida". Temas en Computación Cuántica . OA Cross. pag. 348. ISBN 978-1-4800-2749-7.
- ^ Fortnow, Lance; Rogers, John (1999). "Limitaciones de complejidad en la computación cuántica" (PDF) . J. Comput. Syst. Sci . 59 (2): 240–252. arXiv : cs / 9811023 . doi : 10.1006 / jcss.1999.1651 . ISSN 0022-0000 . S2CID 42516312 .
- ^ L. Adleman, J. DeMarrais y M.-D. Huang. Computabilidad cuántica. SIAM J. Comput., 26 (5): 1524-1540, 1997.
- ^ George, Michael Goderbauer, Stefan. "ECCC - TR18-107" . eccc.weizmann.ac.il . Consultado el 3 de agosto de 2018 .
- ^ Aaronson, Scott (2005). "Computación cuántica, postselección y polinomio probabilístico-tiempo". Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph / 0412187 . Código bibliográfico : 2005RSPSA.461.3473A . doi : 10.1098 / rspa.2005.1546 . S2CID 1770389 .. Preimpresión disponible en [1]
- ^ Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Weblog de complejidad computacional . Consultado el 2 de mayo de 2008 .
- ^ E. Bernstein y U. Vazirani. Teoría de la complejidad cuántica, SIAM Journal on Computing, 26 (5): 1411-1473, 1997.
- ^ L. Adleman, J. DeMarrais y M. Huang. Computabilidad cuántica, SIAM Journal on Computing 26: 1524-1540, 1997.
- ^ Nielsen, Michael A .; Chuang, Isaac L. (2000), Computación cuántica e información cuántica, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.
- ^ a b arXiv: quant-ph / 9508027v2 Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica , Peter W. Shor
- ^ Zalka, Christof (1 de octubre de 1999). "El algoritmo de búsqueda cuántica de Grover es óptimo" . Physical Review A . 60 (4): 2746–2751. arXiv : quant-ph / 9711070 . doi : 10.1103 / PhysRevA.60.2746 .
enlaces externos
- Enlace de Complexity Zoo a BQP Archivado el 3 de junio de 2013 en la Wayback Machine.