Which problems will quantum computing NOT accelerate?

TL;DR (September 28, 2026): Most of what computers do all day will not get faster on a quantum computer. Three ceilings are proven theorems in the query model: unstructured search gains at most Grover's quadratic √N factor, proven optimal in 1997 (Bennett–Bernstein–Brassard–Vazirani, SIAM J. Comput. 26, 1510); computing the parity of n bits saves at most a factor of two (Beals et al., J. ACM 48, 778, 2001); comparison sorting stays at n log n (Høyer, Neerbek & Shi, Algorithmica 34, 429, 2002). On error-corrected hardware the quadratic class even inverts its sign: Google's own compilation study put quantum-accelerated annealing at ≈1 day on ≈1 million physical qubits for spin glasses that classical annealing solves in ≈4 CPU-minutes (Sanders et al., PRX Quantum 1, 020312, 2020) — ×360 slower, by Rosetta Quantum's own declared arithmetic on those two published figures. The honest lane where exponential acceleration will still be expected is narrow: simulating quantum systems and breaking specific cryptography — both in the future tense.

Why is “tries every answer at once” the wrong starting point?

Because a quantum computer that “tried every answer in parallel” would still have to hand you one: measurement collapses the superposition to a single outcome, and the art of a quantum algorithm is arranging interference so the wrong answers cancel — something that only works for problems with the right structure. We unpacked that mechanism in our qubit explainer. The myth matters here because it predicts the opposite of this post: if superposition were parallel brute force, NP-complete optimization would fall first. The published record since 1997 says it will not — and that record, not the myth, is what a buyer should price in.

Which ceilings are proven theorems, not opinions?

At least four, all in the black-box (query) model, and the youngest is 24 years old. Unstructured search: any quantum algorithm needs Ω(√N) oracle queries, so Grover's 1996 algorithm is optimal and the speedup is quadratic, never exponential (BBBV, SIAM J. Comput. 26, 1510, 1997). Parity: computing the parity of n bits takes at least n/2 quantum queries — a maximum saving of ×2 over classical (Beals et al., J. ACM 48, 778, 2001). Comparison sorting: at least ≈0.110·n·log₂n comparisons, so the classical n log n bound survives quantum (Høyer, Neerbek & Shi, Algorithmica 34, 429, 2002). Ordered (binary) search: at least ≈0.220·log₂N queries — a constant-factor gain only, from the same paper. The fine print Rosetta always attaches: these are query-model bounds — they cap any algorithm that treats the problem as a black box; they say nothing about exploiting a problem's internal structure, which is exactly where the few real quantum wins live.

Why won't quantum computing crack NP-complete optimization?

Because BQP — the class of problems a quantum computer solves efficiently — is not believed to contain the NP-complete problems, and the evidence is as old as the field: relative to a random oracle, NP is outside BQP with probability 1 (BBBV 1997). Scott Aaronson made this the centerpiece of his 2008 case that NP-complete problems are “probably not” efficiently solvable by quantum computers (Scientific American 298(3), 62–69, 2008). What quantum offers exact NP-complete optimization is Grover on the brute-force tree — the √N of our Grover explainer, applied to an exponentially large N, which leaves an exponential runtime. Route planning, scheduling, portfolio selection at scale: the honest expectation is that quantum will compete against classical heuristics that are already excellent, not that it will make the exponential disappear.

Why does even the quadratic speedup die on real hardware?

Because error correction charges overhead per step, and a √N advantage buys too few steps back. The numbers are from the vendor side of the ledger, not from skeptics: Google's own team compiled quantum-accelerated simulated annealing for early fault-tolerant processors and reported it “would require roughly a day and a million physical qubits” on spin glasses that classical annealing solves “in about four CPU-minutes” (Sanders et al., PRX Quantum 1, 020312, 2020) — the ×360 on our cover is those two figures divided, our arithmetic, declared. The same group concluded a year later that “quadratic speedups will not enable quantum advantage on early generations” of fault-tolerant machines, and that quartic speedups look significantly more practical (Babbush et al., PRX Quantum 2, 010103, 2021). An independent Microsoft–ETH analysis reached the same partition from raw throughput — a single classical GPU delivers 10¹⁰–10¹³ times more operations per second than an optimistic error-corrected machine, so with a quadratic speedup “even a single floating point or integer operation leads to crossover times of several months”, and “at least cubic or quartic speedups” are required (Hoefler, Häner & Troyer, Commun. ACM 66(5), 82–87, 2023). There is a live debate about whether Grover survives at all outside the black-box setting: one paper argues compiled oracles remove the a-priori advantage (Stoudenmire & Waintal, arXiv:2303.11317, 2023); a non-asymptotic study of Grover-type heuristics on MAX-k-SAT found the per-step speedup did not translate into a practical runtime advantage for the cases studied (Cade et al., Quantum 7, 1133, 2023). Both sides are linked; the theorems above do not depend on either.

