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.
In this paper, we introduce a technique for contracting (i.e. numerically evaluating) ZX-diagrams whose complexity scales with their rank-width, a graph parameter that behaves nicely under ZX rewrite rules. Given a rank-decomposition of width
R, our method simulates a graph-like ZX-diagram in
O~(4R) time. Applied to classical simulation of quantum circuits, it is no slower than either naive state vector simulation or stabiliser decompositions with
α=0.5, and in practice can be significantly faster for suitably chosen rank-decompositions. Since finding optimal rank-decompositions is NP-hard, we introduce heuristics that produce good decompositions in practice. We benchmark our simulation routine against Quimb, a popular tensor contraction library, and observe substantial reductions in floating-point operations (often by several orders of magnitude) for random and structured non-Clifford circuits as well as random ZX-diagrams.
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.
Various algorithms have been developed to simulate quantum circuits on classical hardware. Among the most prominent are approaches based on \emph{stabilizer decompositions} and \emph{tensor network contraction}. In this work, we present a unified framework that bridges these two approaches, placing them under a common formalism. Using this, we present two new algorithms to simulate an
n-qubit circuit
C: one that runs in
O~(Ttw(C)) time and the other in
O~(Tγ⋅tw(C)) time, where
tw(C) and
rw(C) refer to the the tree-width and rank-width, respectively, of a tensor network associated to
C,
T is the number of non-Clifford gates in
C, and
γ≈3.42. The proposed algorithms are simple, only require a linear amount of memory, are trivially parallelizable, and interact nicely with ZX-diagram simplification routines. Furthermore, we introduce the refined complexity measures \emph{focused tree-width} and \emph{focused rank-width}, which are always at least as efficient as their standard equivalent; these can be directly applied within our simulation algorithms, allowing for a more precise upper bound on the run time.
Recent years have seen a rapid growth in literature presenting new methods for simulating non-Clifford quantum circuits with classical hardware. These methods span a range of approaches, including stabiliser decomposition and tensor contraction techniques, varying in efficiency depending on circuit class, depth, non-Clifford gate count, and other metrics. A notable limitation of this literature is the lack of a standardised approach to benchmarking, with each new paper outlining its own specification, simulating its own set of circuits on the authors' own hardware. This paper seeks to address this issue by presenting a standardised and canonical benchmark suite and infrastructure for quantifying the efficiency of non-Clifford classical simulators, with a consistent dataset of circuits and providing consistent (virtual) hardware, thereby enabling a fair comparison of results.
Quantum circuits are considered more powerful than classical circuits and require exponential resources to simulate classically. Clifford circuits are a special class of quantum circuits that can be simulated in polynomial time but still show important quantum effects such as entanglement. In this work, we present an algorithm that simulates Clifford circuits by performing Gaussian elimination on a modified adjacency matrix derived from the circuit structure. Our work builds on a ZX-calculus tensor network representation of Clifford circuits that reduces to quantum graph states. We give a concise formula of amplitudes of graph states based on the LDL decomposition of matrices over GF(2), and use it to get efficient algorithms for strong and weak simulation of Clifford circuits using a tree-decomposition-based sparse LDL algorithm. The complexity of our algorithm matches the state of the art for weak graph state simulation and improves the state of the art for strong graph state simulation by taking advantage of Strassen-like fast matrix multiplication. Our algorithm is also efficient when computing many amplitudes or samples of a Clifford circuit. Further, our amplitudes formula provides a new characterization of locally Clifford equivalent graph states as well as an efficient protocol to learn graph states with low-rank adjacency matrices.