Las clases de complejidad clásicas y cuánticas se relacionan entre sí de una forma complicada que todavía no conocemos en detalle y por ahora todo son hipótesis. Las clases P y BQP son las clases de problemas resolubles de forma eficiente (polinómica) en ordenadores clásicos y cuánticos, resp. Las clases NP y QMA contienen los problemas de decisión que creemos que son más difíciles para ordenadores clásicos y cuánticos, resp., para los que existen algoritmos eficientes, clásicos y cuánticos, resp., que permiten decidir si una solución es correcta o no. Un artículo reciente en Nature Physics ha demostrado que las clases QMA, NP y P colapsarían (serían iguales entre sí), resolviendo la conjetura P versus NP con una igualdad, si se puede resolver de forma eficiente la simulación de sistemas cuánticos descritos por la teoría del funcional densidad (DFT). Por ejemplo, si un modelo concreto, el modelo cuántico de Hubbard, se puede simular en tiempo polinómico. Nadie cree que esto sea posible, pero carecemos de una demostración, todavía. Nos lo cuenta el experto en la teoría de la complejidad cuántica Scott Aaronson, «Computational complexity: Why quantum chemistry is hard,» Nature Physics 5: 707-708, 2009, haciéndose eco del artículo técnico de Norbert Schuch & Frank Verstraete, «Computational complexity of interacting electrons and fundamental limitations of density functional theory,» Nature Physics 5: 732-735, 2009.
La clase de complejidad del Protocolo Merlín-Arturo (MA) es la clase de problemas de decisión resolubles por el protocolo siguiente. Merlín tiene recursos computacionales ilimitados y envía a Arturo una demostración de tamaño polinómico que prueba que la respuesta es «sí.» Arturo puede verificar dicha prueba en la clase BPP (en tiempo polinómico con un algoritmo probabilístico). Si la respuesta es «sí» existe una demostración que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es «no» todas las demostraciones serán aceptadas por Arturo con una probabilidad menor que 1/3.
La clase de complejidad cuántica del Protocolo Merlín-Arturo (QMA) es la versión cuántica de MA y corresponde a un Merlín que envía una mensaje con una prueba cuántica que Arturo puede verificar en la clase BQP (en tiempo polinómico utilizando un algoritmo cuántico). Si la respuesta es «sí» existe un estado cuántico (demostración) que Arturo aceptará como correcta con una probabilidad mayor que 2/3 y si la respuesta es «no» todos los estados (demostraciones) serán rechazados por Arturo con un probabilidad mayor que 2/3.
El modelo de Hubbard describe un gas de electrones fuertemente acoplados por potenciales de Coulomb en la retícula de un sólido y permite comprender la transición entre un material conductor y uno aislante. La técnica matemática más utilizada para simular este modelo físico es la llamada teoría del funcional densidad (density functional theory). El nuevo artículo demuestra que si dicho problema se puede simular de forma eficiente, las clases de complejidad QMA y P serán iguales. Esto implica un gran avance en dos frentes. Por un lado, en la propia teoría de la complejidad de algoritmos cuánticos. Y por otro lado, impone un límite fundamental a la propia teoría del funcional densidad ya que una demostración de que P =!= NP (lo que todo el mundo cree) implicaría que nunca podremos simular eficientemente problemas «aparentemente» tan sencillos como el modelo de Hubbard incluso utilizando ordenadores cuánticos.
Esto sorprenderá a muchos ya que la mayoría pensaba que la utilidad más importante de los ordenadores cuánticos (cuando los haya) será la simulación de sistemas cuánticos. Pero si un sistema cuántico tan sencillo como el modelo de Hubbard es tan complejo de simular en un ordenador cuántico como en uno clásico, dicha ventaja se cae por su propio peso. Los avances en computación cuántica no cesan y cada día nos sorprenden más a los que somos aficionados a este «arte,» a esta ciencia.