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 ordenadores cuánticos , un modelo computacional basado en la mecánica cuántica . Estudia la dificultad 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 ser resueltos por un modelo computacional bajo ciertas restricciones de recursos. Por ejemplo, la clase de complejidad P se define como el conjunto de problemas que puede resolver una máquina de Turing 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 de Turing cuántica 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 polinomial con una máquina de Turing probabilística . ^[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 es válida. Puede que no sea posible que una máquina de Turing probabilística simule modelos de computación cuántica en tiempo polinomial. ^[1]

Tanto la complejidad computacional cuántica de funciones como la complejidad computacional clásica de funciones se expresan a menudo con notación asintótica . Algunas formas comunes de noción asintótica de funciones son , , y . expresa que algo está acotado por encima de donde es una constante tal que y es una función de , expresa que algo está acotado por debajo de donde es una constante tal que y es una función de , y expresa tanto 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)$ ${\estilo de visualización c}$ $c>0$ $T(n)$ ${\estilo de visualización n}$ $\Omega(T(n))$ $cT(n)$ ${\estilo de visualización c}$ $c>0$ $T(n)$ ${\estilo de visualizació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 clases de complejidad importantes P, BPP, BQP, PP y PSPACE se pueden comparar en función de los 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 es 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}}=\varnada$

BQP

La clase de problemas que puede resolver de manera eficiente un ordenador cuántico con error acotado se denomina BQP ("error acotado, cuántico, tiempo polinomial"). Más formalmente, BQP es la clase de problemas que puede resolver una máquina de Turing cuántica de tiempo polinomial con una probabilidad de error de como máximo 1/3.

Como una clase de problemas probabilísticos, BQP es la contraparte cuántica de BPP ("error acotado, probabilístico, tiempo polinomial"), la clase de problemas que pueden ser resueltos eficientemente por máquinas de Turing probabilísticas con error acotado. ^[6] Se sabe que 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}}$

