Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut

Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Quantum Computing Association for Computing Machinery

Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut

Download PDF
15 pages

Loading next page...
 
/lp/association-for-computing-machinery/parameter-transfer-for-quantum-approximate-optimization-of-weighted-02RXyjHujO
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s).
ISSN
2643-6809
eISSN
2643-6817
DOI
10.1145/3584706
Publisher site
See Article on Publisher Site

Abstract

Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.

Journal

ACM Transactions on Quantum Computing – Association for Computing Machinery

Published: Apr 24, 2023

Keywords: QAOA

References

  • Quantum supremacy using a programmable superconducting processor
    [,
  • Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
    [,
  • Quantum computer systems for scientific discovery
    [,
  • Quantum optimization
    [,
  • A quantum approximate optimization algorithm
    [,
  • Counterdiabaticity and the quantum approximate optimization algorithm
    [,
  • Predicting parameters for the quantum approximate optimization algorithm for Max-Cut from the infinite-size limit
    [,
  • The quantum approximate optimization algorithm and the Sherrington–Kirkpatrick model at infinite size
    [,
  • MaxCut quantum approximate optimization algorithm performance guarantees for \(p \gt 1\)
    [,
  • Tensor network quantum simulator with step-dependent parallelization
    [,
  • Classical variational simulation of the quantum approximate optimization algorithm
    [,
  • Classical symmetries and the quantum approximate optimization algorithm
    [,
  • Evaluating quantum approximate optimization algorithm: A case study
    [,
  • Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices
    [,
  • Performance of the quantum approximate optimization algorithm on the maximum cut problem
    [,
  • Multistart methods for quantum approximate optimization
    [,
  • Exploiting symmetry reduces the cost of training QAOA
    [,
  • Empirical performance bounds for quantum approximate optimization
    [,
  • Transferability of optimal QAOA parameters between random graphs
    [,
  • The fixed angle conjecture for QAOA on regular MaxCut graphs
    [,
  • For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances
    [,
  • Ising formulations of many NP problems
    [,
  • Modularity and community structure in networks
    [,
  • QAOAKit: A toolkit for reproducible study, application, and verification of QAOA
    [,
  • QAOAKit
    [,
  • Quantum Algorithms for Scientific Computing and Approximate Optimization
    [,
  • Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems
    [,
  • Quantum approximate optimization algorithm for MaxCut: A fermionic view
    [,
  • The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington–Kirkpatrick model
    [,
  • QAOAKit/data
    [,
  • QAOAKit/data
    [,
  • Learning to optimize variational quantum circuits to solve combinatorial problems
    [,
  • QAOAKit/examples
    [,
  • Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed
    [,
  • The NLopt Nonlinear-Optimization Package
    [,
  • Updating quasi-Newton matrices with limited storage
    [,
  • On the limited memory BFGS method for large scale optimization
    [,
  • Scikit-learn: Machine learning in Python
    [,