Simulating Quantum Computations with Tutte Polynomials
arXiv:2101.00211 · doi:10.1038/s41534-021-00477-0
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.
arXiv comment13 pages, 0 figures, published version
References in corpus (16)
- Simulating quantum computation by contracting tensor networks
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Trading classical and quantum computational resources
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Hyper-optimized tensor network contraction
- Instantaneous Quantum Computation
- Classical Simulation of Quantum Supremacy Circuits
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Simulating the Sycamore quantum supremacy circuits
- Low Depth Quantum Circuits for Ising Models
- Six variations on a theme: almost planar graphs
- Fast simulation of planar Clifford circuits
- Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
- A new edge selection heuristic for computing the Tutte polynomial of an undirected graph