BQP

Clase de problemas de complejidad computacional

BQP en relación con otras clases de complejidad probabilística ( ZPP , RP , co-RP, BPP , PP ), que generalizan P dentro de PSPACE . Se desconoce si alguna de estas contenciones es estricta.

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 todas las instancias. ^[1] Es el análogo cuántico de la clase de complejidad BPP .

Un problema de decisión es 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 ejecutará en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3.

Definición

BQP puede considerarse 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 de tiempo polinomial , tal que ${\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}$

• Para todos , Q _n toma n qubits como entrada y genera 1 bit ${\displaystyle n\in \mathbb {N} }$
• Para todo x en L , ${\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}$
• Para todo x no en L , ${\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}$

Alternativamente, se puede definir BQP en términos de máquinas de Turing cuánticas . Un lenguaje L está en BQP si y solo si existe una máquina de Turing cuántica polinómica 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 una cantidad constante de veces y tomar una mayoría de votos para lograr cualquier probabilidad deseada de corrección 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 el otro, donde c es cualquier constante positiva y n es la longitud de la entrada. ^[3]

Relación con otras clases de complejidad

Problema sin resolver en informática :

¿Cuál es la relación entre y ? ${\displaystyle {\mathsf {BQP}}}$ ${\displaystyle {\mathsf {NP}}}$

(más problemas sin resolver en informática)

La relación sospechada de BQP con otros espacios problemáticos ^[1]

BQP se define para computadoras cuánticas; la clase de complejidad correspondiente para computadoras clásicas (o más formalmente para máquinas de Turing probabilísticas ) es BPP . Al igual que P y BPP , BQP es bajo para sí mismo, lo que significa que 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 a algoritmos de tiempo polinomial como subrutinas, el algoritmo resultante sigue siendo tiempo polinomial.

BQP contiene P y BPP y está contenido en AWPP , ^[4] PP ^[5] y PSPACE . ^[2] De hecho, BQP es bajo para PP , lo que significa que una máquina PP no obtiene ningún beneficio de poder resolver problemas 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ásica son:

${\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}}$

Como el problema de ⁠ ⁠ ${\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {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] La relación entre BQP y NP no se conoce. En mayo de 2018, los científicos informáticos Ran Raz de la Universidad de Princeton y Avishay Tal de la Universidad de Stanford publicaron un artículo ^[6] que mostraba que, en relación con un oráculo , BQP no estaba contenido en PH . Se puede demostrar que existe un oráculo A tal que . ^[7] En un sentido extremadamente informal, esto se puede pensar como dar a PH y BQP una capacidad idéntica, pero adicional, y verificar que BQP con el oráculo (BQP ^A ) puede hacer cosas que PH ^A no puede. Si bien se ha demostrado una separación de oráculos, no se ha demostrado el hecho de que BQP no esté contenido en PH. Una separación de oráculos no prueba si las clases de complejidad son o no las mismas. La separación de oráculos da la intuición de que BQP puede no estar contenido en PH. ${\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }}$

Durante muchos años se ha sospechado que el muestreo de Fourier es un problema que existe dentro de BQP, pero no dentro de la jerarquía polinómica. Conjeturas recientes han proporcionado evidencia de que un problema similar, la comprobación de Fourier, también existe en la clase BQP sin estar contenido en la jerarquía polinómica . Esta conjetura es especialmente notable porque sugiere que los problemas existentes en BQP podrían clasificarse como más difíciles que los problemas NP-completos . Junto con el hecho de que se sospecha que muchos problemas prácticos de BQP existen fuera de P (se sospecha y no se verifica porque no hay prueba de que P ≠ NP ), esto ilustra el poder potencial de la computación cuántica en relación con la computación clásica. ^[7]

La adición de la postselección a BQP da como resultado la clase de complejidad PostBQP que es igual a PP . ^{[8] [9]}

Un problema completo para Promise-BQP

Promise-BQP es la clase de problemas de promesa que se pueden resolver mediante una familia uniforme de circuitos cuánticos (es decir, dentro de BQP). ^[10] Las pruebas de completitud se centran en esta versión de BQP. De manera similar a la noción de NP-completitud y otros problemas completos , podemos definir un problema completo como un problema que está en Promise-BQP y que todos los demás problemas en Promise-BQP se reducen a él en tiempo polinomial.

