Enhancing the Energy Gap of Random Graph Problems via XX-catalysts in Quantum Annealing

• URL: http://arxiv.org/abs/2409.16350v1
• Date: Tue, 24 Sep 2024 18:00:01 GMT
• Title: Enhancing the Energy Gap of Random Graph Problems via XX-catalysts in Quantum Annealing
• Authors: Luca A. Nutricati, Roopayan Ghosh, Natasha Feinstein, Sougato Bose, Paul A. Warburton,
• Abstract summary: We show that employing multiple XX-catalysts on the edges of a graph significantly enhances the minimum energy gap. Remarkably, our analysis shows that the more severe the first-order phase transition, the more effective the catalyst is in opening the gap.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the bottlenecks in solving combinatorial optimisation problems using quantum annealers is the emergence of exponentially-closing energy gaps between the ground state and the first excited state during the annealing, which indicates that a first-order phase transition is taking place. The minimum energy gap scales inversely with the exponential of the system size, ultimately resulting in an exponentially large time required to ensure the adiabatic evolution. In this paper we demonstrate that employing multiple XX-catalysts on all the edges of a graph upon which a MWIS (Maximum Weighted Independent Set) problem is defined significantly enhances the minimum energy gap. Remarkably, our analysis shows that the more severe the first-order phase transition, the more effective the catalyst is in opening the gap. This result is based on a detailed statistical analysis performed on a large number of randomly generated MWIS problem instances on both Erd\H{o}s-R\'enyi and Barab\'asi-Albert graphs. We also observe that similar performance cannot be achieved by the non-stoquastic version of the same catalyst, with the stoquastic catalyst being the preferred choice in this context.

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)
• Thermalization and Criticality on an Analog-Digital Quantum Simulator [133.58336306417294]
  We present a quantum simulator comprising 69 superconducting qubits which supports both universal quantum gates and high-fidelity analog evolution. We observe signatures of the classical Kosterlitz-Thouless phase transition, as well as strong deviations from Kibble-Zurek scaling predictions. We digitally prepare the system in pairwise-entangled dimer states and image the transport of energy and vorticity during thermalization.
  arXiv  Detail & Related papers  (2024-05-27T17:40:39Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  We present a new optimization-based method for sampling called mollified interaction energy descent (MIED) MIED minimizes a new class of energies on probability measures called mollified interaction energies (MIEs) We show experimentally that for unconstrained sampling problems our algorithm performs on par with existing particle-based algorithms like SVGD.
  arXiv  Detail & Related papers  (2022-10-24T16:54:18Z)
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model [0.0]
  We propose a nonstoquastic catalyst to improve the efficiency of a ground-state search. A semiclassical analysis shows that the problematic first-order phase transition can be eliminated. We find that while the energy gap decreases with increasing system size for the original Hamiltonian, it decreases exponentially against the system size for the Hamiltonian with the nonstoquastic catalyst.
  arXiv  Detail & Related papers  (2022-09-05T02:53:41Z)
• Effects of XX-catalysts on quantum annealing spectra with perturbative crossings [0.0]
  We show that non-stoquastic XX-couplings can significantly reduce the gap closing with system size at an avoided level crossing. We also study how the evolution of the ground-state vector is altered by the presence of the catalyst and find that the negative components of the ground-state vector are key to understanding the response of the gap spectrum.
  arXiv  Detail & Related papers  (2022-03-13T22:28:52Z)
• Determination of the critical exponents in dissipative phase transitions: Coherent anomaly approach [51.819912248960804]
  We propose a generalization of the coherent anomaly method to extract the critical exponents of a phase transition occurring in the steady-state of an open quantum many-body system.
  arXiv  Detail & Related papers  (2021-03-12T13:16:18Z)
• Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction [24.794221009364772]
  We study the reduction for a noisy energy estimators variance, which promotes much more effective analysis. We obtain the state-of-the-art results in optimization and uncertainty estimates for synthetic experiments and image data.
  arXiv  Detail & Related papers  (2020-10-02T16:23:35Z)
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling [55.498092486970364]
  Nesterov's Accelerated Gradient (NAG) for optimization has better performance than its continuous time limit (noiseless kinetic Langevin) when a finite step-size is employed. This work explores the sampling counterpart of this phenonemon and proposes a diffusion process, whose discretizations can yield accelerated gradient-based MCMC methods.
  arXiv  Detail & Related papers  (2020-06-16T15:07:37Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)
• Reduction of the energy-gap scaling by coherent catalysis in models of quantum annealing [0.0]
  We show that some Hamiltonians still exhibit unavoidable first-order transitions even with non-stoquastic drivers. This opens up the possibility of using coherent to search for exponential speedups in systems previously thought to be exponentially slow.
  arXiv  Detail & Related papers  (2019-12-27T00:34:09Z)

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.