Teoría de la complejidad cuántica

La teoría de la complejidad cuántica es el subcampo de la teoría de la complejidad computacional que se ocupa de las clases de complejidad definidas mediante computadoras cuánticas , un modelo computacional basado en la mecánica cuántica . Estudia la dureza de los problemas computacionales en relación con estas clases de complejidad, así como la relación entre las clases de complejidad cuántica y las clases de complejidad clásicas (es decir, no cuánticas).

Dos clases importantes de complejidad cuántica son BQP y QMA .

Fondo

Una clase de complejidad es una colección de problemas computacionales que pueden resolverse mediante un modelo computacional bajo ciertas restricciones de recursos. Por ejemplo, la clase de complejidad P se define como el conjunto de problemas que una máquina de Turing puede resolver en tiempo polinomial . De manera similar, las clases de complejidad cuántica pueden definirse utilizando modelos cuánticos de computación, como el modelo de circuito cuántico o la máquina cuántica de Turing equivalente . Uno de los principales objetivos de la teoría de la complejidad cuántica es descubrir cómo se relacionan estas clases con las clases de complejidad clásicas como P , NP , BPP y PSPACE .

Una de las razones por las que se estudia la teoría de la complejidad cuántica son las implicaciones de la computación cuántica para la tesis moderna de Church-Turing . En resumen, la tesis moderna de Church-Turing afirma que cualquier modelo computacional puede simularse en tiempo polinómico con una máquina probabilística de Turing . ^[1]^[2] Sin embargo, surgen preguntas en torno a la tesis de Church-Turing en el contexto de la computación cuántica. No está claro si la tesis de Church-Turing es válida para el modelo de computación cuántica. Hay mucha evidencia de que la tesis no se sostiene. Puede que no sea posible que una máquina probabilística de Turing simule modelos de computación cuántica en tiempo polinómico. ^[1]

Tanto la complejidad computacional cuántica de las funciones como la complejidad computacional clásica de las funciones a menudo se expresan con notación asintótica . Algunas formas comunes de noción asintótica de funciones son , y . expresa que algo está acotado arriba por donde es una constante tal que y es función de , expresa que algo está acotado abajo por donde es una constante tal que y es función de , y expresa ambos y . ^[3] Estas notaciones también tienen sus propios nombres. se llama notación Big O , se llama notación Big Omega y se llama notación Big Theta. $O(T(n))$ $\Omega (T(n))$ $\Theta (T(n))$ $O(T(n))$ $cT(n)$ $c$ $c>0$ $T(n)$ $n$ $\Omega (T(n))$ $cT(n)$ $c$ $c>0$ $T(n)$ $n$ $\Theta (T(n))$ $O(T(n))$ $\Omega (T(n))$ $O(T(n))$ $\Omega (T(n))$ $\Theta (T(n))$

Descripción general de las clases de complejidad

Las importantes clases de complejidad P, BPP, BQP, PP y PSPACE se pueden comparar según problemas de promesa . Un problema de promesa es un problema de decisión en el que se supone que una entrada se selecciona del conjunto de todas las cadenas de entrada posibles. Un problema de promesa es un par , donde es el conjunto de instancias sí y el conjunto de instancias no, y la intersección de estos conjuntos está vacía :. Todas las clases de complejidad anteriores contienen problemas de promesa. ^[4] $A=(A_{\text{sí}},A_{\text{no}})$ $A_{\text{sí}}$ $A_{\text{no}}$ $A_{\text{sí}}\cap A_{\text{no}}=\varnothing$

BQP

La clase de problemas que puede resolver eficientemente una computadora cuántica con error acotado se llama BQP ("error acotado, tiempo polinómico cuántico"). Más formalmente, BQP es la clase de problemas que pueden resolverse mediante una máquina cuántica de Turing de tiempo polinomial con una probabilidad de error de como máximo 1/3.