PROBLEMA DE CIRCUITO APROX.

El problema APPROX-QCIRCUIT-PROB está completo para un cálculo cuántico eficiente, y la versión que se presenta a continuación está completa para la clase de complejidad Promise-BQP (y no para la clase de complejidad BQP total, para la que no se conocen problemas completos). La completitud de APPROX-QCIRCUIT-PROB lo hace útil para pruebas que muestran las relaciones entre otras clases de complejidad y BQP.

Dada una descripción de un circuito cuántico C que actúa sobre n qubits con m puertas, donde m es un polinomio en n y cada puerta actúa sobre uno o dos qubits, y dos números , distinga entre los dos casos siguientes: ${\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }$

• La medición del primer qubit del estado arroja resultados con probabilidad. ${\displaystyle C|0\rangle ^{\otimes n}}$ ${\displaystyle |1\rangle }$ ${\displaystyle \geq \alpha }$
• La medición del primer qubit del estado arroja resultados con probabilidad. ${\displaystyle C|0\rangle ^{\otimes n}}$ ${\displaystyle |1\rangle }$ ${\displaystyle \leq \beta }$

Aquí, hay una promesa en las entradas ya que el problema no especifica el comportamiento si una instancia no está cubierta por estos dos casos.

Reclamo. Cualquier problema de BQP se reduce a un PROBLEMA DE CIRCUITO APROXIMADO.

Demostración. Supongamos que tenemos un algoritmo A que resuelve APPROX-QCIRCUIT-PROB, es decir, dado un circuito cuántico C que actúa sobre n qubits y dos números , A distingue entre los dos casos anteriores. Podemos resolver cualquier problema en BQP con este oráculo, estableciendo . ${\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }$ ${\displaystyle \alpha =2/3,\beta =1/3}$

Para cualquier , existe una familia de circuitos cuánticos tales que para todo , un estado de qubits, si ; de lo contrario si . Fijemos una entrada de n qubits, y el circuito cuántico correspondiente . Primero podemos construir un circuito tal que . Esto se puede hacer fácilmente cableando y aplicando una secuencia de puertas CNOT para voltear los qubits. Luego podemos combinar dos circuitos para obtener , y ahora . Y finalmente, necesariamente los resultados de se obtienen midiendo varios qubits y aplicándoles algunas puertas lógicas (clásicas). Siempre podemos diferir la medición ^{[11] [12]} y redireccionar los circuitos de modo que midiendo el primer qubit de , obtengamos la salida. Este será nuestro circuito C , y decidimos la membresía de ejecutando 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 APPROX-QCIRCUIT-PROB. ${\displaystyle L\in {\mathsf {BQP}}}$ ${\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle |x\rangle }$ ${\displaystyle n}$ ${\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3}$ ${\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3}$ ${\displaystyle |x\rangle }$ ${\displaystyle Q_{n}}$ ${\displaystyle C_{x}}$ ${\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle }$ ${\displaystyle |x\rangle }$ ${\displaystyle C'=Q_{n}C_{x}}$ ${\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }$ ${\displaystyle Q_{n}}$ ${\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }$ ${\displaystyle x\in L}$ ${\displaystyle A(C)}$ ${\displaystyle \alpha =2/3,\beta =1/3}$ ${\displaystyle L\in {\mathsf {BQP}}}$

BQP y EXP

Empecemos con una contención más sencilla. Para demostrar que , basta con demostrar que APPROX-QCIRCUIT-PROB está en EXP ya que APPROX-QCIRCUIT-PROB es BQP-completo. ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}$

Afirmar  -  ${\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}$

Prueba

La idea es sencilla. Dado que tenemos potencia exponencial, dado un circuito cuántico C , podemos utilizar una computadora clásica para estimular cada compuerta en C y obtener el estado final.

