# The Complexity of NISQ

arXiv: https://arxiv.org/abs/2210.07234 · HTML: https://mlsanity.com/paper/2210.07234/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 101 references that are in the map.
- First posted on arXiv 13 Oct 2022.

## Builds on (most cited first, 17 of 17)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Noise-Induced Barren Plateaus in Variational Quantum Algorithms](https://mlsanity.com/paper/2007.14384/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era](https://mlsanity.com/paper/2102.05321/) (2021)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing](https://mlsanity.com/paper/1601.03030/) (2016)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [Verifiable Quantum Advantage without Structure](https://mlsanity.com/paper/2204.02063/) (2022)
- [Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models](https://mlsanity.com/paper/2204.10306/) (2022)

## Built on by (most cited first, 13 of 13)

- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Ansatz-free Hamiltonian learning with Heisenberg-limited scaling](https://mlsanity.com/paper/2502.11900/) (2025)
- [Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises](https://mlsanity.com/paper/2405.00770/) (2024)
- [Addressing the Current Challenges of Quantum Machine Learning through Multi-Chip Ensembles](https://mlsanity.com/paper/2505.08782/) (2025)
- [Hybrid Quantum Neural Networks for Efficient Protein-Ligand Binding Affinity Prediction](https://mlsanity.com/paper/2509.11046/) (2025)
- [Quantum Information Fusion and Correction under the Transferable Belief Model](https://mlsanity.com/paper/2410.08949/) (2024)
- [QuantEIT: Ultra-Lightweight Quantum-Assisted Inference for Chest Electrical Impedance Tomography](https://mlsanity.com/paper/2507.14031/) (2025)
- [QAISim: A Toolkit for Modeling and Simulation of AI in Quantum Cloud Computing Environments](https://mlsanity.com/paper/2512.17918/) (2025)
- [QASM-Eval: A Dataset to Train and Evaluate LLMs on OpenQASM-3 Beyond Quantum Circuits](https://mlsanity.com/paper/2605.30358/) (2026)

## Abstract (arXiv)

The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class textsfNISQ , which is intended to encapsulate problems that can be efficiently solved by a classical computer with access to a NISQ device. To model existing devices, we assume the device can (1) noisily initialize all qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement on all qubits. We first give evidence that textsfBPPsubsetneq textsfNISQsubsetneq textsfBQP, by demonstrating super-polynomial oracle separations among the three classes, based on modifications of Simon's problem. We then consider the power of textsfNISQ for three well-studied problems. For unstructured search, we prove that textsfNISQ cannot achieve a Grover-like quadratic speedup over textsfBPP. For the Bernstein-Vazirani problem, we show that textsfNISQ only needs a number of queries logarithmic in what is required for textsfBPP. Finally, for a quantum state learning problem, we prove that textsfNISQ is exponentially weaker than classical computation with access to noiseless constant-depth quantum circuits.