En términos teóricos de complejidad computacional, esto generalmente significa proporcionar una aceleración superpolinomial sobre el algoritmo clásico más conocido o posible.
[2] El término fue popularizado originalmente por John Preskill[1] pero el concepto de ventaja computacional cuántica, específicamente para simular sistemas cuánticos, se remonta a las propuestas de la misma computación cuántica de Yuri Manin (1980)[3] y Richard Feynman (1981).
[4] El algoritmo de Shor para la factorización de números enteros, que se ejecuta en tiempo polinomial en un ordenador cuántico, proporciona tal aceleración superpolinomial sobre el algoritmo clásico más conocido.
La dificultad de probar lo que no se puede hacer con la computación clásica es un problema común para demostrar definitivamente la supremacía cuántica.
[10] En noviembre de 2018, Google anunció una asociación con la NASA que "analizaría los resultados de los circuitos cuánticos que se ejecutan en los procesadores cuánticos de Google, y... proporcionan comparaciones con la simulación clásica tanto para ayudar a Google a validar su hardware como para establecer una línea de base para la supremacía cuántica".