Más formalmente, sea C un circuito cuántico de tamaño polinomial en n qubits y m puertas, donde m es polinomial en n. Sea y el estado después de que se aplica la i -ésima puerta en el circuito a . Cada estado se puede representar en una computadora clásica como un vector unitario en . Además, cada puerta se puede representar por una matriz en . Por lo tanto, el estado final se puede calcular en el tiempo y, por lo tanto, en conjunto, tenemos un algoritmo de tiempo para calcular el estado final y, por lo tanto, la probabilidad de que se mida que el primer qubit sea uno. Esto implica que . ${\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}}$ ${\displaystyle |\psi _{i}\rangle }$ ${\displaystyle |\psi _{i-1}\rangle }$ ${\displaystyle |\psi _{i}\rangle }$ ${\displaystyle \mathbb {C} ^{2^{n}}}$ ${\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}$ ${\displaystyle |\psi _{m}\rangle }$ ${\displaystyle O(m\cdot 2^{2n})}$ ${\displaystyle 2^{O(n)}}$ ${\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}$

Tenga en cuenta que este algoritmo también requiere espacio para almacenar los vectores y las matrices. En la siguiente sección, demostraremos que podemos mejorar la complejidad del espacio. ${\displaystyle 2^{O(n)}}$

BQP y PSPACE

La suma de historias es una técnica introducida por el físico Richard Feynman para la formulación de la integral de trayectorias . APPROX-QCIRCUIT-PROB se puede formular con la técnica de suma de historias para demostrar que . ^[13] ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}$

Árbol de suma de historias

Consideremos un circuito cuántico C , que consta de t puertas, , donde cada una proviene de un conjunto de puertas universales y actúa sobre, como máximo, dos qubits. Para entender 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 hijos, cada uno de los cuales representa un estado en . El peso en una arista del árbol desde un nodo en el j -ésimo nivel que representa un estado hasta un nodo en el -ésimo 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 las aristas a lo largo del camino. Para obtener la probabilidad de que el estado final sea , sumamos las amplitudes de todos los caminos de raíz a hoja que terminan en un nodo que representa . ${\displaystyle g_{1},g_{2},\cdots ,g_{m}}$ ${\displaystyle g_{j}}$ ${\displaystyle |0\rangle ^{\otimes n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle \mathbb {C} ^{n}}$ ${\displaystyle |x\rangle }$ ${\displaystyle j+1}$ ${\displaystyle |y\rangle }$ ${\displaystyle \langle y|g_{j+1}|x\rangle }$ ${\displaystyle |y\rangle }$ ${\displaystyle g_{j+1}}$ ${\displaystyle |x\rangle }$ ${\displaystyle |\psi \rangle }$ ${\displaystyle |\psi \rangle }$

Más formalmente, para el circuito cuántico C , su árbol de suma de historias es un árbol de profundidad m , con un nivel para cada puerta además de la raíz, y con factor de ramificación . ${\displaystyle g_{i}}$ ${\displaystyle 2^{n}}$

Definición  :  un historial es una ruta en el árbol de suma de historiales. Denotaremos un historial como una secuencia para un estado final x . ${\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)}$

Definir  :  Sea . Sea la amplitud de la arista en el j -ésimo nivel del árbol de suma de historias . Para cualquier historia , la amplitud de transición de la historia es el producto de . ${\displaystyle u,v\in \{0,1\}^{n}}$ ${\displaystyle (|u\rangle ,|v\rangle )}$ ${\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle }$ ${\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})}$ ${\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)}$

Reclamación  —  Para una historia . La amplitud de transición de la historia se puede calcular en tiempo polinomial. ${\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})}$

Prueba

Cada puerta se puede descomponer en algún operador unitario que actúe sobre dos cúbits, que sin pérdida de generalidad se pueden tomar como los dos primeros. Por lo tanto, que se puede calcular en tiempo polinómico en n . Como m es polinómico en n , la amplitud de transición de la historia se puede calcular en tiempo polinómico. ${\displaystyle g_{j}}$ ${\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}}$ ${\displaystyle {\tilde {g}}_{j}}$ ${\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle }$

Afirmación  :  Sea el estado final del circuito cuántico. Para algunos , la amplitud se puede calcular mediante . ${\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle }$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle \alpha _{x}}$ ${\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}}$

Prueba

Tenemos . El resultado viene directamente al insertar entre , y , y así sucesivamente, y luego expandir la ecuación. Entonces cada término corresponde a un , donde ${\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}}$ ${\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|}$ ${\displaystyle g_{1},g_{2}}$ ${\displaystyle g_{2},g_{3}}$ ${\displaystyle \alpha _{h}}$ ${\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}$

