BQP

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 pertenece a BQP si existe un algoritmo cuántico (un algoritmo que se ejecuta en una computadora cuántica) que lo resuelve con alta probabilidad y cuya ejecución en tiempo polinomial está garantizada. 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 errores acotados de circuitos cuánticos . ^{[ 1 ]} Un lenguaje L está en BQP si y solo si existe una familia uniforme de tiempo polinomial de circuitos cuánticos. $\{Q_{n}\colon n\in \mathbb {N} \}$ , de tal manera que

A pesar de $n\in \mathbb {N}$ , Q _n toma n cúbits como entrada y produce 1 bit como salida
Para todo x en L , $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
Para todo x que no está en L , $\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 pertenece a 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 forma 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 tomar una votación mayoritaria para lograr cualquier probabilidad de corrección deseada menor que 1, utilizando la cota de Chernoff . La clase de complejidad no cambia al permitir un error tan alto como 1/2 − n ^{− c} , por un lado, o requerir un error tan pequeño como 2 ^{− n ^c} , por 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?

{\mathsf {BQP}}

y

{\mathsf {NP}}

¿

Más problemas sin resolver en informática

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 baja para sí misma, lo que significa que $BQP BQP = BQP$ . ^{[ 2 ]} De manera informal, esto es cierto porque los algoritmos de tiempo polinomial son cerrados bajo composición. Si un algoritmo de tiempo polinomial llama a algoritmos de tiempo polinomial como subrutinas, el algoritmo resultante sigue siendo de 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 al 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ásicas son:

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

Como el problema de ${\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 ]} Se desconocela relación entre BQP y NP . 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 demostró 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 ${\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }$ [ ⁷^] En un sentido extremadamente informal, esto puede entenderse como otorgar 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 que BQP no esté contenido en PH. Una separación de oráculos no prueba si las clases de complejidad son iguales o no. La separación de oráculos da una idea intuitiva de que BQP puede no estar contenido en PH.

Desde hace años se sospecha 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 aportado pruebas de que un problema similar, la verificació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 que existen 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, pero no se verifica porque no hay prueba de que P ≠ NP ), esto ilustra el potencial de la computación cuántica en relación con la computación clásica. ^{[ 7 ]}

Agregar 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 pueden resolverse 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 forma similar a la noción de NP-completitud y otros problemas completos , podemos definir un problema completo como un problema que pertenece a Promise-BQP y que cualquier otro problema en Promise-BQP se reduce a él en tiempo polinomial.

PROBLEMA DE CIRCUITO APROXIMADO

El problema APPROX-QCIRCUIT-PROB es completo para la computación cuántica eficiente, y la versión que se presenta a continuación es completa para la clase de complejidad Promise-BQP (pero no para la clase de complejidad BQP total, para la cual no se conocen problemas completos). La completitud de APPROX-QCIRCUIT-PROB lo hace útil para demostraciones 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$ cúbits con $m$ compuertas, donde $m$ es un polinomio en $n$ y cada compuerta actúa sobre uno o dos cúbits, y dos números $\alpha ,\beta \in [0,1],\alpha >\beta$ , distinguir entre los dos casos siguientes:

midiendo el primer cúbit del estado $C|0\rangle ^{\otimes n}$ rendimientos $|1\rangle$ con probabilidad $\geq \alpha$
midiendo el primer cúbit del estado $C|0\rangle ^{\otimes n}$ rendimientos $|1\rangle$ con probabilidad $\leq \beta$

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

Afirmación. Cualquier problema BQP se reduce a PROBLEMA-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$ cúbits y dos números $\alpha ,\beta \in [0,1],\alpha >\beta$ , $A$ distingue entre los dos casos anteriores. Podemos resolver cualquier problema en BQP con este oráculo, estableciendo $\alpha =2/3,\beta =1/3$ .

