General conditions for universality of Quantum Hamiltonians

Abstract

Recent work has demonstrated the existence of universal Hamiltonians - simple spin lattice models that can simulate any other quantum many body system to any desired level of accuracy. Until now proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians. In this work we go beyond this approach, and completely classify the simulation ability of quantum Hamiltonians by their complexity classes. We do this by deriving necessary and sufficient complexity theoretic conditions characterising universal quantum Hamiltonians. Although the result concerns the theory of analogue Hamiltonian simulation - a promising application of near-term quantum technology - the proof relies on abstract complexity theoretic concepts and the theory of quantum computation. As well as providing simplified proofs of previous Hamiltonian universality results, and offering a route to new universal constructions, the results in this paper give insight into the origins of universality. For example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in complexity theory.

arXiv comment22 pages. V2 - extended discussion, fixing typos

References in corpus (14)

• Quantum fingerprinting
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Schrieffer-Wolff transformation for quantum many-body systems
• Quantum simulation and computing with Rydberg-interacting qubits
• A concise review of Rydberg atom based quantum computation and quantum simulation
• Simple universal models capture all classical spin physics
• Universal Quantum Hamiltonians
• Toy Models of Holographic Duality between local Hamiltonians
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Importance of the spectral gap in estimating ground-state energies
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Universal Translationally-Invariant Hamiltonians
• Quantum Arthur-Merlin Games

Cited by in corpus (8)

• On the complexity of quantum partition functions
• A comparative study of universal quantum computing models: towards a physical unification
• Universal resources for quantum computing
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
• Simplifying the simulation of local Hamiltonian dynamics
• Universal Hamiltonian simulators in one and two dimensions
• Quantum simulation in the entanglement picture