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:0802.1207

Universal quantum walks and adiabatic algorithms by 1D Hamiltonians

Bradley A. Chase, Andrew J. Landahl

Published Feb 8, 2008• 28 citations
arXivHTMLPDF

Abstract

We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.

DOI
10.48550/arxiv.0802.1207

Related papers

Universal Hamiltonian simulators in one and two dimensions

Leo Zhou, Dorit Aharonov

Abstract A major quantum computing application is analog Hamiltonian simulations, in which the low-lying spectrum of a simulator Hamiltonian $${H}^{{\prime} }$$ H ′ encodes the physics of a target Hamiltonian H . Some families of 2D spin-lattice Hamiltonians—such as the Heisenberg or XY model on the square lattice—are known to be “universal” simulators, in the sense that they can simulate any target Hamiltonian. Unfortunately, while the known simulations of 1D or 2D target Hamiltonians are efficient, they require resources growing exponentially with system sizes for target Hamiltonians with general connectivity. This leaves many important cases such as 3D or all-to-all-connected target Hamiltonians out of reach in practice. Here, we remedy this situation and show how the known 2D universal families of Hamiltonians and a new 1D family can simulate all target local Hamiltonians, with only polynomial-scaling overhead. This exponential improvement is achieved by a nonperturbative method combining the quantum phase-estimation algorithm and the circuit-to-Hamiltonian construction. Furthermore, all Hamiltonians efficiently simulable by quantum circuits, including nonlocal ones, also have efficient analog simulators in our 2D and 1D universal families. Our work establishes that analog simulations of general Hamiltonians can be made efficient, significantly expanding the application potential of analog Hamiltonian simulations in near-term quantum technologies.

arXiv:2102.02991•Nature Communications•Apr 21, 2026•36 citations

Adiabatic and Hamiltonian computing on a 2D lattice with simple two-qubit interactions

Seth Lloyd, Barbara M. Terhal

We show how to perform universal Hamiltonian and adiabatic computing using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, an effective quantum field effect transistor that allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent two-qubit ZZ and XX + YY interactions on an (almost) planar grid. The effective Hamiltonian is arrived at by a single use of first-order perturbation theory avoiding the use of perturbation gadgets. The dynamics and spectral properties of the effective Hamiltonian can be fully determined as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian called the space–time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, our construction is potentially realizable using superconducting or other solid-state qubits.

arXiv:1509.01278•New Journal of Physics•Feb 12, 2016•30 citations

Hamiltonian quantum computer in one dimension

Tzu-Chieh Wei, John C. Liang

Quantum computation can be achieved by preparing an appropriate initial product state of qudits and then letting it evolve under a fixed Hamiltonian. The readout is made by measurement on individual qudits at some later time. This approach is called the Hamiltonian quantum computation and it includes, for example, the continuous-time quantum cellular automata and the universal quantum walk. We consider one spatial dimension and study the compromise between the locality $k$ and the local Hilbert space dimension $d$. For geometrically 2-local (i.e., $k=2$), it is known that $d=8$ is already sufficient for universal quantum computation but the Hamiltonian is not translationally invariant. As the locality $k$ increases, it is expected that the minimum required $d$ should decrease. We provide a construction of a Hamiltonian quantum computer for $k=3$ with $d=5$. One implication is that simulating one-dimensional chains of spin-2 particles is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). Imposing translation invariance will increase the required $d$. For this we also construct another 3-local $(k=3)$ Hamiltonian that is invariant under translation of a unit cell of two sites but that requires $d$ to be 8.

arXiv:1512.06775•Physical Review A•Dec 21, 2015•7 citations

Universal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

David Gosset, Barbara M. Terhal, Anna Vershynina

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.

arXiv:1409.7745•Physical Review Letters•Apr 6, 2015•47 citations

Hamiltonian quantum cellular automata in one dimension

Daniel Nagaj, Paweł Wocjan

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of ten-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state that encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless $\mathrm{BPP}=\mathrm{BQP}$).

arXiv:0802.0886•Physical Review A•Sep 9, 2008•61 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
We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.
Abstract A major quantum computing application is analog Hamiltonian simulations, in which the low-lying spectrum of a simulator Hamiltonian H′{H}^{{\prime} }H′ H ′ encodes the physics of a target Hamiltonian H . Some families of 2D spin-lattice Hamiltonians—such as the Heisenberg or XY model on the square lattice—are known to be “universal” simulators, in the sense that they can simulate any target Hamiltonian. Unfortunately, while the known simulations of 1D or 2D target Hamiltonians are efficient, they require resources growing exponentially with system sizes for target Hamiltonians with general connectivity. This leaves many important cases such as 3D or all-to-all-connected target Hamiltonians out of reach in practice. Here, we remedy this situation and show how the known 2D universal families of Hamiltonians and a new 1D family can simulate all target local Hamiltonians, with only polynomial-scaling overhead. This exponential improvement is achieved by a nonperturbative method combining the quantum phase-estimation algorithm and the circuit-to-Hamiltonian construction. Furthermore, all Hamiltonians efficiently simulable by quantum circuits, including nonlocal ones, also have efficient analog simulators in our 2D and 1D universal families. Our work establishes that analog simulations of general Hamiltonians can be made efficient, significantly expanding the application potential of analog Hamiltonian simulations in near-term quantum technologies.
We show how to perform universal Hamiltonian and adiabatic computing using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, an effective quantum field effect transistor that allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent two-qubit ZZ and XX + YY interactions on an (almost) planar grid. The effective Hamiltonian is arrived at by a single use of first-order perturbation theory avoiding the use of perturbation gadgets. The dynamics and spectral properties of the effective Hamiltonian can be fully determined as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian called the space–time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, our construction is potentially realizable using superconducting or other solid-state qubits.
Quantum computation can be achieved by preparing an appropriate initial product state of qudits and then letting it evolve under a fixed Hamiltonian. The readout is made by measurement on individual qudits at some later time. This approach is called the Hamiltonian quantum computation and it includes, for example, the continuous-time quantum cellular automata and the universal quantum walk. We consider one spatial dimension and study the compromise between the locality kkk and the local Hilbert space dimension ddd. For geometrically 2-local (i.e., k=2k=2k=2), it is known that d=8d=8d=8 is already sufficient for universal quantum computation but the Hamiltonian is not translationally invariant. As the locality kkk increases, it is expected that the minimum required ddd should decrease. We provide a construction of a Hamiltonian quantum computer for k=3k=3k=3 with d=5d=5d=5. One implication is that simulating one-dimensional chains of spin-2 particles is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). Imposing translation invariance will increase the required ddd. For this we also construct another 3-local (k=3)(k=3)(k=3) Hamiltonian that is invariant under translation of a unit cell of two sites but that requires ddd to be 8.
We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of ten-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state that encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP\mathrm{BPP}=\mathrm{BQP}BPP=BQP).
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.