This thesis explores the resource of “magic”, and the use of Majorana fermions, in quantum many-body physics and quantum computing. Along with other quantum resources, magic helps determine the advantage that a quantum circuit can display over classical computation. For the components of the quantum computer itself, Majorana fermions offer promising theoretical advantages, owing to their fermionic nature and noise characteristics.

A tool used throughout this thesis is the Pauli-based model of computation (PBC). We extend this model to the regime of fermionic computation, establishing the analogous “fermion-parity-based computation” (FPBC). We develop certain conceptual tools in fermionic computation, including the idea of a “logical Majorana fermion”, which is used throughout this thesis. We find several results that relate to the ease of implementing PBC or FPBC directly, and which relate the magic of (F)PBC to that of the original circuit.

We apply these insights to study the dynamics of magic in random quantum systems. We use PBC to identify a phase transition in the magic produced by (and its spread in) random quantum circuits. We relate this transition to previously found phase transitions in entanglement, providing further insight into the purported transition in classical simulability of these systems.

We then assess the capabilities of Majorana systems for implementing (F)PBC. We introduce a hardware model with which one can measure arbitrary fermion parities directly, within certain bounds of locality, thus removing an obstacle to (F)PBC present in existing designs.

To further investigate noise-reduction methods in large-scale Majorana-based quantum computing, we perform an in-depth investigation of “Majorana surface codes” as intriguing models of both quantum error-correcting codes and fermionic topological quantum matter. We provide a categorisation of anyonic excitations, boundaries and “twist defects” (lattice defects that can store quantum information) in these codes. Finding that twist defects can store logical Majorana fermions, as well as regular logical qubits expected, we introduce methods for computing with all topologically protected degrees of freedom in the code. We introduce new computing techniques. We finally discuss avenues towards improved quantum resource costs, potential implementations and connections to other codes.