[JC] The Complexity of NISQ

Item: [JC] The Complexity of NISQ
Rating: 4
Author: PostSingularity Institute

by Sung-Bin B. Lee (이성빈)

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYXNatural computing

🎙 Sung-Bin B. Lee (이성빈) 👥 267 📅 January 30, 2026 ⏱ 38 min 👁 41 📄 literature review 🧭 2026-08-15

Available in: English (current) Français

Keywords

NISQcomplexity classquantum advantagedepolarizing noiseSimon's problem

Summary

This presentation, part of the QISCA Journal Club, introduces the complexity of Noisy Intermediate-Scale Quantum (NISQ) computers, based on the paper ‘The Complexity of NISQ’ by Chen et al. The speaker, Sung-Bin Lee, begins by reviewing known relationships in quantum complexity theory, such as P ⊆ BPP ⊆ BQP, and the power of post-selection. He then defines the NISQ complexity class, which involves circuits with single-qubit depolarizing noise, and explains that NISQ is stronger than BPP but weaker than BQP. The main results are proven using modified versions of Simon’s problem: a robustified version shows NISQ can achieve super-polynomial speedup over classical computers, while a lifted version shows NISQ requires exponentially more queries than fault-tolerant quantum computers. The presentation also covers the query complexity framework using tree representations and total variation distance, and discusses implications for practical problems like Grover’s algorithm, time-bassiard problem, and shadow tomography. The speaker emphasizes that for useful problems, noise rates must be exponentially small, while for less practical problems, constant noise rates suffice. The talk concludes with a summary of the key findings and encourages further reading of the original paper.

186 words

Critical Evaluation

Value of the Information & Strength of the Argument

The presentation provides a clear and structured overview of a complex theoretical topic. The speaker effectively explains the significance of the results and the intuition behind the proofs, even when skipping technical details. The argumentation is solid, as it follows the logical structure of the paper and highlights the key separations between complexity classes. The use of Simon’s problem as a central tool is well-motivated, and the discussion of practical implications adds value. However, the speaker admits to not fully understanding all derivations, which may limit the depth of the explanation. Overall, the information is valuable for those seeking an introduction to NISQ complexity, but it is not a substitute for reading the original paper.

Scientific Rigor, Source Quality, Title Accuracy

The presentation is based on a single, well-regarded source: the paper ‘The Complexity of NISQ’ by Chen et al., which was published in Nature Communications. The speaker accurately represents the main results and provides appropriate context. The title of the video matches the content, as it focuses on the complexity of NISQ. The presentation does not introduce original research but serves as a literature review. The speaker’s admission of not fully understanding all details is honest but indicates a potential limitation in the depth of the presentation. No comments were provided for analysis.

223 words

Title / Content Match

The title accurately reflects the content, which focuses on the computational complexity of noisy intermediate-scale quantum (NISQ) computers.

Quality & Reliability

7/10

The presentation is a faithful summary of a peer-reviewed paper (published in Nature Communications) by recognized researchers. The speaker admits to not fully understanding all technical details, which may introduce simplifications. The content is based on rigorous theoretical work, but the presentation itself is a secondary source.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

The Complexity of NISQ — The paper presented in the talk, providing the main results on NISQ complexity.

Concurring Sources

The Complexity of NISQ — The primary source, which the presentation summarizes.

Contribution & Novelties

The presentation offers a concise and accessible summary of a recent theoretical paper, making the complex results more approachable for a broader audience. It highlights the key separations between NISQ and classical/fault-tolerant quantum computers, and discusses practical implications. The speaker’s intuition-based explanations help demystify the proofs.

Pour aller plus loin :

Quantum complexity theory — Overview of complexity classes relevant to quantum computing.
Simon’s problem — The problem used as a basis for the separations.
Quantum error correction — CSS codes are used in the robustification argument.
Nature Communications paper — The published version of the paper (if available).

99 words

Radar Profile

The radar profile shows high scores in information quantity, quality, and technical level, with a slightly lower reliability score due to the presenter's admitted simplifications. This indicates a technically rich and informative presentation, but with some reliance on secondary interpretation.

Reliability 7/10