A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization

• URL: http://arxiv.org/abs/2408.07793v1
• Date: Wed, 14 Aug 2024 20:06:32 GMT
• Title: A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization
• Authors: Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, Davide Venturelli,
• Abstract summary: We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
• Score: 3.3493770627144004
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are relatively small, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened, and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform as a sub-solver within such a multilevel strategy. We combine and extend (via additional classical processing) the recent Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax $\&$ Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's transmon device Ankaa-2. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range $\sim 0.98-1.0$, and the same class with real-valued coefficients (ARs $\sim 0.94-1.0$). Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for $6$ large-scale graphs with at most $\sim 27,000$ variables. The QPU (with classical post-processing steps) is used to find approximate solutions to dozens of problems, at most $82$-qubit, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classical heuristics used as subsolvers within the multilevel approach.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Variational Quantum Multi-Objective Optimization [5.381539115778766]
  We present a variational quantum optimization algorithm to solve discrete multi-objective optimization problems on quantum computers. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives.
  arXiv  Detail & Related papers  (2023-12-21T18:59:21Z)
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
  We propose a framework for designing QAOA circuits to solve larger-scale Max-Cut problem. We derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Our framework only consumes $18$ qubits and $0.9950$ approximation ratio on average.
  arXiv  Detail & Related papers  (2023-07-28T02:06:42Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels [0.0]
  The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. We build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz. We find that the performance of the quantum algorithm depends heavily on what noise model is used.
  arXiv  Detail & Related papers  (2022-05-13T11:29:12Z)
• An evolving objective function for improved variational quantum optimisation [0.0]
  We introduce an evolving objective function, which we call Ascending-CVaR and that can be used for any optimisation problem. We show that Ascending-CVaR in all cases performs better than standard objective functions or the "constant" CVaR of Barkoutsos et al (Quantum 2020) Our proposal achieves higher overlap with the ideal state in all problems, whether we consider easy or hard instances.
  arXiv  Detail & Related papers  (2021-05-25T09:03:56Z)
• 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)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20: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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.