Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0801.3228 · Physical Review A

Computational power of symmetric Hamiltonians

Alastair Kay

Published Jul 23, 2008• 25 citations
arXivHTMLPDF

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 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.

DOI
10.1103/physreva.78.012346

Related papers

Decoherence-free universal quantum computation with symmetric qubit clusters

Christian Boudreault, Hichem Eleuch, Michael Hilke +1 more

One of the most challenging problems for the realization of a scalable quantum computer is to design a physical device that keeps the error rate for each quantum processing operation low. These errors can originate from the accuracy of quantum manipulation, such as the sweeping of a gate voltage in solid state qubits or the duration of a laser pulse in optical schemes. Errors also result from decoherence, which is often regarded as more crucial in the sense that it is inherent to the quantum system, being fundamentally a consequence of the coupling to the external environment. Grouping small collections of qubits into clusters with symmetries may serve to protect parts of the calculation from decoherence. In this work, we use 4-level cores with a straightforward generalization of discrete rotational symmetry, called $\omega$-rotation invariance, to encode pairs of coupled qubits and universal 2-qubit logical gates. We propose a scalable scheme for universal quantum computation where cores play the role of quantum-computational transistors, or \textit{quansistors} for short. Embedding in the environment, initialization and readout are achieved by tunnel-coupling the quansistor to leads. The external leads are explicitly considered and are assumed to be the main source of decoherence. We show that quansistors can be dynamically decoupled from the leads by tuning their internal parameters, giving them the versatility required to act as controllable quantum memory units. With this dynamical decoupling, logical operations within quansistors are also symmetry-protected from unbiased noise in their parameters. We identify technologies that could implement $\omega$-rotation invariance. Many of our results can be generalized to higher-level $\omega$-rotation-invariant systems, or adapted to clusters with other symmetries.

•Jun 1, 2021•0 citations

Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems

Alastair Kay

Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and $O\mathbf{(}\mathrm{log}(N)\mathbf{)}$-body local terms, or local dimension $N$ and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.

arXiv:0704.3142•Physical Review A•Sep 20, 2007•24 citations

Universal quantum computation with symmetric qubit clusters coupled to an environment

Christian Boudreault, Hichem Eleuch, Michael Hilke +1 more

One of the most challenging problems for the realization of a scalable quantum computer is to design a physical device that keeps the error rate for each quantum processing operation low. These errors can originate from the accuracy of quantum manipulation, such as the sweeping of a gate voltage in solid state qubits or the duration of a laser pulse in optical schemes. Errors also result from decoherence, which is often regarded as more crucial in the sense that it is inherent to the quantum system, being fundamentally a consequence of the coupling to the external environment. Grouping small collections of qubits into clusters with symmetries may serve to protect parts of the calculation from decoherence. In this work, we use four-level cores with a straightforward generalization of discrete rotational symmetry, called $\ensuremath{\omega}$-rotation invariance, to encode pairs of coupled qubits and universal two-qubit logical gates. We include quantum errors as a main source of decoherence, and show that symmetry makes logical operations particularly resilient to untimely anisotropic qubit rotations. We propose a scalable scheme for universal quantum computation where cores play the role of quantum-computational transistors, or quansistors for short. Initialization and readout are achieved by tunnel-coupling the quansistor to leads. The external leads are explicitly considered and are assumed to be the other main source of decoherence. We show that quansistors can be dynamically decoupled from the leads by tuning their internal parameters, giving them the versatility required to act as controllable quantum memory units. With this dynamical decoupling, logical operations within quansistors are also symmetry-protected from unbiased noise in their parameters. We identify technologies that could implement $\ensuremath{\omega}$-rotation invariance. Many of our results can be generalized to higher-level $\ensuremath{\omega}$-rotation-invariant systems, or adapted to clusters with other symmetries.

arXiv:2106.00754•Physical Review A•Dec 15, 2022•8 citations

Translationally Invariant Universal Quantum Hamiltonians in 1D

Tamara Kohler, Stephen Piddock, Johannes Bausch +1 more

