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 (1)

• Speed and entropy of an interacting continuous time quantum walk

Cited by in corpus (12)

• Universal computation by quantum walk
• Entropy scaling and simulability by Matrix Product States
• On entropy growth and the hardness of simulating time evolution
• The computational difficulty of finding MPS ground states
• Hamiltonian Quantum Cellular Automata in 1D
• The Computational Power of Symmetric Hamiltonians
• Interfacing with Hamiltonian Dynamics
• Local Hamiltonians in Quantum Computation
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• The Role of Rotational Invariance in the Properties of Hamiltonians
• A PromiseBQP-complete String Rewriting Problem