The Computational Power of Symmetric Hamiltonians

Abstract

The presence of symmetries, be they discrete or continuous, in a physical system typically leads to a reduction in the problem to be solved. Here we report that neither translational invariance nor rotational invariance reduce the computational complexity of simulating Hamiltonian dynamics; the problem is still BQP complete, and is believed to be hard on a classical computer. This is achieved by designing a system to implement a Universal Quantum Interface, a device which enables control of an entire computation through the control of a fixed number of spins, and using it as a building-block to entirely remove the need for control, except in the system initialisation. Finally, it is shown that cooling such Hamiltonians to their ground states in the presence of random magnetic fields solves a QMA-complete problem.

8 pages, 4 figures v3: much clearer presentation of main construction. Results extended to rotationally invariant Hamiltonians

References in corpus (19)

• Topological quantum memory
• Quantum Communication Through an Unmodulated Spin Chain
• Reference frames, superselection rules, and quantum information
• DMRG and periodic boundary conditions: a quantum information perspective
• Perfect Transfer of Arbitrary States in Quantum Spin Networks
• Conclusive and arbitrarily perfect quantum state transfer using parallel spin chain channels
• Quantum Computing with an 'Always On' Heisenberg Interaction
• Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries
• Globally controlled quantum wires for perfect qubit transport, mirroring and computing
• On entropy growth and the hardness of simulating time evolution
• Schemes for Parallel Quantum Computation Without Local Control of Qubits
• Quantum Computing with Globally Controlled Exchange-type Interactions
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Quantum computation via translation-invariant operations on a chain of qubits
• A universally programmable Quantum Cellular Automaton
• Universal quantum interfaces
• Graph State Preparation and Cluster Computation with Global Addressing of Optical Lattices
• Quantum computation in optical lattices via global laser addressing
• A QMA-Complete Translationally Invariant Hamiltonian Problem and the Complexity of Finding Ground State Energies in Physical Systems

Cited by in corpus (19)

• Adiabatic Quantum Computing
• Universal computation by quantum walk
• The Future of Quantum Computing with Superconducting Qubits
• A Review of Perfect State Transfer and its Application as a Constructive Tool
• The power of quantum systems on a line
• Experimental Perfect Quantum State Transfer
• Scalable quantum computation via local control of only two qubits
• Local controllability of quantum networks
• Symmetry Principles in Quantum Systems Theory
• Hamiltonian Quantum Cellular Automata in 1D
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• Computation on Spin Chains with Limited Access
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Interfacing with Hamiltonian Dynamics
• Hamiltonian quantum computer in one dimension
• The Role of Rotational Invariance in the Properties of Hamiltonians
• Perfect transfer of arbitrary continuous variable states across optical waveguide lattices
• Quantum Defragmentation Algorithm