Quantum simulators, continuous-time automata, and translationally invariant systems

Abstract

The general problem of finding the ground state energy of lattice Hamiltonians is known to be very hard, even for a quantum computer. We show here that this is the case even for translationally invariant systems. We also show that a quantum computer can be built in a 1D chain with a fixed, translationally invariant Hamitonian consisting of nearest--neighbor interactions only. The result of the computation is obtained after a prescribed time with high probability.

partily rewritten and important references included

References in corpus (6)

• Entanglement of atoms via cold controlled collisions
• Programmable quantum gate arrays
• A universally programmable Quantum Cellular Automaton
• Ensemble Quantum Computation with atoms in periodic potentials
• Reversible universal quantum computation within translation invariant systems
• Speed and entropy of an interacting continuous time quantum walk

Cited by in corpus (36)

• Quantum Simulation
• Universal computation by quantum walk
• Entropy scaling and simulability by Matrix Product States
• The Future of Quantum Computing with Superconducting Qubits
• A Review of Perfect State Transfer and its Application as a Constructive Tool
• A Survey on Quantum Channel Capacities
• Computational advantage of quantum random sampling
• A review of Quantum Cellular Automata
• On entropy growth and the hardness of simulating time evolution
• Time evolution of many-body localized systems in two spatial dimensions
• The computational difficulty of finding MPS ground states
• Hamiltonian Quantum Cellular Automata in 1D
• Control by quantum dynamics on graphs
• Symmetry & Controllability for Spin Networks with a Single-Node Control
• Quantum time crystals with programmable disorder in higher dimensions
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
• Computation on Spin Chains with Limited Access
• Universal 2-local Hamiltonian Quantum Computing
• The Computational Power of Symmetric Hamiltonians
• Interfacing with Hamiltonian Dynamics
• Local Hamiltonians in Quantum Computation
• A comparative study of universal quantum computing models: towards a physical unification
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• Generating Quantum States through Spin Chain Dynamics
• Scalably learning quantum many-body Hamiltonians from dynamical data
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• Universal resources for quantum computing
• Hamiltonian quantum computer in one dimension
• Is there a physically universal cellular automaton or Hamiltonian?
• Unraveling long-time quantum dynamics using flow equations
• The Role of Rotational Invariance in the Properties of Hamiltonians
• Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations
• Universal Hamiltonians for Exponentially Long Simulation
• A PromiseBQP-complete String Rewriting Problem
• Short-time simulation of quantum dynamics by Pauli measurements
• Dissipative dynamics of a spin system with three-body interaction