This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. Moreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. We believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.

This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. Moreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. We believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.

Topological order is a new field of research involving exotic physics. Among other things it has been suggested as a means for realising fault-tolerant quantum computation. Topological degeneracy, i.e. the ground state degeneracy of a topologically ordered state, is one of the quantities that have been used to characterize such states. Topological order has also been suggested as a possible quantum information storage. We study two-dimensional lattice models defined on a closed manifold, specifically on a torus, and find that these systems exhibit topological degeneracy proportional to the genus of the manifold on which they are defined. We also find that the addition of lattice dislocations increases the ground state degeneracy, a behaviour that can be interpreted as artificially increasing the genus of the manifold. We derive the fusion and braiding rules of the model, which are then used to calculate the braiding properties of the dislocations themselves. These turn out to resemble non-abelian anyons, a property that is important for the possibility to achieve universal quantum computation. One can also emulate lattice dislocations synthetically, by adding an external field. This makes them more realistic for potential experimental realisations. / Topologisk ordning är ett nytt område inom fysik som bland annat verkar lovande som verktyg för förverkligandet av kvantdatorer. En av storheterna som karakteriserar topologiska tillstånd är det totala antalet degenererade grundtillstånd, den topologiska degenerationen. Topologisk ordning har också föreslagits som ett möjligt sätt att lagra kvantdata. Vi undersöker tvådimensionella gittermodeller definierade på en sluten mångfald, specifikt en torus, och finner att dessa system påvisar topologisk degeneration som är proportionerlig mot mångfaldens topologiska genus. När dislokationer introduceras i gittret finner vi att grundtillståndets degeneration ökar, något som kan ses som en artificiell ökning av mångfaldens genus. Vi härleder sammanslagningsregler och flätningsregler för modellen och använder sedan dessa för att räkna ut flätegenskaperna hos själva dislokationerna. Dessa visar sig likna icke-abelska anyoner, en egenskap som är viktiga för möjligheten att kunna utföra universella kvantberäkningar. Det går också att emulera dislokationer i gittret genom att lägga på ett yttre fält. Detta gör dem mer realistiska för eventuella experimentella realisationer.