Analytic study of quantum annealing

We propose a modified quantum annealing protocol, i. e., pulsed quantum annealing} (PQA), in order to increase the success probability by a pulse application during the quantum annealing process. It is well known that the success probability of the conventional quantum annealing is reduced due to the Landau-Zener transitions. By applying a pulse to the system, we modulate the success probability and increase it, compared to the conventional quantum annealing, by optimizing the pulse parameters. We demonstrate our findings for a single qubit both numerically and analytically. The analytical model is based on the tranfer matrix approach and it is in good agreement with the full numerical results. We also investigate the PQA protocol for multi-qubit cases $i. e.,$ random spin-glass instances, and we present an overall increase of the success probability over the conventional quantum annealing, by optimizing the pulse parameters. Our results indicate that PQA can be used to design future high-performance quantum annealing machines, especially for hard instances that the conventional QA protocol behaves poorly.We propose a modified quantum annealing protocol, i. e., pulsed quantum annealing} (PQA), in order to increase the success probability by a pulse application during the quantum annealing process. It is well known that the success probability of the conventional quantum annealing is reduced due to the Landau-Zener transitions. By applying a pulse to the system, we modulate the success probability and increase it, compared to the conventional quantum annealing, by optimizing the pulse parameters. We demonstrate our findings for a single qubit both numerically and analytically. The analytical model is based on the tranfer matrix approach and it is in good agreement with the full numerical results. We also investigate the PQA protocol for multi-qubit cases $i. e.,$ random spin-glass instances, and we present an overall increase of the success probability over the conventional quantum annealing, by optimizing the pulse parameters. Our results indicate that PQA can be used to design future high-performance quantum annealing machines, especially for hard instances that the conventional QA protocol behaves poorly.

arXiv:1806.08517Journal of the Physical Society of JapanAug 17, 20207 citations

Statistical Analysis of Quantum Annealing

Yazhen Wang, Shang Wu, Hongzhi Liu

Statistica SinicaNov 29, 20210 citations

Analytical solution for ground state estimation by a nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian

Bin Yan, Nikolai A. Sinitsyn

We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian $H_I$ by implementing time evolution with a Hamiltonian $H(t)=H_I+g(t) H_t$ . We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling $g(t)$ and a specific mixing Hamiltonian $H_t$ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of $H_I$ , the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time $T$ and uncorrelated from the $H_I$ annealing schedule. This proves the possibility for spin glasses of a faster than $\sim 1/\log^{\beta} T$ energy relaxation.We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian $H_I$ by implementing time evolution with a Hamiltonian $H(t)=H_I+g(t) H_t$. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling $g(t)$ and a specific mixing Hamiltonian $H_t$ that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of $H_I$, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time $T$ and uncorrelated from the $H_I$ annealing schedule. This proves the possibility for spin glasses of a faster than $\sim 1/\log^{\beta} T$ energy relaxation.

Oct 24, 20210 citations

Experiments on Quantum Annealing

G. Aeppli, T. F. Rosenbaum

Lecture notes in physicsNov 16, 20052 citations

Avoided level crossings with exponentially closing gaps in quantum annealing

Arthur Braida, Simon Martiel, Ioan Todinca

This paper explores the phenomenon of avoided level crossings in quantum annealing, a promising framework for quantum computing that may provide a quantum advantage for certain tasks. Quantum annealing (QA) involves letting a quantum system evolve according to the Schr\"odinger equation, with the goal of obtaining the optimal solution to an optimization problem through measurements of the final state. However, the continuous nature of quantum annealing makes analytical analysis challenging, particularly with regard to the instantaneous eigenenergies. The adiabatic theorem provides a theoretical result for the annealing time required to obtain the optimal solution with high probability, which is inversely proportional to the square of the minimum spectral gap. Avoided level crossings can create exponentially closing gaps, which can lead to exponentially long running times for optimization problems. In this paper, we use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We then apply this condition to the MaxCut problem on bipartite graphs. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case. On the other hand, we show that irregularities in the vertex degrees can lead to the satisfaction of the avoided level crossing occurrence condition. We provide numerical evidence to support this theoretical development, and discuss the relation between the presence of exponentially closing gaps and the failure of quantum annealing.This paper explores the phenomenon of avoided level crossings in quantum annealing, a promising framework for quantum computing that may provide a quantum advantage for certain tasks. Quantum annealing (QA) involves letting a quantum system evolve according to the Schr\"odinger equation, with the goal of obtaining the optimal solution to an optimization problem through measurements of the final state. However, the continuous nature of quantum annealing makes analytical analysis challenging, particularly with regard to the instantaneous eigenenergies. The adiabatic theorem provides a theoretical result for the annealing time required to obtain the optimal solution with high probability, which is inversely proportional to the square of the minimum spectral gap. Avoided level crossings can create exponentially closing gaps, which can lead to exponentially long running times for optimization problems. In this paper, we use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We then apply this condition to the MaxCut problem on bipartite graphs. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case. On the other hand, we show that irregularities in the vertex degrees can lead to the satisfaction of the avoided level crossing occurrence condition. We provide numerical evidence to support this theoretical development, and discuss the relation between the presence of exponentially closing gaps and the failure of quantum annealing.

arXiv:2304.12872Physical Review AFeb 12, 20242 citations

Assessing the Quantum in Quantum Annealing

Wade DeGottardi, David Ferguson, С. А. Новиков +2 more

Bulletin of the American Physical SocietyMar 7, 20190 citations

i. e.,

random spin-glass instances, and we present an overall increase of the success probability over the conventional quantum annealing, by optimizing the pulse parameters. Our results indicate that PQA can be used to design future high-performance quantum annealing machines, especially for hard instances that the conventional QA protocol behaves poorly.

We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian

H_I

by implementing time evolution with a Hamiltonian

H(t)=H_I+g(t) H_t

. We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling

g(t)

and a specific mixing Hamiltonian

H_t

that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of

H_I

, the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time

T

and uncorrelated from the

H_I

annealing schedule. This proves the possibility for spin glasses of a faster than

\sim 1/\log^{\beta} T

energy relaxation.