Multistart Methods for Quantum Approximate Optimization

Abstract

Hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) are considered one of the most promising approaches for leveraging near-term quantum computers for practical applications. Such algorithms are often implemented in a variational form, combining classical optimization methods with a quantum machine to find parameters to maximize performance. The quality of the QAOA solution depends heavily on quality of the parameters produced by the classical optimizer. Moreover, the presence of multiple local optima in the space of parameters makes it harder for the classical optimizer. In this paper we study the use of a multistart optimization approach within a QAOA framework to improve the performance of quantum machines on important graph clustering problems. We also demonstrate that reusing the optimal parameters from similar problems can improve the performance of classical optimization methods, expanding on similar results for MAXCUT.

References in corpus (5)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Graph spectra and the detectability of community structure in networks
• Network Community Detection On Small Quantum Computers

Cited by in corpus (32)

• Variational Quantum Algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing for Finance: State of the Art and Future Prospects
• Warm-starting quantum optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Hybrid quantum-classical algorithms for approximate graph coloring
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Scaling Quantum Approximate Optimization on Near-term Hardware
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Syndrome decoding by quantum approximate optimization
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• Variational Quantum Algorithm Landscape Reconstruction by Low-Rank Tensor Completion