What can quantum computers provably not do efficiently?
Some of the most useful results are negative ones.
We prove hardness and no-go theorems that identify limitations of popular approaches, so that research efforts become more targeted.
Quantum computing has attracted expectations that are, in places, not supported by evidence, and in some cases provably impossible to meet.
- Speed-ups are announced without a serious classical baseline.
- Heuristics that have never been shown to converge are presented as if they were algorithms.
- Timelines shorten with every funding round.
We consider honest expectation management to be part of our academic responsibility.
A hardness proof also tells what algorithm subroutines cannot be expected to be efficient without extra assumptions, and also often points to the assumption that has to be dropped for progress to happen.
Five questions for any quantum advantage claim
- Baseline.
Which classical algorithm is it compared against: the best available one, or a straw man?
The classical bar keeps rising, so a baseline from three years ago migth be today's baseline. - Asymptotics.
How does the quantum speed-up scale?
A quadratic speed-up is a real speed-up, but it is typically a too weak one once the constants are counted. - Constants.
What does error correction and the clock rate cost, and where does that put the break-even size?
This is where most quadratic speed-ups stop being useful.
[Schematic: classical run time rises steeply with problem size, quantum run time gently; they cross at the crossover size, and the crossover time has to fall inside the time you are willing to wait].
A speed-up is only useful if the crossover happens at a problem size you care about and within a time you are willing to wait. - Verification.
How do you know the result is correct?
A quantum computer is interesting precisely in the regime where no classical machine can check its output.
See [quantum system characterization].
Selected results
- Training variational quantum algorithms is NP-hard.
L. Bittel, M. Kliesch — [arXiv:2101.07267], Phys. Rev. Lett. 127, 120502 (2021). - Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate.
L. Bittel, S. Gharibian, M. Kliesch — [arXiv:2211.12519], CCC 2023, ([doi:10.4230/LIPIcs.CCC.2023.34]), 34:1–34:24. Also presented as a talk at QIP 2023, Ghent. - Sample complexity of device-independently certified quantum supremacy.
D. Hangleiter, M. Kliesch, J. Eisert, C. Gogolin — [arXiv:1812.01023], Phys. Rev. Lett. 122, 210502 (2019). - Matrix product operators and states: NP-hardness and undecidability.
M. Kliesch, D. Gross, J. Eisert — [arXiv:1404.4466], Phys. Rev. Lett. 113, 160503 (2014). - On computational complexity of unitary and state design properties.
Y. Nakata, Y. Takeuchi, M. Kliesch, A. Darmawan — [arXiv:2410.23353], PRX Quantum 6, 030345 (2025). - Sound certification of memory-bounded quantum computers.
J. Nöller, N. Miklin, M. Kliesch, M. Gachechiladze — [arXiv:2411.04215] (2024), preprint. Presented as a talk at TQC 2025, Bengaluru, and QCTiP 2025, Berlin. - A comprehensive benchmark of an Ising machine on the Max-Cut problem.
[arXiv:2507.22117], New J. Phys. (2026). - Stability of classical shadows under gate-dependent noise.
[arXiv:2310.19947], Phys. Rev. Lett. 134, 090801 (2025).
What this does not mean
We are not arguing that quantum computing is futile.
Shor's algorithm gives a superpolynomial speed-up over the best *known* classical factoring algorithms; a proven classical lower bound does not exist.
Grover's algorithm gives a provably optimal, but only quadratic, speed-up in the black-box model.
Quantum simulation of quantum systems is a natural and well-motivated application, and fault-tolerant architectures are advancing.
Our point is narrower: claims should be stated precisely, compared against the best available classical methods, and separated into what is proven, what is observed, and what is hoped for.
That separation is what our other research areas work on.
[Research overview ›]
