Source-linked AI summary
Contextuality supplies the magic for quantum computation
Mark Howard, Joel J. Wallman, Victor Veitch, Joseph Emerson
TL;DR
The paper addresses which uniquely quantum resources enable computational advantages, a question left unresolved by proposals involving superposition, entanglement, and discord. Using the CSW graph-theoretic framework and stabilizer measurements, it proves that state-dependent contextuality coincides with the possibility of universal quantum computation via magic state distillation for odd-prime qudits.
Problem
Which uniquely quantum resources enable quantum computational advantages remains unresolved, despite proposals involving quantum parallelism, entanglement, and discord.
Method
The paper uses the CSW connection between contextuality and graph theory to construct stabilizer-measurement noncontextuality inequalities and characterize relevant quantum states.
Results
For qudits of odd prime dimension, exactly the states outside PSIM exhibit contextuality in the construction, matching the conditions for quantum speed-up via magic state distillation.
Takeaways & Limitations
The result gives contextuality an operational meaning as necessary and possibly sufficient for the magic enabling universal quantum computation in qudits.
Takeaways & Limitations
For qubits, contextuality alone is insufficient, while for qudits the sufficiency of contextuality for magic-state distillation remains an open problem.
Abstract
from arXiv · showhide
Quantum computers promise dramatic advantages over their classical counterparts, but the answer to the most basic question "What is the source of the power in quantum computing?" has remained elusive. Here we prove a remarkable equivalence between the onset of contextuality and the possibility of universal quantum computation via magic state distillation. This is a conceptually satisfying link because contextuality provides one of the fundamental characterizations of uniquely quantum phenomena and, moreover, magic state distillation is the leading model for experimentally realizing fault-tolerant quantum computation. Furthermore, this connection suggests a unifying paradigm for the resources of quantum information: the nonlocality of quantum theory is a particular kind of contextuality and nonlocality is already known to be a critical resource for achieving advantages with quantum communication. In addition to clarifying these fundamental issues, this work advances the resource framework for quantum computation, which has a number of practical applications, such as characterizing the efficiency and trade-offs between distinct theoretical and experimental schemes for achieving robust quantum computation and bounding the overhead cost for the classical simulation of quantum algorithms.