El poder de los ordenadores cuánticos: Un problema en BQP que no está en PH

Por Francisco R. Villatoro, el 15 julio, 2018. Categoría(s): Ciencia • Computación cuántica • Informática • Noticias • Science ✎ 13

Todo lo que puede calcular un ordenador cuántico se puede calcular mediante un ordenador (clásico), basta simularlo. Se acaba de publicar un problema con oráculo que se puede resolver de forma eficiente en un ordenador cuántico, está en la clase BQP, pero que no se puede resolver de forma eficiente en un ordenador (clásico), incluso bajo la hipótesis P=NP. No sé si lo sabes, pero bajo dicha hipótesis un ordenador (clásico) puede calcular de forma eficiente problemas más allá de la clase NP, los que se encuentran en la clase PH (jerarquía polinómica). Ran Raz (Univ. Princeton) y Avishay Tal (Univ. Stanford) han encontrado un problema con oráculo que está en BQP, pero que no está en PH. Por supuesto, bajo la hipótesis de que P≠NP ya sabíamos que los ordenadores cuánticos son más eficientes, pues hay problemas en BQP que no están en P.

La relación entre BQP y PH ha sido un problema abierto desde 1993. La sospecha entre los expertos era que se trataba de clases de complejidad disjuntas. De hecho, en 2009 Scott Aaronson (entonces en el MIT, hoy en Univ. Texas en Austin) propuso un problema con oráculo en BQP y un esquema de demostración de que estaba más allá de PH. Quedaban algunos flecos por rellenar para obtener una demostración matemática. Se ha requerido casi un década de duro trabajo para rellenarlos. Aunque todavía la nueva demostración no ha superado una revisión por pares oficial, la opinión consensuada es que parece correcta.

Por cierto, se ha demostrado que BQPO ≠ PHO, donde la O significa «con oráculo», lo que en rigor no implica BQP ≠ PH. Sin embargo, para todos los expertos en complejidad computacional cuántica el uso de oráculos es irrelevante, siendo el nuevo resultado suficiente para afirmar que los ordenadores cuánticos son más eficientes que los ordenadores (clásicos). El nuevo artículo es Ran Raz, Avishay Tal, «Oracle Separation of BQP and PH,» TR18-107 (31 May 2018). Te recomiendo también Scott Aaronson, «BQP and the Polynomial Hierarchy,» arXiv:0910.4698 [quant-ph]. Más información divulgativa en Scott Aaronson, «The relativized BQP vs. PH problem (1993-2018),» Shtetl-Optimized, 03 Jun 2018, y en Kevin Hartnett, «Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve,» Quanta Magazine, 21 Jun 2018.

Para una discusión detallada de todas las clases de complejidad conocidas y sus relaciones nos llevaría lejos. Para la complejidad computacional clásica recomiendo el resumen de Scott Aaronson, «P, NP, and Friends,» PHYS771 Lecture 6. Se consideran algoritmos para resolver problemas de decisión, cuya respuesta a una entrada es 1 (sí, o aceptar la entrada), ó 0 (no, o rechazar la entrada). La clase P (polinómico) corresponde a los problemas resolubles en tiempo polinómico (donde por «tiempo» se entiende el número de operaciones). La clase NP (polinómico no determinista) son los problemas que tras aceptar una entrada permiten que esta se verifique en tiempo polinómico; coNP (NP complementaria) son los problemas que tras rechazar una entrada permiten que se verifique el rechazo en tiempo polinómico. Obviamente, P ⊆ NP, pero no sabemos si P = NP o bien P ≠ NP; esto último es lo que creen la mayoría de los expertos, e implica que la búsqueda sistemática por fuerza bruta es el único método general de resolver un problema NP. Tampoco sabemos si NP = coNP o bien NP ≠ coNP; nótese que ambas opciones son compatibles con P≠NP.

La definición de la jerarquía polinómica (PH) requiere introducir cuantificadores. Un problema en NP (≡ Σ1P) se puede escribir como ¿existe un X tal que A(X)=1? La clase Σ2P agrupa los problemas que se pueden escribir como ¿existe un X tal que para todo Y se tiene A(X,Y)=1? La clase Σ3P los problemas tipo ¿existe un X tal que para todo Y existe un Z tal que A(X,Y,Z)=1? Y así sucesivamente se define la clase ΣkP. Por otro lado, un problema en coNP (≡ Π1P) se puede escribir como ¿existe un X tal que A(X)=0? La clase Π2P agrupa a los problemas de tipo ¿para todo X existe un Y tal que A(X,Y)=1? La clase Π3P agrupa a los problemas de tipo ¿para todo X existe un Y tal que para todo Z se tiene A(X,Y,Z)=1? Y así sucesivamente se define la clase ΠkP. La clase PH es la unión de las clases ΣkP y ΠkP para todo k≥ 1. Se puede demostrar que si P = NP entonces la jerarquía polinómica colapsa a P, es decir, PH = P. Más aún, si NP = coNP entonces PH = NP.

Las clases de complejidad cuántica están relacionadas con las clases de complejidad aleatorias (más información en Scott Aaronson, «Randomness,» PHYS771 Lecture 7). La clase PP contiene todos los problemas de decisión para los que existe un algoritmo aleatorio que en tiempo polinomial acepta una entrada con probablidad mayor de 1/2 si la respuesta es 1 (sí) o menor de 1/2 si la respuesta es 0 (no); esta clase es muy grande, NP ⊆ PP y la opinión actual es que esta inclusión es estricta. La clase BPP son los algoritmos aleatorios que aceptan en tiempo polinomial una entrada con probabilidad mayor de 2/3 si la respueta es 1 (sí) y menos de 1/3 si la respuesta es 0 (no). Obviamente, P ⊆ BPP ⊆ PP, pero no se sabe si BPP ⊆ NP (aunque se sabe que BPP ⊆ NPNP, es decir, NP con un oráculo en NP, luego BPP ⊆ Σ2).