Para cualquier $L\in {\mathsf {BQP}}$ Existe una familia de circuitos cuánticos. $\{Q_{n}\colon n\in \mathbb {N} \}$ de tal manera que para todos $n\in \mathbb {N}$ , un estado $|x\rangle$ de $n$ cúbits, si $x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3$ ; de lo contrario, si $x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3$ . Corregir una entrada $|x\rangle$ de $n$ cúbits y el circuito cuántico correspondiente $Q_{n}$ Primero podemos construir un circuito. $C_{x}$ de tal manera que $C_{x}|0\rangle ^{\otimes n}=|x\rangle$ Esto se puede hacer fácilmente mediante cableado. $|x\rangle$ y aplicar una secuencia de compuertas CNOT para invertir los cúbits. Luego podemos combinar dos circuitos para obtener $C'=Q_{n}C_{x}$ y ahora $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ . Y finalmente, necesariamente los resultados de $Q_{n}$ se obtiene midiendo varios cúbits y aplicándoles algunas compuertas lógicas (clásicas). Siempre podemos aplazar la medición ^{[ 11 ]}^{[ 12 ]} y redirigir los circuitos de modo que al medir el primer cúbit de $C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle$ , obtenemos la salida. Este será nuestro circuito $C$ , y decidimos la pertenencia a $x\in L$ corriendo $A(C)$ con $\alpha =2/3,\beta =1/3$ Por definición de BQP, caeremos en el primer caso (aceptación) o en el segundo caso (rechazo), por lo que $L\in {\mathsf {BQP}}$ se reduce a PROBABILIDAD-DE-CIRCUITO-APROXIMADA.

BQP y EXP

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

Afirmar - ${\text{PROBLEMA-DE-CIRCUITO-APROXIMADO}}\in {\mathsf {EXP}}$

Prueba

La idea es simple. Dado que tenemos potencia exponencial, con un circuito cuántico $C$ , podemos usar una computadora clásica para estimular cada puerta en $C$ y obtener el estado final.

De forma más formal, sea $C$ un circuito cuántico de tamaño polinomial con $n$ cúbits y $m$ compuertas, donde m es polinomial en n. $|\psi _ {0}\rangle =|0\rangle ^{\otimes n}$ y $|\psi _{i}\rangle$ sea el estado después de que se aplique la $i -ésima puerta en el circuito$ $|\psi _{i-1}\rangle$ Cada estado $|\psi _{i}\rangle$ puede representarse en una computadora clásica como un vector unitario en $\mathbb {C} ^{2^{n}}$ Además, cada puerta puede representarse mediante una matriz en $\mathbb {C} ^{2^{n}\times 2^{n}}$ Por lo tanto, el estado final $|\psi _{m}\rangle$ se puede calcular en $O(m\cdot 2^{2n})$ tiempo, y por lo tanto todos juntos, tenemos un $2^{O(n)}$ algoritmo de tiempo para calcular el estado final y, por lo tanto, la probabilidad de que el primer cúbit se mida como uno. Esto implica que ${\text{PROBLEMA-DE-CIRCUITO-APROXIMADO}}\in {\mathsf {EXP}}$ .

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

BQP y PSPACE

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

Consideremos un circuito cuántico $C$ , que consta de $t$ puertas, $g_{1},g_{2},\cdots ,g_{m}$ , donde cada $g_{j}$ proviene de un conjunto de puertas universales y actúa sobre como máximo dos cúbits. Para comprender qué 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. $|0\rangle ^{\otimes n}$ y cada nodo del árbol tiene $2^{n}$ niños, cada uno representando un estado en $\mathbb {C} ^{n}$ . El peso en una arista de árbol desde un nodo en el nivel $j$ que representa un estado $|x\rangle$ a un nodo en $j+1$ -ésimo nivel que representa un estado $|y\rangle$ es $\langle y|g_{j+1}|x\rangle$ , la amplitud de $|y\rangle$ después de aplicar $g_{j+1}$ en $|x\rangle$ . 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 del estado final es $|\psi \rangle$ , sumamos las amplitudes de todos los caminos de raíz a salida que terminan en un nodo que representa $|\psi \rangle$ .

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

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

Definir — Dejar $u,v\in \{0,1\}^{n}$ . Sea la amplitud del borde $(|u\rangle ,|v\rangle )$ en el $j$ -ésimo nivel de la suma sobre el árbol de historias sea $\alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle$ Para cualquier historia $h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})$ , la amplitud de transición de la historia es el producto $\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 $(u_{0}\rightarrow \cdots \rightarrow u_{m})$ La amplitud de transición de la historia se puede calcular en tiempo polinomial.

Prueba

Cada puerta $g_{j}$ puede descomponerse en $g_{j}=I\otimes {\tilde {g}}_{j}$ para algún operador unitario ${\tilde {g}}_{j}$ actuando sobre dos cúbits, que sin pérdida de generalidad pueden tomarse como los dos primeros. Por lo tanto, $\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$ que se puede calcular en tiempo polinomial en $n$ . Dado que $m$ es polinomial en $n$ , la amplitud de transición de la historia se puede calcular en tiempo polinomial.

Reclamar — Dejar $C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle$ ser el estado final del circuito cuántico. Para algunos $x\in \{0,1\}^{n}$ , la amplitud $\alpha _{x}$ puede calcularse mediante $\alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}$ .

