¿Qué problemas NO va a acelerar la computación cuántica?

TL;DR (28 de septiembre de 2026): La mayor parte de lo que las computadoras hacen todo el día no se va a acelerar en un computador cuántico. Tres techos son teoremas probados en el modelo de consulta: la búsqueda no estructurada gana a lo sumo el factor cuadrático √N de Grover, probado óptimo en 1997 (Bennett–Bernstein–Brassard–Vazirani, SIAM J. Comput. 26, 1510); computar la paridad de n bits ahorra a lo sumo un factor de dos (Beals et al., J. ACM 48, 778, 2001); ordenar por comparaciones se queda en n log n (Høyer, Neerbek y Shi, Algorithmica 34, 429, 2002). Y en hardware con corrección de errores la clase cuadrática hasta invierte el signo: el propio equipo de Google estimó ≈1 día sobre ≈1 millón de cúbits físicos para vidrios de espín que el annealing clásico resuelve en ≈4 CPU-minutos (Sanders et al., PRX Quantum 1, 020312, 2020) — ×360 más lento, por aritmética propia de Rosetta Quantum declarada sobre esas dos cifras publicadas. El carril honesto donde la aceleración exponencial seguirá siendo esperable es angosto: simular sistemas cuánticos y romper criptografía específica — ambos en tiempo futuro.

¿Por qué «prueba todas las respuestas a la vez» es el punto de partida equivocado?

Porque un computador cuántico que «probara todo en paralelo» igual tendría que entregarte una sola respuesta: la medición colapsa la superposición a un único resultado, y el arte de un algoritmo cuántico es organizar la interferencia para que las respuestas equivocadas se cancelen — algo que solo funciona en problemas con la estructura correcta. Ese mecanismo lo desarmamos en nuestro explicador del qubit. El mito importa aquí porque predice lo contrario de este post: si la superposición fuera fuerza bruta paralela, la optimización NP-completa caería primero. El registro publicado desde 1997 dice que no va a caer — y ese registro, no el mito, es lo que un comprador debería descontar.

¿Qué techos son teoremas probados, no opiniones?

Al menos cuatro, todos en el modelo de caja negra (consulta), y el más joven tiene 24 años. Búsqueda no estructurada: cualquier algoritmo cuántico necesita Ω(√N) consultas al oráculo, así que el algoritmo de Grover de 1996 es óptimo y la aceleración es cuadrática, nunca exponencial (BBBV, SIAM J. Comput. 26, 1510, 1997). Paridad: computar la paridad de n bits exige al menos n/2 consultas cuánticas — un ahorro máximo de ×2 sobre lo clásico (Beals et al., J. ACM 48, 778, 2001). Ordenamiento por comparaciones: al menos ≈0,110·n·log₂n comparaciones, así que la cota clásica n log n sobrevive a lo cuántico (Høyer, Neerbek y Shi, Algorithmica 34, 429, 2002). Búsqueda ordenada (binaria): al menos ≈0,220·log₂N consultas — solo una ganancia de factor constante, del mismo paper. La letra chica que Rosetta siempre adjunta: son cotas del modelo de consulta — acotan a cualquier algoritmo que trate el problema como caja negra; no dicen nada sobre explotar la estructura interna de un problema, que es exactamente donde viven las pocas victorias cuánticas reales.

¿Por qué la cuántica no va a romper la optimización NP-completa?

Porque BQP — la clase de problemas que un computador cuántico resuelve eficientemente — no se cree que contenga los problemas NP-completos, y la evidencia es tan vieja como el campo: relativo a un oráculo aleatorio, NP queda fuera de BQP con probabilidad 1 (BBBV 1997). Scott Aaronson hizo de esto el centro de su argumento de 2008: los problemas NP-completos «probablemente no» serán resolubles eficientemente por computadores cuánticos (Scientific American 298(3), 62–69, 2008). Lo que la cuántica le ofrece a la optimización NP-completa exacta es Grover sobre el árbol de fuerza bruta — el √N de nuestro explicador de Grover, aplicado a un N exponencialmente grande, lo que deja un tiempo de corrida exponencial. Ruteo, scheduling, selección de portafolios a escala: la expectativa honesta es que lo cuántico competirá contra heurísticas clásicas que ya son excelentes, no que hará desaparecer el exponencial.

¿Por qué hasta la aceleración cuadrática muere en hardware real?

Porque la corrección de errores cobra un sobrecosto por paso, y una ventaja √N recupera demasiado pocos pasos. Los números vienen del lado vendor del libro contable, no de los escépticos: el propio equipo de Google compiló simulated annealing acelerado por cuántica para procesadores tolerantes a fallos tempranos y reportó que «requeriría aproximadamente un día y un millón de cúbits físicos» en vidrios de espín que el annealing clásico resuelve «en unos cuatro CPU-minutos» (Sanders et al., PRX Quantum 1, 020312, 2020) — el ×360 de nuestra portada es esas dos cifras divididas, aritmética propia, declarada. El mismo grupo concluyó un año después que «las aceleraciones cuadráticas no habilitarán ventaja cuántica en las primeras generaciones» de máquinas tolerantes a fallos, y que las cuárticas se ven significativamente más prácticas (Babbush et al., PRX Quantum 2, 010103, 2021). Un análisis independiente de Microsoft–ETH llegó a la misma partición desde el throughput crudo — una sola GPU clásica entrega 10¹⁰–10¹³ veces más operaciones por segundo que una máquina corregida optimista, así que con aceleración cuadrática «incluso una sola operación de punto flotante o entera lleva los tiempos de cruce a varios meses», y se requieren «aceleraciones al menos cúbicas o cuárticas» (Hoefler, Häner y Troyer, Commun. ACM 66(5), 82–87, 2023). Hay un debate vivo sobre si Grover sobrevive siquiera fuera del escenario de caja negra: un paper argumenta que los oráculos compilados eliminan la ventaja a priori (Stoudenmire y Waintal, arXiv:2303.11317, 2023); un estudio no asintótico de heurísticas tipo Grover en MAX-k-SAT encontró que la aceleración por paso no se tradujo en ventaja práctica de corrida en los casos estudiados (Cade et al., Quantum 7, 1133, 2023). Ambos lados quedan linkeados; los teoremas de arriba no dependen de ninguno.

