CoChat
Sign Up
Cited by 263Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchQuantum Information and Cryptography

Improving Variational Quantum Optimization using CVaR

Open access
Barkoutsos, Panagiotis Kl., Nannicini, Giacomo, Robert, Anton, Tavernelli, Ivano, Woerner, Stefan·2020·Quantum
DOI 10.22331/q-2020-04-20-256
Open this paper in CoChat — free accountOpen PDF

Abstract

Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.22331/q-2020-04-20-256

Cites

13 of 13 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • All of the objective function approaches (CVar, ascending CVar, Gibbs) serve to foster low-energy solutions and simultaneously avoid getting trapped in local minima.

    “All of these approaches serve to foster low-energy solutions and simultaneously avoid to get trapped in local minima.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [10]

    Section 4 says CVaR emphasizes the best observed, low-energy outcomes, and Section 5 gives an example where CVaR removes a local minimum of the expected-value objective. But Section 5 also says local minima do not map reliably between the objectives. Our copy does not establish that CVaR generally avoids local minima, or address that claim for ascending CVaR and Gibbs objectives. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Experiments utilizing CVar and ascending CVar as the underlying objective function suggest that VQE is more promising than QAOA for shallow circuits due to the reachability issues of QAOA.

    “Experiments utilizing CVar and ascending CVar as the underlying objective function suggest that VQE is more promising than QAOA for shallow circuits due to the reachability issues of QAOA [10, 78].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [10]

    Section 6.1 (Results I: Simulation) reports that QAOA performed substantially worse than VQE at equivalent shallow depths and attributes this tentatively to QAOA’s limited parameters and low overlap with the ground state. Section 4 describes CVaR as an objective for both algorithms, but our copy does not report experiments using an “ascending CVaR” objective; the paper’s explanation for QAOA’s performance is also framed as a conjecture. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Empirically, by tuning hyperparameters, both CVaR and Gibbs measures have been shown to outperform <H> for certain combinatorial optimization problems.

    “Empirically, by tuning the hyperparameters, both measures have been shown to outperform ⟨ H ⟩ for certain combinatorial optimization problems (Barkoutsos et al. , 2020; Li et al. , 2020).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Barkoutsos et al., 2020

  • The VQE approach can be used to solve CO problems.

    “However, with the mappings of CO problems to Hamiltonians stated in the previous section, besides quantum chemical problems, the same approach can be used to solve CO problems [10].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [10]

  • CVar, ascending CVar, and the Gibbs objective function can be regarded as adaptations of standard QAOA or VQE that affect their underlying objective function.

    “In this sense, CVar [10], ascending CVar [78], and the Gibbs objective function [86] can be regarded as adaptations of standard QAOA or VQE that affect their underlying objective function.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [10]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 6

  1. Gavin E Crooks. Performance of the quan- tum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419, 2018. URL https:// arxiv.org/abs/1811.08419. · arXiv
  2. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Op- timization Algorithm. arXiv preprint arXiv:1411.4028, pages 1-16, 2014. URL http://arxiv.org/abs/1411.4028. · arXiv
  3. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Opti- mization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv preprint arXiv:1412.6062, 2014. URL http: //arxiv.org/abs/1412.6062. · arXiv
  4. Edward Farhi, Jeffrey Goldstone, Sam Gut- mann, and Hartmut Neven. Quantum algo- rithms for fixed qubit architectures. arXiv preprint arXiv:1703.06199, 2017. URL https://arxiv.org/abs/1703.06199. · arXiv
  5. Matthew B Hastings. Classical and quantum bounded depth approximation algorithms. arXiv preprint arXiv:1905.07047, 2019. URL https://arxiv.org/abs/1905.07047. · arXiv
  6. Murphy Yuezhen Niu, Sirui Lu, and Isaac L Chuang. Optimizing qaoa: Success probabil- ity and runtime dependence on circuit depth. arXiv preprint arXiv:1905.12134, 2019. URL https://arxiv.org/abs/1905.12134. · arXiv

Cited by

Sorted by citations

Related

Authors
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S.
Affiliations
  • IBM Research - Zurich (CH)
  • IBM Research - Thomas J. Watson Research Center (US)
  • Université Paris Sciences et Lettres (FR)
ORCID
Venue
Quantum
Publisher
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
Published
2020-04-20
Volume
4
Pages
256
ISSN
2521-327X (ISSN-L)
DOI
10.22331/q-2020-04-20-256
OpenAlex
W2960556599
Cited by
263
References
13
Citations by year
2026: 28 · 2025: 42 · 2024: 51 · 2023: 56 · 2022: 34 · 2021: 34 · 2020: 16 · 2019: 2
FWCI
13.76
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
  • Greater South Information System
Funders
  • International Business Machines Corporation
  • Air Force Research Laboratory (FA8750-C-18-0098)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
variational quantum optimization, conditional value at risk, combinatorial optimization, hybrid quantum-classical algorithms, sample aggregation, NISQ devices, convergence rate

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review