La clase complejidad cuántica más relevante es BQP (más información en Scott Aaronson, «Quantum Computing;» PHYS771 Lecture 10). La clase BQP está definida por los algoritmos cuánticos de decisión de tamaño polinómico (que se implementan usando un circuito cuánticos con un número polinómico de puertas) que aceptan una entrada con probabilidad maryo de 2/3 si la respuesta es 1 (sí) y menos de 1/3 si la respuesta es 0 (no). Por definición BPP ⊆ BQP, pues la aleatoriedad cuántica generaliza a la clásica y la opinión general es que BPP ≠ BQP; más aún, BQP ⊆ PP, pero desconocemos la relación entre BQP y PH; haber descubierto un problema en BQP que no está en PH bajo la hipótesis P=NP es un paso hacia adelante, pero queda mucho trabajo pendiente. Como supongo que ya sabes hay problemas en NP que están en BQP, pero no sabemos si NP ⊄ BQP (tampoco sabemos si P ≠ NP implica NP ⊄ BQP).

Te animo a seguir profundizando en el tema de las clases de complejidad. Hay mucho que ignoramos, por ello cada pocos años se publican avances interesantes.



13 Comentarios

  1. Al leer el artículo, me encuentro con demasiadas siglas, cuyo significado no aparece en ningún lugar. Lo que nos lleva a la paradoja de que para informarse del tema primero es necesario saber del tema.

    Sugiero brindar un buen glosario de siglas (quizá un enlace). Eso haría mas accesible el artículo (supongo que eso es deseable).

  2. Interesante artículo, y gracias también por las referencias.
    Nunca he visto una explicación decente de porqué la clase NP se define de esa forma tan rara; más o menos puedo ver la motivación, basada en cierta clase de problemas, pero si hay algún enlace que lo explique de la forma más didáctica posible también lo agradecería.

    Por cierto, me parece que hay un par de erratas en la descripción de la jerarquía Pi(k)P:
    – ¿No deberían ir todas las funciones A(…) en la jerarquía Pi igualadas a 0 en vez de a 1?
    – Aunque la descripción sea equivalente, ¿no tendría más lógica, por paralelismo con la de las Sigma(k)P, y para evitar confusiones, que se hablara en tía la descripción de si «existe un X para todo Y [y para todo Z]…»?

  3. Francis, hace poco escuché, y no sé si es cierto, que se ha demostrado que inferir las propiedades macroscópicas, de un sistema, a partir de sus propiedades cuánticas, no es posible, al ser un problema indecidible ¿Te suena?

      1. Gracias, Francis, reciente, y debe ser lo que me comenta javpod. Pues me sonaba que había un español involucrado , y he encontrado donde lo mencionan: en el podcast Principio de incertidumbre del 17/03/18.

      1. Gracias, javpod, con toda seguridad es eso lo que escuché, pues era un trabajo reciente y estaba involucrado David Pérez. Obviamente me quedé en el tratamiento superficial del tema.

  4. Tengo sesenta y cuatro años, y en el campo profesional cuarenta y cinco de experiencia en electrónica y más de treinta en ordenadores, especialmente de control de sistemas, también me gusta la ciencia, tengo más de 2.000 libros en mi biblioteca y procuro estar al día en los temas que publica el Scientific American, Science y Nature …pero debo confesar que de este artículo no he entendido ni las comas. Me interesan los ordenadores cuánticos, por lo que tienen de innovación tecnológica y la posibilidad de romper las barreras que afectan a la computación clásica, pero hasta ahora no he encontrado ninguna descripción de tales ordenadores que explique nada más que vaguedades. Que me digan que se basan en qbits, que a diferencia de los bits, permiten adoptar multiples valores, incluso de forma simultánea (?) y que esto es la ostia de las revoluciones en los procesos de cálculo, no me dice mucho más que escuchar que los ordenadores normales funcionan con bits, capaces de adoptar dos estados, y que luego te enseñen las salas de servidores de Google o monitores con imágenes de piezas 3D. El salto entre el humilde bit y el funcionamiento real de un ordenador es tan enorme, que la ausencia de una descripción intermedia de cómo se interrelacionan miles de millones de bits y un determinado hardware y software para procesar la información, impide llegar a comprenderlo. Pues con los ordenadores cuánticos ocurre lo mismo.

    …Aún he de encontrar un artículo que explique de forma mínimanente pormenorizada como consiguen meter algunos átomos en helio líquido, cargarles información, aplicarles un programa y que finalmente el resultado aparezca en una pantalla o en la hoja de una impresora. ¿Qué tecnologías se utilizan? ¿Cómo son las interfaces, los dispositivos y los circuitos? ¿Cómo son las órdenes de proceso? ¿Qué hacen y cuales son sus límites? …Ni en forma de pseudocódigo he visto nunca una simulación de computación cuántica… sólo vaguedades de principios físicos que no esclarecen nada o, en el extremo contrario, este artículo, que por falta de nivel matemático (lo reconozco) no entiendo, y cuya relación con los ordenadores cuánticos tampoco veo en absoluto.

    Atentamente

Deja un comentario