Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are physical barriers to implementing large quantum gates. Large Toffoli gates can be decomposed into equivalent sets of smaller, quantum elementary gates. The cost of a quantum circuit can be measured by counting the number of elementary gates in the circuit after all gates have been decomposed. Traditionally this decomposition is done independently for each gate in the circuit. This thesis identifies pairs of gates that, if decomposed together, result in fewer total elementary gates than they would otherwise. These improvements are incorporated into a simple decomposition algorithm which manipulates the circuit in order to search for such pairs. The decomposition algorithm is compared to a naive implementation, and the resulting gate costs are presented and compared.
It is known that a quantum circuit may be simulated with classical hardware via stabilizer state (T-)decomposition in [Formula: see text] time, given t non-Clifford gates and a decomposition efficiency [Formula: see text]. The past years have seen a number of papers presenting new decompositions of lower [Formula: see text] to reduce this runtime and enable simulation of ever larger circuits. More recently, it has been demonstrated that well-placed applications of apparently weaker (higher [Formula: see text]) decompositions can in fact result in better overall efficiency when paired with the circuit simplification strategies of ZX-calculus. In this work, we take the most generalized T-decomposition (namely vertex cutting), which achieves a poor efficiency of [Formula: see text] and identify common structures to which applying this can, after simplification via ZX-calculus rewriting, yield very strong effective efficiencies [Formula: see text]. By taking into account this broader scope of the ZX-diagram and incorporating the simplification facilitated by the well-motivated cuts, we derive a handful of efficient T-decompositions whose applicabilities are relatively frequent. In benchmarking these new ‘dynamic’ decompositions against the existing alternatives, we observe a significant reduction in overall [Formula: see text] and hence overall runtime for classical simulation, particularly for certain common circuit classes.
Abstract We introduce an enhanced technique for strong classical simulation of quantum circuits which combines the ‘sum-of-stabilisers’ method with an automated simplification strategy based on the ZX-calculus. Recently it was shown that quantum circuits can be classically simulated by expressing the non-stabiliser gates in a circuit as magic state injections and decomposing them in chunks of 2–6 states at a time, obtaining sums of (efficiently-simulable) stabiliser states with many fewer terms than the naive approach. We adapt these techniques from the original setting of Clifford circuits with magic state injection to generic ZX-diagrams and show that, by interleaving this ‘chunked’ decomposition with a ZX-calculus-based simplification strategy, we can obtain stabiliser decompositions that are many orders of magnitude smaller than existing approaches. We illustrate this technique to perform exact norm calculations (and hence strong simulation) on the outputs of random 50- and 100-qubit Clifford + T circuits with up to 70 T-gates as well as a family of hidden shift circuits previously considered by Bravyi and Gosset with over 1000 T-gates.
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.
A quantum circuit may be strongly classically simulated with the aid of ZX-calculus by decomposing its
t T-gates into a sum of
2αt classically computable stabiliser terms. In this paper, we introduce a general procedure to find an optimal pattern of vertex cuts in a ZX-diagram to maximise its T-count reduction at the cost of the fewest cuts. Rather than reducing a Clifford+T diagram based on a fixed routine of decomposing its T-gates directly (as is the conventional approach), we focus instead on taking advantage of certain patterns and structures common to such circuits to, in effect, design by automatic procedure an arrangement of spider decompositions that is optimised for the particular circuit. In short, this works by assigning weights to vertices based on how many T-like gates they are blocking from fusing/cancelling and then appropriately propagating these weights through any neighbours which are then blocking weighted vertices from fusing, and so on. Ultimately, this then provides a set of weightings on relevant nodes, which can then each be cut, starting from the highest weighted down. While this is a heuristic approach, we show that, for circuits small enough to verify, this method achieves the most optimal set of cuts possible
71% of the time. Furthermore, there is no upper bound for the efficiency achieved by this method, allowing, in principle, an effective decomposition efficiency
α→0 for highly structured circuits. Even applied to random pseudo-structured circuits (produced from CNOTs, phase gates, and Toffolis), we record the number of stabiliser terms required to reduce all T-gates, via our method as compared to that of the more conventional T-decomposition approaches (namely \cite{kissinger21}, with
α≈0.47), and show consistent improvements of orders of magnitude, with an effective efficiency
0.1≲α≲0.2.
Abstract Recent advances in classical simulation of Clifford+T circuits make use of the ZX calculus to iteratively decompose and simplify magic states into stabiliser terms We improve on this method by studying stabiliser decompositions of ZX diagrams involving the triangle operation. We show that this technique greatly speeds up the simulation of quantum circuits involving multi-controlled gates which can be naturally represented using triangles. We implement our approach in the QuiZX library (2022 A. Kissinger amd J. van de Wetering Quantum Science and Technology 7, 044001), (2022 A. Kissinger et al F. Le Gall and T. Morimae, ed. 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), Leibniz International Proceedings in Informatics (LIPIcs) 232, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp 5:1–5:13) and demonstrate a significant simulation speed-up (up to multiple orders of magnitude) for random circuits and a variation of previously used benchmarking circuits. Furthermore, we use our software to contract diagrams representing the gradient variance of parametrised quantum circuits, which yields a tool for the automatic numerical detection of the barren plateau phenomenon in ansätze used for quantum machine learning. Compared to traditional statistical approaches, our method yields exact values for gradient variances and only requires contracting a single diagram. The performance of this tool is competitive with tensor network approaches, as demonstrated with benchmarks against the quimb library (2018 J. Gray Journal of Open Source Software 3, 819).