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

Local Hamiltonians in Quantum Computation

Daniel Nagaj

Published Aug 15, 2008• 17 citations
arXivHTMLPDF

Abstract

In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show that to succeed using AQC, the Hamiltonian involved must have local structure, which leads to a result about eigenvalue gaps from information theory. I also improve results about simulating quantum circuits with AQC. Second, I look at classically simulating time evolution with local Hamiltonians and finding their ground state properties. I give a numerical method for finding the ground state of translationally invariant Hamiltonians on an infinite tree. This method is based on imaginary time evolution within the Matrix Product State ansatz, and uses a new method for bringing the state back to the ansatz after each imaginary time step. I then use it to investigate the phase transition in the transverse field Ising model on the Bethe lattice. Third, I focus on locally constrained quantum problems Local Hamiltonian and Quantum Satisfiability and prove several new results about their complexity. Finally, I define a Hamiltonian Quantum Cellular Automaton, a continuous-time model of computation which doesn't require control during the computation process, only preparation of product initial states. I construct two of these, showing that time evolution with a simple, local, translationally invariant and time-independent Hamiltonian can be used to simulate quantum circuits.

DOI
10.48550/arxiv.0808.2117

Related papers

Adiabatic Quantum Computation

Friederike Anna Dziemba

The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the $L$ computation steps and influencing the scaling of the necessary evolution time by its spectral gap of $\mathcal{O}\left(\frac{1}{L^2}\right)$. Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap $\mathcal{O}\left(\frac{1}{L^k}\right)$, $k<2$, turn out to contradict very likely, graphs with $k<1$ even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.

arXiv:1610.04708•Oct 15, 2016•1 citation

From quantum circuits to adiabatic algorithms

M. Stewart Siu

This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an $n$-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.

arXiv:quant-ph/0409024•Physical Review A•Jun 14, 2005•35 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•8 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•55 citations

On Quantum Simulators and Adiabatic Quantum Algorithms

Sarah Mostame

This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.

•Oct 2, 2008•0 citations

Quantum computer simulations of time-dependent hamiltonians

Nathan Wiebe

In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.

•Jan 1, 2011•0 citations
In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show that to succeed using AQC, the Hamiltonian involved must have local structure, which leads to a result about eigenvalue gaps from information theory. I also improve results about simulating quantum circuits with AQC. Second, I look at classically simulating time evolution with local Hamiltonians and finding their ground state properties. I give a numerical method for finding the ground state of translationally invariant Hamiltonians on an infinite tree. This method is based on imaginary time evolution within the Matrix Product State ansatz, and uses a new method for bringing the state back to the ansatz after each imaginary time step. I then use it to investigate the phase transition in the transverse field Ising model on the Bethe lattice. Third, I focus on locally constrained quantum problems Local Hamiltonian and Quantum Satisfiability and prove several new results about their complexity. Finally, I define a Hamiltonian Quantum Cellular Automaton, a continuous-time model of computation which doesn't require control during the computation process, only preparation of product initial states. I construct two of these, showing that time evolution with a simple, local, translationally invariant and time-independent Hamiltonian can be used to simulate quantum circuits.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the LLL computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(1L2)\mathcal{O}\left(\frac{1}{L^2}\right)O(L21​). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(1Lk)\mathcal{O}\left(\frac{1}{L^k}\right)O(Lk1​), k<2k<2k<2, turn out to contradict very likely, graphs with k<1k<1k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
This paper explores several aspects of the adiabatic quantum-computation model. We first show a way that directly maps any arbitrary circuit in the standard quantum-computing model to an adiabatic algorithm of the same depth. Specifically, we look for a smooth time-dependent Hamiltonian whose unique ground state slowly changes from the initial state of the circuit to its final state. Since this construction requires in general an nnn-local Hamiltonian, we will study whether approximation is possible using previous results on ground-state entanglement and perturbation theory. Finally we will point out how the adiabatic model can be relaxed in various ways to allow for 2-local partially adiabatic algorithms as well as 2-local holonomic quantum algorithms.
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 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).
This Thesis focuses on different aspects of quantum computation theory: adiabatic quantum algorithms, decoherence during the adiabatic evolution and quantum simulators. After an overview on the area of quantum computation and setting up the formal ground for the rest of the Thesis we derive a general error estimate for adiabatic quantum computing. We demonstrate that the first-order correction, which has frequently been used as a condition for adiabatic quantum computation, does not yield a good estimate for the computational error. Therefore, a more general criterion is proposed, which includes higher-order corrections and shows that the computational error can be made exponentially small – which facilitates significantly shorter evolution times than the first-order estimate in certain situations. Based on this criterion and rather general arguments and assumptions, it can be demonstrated that a run-time of order of the inverse minimum energy gap is sufficient and necessary. Furthermore, exploiting the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover’s search algorithm. It turns out that (in contrast to first-order transitions) the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins/qubits), which might limit the scalability of the system. Finally, we propose the use of electron systems to construct laboratory systems based on present-day technology which reproduce and thereby simulate the quantum dynamics of the Ising model and the O(3) nonlinear sigma model.
In this thesis, we present three innovations that can be used to simulate quantum dynamics on both quantum and classical computers. Our primary innovation is an efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer. Given conditions on the smoothness of the Hamiltonian, the complexity of the algorithm is close to linear in the evolution time, and therefore is comparable to algorithms for time-independent Hamiltonians. In addition, we show how the complexity can be reduced by optimizing the time steps. The complexity of the algorithm is quantified by calls to an oracle, which yields information about the Hamiltonian. In contrast to previous work, which allowed an oracle query to yield an arbitrary number of bits or qubits, we assign a cost for each bit or qubit accessed, revealing hitherto unnoticed simulation costs. We also account for discretization errors in the time and the representation of the Hamiltonian. This work is enabled by our development of a decomposition scheme based on Lie-Trotter- Suzuki product formulae for ordered operator exponentials. We show, by counterexample, that Lie-Trotter-Suzuki approximations may be lower order than expected when applied to problems that have singularities or discontinuous derivatives of appropriate order. We address this problem by presenting a set of criteria that is sufficient for the validity of these approximations, prove convergence and provide upper bounds for the approximation error. We also provide a new analysis of the evolution of quantum adiabatic systems in this thesis. Our work contains the tightest upper bounds that are currently known, and the first tight lower bounds, for the error in the adiabatic approximation applied to fixed Hamiltonians in the limit of slow evolution. We use our results to address the Marzlin- Sanders counterexample Hamiltonian. Specifically, we provide sufficiency conditions for the validity of the adiabatic approximation and demonstrate that the Marzlin-Sanders counterexample fails to satisfy them. We also find a new class of time-dependent Hamiltonians that are related to the Marzlin0Sanders counterexample Hamiltonian, but nonetheless obey the adiabatic approximation for sufficiently slow evolutions.