  A central question in quantum computation is to identify the resources that
are responsible for quantum speed-up. Quantum contextuality has been recently
shown to be a resource for quantum computation with magic states for odd-prime
dimensional qudits and two-dimensional systems with real wavefunctions. The
phenomenon of state-independent contextuality poses a priori an obstruction to
characterizing the case of regular qubits, the fundamental building block of
quantum computation. Here, we establish contextuality of magic states as a
necessary resource for a large class of quantum computation schemes on qubits.
We illustrate our result with a concrete scheme related to measurement-based
quantum computation.
