MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA

• URL: http://arxiv.org/abs/2404.14399v3
• Date: Tue, 30 Apr 2024 23:05:47 GMT
• Title: MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Authors: Bao Bach, Jose Falla, Ilya Safro,
• Abstract summary: We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on very large graphs by achieving high-quality solutions in a much faster time.
• Score: 0.7560883489000579
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on very large graphs by achieving high-quality solutions in a much faster time. Reproducibility: Our source code and results are available at https://github.com/bachbao/MLQAOA

Related papers

• Quantum Maximum Entropy Inference and Hamiltonian Learning [4.9614587340495]
  This work extends algorithms for maximum entropy inference and learning of graphical models to the quantum realm. The generalization, known as quantum iterative scaling (QIS), is straightforward, but the key challenge lies in the non-commutative nature of quantum problem instances. We explore quasi-Newton methods to enhance the performance of QIS and GD.
  arXiv  Detail & Related papers  (2024-07-16T08:11:34Z)
• Hamiltonian-based Quantum Reinforcement Learning for Neural Combinatorial Optimization [2.536162003546062]
  We introduce Hamiltonian-based Quantum Reinforcement Learning (QRL) an approach at the intersection of Quantum Computing (QC) and Neuralial Optimization (NCO) Our ansatzes show favourable trainability properties when compared to the hardware efficient ansatzes, while also not being limited to graph-based problems, unlike previous works. In this work, we evaluate the performance of Hamiltonian-based QRL on a diverse set of optimization problems to demonstrate the broad applicability of our approach and compare it to QAOA.
  arXiv  Detail & Related papers  (2024-05-13T14:36:22Z)
• Quantum Graph Optimization Algorithm [7.788671046805509]
  This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism. In terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA.
  arXiv  Detail & Related papers  (2024-04-09T16:25:07Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Quantum-Informed Recursive Optimization Algorithms [0.0]
  We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps. We use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.
  arXiv  Detail & Related papers  (2023-08-25T18:02:06Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)

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.