Classical Ising model test for quantum circuits

Abstract

We exploit a recently constructed mapping between quantum circuits and graphs in order to prove that circuits corresponding to certain planar graphs can be efficiently simulated classically. The proof uses an expression for the Ising model partition function in terms of quadratically signed weight enumerators (QWGTs), which are polynomials that arise naturally in an expansion of quantum circuits in terms of rotations involving Pauli matrices. We combine this expression with a known efficient classical algorithm for the Ising partition function of any planar graph in the absence of an external magnetic field, and the Robertson-Seymour theorem from graph theory. We give as an example a set of quantum circuits with a small number of non-nearest neighbor gates which admit an efficient classical simulation.

17 pages, 2 figures. v2: main result strengthened by removing oracular setting

References in corpus (12)

• Simulated Quantum Computation of Molecular Energies
• Fast simulation of stabilizer circuits using a graph state representation
• Strings, Projected Entangled Pair States, and variational Monte Carlo methods
• On measurement-based quantum computation with the toric code states
• Completeness of the classical 2D Ising model and universal quantum computation
• Classical spin models and the quantum stabilizer formalism
• Fermionic Linear Optics Revisited
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• Classical simulation of limited-width cluster-state quantum computation
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs

Cited by in corpus (14)

• Characterizing Quantum Supremacy in Near-Term Devices
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Quantum algorithms for classical lattice models
• Twins Percolation for Qubit Losses in Topological Color Codes
• Dual correspondence between classical spin models and quantum CSS states
• Low Depth Quantum Circuits for Ising Models
• Phase transition in a noisy Kitaev toric code model
• Emulating Quantum Interference with Generalized Ising Machines
• Classical criticality establishes quantum topological order
• Analytical percolation theory for topological color codes under qubit loss
• A quantum information approach to statistical mechanics
• Noisy Toric code and random bond Ising model: The error threshold in a dual picture
• Systematic study of the completeness of two-dimensional classical ${\varphi }^4$ theory