We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.We present a bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\ensuremath{\Delta}$. We use this bound to obtain a significant improvement over the cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/{\ensuremath{\Delta}}^{2}$, and a method based on fixed-point search has a maximum cost of order $1/{\ensuremath{\Delta}}^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/{\ensuremath{\Delta}}^{3/2}$ and $1/\ensuremath{\Delta}$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/{\ensuremath{\Delta}}^{3}$.

arXiv:1311.7073Physical Review AJan 15, 201417 citations

Adiabatic optimization without local minima | NIST

Stephen P. Jordan, Michael Jarret

Quantum Information and ComputationMar 1, 20150 citations

Eigenpath traversal by phase randomization

Sergio Boixo, E. Knill, Rolando D. Somma

A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is $\cO(L^{2} /\Delta)$ for constant error probability, where $L$ is the length of the path of eigenstates and $\Delta$ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on $\Delta$ is optimal. Making explicit the dependence on the path length is useful for cases where $L$ is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a discretized form of the path: At each step we apply the instantaneous Hamiltonian for a random time. The resulting decoherence approximates a projective measurement onto the desired eigenstate, achieving a version of the quantum Zeno effect. If negative evolution times can be implemented with constant overhead, then the average absolute evolution time required by our method is $\cO(L^{2} /\Delta)$ for constant error probability, where $L$ is the length of the path of eigenstates and $\Delta$ is the minimum spectral gap of the Hamiltonian. The dependence of the cost on $\Delta$ is optimal. Making explicit the dependence on the path length is useful for cases where $L$ is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.

Quantum Information and ComputationSep 1, 200951 citations

L

is the length of the path of eigenstates and

\Delta

is the minimum spectral gap of the Hamiltonian. The dependence of the cost on

\Delta

is optimal. Making explicit the dependence on the path length is useful for cases where

L

is much less than the general bound. The complexity of our method has a logarithmic improvement over previous algorithms of this type. The same cost applies to the discrete-time case, where a family of unitary operators is given and each unitary and its inverse can be used. Restriction to positive evolution times incurs an error that decreases exponentially with the cost. Applications of this method to unstructured search and quantum sampling are considered. In particular, we discuss the quantum simulated annealing algorithm for solving combinatorial optimization problems. This algorithm provides a quadratic speed-up in the gap of the stochastic matrix over its classical counterpart implemented via Markov chain Monte Carlo.