Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems

• URL: http://arxiv.org/abs/2310.05062v2
• Date: Tue, 10 Oct 2023 02:11:43 GMT
• Title: Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems
• Authors: Bo Yue, Shibei Xue, Yu Pan, Min Jiang, Daoyi Dong
• Abstract summary: Quantum Approximate Optimization Algorithm (QAOA) is considered as a promising candidate to demonstrate quantum supremacy. limited qubit availability and restricted coherence time challenge QAOA to solve large-scale pseudo-Boolean problems. We propose a distributed QAOA which can solve a general pseudo-Boolean problem by converting it to a simplified Ising model.
• Score: 7.723735038335632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With the rapid advancement of quantum computing, Quantum Approximate Optimization Algorithm (QAOA) is considered as a promising candidate to demonstrate quantum supremacy, which exponentially solves a class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, limited qubit availability and restricted coherence time challenge QAOA to solve large-scale pseudo-Boolean problems on currently available Near-term Intermediate Scale Quantum (NISQ) devices. In this paper, we propose a distributed QAOA which can solve a general pseudo-Boolean problem by converting it to a simplified Ising model. Different from existing distributed QAOAs' assuming that local solutions are part of a global one, which is not often the case, we introduce community detection using Louvian algorithm to partition the graph where subgraphs are further compressed by community representation and merged into a higher level subgraph. Recursively and backwards, local solutions of lower level subgraphs are updated by heuristics from solutions of higher level subgraphs. Compared with existing methods, our algorithm incorporates global heuristics into local solutions such that our algorithm is proven to achieve a higher approximation ratio and outperforms across different graph configurations. Also, ablation studies validate the effectiveness of each component in our method.

Related papers

• Distributed Quantum Approximate Optimization Algorithm on Integrated High-Performance Computing and Quantum Computing Systems for Large-Scale Optimization [1.7099366779394252]
  Quantum approximated optimization algorithm (QAOA) has shown promise for solving optimization problems by providing quantum speedup on gate-based quantum computing systems. We propose a distributed QAOA (DQAOA), which leverages a high-performance computing-quantum computing integrated system. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible with our strategies.
  arXiv  Detail & Related papers  (2024-07-29T17:42:25Z)
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
  We use basin-hopping global methods to navigate the energy landscapes for QAOA ans"atze for various graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities.
  arXiv  Detail & Related papers  (2024-01-09T19:17:01Z)
• Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization [0.0]
  We propose a global optimization algorithm based on quantizing the energy level of an objective function in an NP-hard problem. Numerical experiments show that the proposed algorithm outperforms conventional learning methods in solving NP-hard optimization problems.
  arXiv  Detail & Related papers  (2022-11-08T03:01:45Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear Programs [0.4925222726301578]
  We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm. The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price.
  arXiv  Detail & Related papers  (2021-03-29T08:59:26Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
  arXiv  Detail & Related papers  (2020-11-10T22:17:50Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

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.