Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters

• URL: http://arxiv.org/abs/2307.14079v4
• Date: Mon, 8 Jan 2024 17:48:23 GMT
• Title: Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Authors: Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele, and Procolo Lucignano
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Digitized-Counterdiabatic (CD) Quantum Approximate Optimization Algorithm (QAOA) has been proposed to make QAOA converge to the solution of an optimization problem in fewer steps, inspired by Trotterized counterdiabatic driving in continuous-time quantum annealing. In this paper, we critically revisit this approach by focusing on the paradigmatic weighted and unweighted one-dimensional MaxCut problem. We study two variants of QAOA with first and second-order CD corrections. Our results show that, indeed, higher order CD corrections allow for a quicker convergence to the exact solution of the problem at hand by increasing the complexity of the variational cost function. Remarkably, however, the total number of free parameters needed to achieve this result is independent of the particular QAOA variant analyzed.

Related papers

• Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
  We show that the search space of the quadratic assignment problem can be reduced using Grover adaptive search (GAS) with Dicke state operators. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty.
  arXiv  Detail & Related papers  (2024-10-16T03:00:37Z)
• The role of gaps in digitized counterdiabatic QAOA for fully-connected spin models [0.0]
  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.
  arXiv  Detail & Related papers  (2024-09-05T13:17:56Z)
• 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)
• Optimizing Counterdiabaticity by Variational Quantum Circuits [3.4092751295027997]
  We propose a technique of finding optimal coefficients of the CD terms using a variational quantum circuit. By classical optimizations routines, the parameters of this circuit are optimized to provide the coefficients corresponding to the CD terms. Their improved performance is exemplified in Greenberger-Horne-Zeilinger state preparation on nearest-neighbor Ising model.
  arXiv  Detail & Related papers  (2022-08-03T14:12:26Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
  We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the challenges for graph maximum cut (MaxCut) problem. DC-QAOA achieves 97.14% approximation ratio (20.32% higher than classical counterpart) It also reduces the time complexity of conventional QAOA from exponential to quadratic.
  arXiv  Detail & Related papers  (2021-02-26T03:10:30Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems. We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
  arXiv  Detail & Related papers  (2020-05-20T18:00:01Z)

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.