Is contextuality the resource behind quantum computational speedup?
46No. 878 in all physics · No. 44 in Quantum Information and Foundations
For magic-state injection with odd-prime-dimension qudits, contextuality of the injected state is necessary for universal quantum computation (Howard, Wallman, Veitch, Emerson, Nature 2014). Determine whether an analogous necessity theorem holds for qubits, where stabilizer operations are themselves state-independently contextual, and for measurement-based and Hamiltonian models, with a quantitative relation between a contextuality measure and classical simulation cost.
What would settle it
A theorem tying a contextuality monotone to classical simulation cost for qubit circuits, with matching simulation algorithms.
No solutions, ideas or subproblems yet.
Details, signature and history
- Kind
- Phenomenon to explain
- Answer
- Mechanism
- Posed
- 2014
- Topic review
- Budroni, Cabello, Guhne, Kleinmann, Larsson, Kochen-Specker contextuality, Reviews of Modern Physics, 2022. Link
- Record
- Revision 1 · imported from the seed collection · compiled by AI, not yet reviewed by an editor
Proof
- Fingerprint
- e06cf3105fac…
- Public log
- Entry 1,982, 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.
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.