Afirmar  -  ${\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}}$

Observe que en el algoritmo de suma de historiales para calcular cierta amplitud , solo se almacena un historial en cualquier punto del cálculo. Por lo tanto, el algoritmo de suma de historiales utiliza espacio para calcular cualquier x, ya que se necesitan bits para almacenar los historiales además de algunas variables del espacio de trabajo. ${\displaystyle \alpha _{x}}$ ${\displaystyle O(nm)}$ ${\displaystyle \alpha _{x}}$ ${\displaystyle O(nm)}$

Por lo tanto, en el espacio polinomial, podemos calcular sobre todo x con el primer qubit siendo ${\displaystyle \sum _{x}|\alpha _{x}|^{2}}$1 , que es la probabilidad de que el primer qubit medido sea 1 al final del circuito.

Observe que, en comparación con la simulación dada para la prueba de que , nuestro algoritmo aquí ocupa mucho menos espacio pero mucho más tiempo. ¡De hecho, lleva tiempo calcular una sola amplitud! ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}$ ${\displaystyle O(m\cdot 2^{mn})}$

BQP y PP

Se puede utilizar un argumento similar de suma sobre historias para demostrar que . ^[14] ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}$

P y BQP

Lo sabemos porque todo circuito clásico puede ser simulado por un circuito cuántico. ^[15] ${\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}}$

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 presentan algunas pruebas de la conjetura:

• Factorización de enteros (ver algoritmo de Shor ) ^[16]
• Logaritmo discreto ^[16]
• 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 Harrow-Hassidim-Lloyd (HHL)

Véase también

• Problema del subgrupo oculto
• Jerarquía polinómica (PH)
• Teoría de la complejidad cuántica
• QMA , el equivalente cuántico de NP .
• QIP , el equivalente cuántico de IP.

Referencias

1. Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN  0-521-63503-9 .
2. Bernstein, Ethan; Vazirani, Umesh (octubre de 1997). "Teoría de la complejidad cuántica". Revista SIAM de informática . 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186 . doi :10.1137/S0097539796300921. 
3. Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora y Boaz Barak. Cambridge. p. 122. Consultado el 24 de julio de 2018 .{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: multiple names: authors list (link)
4. Fortnow, Lance; Rogers, John (1999). "Limitaciones de complejidad en 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. Archivado (PDF) desde el original el 2022-10-09.
5. L. Adleman, J. DeMarrais y M.-D. Huang. Computabilidad cuántica. SIAM J. Comput., 26(5):1524–1540, 1997.
6. George, Michael Goderbauer, Stefan. "ECCC - TR18-107". eccc.weizmann.ac.il . Consultado el 3 de agosto de 2018 .{{cite web}}: CS1 maint: multiple names: authors list (link)
7. Aaronson, Scott (2010). "BQP y la jerarquía polinomial" (PDF) . Actas de ACM STOC 2010. Archivado (PDF) desde el original el 2022-10-09.
8. Aaronson, Scott (2005). "Computación cuántica, postselección y tiempo polinomial probabilístico". Actas de la 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]
9. Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP". Weblog sobre complejidad computacional . Consultado el 2 de mayo de 2008 .
10. Janzing, Dominik; Wocjan, Pawel (30 de marzo de 2007). "Un problema de matriz simple PromiseBQP-completo" (PDF) . Theory of Computing . 3 (4): 61–79. doi :10.4086/toc.2007.v003a004 . Consultado el 18 de abril de 2024 .
11. 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. Cambridge University Press. pág. 186. ISBN 978-1-139-49548-6.
12. Odel A. Cross (5 de noviembre de 2012). "5.2.2 Medición diferida". Temas de computación cuántica. OA Cross. pág. 348. ISBN 978-1-4800-2749-7.
13. E. Bernstein y U. Vazirani. Teoría de la complejidad cuántica, SIAM Journal on Computing, 26(5):1411-1473, 1997.
14. L. Adleman, J. DeMarrais y M. Huang. Computabilidad cuántica, SIAM Journal on Computing 26:1524-1540, 1997.
15. 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.
16. arXiv:quant-ph/9508027v2 Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica, Peter W. Shor

Enlaces externos

• Enlace de Complexity Zoo a BQP Archivado el 3 de junio de 2013 en Wayback Machine.