Quantum Vertex Model for Reversible Classical Computing
arXiv:1604.05354 · doi:10.1038/ncomms15303
Abstract
Mappings of classical computation onto statistical mechanics models have led to remarkable successes in addressing some complex computational problems. However, such mappings display thermodynamic phase transitions that may prevent reaching solution even for easy problems known to be solvable in polynomial time. Here we map universal reversible classical computations onto a planar vertex model that exhibits no bulk classical thermodynamic phase transition, independent of the computational circuit. Within our approach the solution of the computation is encoded in the ground state of the vertex model and its complexity is reflected in the dynamics of the relaxation of the system to its ground state. We use thermal annealing with and without 'learning' to explore typical computational problems. We also construct a mapping of the vertex model into the Chimera architecture of the D-Wave machine, initiating an approach to reversible classical computation based on state-of-the-art implementations of quantum annealing.
arXiv commentUpdated to accepted version
References in corpus (16)
- Quantum Computing
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum Networks for Elementary Arithmetic Operations
- Glassy dynamics of kinetically constrained models
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Glassy dynamics and aging in an exactly solvable spin model
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Glassiness and constrained dynamics of a short-range non-disordered spin model
- Dynamic scaling at classical phase transitions approached through non-equilibrium quenching
- Ground State Spin Logic
- Slow Cooling of an Ising Ferromagnet
- High-Temperature Criticality in Strongly Constrained Quantum Systems
- Dual time scales in simulated annealing of a two-dimensional Ising spin glass
- Making Classical Ground State Spin Computing Fault-Tolerant
Cited by in corpus (6)
- Dual time scales in simulated annealing of a two-dimensional Ising spin glass
- Obstacles to quantum annealing in a planar embedding of XORSAT
- Tensor network method for reversible classical computation
- Faster manipulation of large quantum circuits using wire label reference diagrams
- A Toffoli Gadget for Magnetic Tunnel Junctions Boltzmann Machines
- Ultra-slow dynamics in a translationally invariant spin model for multiplication and factorization