Como clase de problemas probabilísticos, BQP es la contraparte cuántica de BPP ("error acotado, probabilístico, tiempo polinómico"), la clase de problemas que pueden resolverse eficientemente mediante máquinas probabilísticas de Turing con error acotado. ^[6] Se sabe y se sospecha ampliamente, pero no se ha demostrado, que lo que intuitivamente significaría que las computadoras cuánticas son más poderosas que las computadoras clásicas en términos de complejidad temporal. ^[7] BQP es un subconjunto de PP . ${\mathsf {BPP\subseteq BQP}}$ ${\mathsf {BQP\nsubseteq BPP}}$

Se desconoce la relación exacta de BQP con P , NP y PSPACE . Sin embargo, se sabe que ; es decir, la clase de problemas que pueden resolverse eficientemente mediante computadoras cuánticas incluye todos los problemas que pueden resolverse eficientemente mediante computadoras clásicas deterministas, pero no incluye ningún problema que no puedan resolverse mediante computadoras clásicas con recursos espaciales polinomiales. Además, se sospecha que BQP es un superconjunto estricto de P, lo que significa que hay problemas que pueden resolverse eficientemente mediante computadoras cuánticas que no pueden resolverse eficientemente mediante computadoras clásicas deterministas. Por ejemplo, se sabe que la factorización de enteros y el problema de logaritmos discretos están en BQP y se sospecha que están fuera de P. Sobre la relación de BQP con NP, poco se sabe más allá del hecho de que algunos problemas de NP están en BQP (factorización de enteros y el problema de logaritmos discretos están ambos en NP, por ejemplo). Se sospecha que ; es decir, se cree que existen problemas comprobables de manera eficiente que no pueden resolverse de manera eficiente mediante una computadora cuántica. Como consecuencia directa de esta creencia, también se sospecha que BQP está separado de la clase de problemas NP-completos (si algún problema NP-completo estuviera en BQP, entonces de la dureza NP se deduce que todos los problemas en NP están en BQP). ). ^[8] ${\mathsf {P\subseteq BQP\subseteq PSPACE}}$ ${\mathsf {NP\nsubseteq BQP}}$

La relación de BQP con las clases de complejidad clásicas esenciales se puede resumir como:

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