Why is big data a wall, not a runway?

Because before a quantum computer accelerates anything, the data has to get in — and input is where the machine is weakest. The Microsoft–ETH comparison puts an optimistic quantum input channel around 10,000× below a classical machine's memory bandwidth, and concludes quantum computers will be practical for “big compute” problems on small data, not big-data problems (Hoefler, Häner & Troyer, CACM 66(5), 2023). The hardware that was supposed to fix this — QRAM — does not exist at scale, as we documented in our QRAM post. The algorithmic fine print compounds it: HHL's four conditions (our HHL post) and the dequantization wave that followed Tang's 2018 result removed the exponential claims for recommendation systems, PCA and low-rank ML on classical data (our dequantization ledger). Recommendation engines, business analytics, training large language models on classical text: expect nothing from quantum hardware here on any published evidence to date.

What should you expect from each machine type?

Nothing outside its structural lane — the point of our analog-vs-universal explainer. An analog simulator has no gate set, so it will never run Shor or Grover — one Hamiltonian family per machine, by construction. An annealer is optimization-shaped only, and its flagship advantage claim is still in an open re-run cycle. A gate-based NISQ processor runs shallow circuits under mitigation; the algorithm the textbooks promise, phase estimation, has zero useful-scale runs on record, as we counted in our QPE post. And watts do not rescue the case: in the only benchmarked head-to-head our energy post found, the classical re-run used less energy, and there is no measured energy advantage for a QPU on any task to date.

So where should you still expect real acceleration?

In a short lane, and in the future tense. Simulating quantum systems — chemistry, materials, condensed matter — remains the strongest case on every serious analysis, including the skeptical ones (Hoefler et al. 2023); the honest asterisk is that for ground-state chemistry specifically, a Caltech-Google-led study concluded evidence of exponential advantage “has yet to be found”, with polynomial speedups still plausible (Lee et al., Nat. Commun. 14, 1952, 2023). Factoring and discrete logarithms will fall to Shor when a fault-tolerant machine exists — the resource count and the timeline live in our RSA-2048 post. A fresh secondary map reaches the same partition: the Quantum Utility Ladder published in May 2026 (updated August 2026) ranks physical simulation as the strongest fault-tolerant lane and calls quadratic-speedup applications in finance and logistics “uncompetitive against massively parallelized classical heuristics” (postquantum.com). Rosetta Quantum's own scoreboard is the sharpest summary we can offer: verified advantaged solves on our ledger, across every problem class on this page, to date: 0.

What we don't know

We don't know that these separations hold absolutely: NP ⊄ BQP is a conjecture backed by oracle evidence, not a theorem — a proof either way would redraw complexity theory, and the query-model ceilings above cap black-box algorithms, not every conceivable structured attack. We don't know that today's error-correction overheads are final: Babbush et al. themselves flag that a significant improvement in error correction would re-open the quadratic class (PRX Quantum 2, 010103, 2021) — the ×360 is a statement about surface codes as of 2020, not about physics. We don't know which way the next algorithmic surprise cuts: dequantization erased quantum claims, but new quantum algorithms could appear — Rosetta Quantum will re-verify this page's verdicts and update them, dated, when they move. And a scope note: the ceilings cited here are the literature's, not our bench's — our own in-house negative (a quantum walk losing to classical propagators at matched budget, p = 0.095) is one data point on one instance family, and we have not measured the Grover-compilation dispute ourselves.

Rosetta Quantum publishes verdicts with raw, reproducible data. This is educational content, not a product claim.