Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing

• URL: http://arxiv.org/abs/2304.12872v2
• Date: Mon, 4 Dec 2023 13:50:24 GMT
• Title: Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
• Authors: Arthur Braida, Simon Martiel and Ioan Todinca
• Abstract summary: We use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 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.

Related papers

• Exponential speed-up of quantum annealing via n-local catalysts [0.0]
  We show that $n-$local catalysts can re-open the gap or prevent it from closing during the anneal process. Our analysis suggests that non-local quantum fluctuations entangling multiple qubits are key to achieving the desired quantum advantage.
  arXiv  Detail & Related papers  (2024-09-19T18:01:53Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• Minimum-Time Quantum Control and the Quantum Brachistochrone Equation [3.0616044531734192]
  We present the general solution to the full quantum brachistochrone equation. We prove that the speed of evolution under constraints is reduced with respect to the unrestricted case. We find that solving the quantum brachistochrone equation is closely connected to solving the dynamics of the Lagrange multipliers.
  arXiv  Detail & Related papers  (2022-04-27T09:26:59Z)
• Assessing the performance of quantum annealing with nonlinear driving [0.0]
  We report studies of the diabatic excitations arising from nonlinear protocols applied to the transverse field Ising chain. We find that the paradigmatic Kibble-Zurek behavior can be suppressed with pauses'' in the evolution.
  arXiv  Detail & Related papers  (2022-03-31T13:08:00Z)
• Quantum and classical annealing in a continuous space with multiple local minima [0.0]
  We show that quantum annealing yields a power law convergence, thus an exponential improvement over simulated annealing. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum.
  arXiv  Detail & Related papers  (2022-03-22T02:02:23Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• The quantum annealing gap and quench dynamics in the exact cover problem [0.0]
  Annealing explores equilibrium phases of a Hamiltonian with slowly changing parameters. Quenches are sudden changes of the Hamiltonian, producing a non-equilibrium situation.
  arXiv  Detail & Related papers  (2021-06-15T12:43:23Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions [55.41644538483948]
  We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions. We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain. We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
  arXiv  Detail & Related papers  (2020-02-05T00:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.