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 una computadora cuántica puede resolver en tiempo polinómico , 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 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 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 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 que no esté en L , ${\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}$

Alternativamente, se puede definir BQP en términos de máquinas cuánticas de Turing . Un lenguaje L está en BQP si y sólo si existe una máquina de Turing cuántica polinomial que acepte L con una probabilidad de error de como máximo 1/3 para todos los casos. ^[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 inferior a 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 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 entrada. ^[3]

Relación con otras clases de complejidad

Problema no resuelto 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 sospecha de relación de BQP con otros espacios problemáticos ^[1]

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 en sí mismo, lo que significa BQP ^BQP = BQP . ^[2] Informalmente, esto es cierto porque los algoritmos de tiempo polinomial están cerrados bajo composición. Si un algoritmo de tiempo polinómico llama a algoritmos de tiempo polinómico como subrutinas, el algoritmo resultante sigue siendo de tiempo polinómico.

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 de PP no logra ningún beneficio al poder resolver problemas de BQP al instante, una indicación de la posible diferencia de potencia entre estas clases similares. Las relaciones conocidas con clases de complejidad clásicas 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 la desigualdad entre BQP y las clases mencionadas anteriormente es difícil. ^[2] Se desconoce la 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 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, se puede pensar que esto da a PH y BQP una capacidad idéntica, pero adicional, y verifica 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 Oracle, no se ha demostrado el hecho de que BQP no esté contenido en PH. Una separación de Oracle no prueba si las clases de complejidad son iguales o no. La separación del oráculo 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 polinomial. Conjeturas recientes han proporcionado evidencia de que un problema similar, la verificación de Fourier, también existe en la clase BQP sin estar contenido en la jerarquía polinomial . 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 pruebas 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]

Agregar 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 pueden resolverse mediante una familia uniforme de circuitos cuánticos (es decir, dentro de BQP). ^[10] Las pruebas de integridad se centran en esta versión de BQP. De manera similar a la noción de completitud NP 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 polinómico.

APROX-QCIRCUIT-PROB

El problema APPROX-QCIRCUIT-PROB está completo para la computación cuántica 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 cual no se conocen problemas completos). La integridad 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 }$

• medir el primer qubit del estado produce con probabilidad ${\displaystyle C|0\rangle ^{\otimes n}}$ ${\displaystyle |1\rangle }$ ${\displaystyle \geq \alpha }$
• medir el primer qubit del estado produce 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.

Afirmar. Cualquier problema de BQP se reduce a APROX-QCIRCUIT-PROB.

Prueba. 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 solucionar cualquier problema en BQP con este oráculo, configurando . ${\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }$ ${\displaystyle \alpha =2/3,\beta =1/3}$

Para cualquiera , existe una familia de circuitos cuánticos tal que para todos , un estado de qubits, si ; más si . Fijar una entrada de n qubits y el circuito cuántico correspondiente . Primero podemos construir un circuito tal que . Esto se puede hacer fácilmente mediante cableado y aplicando una secuencia de puertas CNOT para invertir los qubits. Luego podemos combinar dos circuitos para obtener , y ahora . Y finalmente, necesariamente los resultados 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 para que al medir 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

Comenzamos con una contención más fácil. Para demostrarlo , basta con mostrar que APPROX-QCIRCUIT-PROB está en EXP ya que APPROX-QCIRCUIT-PROB está completo en BQP. ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}$

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

Prueba

La idea es sencilla. Como tenemos potencia exponencial, dado un circuito cuántico C , podemos usar una computadora clásica para estimular cada puerta en C para obtener el estado final.

Más formalmente, sea C un circuito cuántico de tamaño polinómico en n qubits y m puertas, donde m es un polinomio en n. Sea y el estado después de que se aplica la i -ésima puerta del circuito . 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 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. Mostraremos en la siguiente sección 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 integrales de trayectoria . APPROX-QCIRCUIT-PROB se puede formular en la técnica de suma de historias para demostrar que . ^[13] ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}$

Árbol de suma de historias

Considere un circuito cuántico C , que consta de t puertas, donde cada una proviene de un conjunto de puertas universales y actúa sobre dos qubits como máximo. 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 el borde de un á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 . 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 todos los caminos de raíz a salida 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 sobre 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}}$

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

Definir  -  Dejar . Sea la amplitud del borde en el j -ésimo nivel de la suma del árbol de historias . Para cualquier historia , la amplitud de transición de la historia es el producto . ${\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)}$

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

Prueba

Cada puerta se puede descomponer en algún operador unitario que actúa sobre dos qubits, que sin pérdida de generalidad pueden considerarse los dos primeros. Por lo tanto, que se puede calcular en tiempo polinomial en n . Dado que 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 }$

Reclamació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 insertando entre , y , y así sucesivamente, y luego expande la ecuación. Entonces cada término corresponde a a , 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 siendo el primer qubit ${\displaystyle \sum _{x}|\alpha _{x}|^{2}}$1 , que es la probabilidad de que se mida que el primer qubit 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, ¡se necesita tiempo para 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 de historias para demostrar que . ^[14] ${\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}$

P y BQP

Lo sabemos , ya que todo circuito clásico puede simularse mediante 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 muestran 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 )
• Aproximar el polinomio de Jones en ciertas raíces de la unidad
• Algoritmo Harrow-Hassidim-Lloyd (HHL)

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 .
• 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: Prensa de la Universidad de Cambridge. ISBN  0-521-63503-9 .
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. pag. 122 . Consultado el 24 de julio de 2018 .{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: multiple names: authors list (link)
4. Por ahora, Lance; Rogers, Juan (1999). "Limitaciones de complejidad en la computación cuántica" (PDF) . J. Computación. Sistema. Ciencia . 59 (2): 240–252. arXiv : cs/9811023 . doi :10.1006/jcss.1999.1651. ISSN  0022-0000. S2CID  42516312. Archivado (PDF) desde el original el 9 de octubre de 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: multiple names: authors list (link)
7. Aaronson, Scott (2010). "BQP y la jerarquía polinómica" (PDF) . Actas de ACM STOC 2010 . Archivado (PDF) desde el original el 9 de octubre de 2022.
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 Bib : 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". Blog 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 y completo de PromiseBQP" (PDF) . Teoría de la Computación . 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. Prensa de la Universidad de Cambridge. pag. 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. Cruz OA. pag. 348.ISBN​ 978-1-4800-2749-7.
13. E. Bernstein y U. Vazirani. Teoría de la complejidad cuántica, Revista SIAM de Computación, 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, SEÑOR 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.