Revision 1

Accepted · first revision · record

Title: Is contextuality the resource behind quantum computational speedup?
Plain: For quantum computers that draw their power from special 'magic' input states, contextuality was proved necessary for universal computing when the basic units have an odd prime number of levels. Whether this holds for ordinary qubits and other models is disputed.
Precise: 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.
Settled by: A theorem tying a contextuality monotone to classical simulation cost for qubit circuits, with matching simulation algorithms.
Kind: phenomenon
Answer type: mechanism
References: (empty)
Literature status: contested
Status note: (empty)
Posed since: 2014