Abstract Recent work has characterized rigorously what it means for one quantum system to simulate another and demonstrated the existence of universal Hamiltonians—simple spin lattice Hamiltonians that can replicate the entire physics of any other quantum many-body system. Previous universality results have required proofs involving complicated ‘chains’ of perturbative ‘gadgets.’ In this paper, we derive a significantly simpler and more powerful method of proving universality of Hamiltonians, directly leveraging the ability to encode quantum computation into ground states. This provides new insight into the origins of universal models and suggests a deep connection between universality and complexity. We apply this new approach to show that there are universal models even in translationally invariant spin chains in 1D. This gives as a corollary a new Hamiltonian complexity result that the local Hamiltonian problem for translationally invariant spin chains in one dimension with an exponentially small promise gap is PSPACE-complete. Finally, we use these new universal models to construct the first known toy model of 2D–1D holographic duality between local Hamiltonians.

arXiv:2003.13753•Annales Henri Poincaré•Oct 23, 2021•22 citations

Programmable quantum simulation by dynamic Hamiltonian engineering

David Hayes, Steven T. Flammia, Michael J. Biercuk

Quantum simulation is a promising near term application for quantum information processors with the potential to solve computationally intractable problems using just a few dozen interacting qubits. A range of experimental platforms have recently demonstrated the basic functionality of quantum simulation applied to quantum magnetism, quantum phase transitions and relativistic quantum mechanics. However, in all cases, the physics of the underlying hardware restricts the achievable inter-particle interactions and forms a serious constraint on the versatility of the simulators. To broaden the scope of these analog devices, we develop a suite of pulse sequences that permit a user to efficiently realize average Hamiltonians that are beyond the native interactions of the system. Specifically, this approach permits the generation of all symmetrically coupled translation-invariant two-body Hamiltonians with homogeneous on-site terms, a class which includes all spin- XYZ chains, but generalized to include long-range couplings. Our work builds on previous work proving that universal simulation is possible using both entangling gates and single-qubit unitaries. We show that determining the appropriate 'program' of unitary pulse sequences which implements an arbitrary Hamiltonian transformation can be formulated as a linear program over functions defined by those pulse sequences, running in polynomial time and scaling efficiently in hardware resources. Our analysis extends from circuit model quantum information to adiabatic quantum evolutions, representing an important and broad-based success in applying functional analysis to the field of quantum information.

arXiv:1309.6736•New Journal of Physics•Aug 12, 2014•37 citations

SIM-GRAPH: A universal guide to symmetric interactions

R. C. Verstraten, C. Morais Smith

Symmetry plays a central role throughout physics, from Fourier analysis on discrete lattices to the classification of elementary particles in the standard model. In finite quantum systems, symmetries are often discrete, such as reflection and rotational symmetries. Here, we present the SIM-GRAPH method (Symmetric Ising Models - Graph Reduction And Projected Hamiltonians), which uses such symmetries to efficiently calculate ground-state observables of interacting quantum systems. By projecting all interactions onto a symmetric subset of the system, the method effectively reduces the number of sites, thus providing an exponential speedup over standard exact diagonalization. Furthermore, we introduce two extensions that broaden the applicability of the method and allow for a controlled trade-off between computational cost and accuracy.

