Completeness of the classical 2D Ising model and universal quantum computation

Abstract

We prove that the 2D Ising model is complete in the sense that the partition function of any classical q-state spin model (on an arbitrary graph) can be expressed as a special instance of the partition function of a 2D Ising model with complex inhomogeneous couplings and external fields. In the case where the original model is an Ising or Potts-type model, we find that the corresponding 2D square lattice requires only polynomially more spins w.r.t the original one, and we give a constructive method to map such models to the 2D Ising model. For more general models the overhead in system size may be exponential. The results are established by connecting classical spin models with measurement-based quantum computation and invoking the universality of the 2D cluster states.

4 pages, 1 figure. Minor changes

References in corpus (10)

• Persistent entanglement in arrays of interacting particles
• Criticality, the area law, and the computational power of PEPS
• The computational complexity of PEPS
• Universal resources for measurement-based quantum computation
• Simulating Ising Spin Glasses on a Quantum Computer
• A Quantum Approach to Classical Statistical Mechanics
• Fundamentals of universality in one-way quantum computation
• On measurement-based quantum computation with the toric code states
• Classical spin models and the quantum stabilizer formalism
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants

Cited by in corpus (43)

• Measurement-based quantum computation
• Explicit tensor network representation for the ground states of string-net models
• Simple universal models capture all classical spin physics
• Digital-Analog Quantum Computation
• Universal Quantum Hamiltonians
• Architectures for quantum simulation showing a quantum speedup
• Ancilla-Driven Universal Blind Quantum Computation
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Statistical Mechanical Models and Topological Color Codes
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Unifying all classical spin models in a Lattice Gauge Theory
• Topological color codes on Union Jack lattices: A stable implementation of the whole Clifford group
• Measurement-Based Quantum Computation
• Local convertibility and the quantum simulation of edge states in many-body systems
• Completeness of classical spin models and universal quantum computation
• Mapping all classical spin models to a lattice gauge theory
• A quantum algorithm for additive approximation of Ising partition functions
• Acausal measurement-based quantum computing
• Classical Ising model test for quantum circuits
• Dual correspondence between classical spin models and quantum CSS states
• 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
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Completeness of classical ${\varphi }^4$ theory on 2D lattices
• Measurement-based quantum simulation of Abelian lattice gauge theories
• Phase transition in a noisy Kitaev toric code model
• Translationally invariant universal classical Hamiltonians
• Analytical percolation theory for topological color codes under qubit loss
• A quantum information approach to statistical mechanics
• Classical criticality establishes quantum topological order
• Quantum computation and the evaluation of tensor networks
• Classical spin systems and the quantum stabilizer formalism: general mappings and applications
• Quantum simulation of classical thermal states
• Noisy Toric code and random bond Ising model: The error threshold in a dual picture
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Topological Aspects of Matters and Langlands Program
• Systematic study of the completeness of two-dimensional classical ${\varphi }^4$ theory
• Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models
• Stabilizer states and local realism
• Ising models and topological codes: classical algorithms and quantum simulation
• Perpendicular-anisotropy artificial spin ice with spontaneous ordering: a platform for neuromorphic computing with flexible timescales
• Signature candidate of quantum chaos far from the semiclassical regime