Robert Raussendorf

An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd.The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space.The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.

View record

We consider ground states of quantum spin chains with symmetry-protected topological (SPT) order as resources for measurement-based quantum computation (MBQC). Using tensor network methods, we show that SPT phases protected by a finite abelian on-site symmetry group exhibit uniform computational power. That is, any state from a given phase leads to the same Lie group of executable gates when used as a resource for MBQC. This Lie group is determined by the same algebraic information that labels the SPT phase itself, and we give a necessary condition on the phase that guarantees a full set of single-qubit gates. To obtain our results, we construct several new techniques in MBQC and refine the structure of quantum states with abelian SPT order. Our results are analogous to similar results relating topological order and topological quantum computation, and we comments on their implications on the general connection between quantum phases of matter and quantum computation.

View record

Realism defined in EPR paper as “In a complete theory there is an element corresponding to each element of reality.” Bell showed that there is a forbidden triangle (Realism, Quantum Statistics, and Locality), and we are only allowed to pick two out of three. In this thesis, we investigate other inequalities and no-go theorems that we face. We also discuss possible Hidden Variable Models that are tailored to be consistent with Quantum Mechanics and the specific no-go theorems. In the special case of the Leggett Inequality the proposed hidden variable is novel in the sense that the hidden variable is in the measurement device rather than the wave-function.

View record

We study the resources necessary for quantum computation with rebits (qubit states with real amplitudes in the standard basis). We introduce a scheme for universal quantum computation by state injection, and define a Wigner function appropriate for this scheme. We show that the Wigner function obeys a Hudson’s theorem and transforms covariantly under CSS-ness preserving unitary gates; these results allows us to establish that Wigner function negativity is necessary for quantum computation. Furthermore, we establish contextuality as another necessary computational resource. We show that in contrast with the case of qudits [M. Howard et al., Nature 510, 351 (2014)], negativity does not imply contextuality. We discuss state independent contextuality and why it does not arise in our computational scheme.

View record