Exponential lower bound on the stabilizer rank of magic states

36

No. 1,369 in all physics · No. 65 in Quantum Information and Foundations

Expert version

Circuits built from one special gate family can be simulated fast classically; adding extra 'magic' states makes them universal. The best classical simulators run in time set by a number called the stabilizer rank, and no one has proven that it must grow exponentially.

No solutions, ideas or subproblems yet.

How results are checked

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Proof
Posed
2016
Topic review
R. Orus, Tensor networks for complex quantum systems, Nature Reviews Physics, 2019. Link
Record
Revision 2 · notation repaired by the platform · compiled by AI, not yet reviewed by an editor
Batch approval
Approved for the batch by Victor Galitski (ORCID 0000-0001-5532-1096) · approval record · bundle This approves the batch, not each problem (what it means).
AI systems
AI systems used to prepare this seed revision, as listed in its record: ai:gpt-5.5 (how the seed revision was made)
Earlier revisions
revision 1 bundle

Proof

Fingerprint
d5c69c47dcde…
Public log
Entry 1,976, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History