Prueba

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

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

Observe en el algoritmo de suma sobre historiales para calcular alguna amplitud $\alpha _{x}$ , solo se almacena un historial en cualquier punto del cálculo. Por lo tanto, el algoritmo de suma sobre historiales utiliza $O(nm)$ espacio para calcular $\alpha _{x}$ para cualquier $x$ desde $O(nm)$ 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 $\sum _{x}|\alpha _{x}|^{2}$ sobre todo $x$ siendo el primer cúbit1 , que es la probabilidad de que el primer cúbit se mida como 1 al final del circuito.

Nótese que en comparación con la simulación dada para la prueba de que ${\mathsf {BQP}}\subseteq {\mathsf {EXP}}$ Nuestro algoritmo ocupa mucho menos espacio, pero mucho más tiempo. De hecho, tarda $O(m\cdot 2^{mn})$ ¡Es hora de calcular una sola amplitud!

BQP y PP

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

P y BQP

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

Se conjetura que BQP resuelve problemas difíciles fuera de P, específicamente, problemas en NP. Esta afirmación es indefinida porque no sabemos si P=NP, por lo que no sabemos si esos problemas pertenecen realmente a P. A continuación se presentan algunas pruebas de la conjetura:

Factorización de enteros (véase el algoritmo de Shor ) ^{[ 16 ]}
Logaritmo discreto ^{[ 16 ]}
Simulación de sistemas cuánticos (véase simulador cuántico universal )
Aproximación del polinomio de Jones en ciertas raíces de la unidad.
Algoritmo de Harrow-Hassidim-Lloyd (HHL)

Véase también

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

Referencias

1 2 3 Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
^ 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. pág. 122. Recuperado el 24 de julio de 2018 . {{cite book}}: CS1 maint: falta el editor de la ubicación ( enlace ) CS1 maint: varios nombres: lista de autores ( enlace )
↑ 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. Archivado (PDF) del original el 09-10-2022.
^ 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 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
1 2 Aaronson, Scott (2010). "BQP y la jerarquía polinomial" (PDF) . Actas de ACM STOC 2010. Archivado ( PDF) del original el 09/10/2022.
↑ 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 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . . Preimpresión disponible en
↑ Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Blog de complejidad computacional . Recuperado el 2 de mayo de 2008 .
↑ Janzing, Dominik; Wocjan, Pawel (30 de marzo de 2007). "Un problema matricial simple PromiseBQP-completo" (PDF) . Theory of Computing . 3 (4): 61–79 . doi : 10.4086/toc.2007.v003a004 . Consultado el 18 de abril de 2024 .
↑ 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.
↑ Odel A. Cross (5 de noviembre de 2012). "5.2.2 Medición diferida". Temas en computación cuántica . OA Cross. pág. 348. ISBN 978-1-4800-2749-7.
↑ 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 Comput- ing 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.
1 2 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.

[Chuang2000-1] 1 2 3 Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN 0-521-63503-9.

[BernVazi-2] 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 .

[3] Barak, Sanjeev Arora, Boaz (2009). Complejidad computacional: un enfoque moderno / Sanjeev Arora y Boaz Barak . Cambridge. pág. 122. Recuperado el 24 de julio de 2018 . {{cite book}}: CS1 maint: falta el editor de la ubicación ( enlace ) CS1 maint: varios nombres: lista de autores ( enlace )

[4] 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. Archivado (PDF) del original el 09-10-2022.

[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: varios nombres: lista de autores ( enlace )

[:0-7] 1 2 Aaronson, Scott (2010). "BQP y la jerarquía polinomial" (PDF) . Actas de ACM STOC 2010. Archivado ( PDF) del original el 09/10/2022.

[PostBQP=PP-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 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 . . Preimpresión disponible en

[9] Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Blog de complejidad computacional . Recuperado el 2 de mayo de 2008 .

[janzing-wocjan-10] Janzing, Dominik; Wocjan, Pawel (30 de marzo de 2007). "Un problema matricial simple PromiseBQP-completo" (PDF) . Theory of Computing . 3 (4): 61–79 . doi : 10.4086/toc.2007.v003a004 . Consultado el 18 de abril de 2024 .

[NielsenChuang2010-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.

[Cross2012-12] Odel A. Cross (5 de noviembre de 2012). "5.2.2 Medición diferida". Temas en 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 Comput- ing 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.

[Shor-16] 1 2 arXiv:quant-ph/9508027v2 Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica , Peter W. Shor

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]