Quantum algorithms for spin models and simulable gate sets for quantum computation

Abstract

We present elementary mappings between classical lattice models and quantum circuits. These mappings provide a general framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. For example, we recover and generalize the simulability of Valiant's match-gates by invoking the solvability of the free-fermion eight-vertex model. Our mappings furthermore provide a systematic formalism to obtain simple quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. For example, we present an efficient quantum algorithm for the six-vertex model as well as a 2D Ising-type model. We finally show that simulating our quantum algorithms on a classical computer is as hard as simulating universal quantum computation (i.e. BQP-complete).

6 pages, 2 figures

References in corpus (10)

• Criticality, the area law, and the computational power of PEPS
• Matchgates and classical simulation of quantum circuits
• A Quantum Approach to Classical Statistical Mechanics
• 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
• Statistical Mechanical Models and Topological Color Codes
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants

Cited by in corpus (27)

• Quantum speedup of Monte Carlo methods
• Graph isomorphism and Gaussian boson sampling
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Quantum algorithms for classical lattice models
• Quantum circuits and low-degree polynomials over F_2
• Computing partition functions in the one clean qubit model
• Measuring complex partition function zeroes of Ising models in quantum simulators
• Solving search problems by strongly simulating quantum circuits
• Mapping all classical spin models to a lattice gauge theory
• A quantum algorithm for additive approximation of Ising partition functions
• The U(1) Lattice Gauge Theory Universally Connects All Classical Models with Continuous Variables, Including Background Gravity
• An algorithmic proof for the completeness of two-dimensional Ising model
• Low Depth Quantum Circuits for Ising Models
• Completeness of classical ${\varphi }^4$ theory on 2D lattices
• Emulating Quantum Interference with Generalized Ising Machines
• Phase transition in a noisy Kitaev toric code model
• A quantum information approach to statistical mechanics
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Quantum computation and the evaluation of tensor networks
• Quantum algorithm for exact Monte Carlo sampling
• Normalizer Circuits and Quantum Computation
• Shaded Tangles for the Design and Verification of Quantum Programs (Extended Abstract)
• Noisy Toric code and random bond Ising model: The error threshold in a dual picture
• Abelian Hypergroups and Quantum Computation
• Shaded tangles for the design and verification of quantum circuits
• Mutual information in interacting spin systems
• Quantum information and statistical mechanics: an introduction to frontier