También se sabe que BQP está contenido en la clase de complejidad (o más precisamente en la clase asociada de problemas de decisión ), ^[8] que es un subconjunto de PSPACE . $\color {Blue}{\mathsf {\#P}}$ ${\mathsf {P^{\#P}}}$

Simulación de circuitos cuánticos.

No se conoce ninguna forma de simular eficientemente un modelo computacional cuántico con una computadora clásica. Esto significa que una computadora clásica no puede simular un modelo computacional cuántico en tiempo polinómico. Sin embargo, un circuito cuántico de qubits con puertas cuánticas puede simularse mediante un circuito clásico con puertas clásicas . ^[3] Este número de puertas clásicas se obtiene determinando cuántas operaciones de bits son necesarias para simular el circuito cuántico. Para hacer esto, primero se deben tener en cuenta las amplitudes asociadas con los qubits. Cada uno de los estados de los qubits puede describirse mediante un vector complejo bidimensional, o vector de estado. Estos vectores de estado también se pueden describir como una combinación lineal de sus vectores componentes con coeficientes llamados amplitudes. Estas amplitudes son números complejos normalizados a uno, lo que significa que la suma de los cuadrados de los valores absolutos de las amplitudes debe ser uno. ^[3] Las entradas del vector de estado son estas amplitudes. La entrada de cada una de las amplitudes corresponde al componente distinto de cero del vector componente del cual son coeficientes en la descripción de la combinación lineal. Como ecuación, esto se describe como o usando la notación de Dirac . El estado de todo el sistema qubit se puede describir mediante un único vector de estado. Este vector de estado que describe todo el sistema es el producto tensorial de los vectores de estado que describen los qubits individuales del sistema. El resultado de los productos tensoriales de los qubits es un vector de estado único que tiene dimensiones y entradas que son las amplitudes asociadas con cada estado base o vector componente. Por lo tanto, las amplitudes deben tenerse en cuenta con un vector complejo dimensional que es el vector de estado del sistema qubit. ^[9] Para obtener un límite superior para el número de puertas necesarias para simular un circuito cuántico, necesitamos un límite superior suficiente para la cantidad de datos utilizados para especificar la información sobre cada una de las amplitudes. Para hacer esto, son suficientes bits de precisión para codificar cada amplitud. ^[3] Por lo tanto, se necesitan bits clásicos para tener en cuenta el vector de estado del sistema qubit. A continuación hay que tener en cuenta la aplicación de las puertas cuánticas a las amplitudes. Las puertas cuánticas se pueden representar como matrices dispersas . ^[3] Entonces, para tener en cuenta la aplicación de cada una de las puertas cuánticas, el vector de estado debe multiplicarse por una matriz dispersa para cada una de las $S(n)$ $T(n)$ $O(2^{S(n)}T(n)^{3})$ $S(n)$ $S(n)$ $\alpha {\begin{bmatrix}1\\0\end{bmatrix}}+\beta {\begin{bmatrix}0\\1\end{bmatrix}}={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}$ $\alpha \left\vert 1\right\rangle +\beta \left\vert 0\right\rangle ={\begin{bmatrix}\alpha \\\beta \end{bmatrix}}$ $S(n)$ $S(n)$ $2^{S(n)}$ $2^{S(n)}$ $2^{S(n)}$ $S(n)$ $2^{S(n)}$ $O(T(n))$ $O(2^{S(n)}T(n))$ $S(n)$ $T(n)$ $2^{S(n)}$ $2^{S(n)}\times 2^{S(n)}$ $T(n)$ $2^{S(n)}\times 2^{S(n)}$ $T(n)$ puertas cuánticas. Cada vez que el vector de estado se multiplica por una matriz dispersa, se deben realizar operaciones aritméticas. ^[3] Por lo tanto, existen operaciones de bits para cada puerta cuántica aplicada al vector de estado. Por lo tanto, se necesitan puertas clásicas para simular un circuito qubit con una sola puerta cuántica. Por lo tanto, se necesitan puertas clásicas para simular un circuito cuántico de qubits con puertas cuánticas. ^[3] Si bien no existe una forma conocida de simular eficientemente una computadora cuántica con una computadora clásica, es posible simular eficientemente una computadora clásica con una computadora cuántica. Esto es evidente por el hecho de que . ^[4] $2^{S(n)}\times 2^{S(n)}$ $O(2^{S(n)})$ $O(2^{S(n)}T(n)^{2})$ $O(2^{S(n)}T(n)^{2})$ $S(n)$ $O(2^{S(n)}T(n)^{3})$ $S(n)$ $T(n)$ ${\mathsf {BPP\subseteq BQP}}$

Complejidad de las consultas cuánticas

Una ventaja importante de utilizar un sistema computacional cuántico en lugar de uno clásico es que una computadora cuántica puede proporcionar un algoritmo de tiempo polinómico para algún problema para el cual no existe un algoritmo de tiempo polinómico clásico, pero lo que es más importante, una computadora cuántica puede significativamente disminuir el tiempo de cálculo de un problema que una computadora clásica ya puede resolver de manera eficiente. Esencialmente, una computadora cuántica puede determinar cuánto tiempo llevará resolver un problema, mientras que una computadora clásica puede no poder hacerlo, y también puede mejorar en gran medida la eficiencia computacional asociada con la solución de un problema en particular. La complejidad de las consultas cuánticas se refiere a qué tan complejas o cuántas consultas al gráfico asociado con la solución de un problema en particular se requieren para resolver el problema. Antes de profundizar más en la complejidad de las consultas, consideremos algunos antecedentes sobre cómo representar gráficamente soluciones a problemas particulares y las consultas asociadas con estas soluciones.

Modelos de consulta de gráficos dirigidos.

Un tipo de problema que la computación cuántica puede facilitar la resolución son los problemas de gráficos. Si vamos a considerar la cantidad de consultas a un gráfico que se requieren para resolver un problema determinado, consideremos primero los tipos de gráficos más comunes, llamados gráficos dirigidos , que están asociados con este tipo de modelado computacional. En resumen, los gráficos dirigidos son gráficos donde todos los bordes entre los vértices son unidireccionales. Los grafos dirigidos se definen formalmente como el grafo , donde N es el conjunto de vértices o nodos y E es el conjunto de aristas. ^[10] $G=(N,E)$

Modelo de matriz de adyacencia

Al considerar el cálculo cuántico de la solución de problemas de gráficos dirigidos, hay que comprender dos modelos de consulta importantes. Primero, está el modelo de matriz de adyacencia , donde la gráfica de la solución viene dada por la matriz de adyacencia: , con , si y sólo si . ^[11] $M\in \{0,1\}a^{n\mathrm {X} n}$ $M_{ij}=1$ $(v_{i},v_{j})\in E$

Modelo de matriz de adyacencia

A continuación, está el modelo de matriz de adyacencia, un poco más complicado, construido sobre la idea de listas de adyacencia , donde cada vértice , está asociado con una matriz de vértices vecinos de modo que , para los grados externos de los vértices , donde está el valor mínimo de límite superior de este modelo y devuelve el " " vértice adyacente a . Además, el modelo de matriz de adyacencia satisface la condición de gráfico simple, lo que significa que solo hay un borde entre cualquier par de vértices y el número de bordes se minimiza en todo el modelo (consulte Modelo de árbol de expansión para obtener más información). ^[11] $u$ $f_{i}:[d_{i}^{+}]\rightarrow [n]$ $d_{i}^{+},...,d_{n}^{+}$ $n$ $f_{i}(j)$ $j^{th}$ $i$ $\forall i\in [n],j,j'\in [k],j\neq j':f_{i}(j)\neq f_{i}(j')$

Complejidad de consultas cuánticas de ciertos tipos de problemas de gráficos.

Ambos modelos anteriores se pueden utilizar para determinar la complejidad de la consulta de tipos particulares de problemas de gráficos, incluida la conectividad , la conectividad fuerte (una versión de gráfico dirigido del modelo de conectividad), el árbol de expansión mínimo y los modelos de gráficos de ruta más corta de fuente única . Una advertencia importante a considerar es que la complejidad cuántica de un tipo particular de problema gráfico puede cambiar según el modelo de consulta (es decir, matriz o matriz) utilizado para determinar la solución. La siguiente tabla que muestra las complejidades de las consultas cuánticas de este tipo de problemas gráficos ilustra bien este punto.

Observe la discrepancia entre las complejidades de las consultas cuánticas asociadas con un tipo particular de problema, según el modelo de consulta que se utilizó para determinar la complejidad. Por ejemplo, cuando se utiliza el modelo matricial, la complejidad cuántica del modelo de conectividad en notación O grande es , pero cuando se utiliza el modelo de matriz, la complejidad es . Además, por motivos de brevedad, utilizamos la taquigrafía en ciertos casos, donde . ^[11] La implicación importante aquí es que la eficiencia del algoritmo utilizado para resolver un problema gráfico depende del tipo de modelo de consulta utilizado para modelar el gráfico. $\Theta (n^{3/2})$ $\Theta (n)$ $m$ $m=\Theta (n^{2})$

Otros tipos de consultas computacionales cuánticas

En el modelo de complejidad de consultas, la entrada también se puede proporcionar como un oráculo (cuadro negro). El algoritmo obtiene información sobre la entrada solo consultando al oráculo. El algoritmo comienza en algún estado cuántico fijo y el estado evoluciona a medida que consulta al oráculo.

De manera similar al caso de los problemas gráficos, la complejidad de la consulta cuántica de un problema de caja negra es el número más pequeño de consultas al oráculo que se requieren para calcular la función. Esto hace que la complejidad de la consulta cuántica sea un límite inferior de la complejidad temporal general de una función.

algoritmo de Grover

Un ejemplo que muestra el poder de la computación cuántica es el algoritmo de Grover para buscar bases de datos no estructuradas. La complejidad de la consulta cuántica del algoritmo es una mejora cuadrática con respecto a la mejor complejidad de consulta clásica posible , que es una búsqueda lineal . El algoritmo de Grover es asintóticamente óptimo ; de hecho, utiliza como máximo una fracción más de consultas que el mejor algoritmo posible. ^[12] ${\textstyle O{\left({\sqrt {N}}\right)}}$ $O(N)$ $1+o(1)$

Algoritmo de Deutsch-Jozsa

El algoritmo Deutsch-Jozsa es un algoritmo cuántico diseñado para resolver un problema de juguete con una complejidad de consulta menor que la posible con un algoritmo clásico. El problema del juguete pregunta si una función es constante o equilibrada, siendo esas las dos únicas posibilidades. ^[2] La única forma de evaluar la función es consultar una caja negra u oráculo . Un algoritmo determinista clásico tendrá que verificar más de la mitad de las posibles entradas para estar seguro de si la función es constante o equilibrada. Con posibles entradas, la complejidad de la consulta del algoritmo determinista clásico más eficiente es . ^[2] El algoritmo Deutsch-Jozsa aprovecha el paralelismo cuántico para verificar todos los elementos del dominio a la vez y solo necesita consultar el oráculo una vez, lo que hace que la consulta sea compleja . ^[2] $f:\{0,1\}^{n}\rightarrow \{0,1\}$ $f$ $2^{n}$ $2^{n-1}+1$ $1$

Otras teorías de la física cuántica

Se ha especulado que mayores avances en física podrían conducir a computadoras aún más rápidas. Por ejemplo, se ha demostrado que una computadora cuántica de variables ocultas no locales basada en la mecánica de Bohm podría implementar una búsqueda en una base de datos $de N$ elementos en la mayoría de los pasos, una ligera aceleración con respecto al algoritmo de Grover , que se ejecuta en pasos. Sin embargo, tenga en cuenta que ninguno de los métodos de búsqueda permitiría a las computadoras cuánticas resolver problemas NP-completos en tiempo polinomial. ^[13] Las teorías de la gravedad cuántica , como la teoría M y la gravedad cuántica de bucles , pueden permitir la construcción de computadoras aún más rápidas. Sin embargo, definir la computación en estas teorías es un problema abierto debido al problema del tiempo ; es decir, dentro de estas teorías físicas actualmente no existe una forma obvia de describir lo que significa para un observador enviar información a una computadora en un momento dado y luego recibir resultados en un momento posterior. ^[14]^[15] $O({\sqrt[{3}]{N}})$ $O({\sqrt {N}})$

Ver también

Notas

^ ab Vazirani, Umesh V. (2002). "Un estudio de la teoría de la complejidad cuántica". Actas de simposios en matemáticas aplicadas . 58 : 193–217. doi : 10.1090/psapm/058/1922899. ISBN 9780821820841. ISSN 2324-7088.
^ abcd Nielsen, Michael A., 1974- (2010). Computación cuántica e información cuántica. Chuang, Isaac L., 1968- (edición del décimo aniversario). Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-1-107-00217-3. OCLC 665137861.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ abcdefg Cleve, Richard (2000), "Introducción a la teoría de la complejidad cuántica", Computación cuántica y teoría de la información cuántica , WORLD SCIENTIFIC, págs. 103-127, arXiv : quant-ph/9906111 , Bibcode : 2000qcqi.book..103C , doi :10.1142/9789810248185_0004, ISBN 978-981-02-4117-9, S2CID 958695 , consultado el 10 de octubre de 2020
^ abcdefg Watrous, John (21 de abril de 2008). "Complejidad computacional cuántica". arXiv : 0804.3401 [cuántico-ph].
^ Nielsen, pág. 42
^ Nielsen, Michael ; Chuang, Isaac (2000). Computación cuántica e información cuántica. Cambridge: Prensa de la Universidad de Cambridge. pag. 41.ISBN 978-0-521-63503-5. OCLC 174527496.
^ Nielsen, pág. 201
^ ab Bernstein, Ethan; Vazirani, Umesh (1997). "Teoría de la complejidad cuántica". Revista SIAM de Computación . 26 (5): 1411-1473. CiteSeerX 10.1.1.144.7852 . doi :10.1137/S0097539796300921.
^ Haner, Thomas; Steiger, Damián S. (12 de noviembre de 2017). "Simulación de 0,5 petabytes de un circuito cuántico de 45 qubits". Actas de la Conferencia Internacional sobre Computación, Redes, Almacenamiento y Análisis de Alto Rendimiento . Nueva York, NY, Estados Unidos: ACM. págs. 1–10. arXiv : 1704.01127 . doi :10.1145/3126908.3126947. ISBN 978-1-4503-5114-0. S2CID 3338733.
^ Nykamp, DQ "Definición de gráfico dirigido".
^ abc Durr, Christoph; Heiligman, Mark; Hoyer, Peter; Mhalla, Mehdi (enero de 2006). "Complejidad de consultas cuánticas de algunos problemas de gráficos". Revista SIAM de Computación . 35 (6): 1310-1328. arXiv : quant-ph/0401091 . doi : 10.1137/050644719. ISSN 0097-5397. S2CID 27736397.
^ Zalka, Christof (1 de octubre de 1999). "El algoritmo de búsqueda cuántica de Grover es óptimo". Revisión física A. 60 (4): 2746–2751. arXiv : quant-ph/9711070 . Código Bib : 1999PhRvA..60.2746Z. doi : 10.1103/PhysRevA.60.2746. S2CID 1542077.
^ Aaronson, Scott. "Computación cuántica y variables ocultas" (PDF) .
^ Aaronson, Scott (2005). "Problemas NP-completos y realidad física". Noticias ACM SIGACT . 2005 . arXiv : quant-ph/0502072 . Código Bib : 2005quant.ph..2072A.Consulte la sección 7 "Gravedad cuántica": "[...] para cualquiera que quiera una prueba o punto de referencia para una teoría de la gravedad cuántica favorita, [nota al pie del autor: Es decir, uno sin la molestia de hacer predicciones numéricas y compararlas con la observación ] permítanme proponer humildemente lo siguiente: ¿pueden definir el tiempo polinómico de gravedad cuántica [...] hasta que podamos decir qué significa que un 'usuario' especifique una 'entrada' y 'más tarde' reciba una 'salida'? no existe la computación, ni siquiera teóricamente " (énfasis en el original) .
^ "D-Wave Systems vende su primer sistema de computación cuántica a Lockheed Martin Corporation". Onda D. 25 de mayo de 2011. Archivado desde el original el 22 de diciembre de 2020 . Consultado el 30 de mayo de 2011 .

Referencias

Nielsen, Michael ; Chuang, Isaac (2000). Computación cuántica e información cuántica . Cambridge: Prensa de la Universidad de Cambridge. ISBN 978-0-521-63503-5. OCLC 174527496.
Arora, Sanjeev ; Barac, Booz (2016). Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge. págs. 201–236. ISBN 978-0-521-42426-4.
Watrous, John (2008). "Complejidad computacional cuántica". arXiv : 0804.3401v1 [cuántico-ph].
Watrous J. (2009) Complejidad computacional cuántica. En: Meyers R. (eds) Enciclopedia de complejidad y ciencia de sistemas. Springer, Nueva York, Nueva York

enlaces externos

Conferencias del MIT a cargo de Scott Aaronson