The role of gaps in digitized counterdiabatic QAOA for fully-connected spin models

• URL: http://arxiv.org/abs/2409.03503v2
• Date: Tue, 12 Nov 2024 14:38:53 GMT
• Title: The role of gaps in digitized counterdiabatic QAOA for fully-connected spin models
• Authors: Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele, Procolo Lucignano,
• Abstract summary: CD corrections to the quantum approximate optimization algorithm (QAOA) have been proposed, yielding faster convergence within the desired accuracy than standard QAOA. We show that the performances of the algorithm are related to the spectral properties of the instances analyzed.
• Score: 0.0
• License:
• Abstract: Recently, digitized-counterdiabatic (CD) corrections to the quantum approximate optimization algorithm (QAOA) have been proposed, yielding faster convergence within the desired accuracy than standard QAOA. In this manuscript, we apply this approach to a fully-connected spin model with random couplings. We show that the performances of the algorithm are related to the spectral properties of the instances analyzed. In particular, the larger the gap between the ground state and the first excited states, the better the convergence to the exact solution.

Related papers

• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters [0.0]
  We show that higher order CD corrections allow for a quicker convergence to the exact solution of the problem at hand. Remarkably, however, the total number of free parameters needed to achieve this result is independent of the particular QAOA variant analyzed.
  arXiv  Detail & Related papers  (2023-07-26T10:02:47Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• 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)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time. This is the first speed-up of this type to be obtained over the seminal nearly-linear time of vStefankovivc, Vempala and Vigoda.
  arXiv  Detail & Related papers  (2022-07-18T14:41:48Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  We consider approximations of sampling algorithms, such as Gradient Langevin Dynamics (SGLD) and the Random Batch Method (RBM) for Interacting Particle Dynamcs (IPD) We observe that the noise introduced by the approximation is nearly Gaussian due to the Central Limit Theorem (CLT) while the driving Brownian motion is exactly Gaussian. We harness this structure to absorb the approximation error inside the diffusion process, and obtain improved convergence guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-06-08T10:17:40Z)
• Digitized-counterdiabatic quantum approximate optimization algorithm [3.0638256603183054]
  We propose a digitized version of QAOA enhanced via the use of shortcuts to adiabaticity. We apply our digitized-counterdiabatic QAOA to Ising models, classical optimization problems, and the P-spin model, demonstrating that it outperforms standard QAOA in all cases.
  arXiv  Detail & Related papers  (2021-07-06T17:57:32Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size [0.0]
  We show that for mixed-spin models the performance of depth $1$ QAOA is independent of the specific instance in the limit of infinite sized systems. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.
  arXiv  Detail & Related papers  (2021-02-24T03:19:15Z)

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.