A flexible optimisation framework, not guaranteed superiority
Performance depends on circuit depth, parameter training, graph structure, noise and the classical comparison.
Algorithms
Which Problems Can Quantum Computers Solve Faster? Algorithms, Evidence and Limitations
A separation of mathematically established speedups, promising applications, caveat-heavy heuristics and workloads unlikely to benefit.
Written by QuantumNews Research Desk Editorially reviewed by QuantumNews Research Desk Last reviewed: 14 July 2026 28 min read
⚡ Quantum Brief
Quantum computers have proven theoretical speedups for specific problem structures, including integer factorisation with Shor’s algorithm, unstructured search with Grover’s algorithm and simulation of quantum systems. Some linear-algebra, sampling and estimation problems also have quantum speedups under important assumptions. That does not mean today’s hardware solves useful instances faster. Optimisation, machine learning, finance, logistics and drug discovery remain promising but generally unproven as broad commercial advantages once data loading, output, error correction and the best classical alternatives are included.
Key takeaways
- A theoretical speedup is a statement about scaling in a mathematical model, not a current product benchmark.
- Input preparation, output extraction and error correction can dominate an apparent algorithmic gain.
- Shor and Grover provide different kinds of speedup and require fault-tolerant resources at useful scale.
- QAOA, VQE and quantum machine learning are research families, not guaranteed advantage mechanisms.
- Most ordinary software has no known reason to run faster on a quantum computer.
On this page
Problems with Proven Algorithmic SpeedupsPromising but Unproven Commercial AdvantagesMethods That Need Important CaveatsProblems Quantum Computers Probably Will Not ImproveSeven Questions for Any Speedup ClaimFrequently asked questionsProblems with Proven Algorithmic Speedups
“Proven” here refers to algorithmic complexity under stated models, not demonstrated economic advantage on current hardware.
| Problem | Quantum approach | Speedup and qualification |
|---|---|---|
| Integer factorisation / discrete logarithms | Shor’s algorithm | Polynomial-time quantum algorithms versus best known classical sub-exponential methods; large fault-tolerant circuits required |
| Unstructured search | Grover / amplitude amplification | Quadratic query reduction, not exponential; oracle and error-correction costs matter |
| Quantum-system simulation | Hamiltonian simulation and phase estimation | Potential exponential representation advantage for suitable quantum systems; state preparation and observables matter |
| Selected linear algebra | Quantum linear-system algorithms | Strong asymptotic gains under sparsity, conditioning, state-input and quantum-output assumptions |
| Amplitude estimation | Coherent estimation algorithms | Quadratic sampling improvement in ideal settings; deep controlled operations can be expensive |
Promising but Unproven Commercial Advantages
| Area | Why quantum is explored | What remains unproven |
|---|---|---|
| Combinatorial optimisation | Quantum search, annealing and variational heuristics | Consistent end-to-end advantage over specialist classical solvers |
| Machine learning | Quantum kernels, sampling and linear-algebra subroutines | Efficient data access and advantage over rapidly improving classical ML |
| Finance | Amplitude estimation, optimisation and generative modelling | Realistic constraints, precision and total runtime advantage |
| Logistics | Large routing and scheduling search spaces | Encoding and solution quality against mature heuristics |
| Drug discovery | Quantum chemistry and sampling components | A benefit across the complete discovery and experimental pipeline |
| Materials engineering | Electronic-structure and dynamics calculations | Resource-efficient calculations at decision-relevant accuracy |
Methods That Need Important Caveats
Useful for experiments, but scaling is difficult
Measurement cost, optimiser behaviour, ansatz quality and noise can erase practical benefit.
Quantum models do not automatically beat classical AI
Data encoding, trainability, sample complexity and fair baselines must be addressed.
Theoretical amplitude-estimation gains require coherent depth
Fault-tolerant resource cost and loading the probability model can determine viability.
Problems Quantum Computers Probably Will Not Improve
| Workload | Why classical remains appropriate |
|---|---|
| Web browsing and email | Networking, rendering, storage and user interaction have no known quantum advantage |
| Ordinary databases | Classical memory and database engines efficiently return full records; quantum readout is constrained |
| Basic arithmetic | Classical processors perform routine arithmetic cheaply and reliably |
| Office software | The workload is general control, text, graphics and storage rather than a quantum-suitable kernel |
| Most conventional programs | Rewriting as reversible quantum circuits adds overhead without a known algorithmic benefit |
Seven Questions for Any Speedup Claim
- 1
What is the exact problem?
Name input, output, size, constraints and required precision.
- 2
What quantum algorithm is used?
Separate a proven algorithm from a heuristic or analogy.
- 3
What is the classical baseline?
Use the best relevant algorithm and realistic hardware.
- 4
How is data loaded?
Account for state preparation or oracle construction.
- 5
How is the answer read out?
A quantum state is not automatically a full classical data structure.
- 6
What hardware is required?
Report logical qubits, gates, depth, error rate and runtime—not only physical qubits.
- 7
What evidence exists?
Label theory, simulation, hardware experiment, independent replication and production evidence separately.
Frequently asked questions
What is the main problem quantum computers can solve faster?
Integer factorisation is the best-known dramatic example because Shor’s algorithm changes the asymptotic complexity. Useful cryptographic sizes still require large fault-tolerant hardware.
Can quantum computers solve NP-complete problems quickly?
No general efficient quantum algorithm is known for NP-complete problems. Grover-style search gives a quadratic improvement, which does not make exponential search polynomial.
Can quantum computers optimise logistics?
They can run optimisation experiments and heuristics, but broad practical advantage over advanced classical solvers has not been established.
Does a quantum speedup mean the result is useful?
No. The problem may be artificial, the input small, the accuracy irrelevant or the full workflow more expensive than a classical alternative.
Can quantum computers solve every difficult problem faster?
No. Computational difficulty alone does not imply a quantum speedup. A useful quantum algorithm must exploit specific mathematical structure, and many hard problems have no known substantial quantum advantage.
Related answers
Methodology
QuantumNews separates demonstrated results from vendor targets and forecasts. Technical claims are checked against primary research, official documentation and disclosed benchmark conditions. Metrics from different hardware architectures are not treated as directly interchangeable.
Update history
14 July 2026 — Initial detailed editorial draft created for review.
Corrections
Found an error or newer technical evidence? Contact the QuantumNews editorial team.
References
- Algorithms for quantum computation: discrete logarithms and factoring Peter Shor / IEEE
- A fast quantum mechanical algorithm for database search Lov Grover / ACM
- Quantum algorithms: an overview Ashley Montanaro / npj Quantum Information
- Quantum computational advantage with a programmable photonic processor Nature