Allen School Colloquium: Why Can’t We Classically Describe Quantum Systems?

Why It Matters

The NLTS breakthrough proves that even approximate low‑energy quantum states lack efficient classical representations, cementing a fundamental barrier to classical simulation and underscoring the essential role of quantum computers in tackling many‑body physics.

Key Takeaways

• NLTS conjecture resolved, proving no low‑energy classical proofs.
• Quantum states require exponential description due to entanglement.
• Local Hamiltonians have polynomial‑size descriptions but hard to solve.
• Approximate low‑energy states likely lack efficient classical representations.
• Complexity links description length to entanglement structure in quantum systems.

Summary

The colloquium centered on a fundamental question: why classical computers cannot efficiently describe quantum many‑body systems. Chin‑Mai highlighted the recent breakthrough on the No‑Low‑Energy‑Trivial‑States (NLTS) conjecture, which shows that even approximate low‑energy ground states of certain local Hamiltonians resist any short classical description. This result builds on earlier work by Kitaev proving exact ground‑state descriptions are QMA‑hard, and it sharpens the boundary between what quantum physics can be simulated classically and what remains intrinsically quantum.

The talk explained that a generic n‑qubit state lives in a 2^n‑dimensional vector space, making its naïve description exponentially large. Entanglement is the core obstacle: unlike classical bits, quantum particles cannot be described independently, so the overall state’s description length grows with the entanglement structure. While the Hamiltonian governing a physical system often has a compact, polynomial‑size specification—being a sum of local terms—the corresponding low‑energy eigenstates can encode highly complex correlations. The speaker argued that for the NLTS family of Hamiltonians, every state with energy below a constant fraction of the system size still requires a super‑polynomial classical description.

Illustrative examples included the Bell pair, which cannot be reduced to separate coin flips, and Feynman's insight that either a quantum computer is needed to simulate many‑body physics or the underlying description must be dramatically simpler. By framing low‑energy states as quantum analogues of constraint‑satisfaction problems, the talk connected condensed‑matter ground‑state physics to computational complexity theory, showing that even approximate solutions inherit the hardness of the underlying quantum CSP.

The implications are twofold: first, they set rigorous limits on classical simulation techniques for realistic materials, reinforcing the promise of quantum computers for studying condensed‑matter phenomena. Second, they provide a new lens for evaluating quantum algorithms, as any efficient classical representation would contradict the NLTS result, thereby guiding both theoretical research and practical expectations for near‑term quantum devices.

Original Description

Title: Why can’t we classically describe quantum systems?

Speaker: Chinmay Nirkhe, UC Berkeley (IBM Quantum)

Date: March 2, 2023

Abstract: A central goal of physics is to understand the low-energy solutions of quantum interactions between particles. This talk will focus on the complexity of describing low-energy solutions; Dr. Nirkhe will show that we can construct quantum systems for which the low-energy solutions are highly complex and unlikely to exhibit succinct classical descriptions. He will discuss the implications these results have for robust entanglement at constant temperature and the quantum PCP conjecture. En route, he will discuss our positive resolution of the No Low-energy Trivial States (NLTS) conjecture on the existence of robust complex entanglement.

Mathematically, for an n-particle system, the low-energy states are the eigenvectors corresponding to small eigenvalues of an exp(n)-sized matrix called the Hamiltonian, which describes the interactions between the particles. Low-energy states are the quantum generalizations of approximate solutions to satisfiability problems such as 3-SAT. In this talk, Dr. Nirkhe will discuss the theoretical computer science techniques used to prove circuit lower bounds for all low-energy states. This morally demonstrates the existence of Hamiltonian systems whose entire low-energy subspace is robustly entangled.

Bio: Chinmay Nirkhe is a research staff scientist with IBM Quantum at the MIT-IBM Watson AI Lab, primarily focusing on the intersection of computational complexity theory and quantum computation. Some of his research interests include error correction, hardness of approximation, and demonstrations of quantum/classical separations. His favorite open questions are the quantum PCP conjecture and whether QCMA equals QMA. He received his Ph.D. in Computer Science from UC Berkeley and his B.S. in Mathematics and Computer Science from Caltech.

This talk is in the process of being closed captioned.