The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.For example, we extract the stabiliser tableau of a 2n×2n matrix, promised to be a Clifford gate, in O(n2n) time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.We provide implementations of our algorithms in Python and C++ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from
O(elln2) to
O(mn2), where
ell is the total number of gates in the circuit, and
m is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever
ellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of
ketpsiotimesm, where
ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state
ketpsi, we find stabilizer decompositions of
ketpsiotimesm with
2mlog2(3)/4 terms. This improves on the best known bound of
2mlog2(7)/6. \nSimilarly, for any single qubit equatorial state
ketpsi, we give a stabilizer decomposition of
ketpsiotimesm with
2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail,
d-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo
d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd
d, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even
d case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.
Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only
2αt stabiliser terms, where
α≈0.396, to simulate a circuit with T-count
t. This matches the
α found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.
Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.
The stabiliser formalism is a widely used and successful subtheory of quantum mechanics consisting of stabiliser states, Clifford unitaries and Pauli measurements. The power of the formalism comes from the description of its elements via simple group theory. Although the origins of the formalism lie in quantum error correction and fault-tolerant quantum computing, the utility of the formalism goes beyond that. The Gottesman-Knill theorem states that the dynamics of stabiliser states under Clifford unitaries and Pauli measurements can be efficiently simulated on a classical computer. This algorithm can be extended to arbitrary states and unitaries in multiple ways at the cost of an increased runtime. This runtime can be seen as a quantification of the non-stabiliser resources needed to implement a quantum circuit. Moreover, as non-stabiliser elements are necessary for universal quantum computing, the runtime provides a way to measure the “non-classicality” of a computation. This is particularly pronounced in the magic state model of quantum computing where the only non-stabiliser elements are given by magic states. Hence, in the resource theory of magic, resources are measured through magic monotones which are operationally linked to runtimes of classical simulation algorithms. In this thesis, I discuss different aspects of the resource theory of magic. The mentioned classical simulation algorithms require the computation of magic monotones which is in general a computationally intractable problem. However, I show that the computational complexity can be exponentially reduced for certain classes of symmetric states, such as copies of magic states. To this end, the symmetries of the convex hull of stabiliser states are characterised and linked to their properties as so-called designs. In addition, I study the recently introduced class of completely stabiliser-preserving channels (CSP), which is the class of quantum channels unable to generate magic resources. It is shown that this class is strictly larger than the class of stabiliser operations, composed of Clifford unitaries and Pauli measurements. This finding could have several interesting consequences. First, it implies that there is a class of efficiently simulable quantum channels beyond the Gottesman-Knill theorem. Second, it is possible that optimal magic state distillation rates cannot be achieved via stabiliser operations and this gap is in fact significant. Further applications of the stabiliser formalism come through design theory. A unitary t-design is an ensemble of unitaries which reproduce the first t moments of the Haar measure on the unitary group. Randomness in the form of Haar-random unitaries is an essential building block in many quantum information protocols. Implementing such Haar-random unitaries is however often impractical. Here, designs can exhibit considerably lower resource requirements while still being random enough for most applications. Some of the most prominent examples of such protocols concern the certification and characterisation of quantum systems, such as randomised benchmarking. Interestingly, the group of Clifford unitaries forms a unitary 3-design and is often the prime choice thanks to efficient group operations. In this thesis, I summarise my recent results obtained with collaborators in constructing approximate unitary t-designs from the Clifford group supplemented by only few non-Clifford gates. Intriguingly, this construction uses only O(t^4) single qubit non-Clifford gates and is independent of the number of qubits n. Overall, this yields a gate count which is a significant improvement over for the Brandao-Harrow- Horodecki construction based on local random circuits. To provide context for this result, I review the representation theory of the Clifford group and define the Clifford semigroup. In an attempt to generalise approximations results for the unitary group to the Clifford group, the Clifford semigroup is investigated for suitable approximations of the Clifford twirl.
The stabiliser fragment of quantum theory is a foundational building block for quantum error correction and the fault-tolerant compilation of quantum programs. In this article, we develop a sound, universal and complete denotational semantics for stabiliser operations which include measurement, classically-controlled Pauli operators, and affine classical operations, in which quantum error-correcting codes are first-class objects. The operations are interpreted as certain affine relations over finite fields. This offers a conceptually motivated and computationally-tractable alternative to the standard operator-algebraic semantics of quantum programs (whose time complexity grows exponentially as the state space increases in size). We demonstrate the power of the resulting semantics by describing a small, proof-of-concept assembly language for stabiliser programs with fully-abstract denotational semantics.