cond-mat.str-elCross-listedarXiv:2609.09996•Sep 10, 2026•1 citation
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.
One of the most challenging problems for the realization of a scalable quantum computer is to design a physical device that keeps the error rate for each quantum processing operation low. These errors can originate from the accuracy of quantum manipulation, such as the sweeping of a gate voltage in solid state qubits or the duration of a laser pulse in optical schemes. Errors also result from decoherence, which is often regarded as more crucial in the sense that it is inherent to the quantum system, being fundamentally a consequence of the coupling to the external environment. Grouping small collections of qubits into clusters with symmetries may serve to protect parts of the calculation from decoherence. In this work, we use 4-level cores with a straightforward generalization of discrete rotational symmetry, called ω\omegaω-rotation invariance, to encode pairs of coupled qubits and universal 2-qubit logical gates. We propose a scalable scheme for universal quantum computation where cores play the role of quantum-computational transistors, or \textit{quansistors} for short. Embedding in the environment, initialization and readout are achieved by tunnel-coupling the quansistor to leads. The external leads are explicitly considered and are assumed to be the main source of decoherence. We show that quansistors can be dynamically decoupled from the leads by tuning their internal parameters, giving them the versatility required to act as controllable quantum memory units. With this dynamical decoupling, logical operations within quansistors are also symmetry-protected from unbiased noise in their parameters. We identify technologies that could implement ω\omegaω-rotation invariance. Many of our results can be generalized to higher-level ω\omegaω-rotation-invariant systems, or adapted to clusters with other symmetries.
Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and O(log(N))O\mathbf{(}\mathrm{log}(N)\mathbf{)}O(log(N))-body local terms, or local dimension NNN and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.
One of the most challenging problems for the realization of a scalable quantum computer is to design a physical device that keeps the error rate for each quantum processing operation low. These errors can originate from the accuracy of quantum manipulation, such as the sweeping of a gate voltage in solid state qubits or the duration of a laser pulse in optical schemes. Errors also result from decoherence, which is often regarded as more crucial in the sense that it is inherent to the quantum system, being fundamentally a consequence of the coupling to the external environment. Grouping small collections of qubits into clusters with symmetries may serve to protect parts of the calculation from decoherence. In this work, we use four-level cores with a straightforward generalization of discrete rotational symmetry, called $\ensuremath{\omega}$-rotation invariance, to encode pairs of coupled qubits and universal two-qubit logical gates. We include quantum errors as a main source of decoherence, and show that symmetry makes logical operations particularly resilient to untimely anisotropic qubit rotations. We propose a scalable scheme for universal quantum computation where cores play the role of quantum-computational transistors, or quansistors for short. Initialization and readout are achieved by tunnel-coupling the quansistor to leads. The external leads are explicitly considered and are assumed to be the other main source of decoherence. We show that quansistors can be dynamically decoupled from the leads by tuning their internal parameters, giving them the versatility required to act as controllable quantum memory units. With this dynamical decoupling, logical operations within quansistors are also symmetry-protected from unbiased noise in their parameters. We identify technologies that could implement $\ensuremath{\omega}$-rotation invariance. Many of our results can be generalized to higher-level $\ensuremath{\omega}$-rotation-invariant systems, or adapted to clusters with other symmetries.
Abstract Recent work has characterized rigorously what it means for one quantum system to simulate another and demonstrated the existence of universal Hamiltonians—simple spin lattice Hamiltonians that can replicate the entire physics of any other quantum many-body system. Previous universality results have required proofs involving complicated ‘chains’ of perturbative ‘gadgets.’ In this paper, we derive a significantly simpler and more powerful method of proving universality of Hamiltonians, directly leveraging the ability to encode quantum computation into ground states. This provides new insight into the origins of universal models and suggests a deep connection between universality and complexity. We apply this new approach to show that there are universal models even in translationally invariant spin chains in 1D. This gives as a corollary a new Hamiltonian complexity result that the local Hamiltonian problem for translationally invariant spin chains in one dimension with an exponentially small promise gap is PSPACE-complete. Finally, we use these new universal models to construct the first known toy model of 2D–1D holographic duality between local Hamiltonians.
Quantum simulation is a promising near term application for quantum information processors with the potential to solve computationally intractable problems using just a few dozen interacting qubits. A range of experimental platforms have recently demonstrated the basic functionality of quantum simulation applied to quantum magnetism, quantum phase transitions and relativistic quantum mechanics. However, in all cases, the physics of the underlying hardware restricts the achievable inter-particle interactions and forms a serious constraint on the versatility of the simulators. To broaden the scope of these analog devices, we develop a suite of pulse sequences that permit a user to efficiently realize average Hamiltonians that are beyond the native interactions of the system. Specifically, this approach permits the generation of all symmetrically coupled translation-invariant two-body Hamiltonians with homogeneous on-site terms, a class which includes all spin- XYZ chains, but generalized to include long-range couplings. Our work builds on previous work proving that universal simulation is possible using both entangling gates and single-qubit unitaries. We show that determining the appropriate 'program' of unitary pulse sequences which implements an arbitrary Hamiltonian transformation can be formulated as a linear program over functions defined by those pulse sequences, running in polynomial time and scaling efficiently in hardware resources. Our analysis extends from circuit model quantum information to adiabatic quantum evolutions, representing an important and broad-based success in applying functional analysis to the field of quantum information.
Symmetry plays a central role throughout physics, from Fourier analysis on discrete lattices to the classification of elementary particles in the standard model. In finite quantum systems, symmetries are often discrete, such as reflection and rotational symmetries. Here, we present the SIM-GRAPH method (Symmetric Ising Models - Graph Reduction And Projected Hamiltonians), which uses such symmetries to efficiently calculate ground-state observables of interacting quantum systems. By projecting all interactions onto a symmetric subset of the system, the method effectively reduces the number of sites, thus providing an exponential speedup over standard exact diagonalization. Furthermore, we introduce two extensions that broaden the applicability of the method and allow for a controlled trade-off between computational cost and accuracy.