No se conoce la relación exacta de BQP con P , NP y PSPACE . Sin embargo, se sabe que ; es decir, la clase de problemas que pueden ser resueltos eficientemente por computadoras cuánticas incluye todos los problemas que pueden ser resueltos eficientemente por computadoras clásicas deterministas pero no incluye ningún problema que no pueda ser resuelto por computadoras clásicas con recursos de espacio polinomial. Se sospecha además que BQP es un superconjunto estricto de P, lo que significa que hay problemas que son eficientemente solucionables por computadoras cuánticas que no son eficientemente solucionables por computadoras clásicas deterministas. Por ejemplo, se sabe que la factorización de enteros y el problema del logaritmo discreto están en BQP y se sospecha que están fuera de P. Sobre la relación de BQP con NP, se sabe poco más allá del hecho de que algunos problemas NP están en BQP (la factorización de enteros y el problema del logaritmo discreto están ambos en NP, por ejemplo). Se sospecha que ; es decir, se cree que hay problemas comprobables eficientemente que no son eficientemente solucionables por una computadora cuántica. Como consecuencia directa de esta creencia, también se sospecha que BQP es disjunto de la clase de problemas NP-completos (si cualquier problema NP-completo estuviera en BQP, entonces se deduce de la NP-dureza 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 de la siguiente manera:

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

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

Simulación de circuitos cuánticos

No se conoce ninguna forma de simular de manera eficiente 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 polinomial. Sin embargo, un circuito cuántico de qubits con puertas cuánticas puede ser simulado por 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 un vector de estado. Estos vectores de estado también pueden describirse como una combinación lineal de sus vectores componentes con coeficientes llamados amplitudes. Estas amplitudes son números complejos que se normalizan 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 que son los 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 de qubits 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 en el sistema. El resultado de los productos tensoriales de los qubits es un único vector de estado 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 para el sistema de qubits. ^[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, los bits de precisión son suficientes para codificar cada amplitud. ^[3] Por lo tanto, se necesitan bits clásicos para tener en cuenta el vector de estado del sistema de qubits. A continuación, debe tenerse en cuenta la aplicación de las puertas cuánticas en las amplitudes. Las puertas cuánticas se pueden representar como matrices dispersas . ^[3] Por lo tanto, 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, hay 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 cuántico de qubits 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 se conoce una forma eficiente de simular 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 consulta cuántica

Una de las principales ventajas de utilizar un sistema computacional cuántico en lugar de uno clásico es que un ordenador cuántico puede ser capaz de proporcionar un algoritmo de tiempo polinomial para algún problema para el que no existe un algoritmo de tiempo polinomial clásico, pero lo que es más importante, un ordenador cuántico puede reducir significativamente el tiempo de cálculo para un problema que un ordenador clásico ya puede resolver de manera eficiente. Básicamente, un ordenador cuántico puede ser capaz de determinar cuánto tiempo llevará resolver un problema, mientras que un ordenador clásico puede ser incapaz de hacerlo, y también puede mejorar en gran medida la eficiencia computacional asociada con la solución de un problema particular. La complejidad de las consultas cuánticas se refiere a qué tan complejas son las consultas al gráfico asociado con la solución de un problema particular, o cuántas consultas al gráfico asociado con la solución, se requieren para resolver el problema. Antes de profundizar más en la complejidad de las consultas, consideremos algunos antecedentes sobre la representación gráfica de soluciones a problemas particulares y las consultas asociadas con estas soluciones.

Consulta de modelos de grafos dirigidos

Un tipo de problema que la computación cuántica puede facilitar su solución son los problemas de grafos. Si vamos a considerar la cantidad de consultas a un grafo que se requieren para resolver un problema dado, consideremos primero los tipos de grafos más comunes, llamados grafos dirigidos , que están asociados con este tipo de modelado computacional. En resumen, los grafos dirigidos son grafos donde todas las aristas 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 grafos dirigidos, hay dos modelos de consulta importantes que se deben comprender. En primer lugar, está el modelo de matriz de adyacencia , donde el grafo de la solución está dado por la matriz de adyacencia: , con , si y solo 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 ligeramente 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 de salida de los vértices , donde es el valor mínimo del 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 una arista entre cualquier par de vértices, y el número de aristas se minimiza en todo el modelo (consulte el 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 consulta cuántica de ciertos tipos de problemas de gráficos

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

Observe la discrepancia entre las complejidades de consulta cuántica asociadas con un tipo particular de problema, dependiendo de qué modelo de consulta 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 Big O es , pero cuando se utiliza el modelo de matriz, la complejidad es . Además, para abreviar, usamos la abreviatura en ciertos casos, donde . ^[11] La implicación importante aquí es que la eficiencia del algoritmo utilizado para resolver un problema de gráficos 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 consulta, la entrada también se puede proporcionar como un oráculo (caja negra). El algoritmo obtiene información sobre la entrada únicamente al consultar el oráculo. El algoritmo comienza en un estado cuántico fijo y el estado evoluciona a medida que consulta el oráculo.

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

Algoritmo de Grover

Un ejemplo que ilustra el poder de la computación cuántica es el algoritmo de Grover para buscar bases de datos no estructuradas. La complejidad de 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 Jozsa en alemán

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 únicas dos posibilidades. ^[2] La única forma de evaluar la función es consultar una caja negra o un oráculo . Un algoritmo determinista clásico tendrá que comprobar 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 consulta del algoritmo determinista clásico más eficiente es . ^[2] El algoritmo Deutsch-Jozsa aprovecha el paralelismo cuántico para comprobar todos los elementos del dominio a la vez y solo necesita consultar el oráculo una vez, lo que hace que su complejidad de consulta sea . ^[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 los avances en física podrían llevar 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 de una base de datos de $N$ elementos en pasos como máximo , una ligera aceleración sobre el 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 que se construyan 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 hay una forma obvia de describir lo que significa para un observador enviar una entrada a una computadora en un punto en el tiempo y luego recibir la salida en un punto posterior en el tiempo. ^[14]^[15] $O({\sqrt[{3}]{N}})$ $O({\sqrt {N}})$

Véase también

Notas

^ ab Vazirani, Umesh V. (2002). "Un estudio de la teoría de la complejidad cuántica". Actas de simposios sobre 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: Cambridge University Press. 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 [quant-ph].
^ Nielsen, pág. 42
^ Nielsen, Michael ; Chuang, Isaac (2000). Computación cuántica e información cuántica. Cambridge: Cambridge University Press. pág. 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 informática . 26 (5): 1411–1473. CiteSeerX 10.1.1.144.7852 . doi :10.1137/S0097539796300921.
^ Häner, Thomas; Steiger, Damian 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 de Computación de Alto Rendimiento, Redes, Almacenamiento y Análisis . Nueva York, NY, EE. UU.: ACM. págs. 1–10. arXiv : 1704.01127 . doi :10.1145/3126908.3126947. ISBN . 978-1-4503-5114-0.S2CID3338733 .
^ Nykamp, DQ "Definición de gráfico dirigido".
^ abc Durr, Christoph; Heiligman, Mark; Hoyer, Peter; Mhalla, Mehdi (enero de 2006). "Complejidad de consulta cuántica de algunos problemas de grafos". SIAM Journal on Computing . 35 (6): 1310–1328. arXiv : quant-ph/0401091 . doi :10.1137/050644719. ISSN 0097-5397. S2CID 27736397.
^ Zalka, Christof (1999-10-01). "El algoritmo de búsqueda cuántica de Grover es óptimo". Physical Review A . 60 (4): 2746–2751. arXiv : quant-ph/9711070 . Código Bibliográfico :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 de ACM SIGACT . 2005. arXiv : quant-ph/0502072 . Código Bibliográfico :2005quant.ph..2072A.Véase la sección 7 "Gravedad cuántica": "[...] a cualquiera que quiera una prueba o punto de referencia para una teoría de gravedad cuántica favorita, [nota al pie del autor: Es decir, una que no tenga que hacer toda la molestia de hacer predicciones numéricas y compararlas con la observación] permítanme humildemente proponer lo siguiente: ¿ pueden definir el Tiempo Polinomial de Gravedad Cuántica? [...] hasta que podamos decir qué significa para un 'usuario' especificar una 'entrada' y 'más tarde' recibir una 'salida', no existe tal cosa como 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». D-Wave. 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: Cambridge University Press. ISBN 978-0-521-63503-5.OCLC 174527496 .
Arora, Sanjeev ; Barak, Boaz (2016). Complejidad computacional: un enfoque moderno . Cambridge University Press. págs. 201–236. ISBN 978-0-521-42426-4.
Watrous, John (2008). "Complejidad computacional cuántica". arXiv : 0804.3401v1 [quant-ph].
Watrous J. (2009) Complejidad computacional cuántica. En: Meyers R. (eds.) Enciclopedia de complejidad y ciencia de sistemas. Springer, Nueva York, NY

Enlaces externos

Conferencias de Scott Aaronson en el MIT