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

2008/05/08 by M. Van den Nest, W. Dür, Wolfgang Dür +4 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Computation #Computer science #Discrete mathematics #Ising model #Markov Chains and Monte Carlo Methods #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Turing machine #Quantum algorithm #Quantum circuit #Quantum computer #Quantum error correction #Quantum gate #Quantum many-body systems #Quantum mechanics #Theoretical computer science #quant-ph

paper · pdf · doi:10.1103/physreva.80.052334

published as Phys. Rev. A 80, 052334 (2009) · 6 pages, 2 figures

arxiv created 2008/05/08 · openalex publication_date 2009/11/30 · arxiv updated 2012/02/20 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

We present simple mappings between classical lattice models and quantum circuits, which provide a systematic formalism to obtain quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. We, e.g., present an efficient quantum algorithm for the six-vertex model as well as a two-dimensional Ising-type model. We show that classically simulating these (complex-parameter) spin models is as hard as simulating universal quantum computation, i.e., BQP complete (BQP denotes bounded-error quantum polynomial time). Furthermore, our mappings provide a framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. We, e.g., show that the simulability of Valiant's match gates can be recovered by using the solvability of the free-fermion eight-vertex model.

Citations

• Completeness of the Classical 2D Ising Model and Universal Quantum Computation
• Simulating Ising spin glasses on a quantum computer
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• Fermionic Linear Optics Revisited
• Criticality, the area law, and the computational power of PEPS
• On the quantum computational complexity of the Ising spin glass partition function and of knot invariants
• Fault-tolerant quantum computation by anyons
• Matchgates and classical simulation of quantum circuits

Cited by

• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Quantum algorithms for classical lattice models

Related

• Quantum algorithms for classical lattice models
• A quantum algorithm for additive approximation of Ising partition functions
• Simulating quantum computers with probabilistic methods
• Completeness of the Classical 2D Ising Model and Universal Quantum Computation
• Toward the first quantum simulation with quantum speedup