Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2101.00211 · npj Quantum Information

Simulating quantum computations with Tutte polynomials

Ryan L. Mann

Published Sep 24, 2021• 6 citations
arXivHTMLPDF

Abstract

Abstract We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial recursively using the deletion–contraction property while attempting to exploit structural properties of the matroid. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits.

DOI
10.1038/s41534-021-00477-0

Related papers

How to Simulate Quantum Measurement without Computing Marginals

Sergey B. Bravyi, David Gosset, Yinchen Liu

We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithms can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain the first efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph and any schedule of measurements.

arXiv:2112.08499•Physical Review Letters•Jun 1, 2022•24 citations

Simulating Clifford Circuits with Gaussian Elimination

Yuchen Pang, Edgar Solomonik

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.

quant-pharXiv:2511.06127•Nov 11, 2025•0 citations

Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation

Roman Schutski, Taras Khakhulin, Ivan Valer'evich Oseledets +1 more

Tensor networks are the main building blocks in various computational sciences, ranging from many-body theory and quantum computing to probability and machine learning. Here we propose a parallel algorithm for the contraction of tensor networks using probabilistic graphical models. Given a tensor network, this algorithm splits the contraction task almost optimally into subtasks, which can be contracted independently in parallel. Our approach is based on the heuristic solution of the $\ensuremath{\mu}$-treewidth deletion problem in graph theory. We apply the resulting algorithm to the simulation of random quantum circuits and discuss the extensions for general tensor network contractions. According to our estimates, the lower bound on the simulation time of 1 million amplitudes of a 49-qubit circuit of depth 40 on the Summit supercomputer is $>5$ seconds.

arXiv:2004.10892•Physical Review A•Dec 28, 2020•20 citations

Quantum Tutte Embeddings

Shion Fukuzawa, Michael T. Goodrich, Sandy Irani

Using the framework of Tutte embeddings, we begin an exploration of \emph{quantum graph drawing}, which uses quantum computers to visualize graphs. The main contributions of this paper include formulating a model for quantum graph drawing, describing how to create a graph-drawing quantum circuit from a given graph, and showing how a Tutte embedding can be calculated as a quantum state in this circuit that can then be sampled to extract the embedding. To evaluate the complexity of our quantum Tutte embedding circuits, we compare them to theoretical bounds established in the classical computing setting derived from a well-known classical algorithm for solving the types of linear systems that arise from Tutte embeddings. We also present empirical results obtained from experimental quantum simulations.

arXiv:2307.08851•Jul 17, 2023•1 citation

Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm

Chu Guo, Youwei Zhao, He-Liang Huang

The ability to efficiently simulate random quantum circuits using a classical computer is increasingly important for developing noisy intermediate-scale quantum devices. Here, we present a tensor network states based algorithm specifically designed to compute amplitudes for random quantum circuits with arbitrary geometry. Singular value decomposition based compression together with a two-sided circuit evolution algorithm are used to further compress the resulting tensor network. To further accelerate the simulation, we also propose a heuristic algorithm to compute the optimal tensor contraction path. We demonstrate that our algorithm is up to 2 orders of magnitudes faster than the Schrödinger-Feynman algorithm for verifying random quantum circuits on the 53-qubit Sycamore processor, with circuit depths below 12. We also simulate larger random quantum circuits with up to 104 qubits, showing that this algorithm is an ideal tool to verify relatively shallow quantum circuits on near-term quantum computers.

arXiv:2011.02621•Physical Review Letters•Feb 16, 2021•29 citations

Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States

Kaifeng Bu, Dax Enshan Koh

We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states. First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the l_{1} norm, of a large fraction of Clifford circuits. The running time of our algorithm decreases as the inputs become more mixed. Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured. This restriction depends on a magic monotone that we call the Pauli rank. We apply our results to give an efficient output probability approximation algorithm for some restricted quantum computation models, such as Clifford circuits with solely magic state inputs, Pauli-based computation, and instantaneous quantum polynomial time circuits. Finally, we discuss the relationship between Pauli rank and stabilizer rank.

arXiv:1902.11257•Physical Review Letters•Oct 23, 2019•48 citations
Abstract We establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial recursively using the deletion–contraction property while attempting to exploit structural properties of the matroid. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits.
We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state in the standard basis, that is, sampling a bit string from the probability distribution determined by the Born rule. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. Two classes of quantum states are considered: output states of polynomial-size quantum circuits, and ground states of local Hamiltonians with an inverse polynomial spectral gap. We show that our algorithms can significantly accelerate quantum circuit simulations based on tensor network contraction or low-rank stabilizer decompositions. As another striking consequence we obtain the first efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph and any schedule of measurements.
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.
Tensor networks are the main building blocks in various computational sciences, ranging from many-body theory and quantum computing to probability and machine learning. Here we propose a parallel algorithm for the contraction of tensor networks using probabilistic graphical models. Given a tensor network, this algorithm splits the contraction task almost optimally into subtasks, which can be contracted independently in parallel. Our approach is based on the heuristic solution of the $\ensuremath{\mu}$-treewidth deletion problem in graph theory. We apply the resulting algorithm to the simulation of random quantum circuits and discuss the extensions for general tensor network contractions. According to our estimates, the lower bound on the simulation time of 1 million amplitudes of a 49-qubit circuit of depth 40 on the Summit supercomputer is >5>5>5 seconds.
Using the framework of Tutte embeddings, we begin an exploration of \emph{quantum graph drawing}, which uses quantum computers to visualize graphs. The main contributions of this paper include formulating a model for quantum graph drawing, describing how to create a graph-drawing quantum circuit from a given graph, and showing how a Tutte embedding can be calculated as a quantum state in this circuit that can then be sampled to extract the embedding. To evaluate the complexity of our quantum Tutte embedding circuits, we compare them to theoretical bounds established in the classical computing setting derived from a well-known classical algorithm for solving the types of linear systems that arise from Tutte embeddings. We also present empirical results obtained from experimental quantum simulations.
The ability to efficiently simulate random quantum circuits using a classical computer is increasingly important for developing noisy intermediate-scale quantum devices. Here, we present a tensor network states based algorithm specifically designed to compute amplitudes for random quantum circuits with arbitrary geometry. Singular value decomposition based compression together with a two-sided circuit evolution algorithm are used to further compress the resulting tensor network. To further accelerate the simulation, we also propose a heuristic algorithm to compute the optimal tensor contraction path. We demonstrate that our algorithm is up to 2 orders of magnitudes faster than the Schrödinger-Feynman algorithm for verifying random quantum circuits on the 53-qubit Sycamore processor, with circuit depths below 12. We also simulate larger random quantum circuits with up to 104 qubits, showing that this algorithm is an ideal tool to verify relatively shallow quantum circuits on near-term quantum computers.
We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states. First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the l_{1} norm, of a large fraction of Clifford circuits. The running time of our algorithm decreases as the inputs become more mixed. Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured. This restriction depends on a magic monotone that we call the Pauli rank. We apply our results to give an efficient output probability approximation algorithm for some restricted quantum computation models, such as Clifford circuits with solely magic state inputs, Pauli-based computation, and instantaneous quantum polynomial time circuits. Finally, we discuss the relationship between Pauli rank and stabilizer rank.