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:quant-ph/0208189

Total suppression of a large spin tunneling barrier in quantum adiabatic computation

Alex Bulatov, Vadim Smelyanskiy

Published Aug 29, 2002• 2 citations
arXivHTMLPDF

Abstract

We apply a quantum adiabatic evolution algorithm to a combinatorial optimization problem where the cost function depends entirely on the of the number of unit bits in a n-bit string (Hamming weight). The solution of the optimization problem is encoded as a ground state of the problem Hamiltonian H_p for the z-projection of a total spin-n/2. We show that tunneling barriers for the total spin can be completely suppressed during the algorithm if the initial Hamiltonian has its ground state extended in the space of the z-projections of the spin. This suppression takes place even if the cost function has deep and well separated local minima. We provide an intuitive picture for this effect and show that it guarantees the polynomial complexity of the algorithm in a very broad class of cost functions. We suggest a simple example of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hat S_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1. We use WKB analysis for the large spin to estimate the minimum energy gap between the two lowest adiabatic eigenvalues of H(tau).

DOI
10.48550/arxiv.quant-ph/0208189

Related papers

The performance of the quantum adiabatic algorithm on spike Hamiltonians

Linghang Kong, Elizabeth Crosson

Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.

arXiv:1511.06991•International Journal of Quantum Information•Feb 7, 2017•17 citations

Dynamics of quantum adiabatic evolution algorithm for Number Partitioning

Vadim Smelyanskiy, U. von Toussaint, Doǧan A. Timuçin

We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size $n$. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, $g_{\rm min}={\cal O}(n 2^{-n/2})$, corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.

arXiv:quant-ph/0202155•Feb 26, 2002•10 citations

Case studies in quantum adiabatic optimization

David Gosset

Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We

•Jan 1, 2011•1 citation

Quantum adiabatic algorithms and large spin tunnelling

A. Boulatov, Vadim Smelyanskiy

We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin $n/2$ and provide a complete characterization of such paths.

arXiv:quant-ph/0309150•Physical Review A•Dec 24, 2003•15 citations

The quantum adiabatic optimization algorithm and local minima

Ben W. Reichardt

The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•110 citations

Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization

Lucas T. Brady, Wim van Dam

We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at $n$ qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.

arXiv:1601.01720•Physical Review A•Sep 9, 2016•17 citations
We apply a quantum adiabatic evolution algorithm to a combinatorial optimization problem where the cost function depends entirely on the of the number of unit bits in a n-bit string (Hamming weight). The solution of the optimization problem is encoded as a ground state of the problem Hamiltonian H_p for the z-projection of a total spin-n/2. We show that tunneling barriers for the total spin can be completely suppressed during the algorithm if the initial Hamiltonian has its ground state extended in the space of the z-projections of the spin. This suppression takes place even if the cost function has deep and well separated local minima. We provide an intuitive picture for this effect and show that it guarantees the polynomial complexity of the algorithm in a very broad class of cost functions. We suggest a simple example of the Hamiltonian for the adiabatic evolution: H(tau) = (1-tau) hat S_{x}^{2} + tau H_p, with parameter tau slowly varying in time between 0 and 1. We use WKB analysis for the large spin to estimate the minimum energy gap between the two lowest adiabatic eigenvalues of H(tau).
Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the “the Hamming weight with a spike” problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.
We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size nnn. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxilary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap, gmin=O(n2−n/2)g_{\rm min}={\cal O}(n 2^{-n/2})gmin​=O(n2−n/2), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simulteneous fipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We
We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians $H(\ensuremath{\tau})$ sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi et al. when different evolution paths preserve the bit symmetry of the control Hamiltonians $H(\ensuremath{\tau})$ and are generated by an ensemble of random $8\ifmmode\times\else\texttimes\fi{}8$ matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of $H(\ensuremath{\tau})$ in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin n/2n/2n/2 and provide a complete characterization of such paths.
The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.
We investigate the efficiency of quantum adiabatic optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at nnn qubit systems with symmetric cost functions $f:{{0,1}}^{n}\ensuremath{\rightarrow}\mathbb{R}$, where the ground state must tunnel through a potential barrier of width ${n}^{\ensuremath{\alpha}}$ and height ${n}^{\ensuremath{\beta}}$. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with $1/2\ensuremath{\le}\ensuremath{\alpha}+\ensuremath{\beta}$ and $\ensuremath{\alpha}<1/2$ and show that the minimum gap scales polynomially as ${n}^{1/2\ensuremath{-}\ensuremath{\alpha}\ensuremath{-}\ensuremath{\beta}}$ when $2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{\le}1$ and exponentially as ${n}^{\ensuremath{-}\ensuremath{\beta}/2}exp(\ensuremath{-}C{n}^{(2\ensuremath{\alpha}+\ensuremath{\beta}\ensuremath{-}1)/2})$ when $1<2\ensuremath{\alpha}+\ensuremath{\beta}$. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone from 2002, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson [arXiv:1511.06991] and Jiang et al. [arXiv:1603.01293] about the exponential gap scaling.