2008/01/31 by Alastair Kay · 1 citation
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum many-body systems #quant-ph
paper · pdf · doi:10.1103/physreva.78.012346
published as Phys. Rev. A 78, 012346 (2008) · 8 pages, 4 figures v3: much clearer presentation of main construction. Results extended to rotationally invariant Hamiltonians
arxiv created 2008/03/17 · openalex publication_date 2008/07/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 bounded error, quantum polynomial time 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 arbitrary 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 initialization. Finally, it is shown that cooling such Hamiltonians to their ground states in the presence of random magnetic fields solves a Quantum-Merlin-Arthur-complete problem.