¿Por qué el big data es una pared y no una pista de despegue?

Porque antes de que un computador cuántico acelere nada, los datos tienen que entrar — y la entrada es donde la máquina es más débil. La comparación de Microsoft–ETH pone un canal de entrada cuántico optimista unas 10.000 veces por debajo del ancho de banda de memoria de una máquina clásica, y concluye que los computadores cuánticos serán prácticos para problemas de «mucho cómputo sobre datos chicos», no de big data (Hoefler, Häner y Troyer, CACM 66(5), 2023). El hardware que iba a arreglar esto — la QRAM — no existe a escala, como documentamos en nuestro post de QRAM. La letra chica algorítmica lo agrava: las cuatro condiciones de HHL (nuestro post de HHL) y la ola de desquantización que siguió al resultado de Tang de 2018 eliminaron los claims exponenciales para sistemas de recomendación, PCA y ML de bajo rango sobre datos clásicos (nuestro ledger de dequantización). Motores de recomendación, analítica de negocio, entrenar modelos grandes de lenguaje sobre texto clásico: no esperes nada del hardware cuántico aquí con ninguna evidencia publicada a la fecha.

¿Qué deberías esperar de cada tipo de máquina?

Nada fuera de su carril estructural — el punto de nuestro explicador analógico-vs-universal. Un simulador analógico no tiene conjunto de compuertas, así que jamás va a correr Shor ni Grover — una familia de Hamiltonianos por máquina, por construcción. Un annealer solo toma problemas con forma de optimización, y su claim insignia de ventaja sigue en un ciclo abierto de re-corridas. Un procesador de compuertas NISQ corre circuitos poco profundos bajo mitigación; el algoritmo que prometen los libros, la estimación de fase, tiene cero corridas a escala útil en el registro, como contamos en nuestro post de QPE. Y los vatios no rescatan el caso: en el único cara-a-cara con benchmark que encontró nuestro post de energía, la re-corrida clásica gastó menos energía, y no hay ventaja energética medida para una QPU en ninguna tarea a la fecha.

¿Y entonces dónde sí deberías esperar aceleración real?

En un carril corto, y en tiempo futuro. Simular sistemas cuánticos — química, materiales, materia condensada — sigue siendo el caso más fuerte en todos los análisis serios, incluidos los escépticos (Hoefler et al. 2023); el asterisco honesto es que para química de estado fundamental en particular, un estudio liderado por Caltech y Google concluyó que la evidencia de ventaja exponencial «aún no se ha encontrado», con aceleraciones polinomiales todavía plausibles (Lee et al., Nat. Commun. 14, 1952, 2023). La factorización y los logaritmos discretos caerán ante Shor cuando exista una máquina tolerante a fallos — el conteo de recursos y el reloj viven en nuestro post de RSA-2048. Un mapa secundario fresco llega a la misma partición: la Quantum Utility Ladder publicada en mayo de 2026 (actualizada en agosto de 2026) pone la simulación física como el carril tolerante a fallos más fuerte y llama a las aplicaciones de aceleración cuadrática en finanzas y logística «no competitivas contra heurísticas clásicas masivamente paralelizadas» (postquantum.com). El marcador propio de Rosetta Quantum es el resumen más filoso que podemos ofrecer: advantaged solves verificados en nuestro ledger, en todas las clases de problema de esta página, a la fecha: 0.

Qué no sabemos

No sabemos que estas separaciones valgan en absoluto: NP ⊄ BQP es una conjetura respaldada por evidencia de oráculo, no un teorema — una prueba en cualquier dirección redibujaría la teoría de la complejidad, y los techos del modelo de consulta acotan algoritmos de caja negra, no todo ataque estructurado concebible. No sabemos que los sobrecostos de corrección de errores de hoy sean finales: los propios Babbush et al. marcan que una mejora significativa en corrección de errores reabriría la clase cuadrática (PRX Quantum 2, 010103, 2021) — el ×360 es una afirmación sobre códigos de superficie al 2020, no sobre la física. No sabemos hacia qué lado corta la próxima sorpresa algorítmica: la dequantización borró claims cuánticos, pero podrían aparecer algoritmos cuánticos nuevos — Rosetta Quantum re-verificará los veredictos de esta página y los actualizará, con fecha, cuando se muevan. Y una nota de alcance: los techos citados aquí son de la literatura, no de nuestra mesa — nuestro propio negativo de casa (una caminata cuántica perdiendo contra propagadores clásicos a presupuesto emparejado, p = 0,095) es un dato sobre una familia de instancias, y la disputa de la compilación de Grover no la hemos medido nosotros.

Rosetta Quantum publica veredictos con datos crudos reproducibles. Esto es contenido educativo, no un claim de producto.