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.
Samuel C. C. Ting (Premio Nobel de Física en 1976) es el investigador principal del experimento AMS (Alpha Magnetic Spectrometer) que está instalado en la ISS (International Space Station) y desde mayo de 2011 está observando rayos cósmicos de diferente tipo y masa. Lo más sorprendente es el exceso de positrones para energías por encima de 300 GeV, cuyo flujo coincide con el flujo de antiprotones y protones (que tienen una masa casi 2000 veces mayor). La aniquilación de una partícula de materia oscura con una masa de 1.2 TeV/c² podría explicar el exceso de positrones y antiprotones, pero no explica que coincida con el de protones. Fuentes astrofísicas, como púlsares y supernovas, explican algunos de estos flujos, pero no todos. La solución al misterio requiere seguir tomando datos y una mente abierta a sorpresas.
