A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation

• URL: http://arxiv.org/abs/2310.17927v6
• Date: Fri, 26 Jan 2024 02:11:50 GMT
• Title: A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation
• Authors: Da You Lv and An Min Wang
• Abstract summary: We propose a general-purpose pure quantum approximate optimization algorithm. The algorithm is constructed to a $p$-level divide-and-conquer structure. We show the algorithm performance in detail when the required qubits number of the two optimization problems is 10.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: By introducing the "comparison and replacement" (CNR) operation, we propose a general-purpose pure quantum approximate optimization algorithm and derive its core optimization mechanism quantitatively. The algorithm is constructed to a $p$-level divide-and-conquer structure based on the CNR operations. The quality of approximate optimization improves with the increase of $p$. For sufficiently general optimization problems, the algorithm can work and produce the near-optimal solutions as expected with considerably high probability. Moreover, we demonstrate that the algorithm is scalable to be applied to large size problems. Our algorithm is applied to two optimization problems with significantly different degeneracy, the Gaussian weighted 2-edge graph and MAX-2-XOR, and then we show the algorithm performance in detail when the required qubits number of the two optimization problems is 10.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Recursive Quantum Approximate Optimization Algorithm for the MAX-CUT problem on Complete graphs [1.90365714903665]
  Quantum approximate optimization algorithms are hybrid quantum-classical variational algorithms designed to approximately solve optimization problems such as the MAX-CUT problem. In spite of its potential for near-term quantum applications, it has been known that quantum approximate optimization algorithms have limitations for certain instances to solve the MAX-CUT problem.
  arXiv  Detail & Related papers  (2022-11-28T23:51:02Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Optimizing Optimizers: Regret-optimal gradient descent algorithms [9.89901717499058]
  We study the existence, uniqueness and consistency of regret-optimal algorithms. By providing first-order optimality conditions for the control problem, we show that regret-optimal algorithms must satisfy a specific structure in their dynamics. We present fast numerical methods for approximating them, generating optimization algorithms which directly optimize their long-term regret.
  arXiv  Detail & Related papers  (2020-12-31T19:13:53Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  We consider the task of decentralized minimization of the sum of smooth strongly convex functions stored across the nodes of a network. We propose two new algorithms for this decentralized optimization problem and equip them with complexity guarantees.
  arXiv  Detail & Related papers  (2020-06-21T11:23:20Z)
• 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)

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.