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

Simulated Quantum Annealing is Efficient on the Spike Hamiltonian

Thiago Bergamaschi

Published Nov 30, 2020• 0 citations
arXivHTMLPDF

Abstract

In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.

DOI
10.48550/arxiv.2011.15094

Related papers

Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.

arXiv:1601.03030•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•76 citations

Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width n^ζ and height n^α for ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.

•Oct 1, 2016•89 citations

Tunneling through high energy barriers in simulated quantum annealing

Elizabeth Crosson, Mingkai Deng

We analyze the performance of simulated quantum annealing (SQA) on an optimization problem for which simulated classical annealing (SA) is provably inefficient because of a high energy barrier. We present evidence that SQA can pass through this barrier to find the global minimum efficiently. This demonstrates the potential for SQA to inherit some of the advantages of quantum annealing (QA), since this problem has been previously shown to be efficiently solvable by quantum adiabatic optimization.

arXiv:1410.8484•Oct 30, 2014•9 citations

Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy

Hiroshi Hayasaka, Takashi Imoto, Yuichiro Matsuzaki +1 more

Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where $L$ is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic $p$-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.

arXiv:2212.09995•Physical Review A•Aug 26, 2024•4 citations

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 simulated quantum annealing in random Ising chains

Glen Bigan Mbeng, Lorenzo Privitera, Luca Arceci +1 more

Simulated quantum annealing (SQA) is a classical computational strategy that emulates a quantum annealing (QA) dynamics through a path-integral Monte Carlo whose parameters are changed during the simulation. Here we apply SQA to the one-dimensional transverse field Ising chain, where previous works have shown that, in the presence of disorder, a coherent QA provides a quadratic speedup with respect to classical simulated annealing, with a density of Kibble-Zurek defects decaying as ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}2}$ as opposed to ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}1}, \ensuremath{\tau}$ being the total annealing time, while for the ordered case both give the same power law ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\approx}{\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}1/2}$. We show that the dynamics of SQA, while correctly capturing the Kibble-Zurek scaling ${\ensuremath{\tau}}^{\ensuremath{-}1/2}$ for the ordered case, is unable to reproduce the QA dynamics in the disordered case at intermediate $\ensuremath{\tau}$. We analyze and discuss several issues related to the choice of the Monte Carlo moves (local or global in space), the time-continuum limit needed to eliminate the Trotter-discretization error, and the long autocorrelation times shown by a local-in-space Monte Carlo dynamics for large disordered samples.

arXiv:1809.02124•Physical review. B./Physical review. B•Feb 1, 2019•11 citations
In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width n^ζ and height n^α for ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.
Quantum annealing (QA) is a method for solving combinatorial optimization problems. We can estimate the computational time for QA using what is referred to as the adiabatic condition derived from the adiabatic theorem. The adiabatic condition consists of two parts: an energy gap and a transition matrix. Most past studies have focused on the relationship between the energy gap and computational time. The success probability of QA is considered to decrease exponentially owing to the exponentially decreasing energy gap at the first-order phase-transition point. In this study, through a detailed analysis of the relationship between the energy gap, transition matrix, and computational cost during QA, we propose a general method for constructing counterintuitive models wherein QA with a constant annealing time fails despite a constant energy gap, based on polynomial energy. We assume that the energy of the total Hamiltonian is at most $\mathrm{\ensuremath{\Theta}}(L)$, where LLL is the number of qubits. In our formalism, we choose a known model that exhibits an exponentially small energy gap during QA, and modify the model by adding a specific penalty term to the Hamiltonian. In the modified model, the transition matrix in the adiabatic condition becomes exponentially large as the number of qubits increases, while the energy gap remains constant. Moreover, we achieve a quadratic speedup, for which the upper bound for improvement in the adiabatic condition is determined by the polynomial energy. For concrete examples, we consider the adiabatic Grover search and the ferromagnetic ppp-spin model. In these cases, with the addition of the penalty term, although the success probability of QA on the modified models becomes exponentially small despite a constant energy gap, we are able to achieve a success probability considerably higher than that of conventional QA. Moreover, in concrete examples, we numerically show the scaling of the computational cost is quadratically improved compared to the conventional QA. Our findings pave the way for a better understanding of QA performance.
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.
Simulated quantum annealing (SQA) is a classical computational strategy that emulates a quantum annealing (QA) dynamics through a path-integral Monte Carlo whose parameters are changed during the simulation. Here we apply SQA to the one-dimensional transverse field Ising chain, where previous works have shown that, in the presence of disorder, a coherent QA provides a quadratic speedup with respect to classical simulated annealing, with a density of Kibble-Zurek defects decaying as ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}2}$ as opposed to ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}1}, \ensuremath{\tau}$ being the total annealing time, while for the ordered case both give the same power law ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\approx}{\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}1/2}$. We show that the dynamics of SQA, while correctly capturing the Kibble-Zurek scaling ${\ensuremath{\tau}}^{\ensuremath{-}1/2}$ for the ordered case, is unable to reproduce the QA dynamics in the disordered case at intermediate $\ensuremath{\tau}$. We analyze and discuss several issues related to the choice of the Monte Carlo moves (local or global in space), the time-continuum limit needed to eliminate the Trotter-discretization error, and the long autocorrelation times shown by a local-in-space Monte Carlo dynamics for large disordered samples.