PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Variational Quantum Optimization using CVaR

Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, Stefan Woerner

arXiv:1907.04769v3quant-ph

TL;DR

Expectation-based optimization is natural for quantum observables but may be poorly matched to classical combinatorial problems with diagonal Hamiltonians. The paper replaces the sample mean with CVaR and reports faster convergence and better solutions across tested problems, while identifying sampling-accuracy and parameterization constraints.

  • Problem

    For combinatorial optimization with diagonal Hamiltonians, the sample mean may poorly target the best measurement outcomes that determine solutions.

  • Method

    The paper replaces expected-value minimization in VQE and QAOA with Conditional Value-at-Risk, which emphasizes the lower tail of measurement outcomes.

  • Results

    Across the tested combinatorial optimization problems, CVaR improves convergence and solution quality in simulation and on quantum hardware, reaching optimal solutions much faster on IBM hardware.

  • Takeaways & Limitations

    CVaR provides a smoother objective that emphasizes best samples while retaining a tunable connection to both the minimum and expected value.

  • Takeaways & Limitations

    Small α increases estimator standard error, requiring approximately K/α samples for expected-value-level accuracy; empirical guidance suggests α ∈[0.1, 0.25].

Abstract

from arXiv · show

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.

1 Introduction

The paper motivates variational quantum algorithms for combinatorial optimization and identifies weaknesses in expectation-based objectives. It proposes CVaR aggregation to improve VQE and QAOA performance on noisy quantum computers.

  • Combinatorial optimization problems are widely useful but often NP-hard, motivating quantum methods for quickly finding near-optimal solutions.
  • VQE and QAOA use parametrized circuits to generate trial states while a classical optimizer adjusts their parameters.
  • Expectation-based objectives have documented weaknesses for CO in VQE, while evidence about QAOA’s practical advantage over classical algorithms is mixed.
  • The paper replaces expected-value minimization with CVaR minimization, using the distribution’s tail to better target heuristic solutions.
  • Analytical and numerical studies report improved performance and robustness for VQE and QAOA, including experiments on simulators and IBM quantum hardware.

2 Variational Quantum Eigensolver

VQE maps combinatorial optimization problems to diagonal Hamiltonians and estimates their objective from measurement samples. Its parametrized circuit uses repeated rotations and entangling gates to prepare trial states for classical optimization.

  • QUBO and Ising formulations represent binary optimization problems and are NP-hard.
  • A QUBO-derived Hamiltonian replaces spin variables with Pauli Z operators, allowing its ground state to encode an optimal solution.
  • VQE applies single-qubit Y-rotations and repeated controlled-Z entangling layers, with parameters indexed by qubit and repetition.
  • On hardware, nearest-neighbor controlled-Z gates follow device connectivity to reduce two-qubit gates, while later rotation layers aid classical parameter optimization.
  • For n = 3 qubits and depth p = 2, Figure 1 illustrates the VQE variational form.
  • Measurements produce n-bit strings and Hamiltonian samples H_k(θ), whose sample mean estimates the expected value used by the classical optimizer.

3 Quantum Approximate Optimization Algorithm

QAOA is a CO-focused VQE variant whose problem-derived variational form alternates unitaries after an initial Hadamard layer. Its compact parameterization and convergence properties distinguish it from the VQE form.

  • QAOA is a hybrid quantum/classical algorithm specifically developed for combinatorial optimization.
  • QAOA can be viewed as VQE with a problem-Hamiltonian-derived variational form and has stronger convergence properties in some analyses.
  • At depth p, QAOA uses an initial Hadamard layer followed by alternating unitaries derived from the problem Hamiltonian.
  • The variational parameters β and γ are vectors in R^p, and H denotes a Hadamard gate in the defining expression.
  • As in VQE, QAOA estimates the expected value with measurement-sample means and returns the bitstring with the smallest observed Hamiltonian sample.
  • QAOA uses 2p variational parameters, compared with n(1+p) for VQE, and its circuit depth also depends on problem-Hamiltonian clauses.
  • The implementation’s gate count scales as O(n^2p) for single-qubit rotations and CNOT gates, with potentially better scaling when Q is sparse.

4 CVaR Optimization

For diagonal Hamiltonians arising from combinatorial optimization, the paper replaces sample-mean objectives with CVaR to emphasize strong measurement outcomes while retaining a smoother objective.

  • Motivation: For diagonal Hamiltonians, the best measured basis-state outcome may better reflect the practical optimization goal than the average measurement outcome.The ground state is a basis state, so selecting the minimum observed eigenvalue directly targets a candidate solution.
  • Motivation: Using the minimum observed outcome directly can produce a non-smooth, ill-behaved objective for finite samples.
  • CVaR objective: CVaR smooths this objective while continuing to focus on the lower tail of measured outcomes rather than their average.It is defined from the lower α-tail of the outcome distribution.
  • CVaR objective: As α approaches 0, CVaR approaches the minimum, whereas α = 1 recovers the expected value.Thus CVaR generalizes both the best observed sample and the sample mean.
  • CVaR objective: Replacing the sample mean with CVaR yields the algorithms CVaR-VQE and CVaR-QAOA.

5 Analysis of CVaR Optimization

The analysis formalizes how CVaR changes variational optimization landscapes and shows that its minima need not correspond to sample-mean minima. It also identifies sampling-cost and circuit-expressivity considerations.

  • Setup: The paper defines X(θ) as the QUBO objective value of a single measurement from |ψ(θ)⟩, with probabilities determined by the state amplitudes.
  • Landscape analysis: Proposition 5.1 states that local minima of the expected-value and CVaR objectives do not necessarily correspond to one another.
  • Landscape analysis: For a two-qubit example, the expected-value objective is constant in θ, while CVaR with α = 0.5 becomes sin^2 θ and has informative variation.
  • Landscape analysis: If a trial state has ground-state overlap ρ > 0, it is a global CVaR optimum for every α ≤ ρ, even when it is not a local expected-value minimum.
  • Landscape analysis: When the variational form can reach a ground state of a diagonal Hamiltonian, every global expected-value optimum is also a global CVaR optimum for any α.
  • Sampling accuracy: The empirical CVaR estimator has variance O(1/(Kα^2)), so matching expected-value accuracy requires approximately K/α samples.
  • Sampling accuracy: The analysis notes that α can be chosen independently of the number of qubits, yielding a constant sample increase for fixed accuracy in the experiments.

6 Computational experiments

Computational experiments across six combinatorial optimization problems found that CVaR generally improves convergence and optimal-solution sampling for VQE and QAOA, in simulation and on quantum hardware. Smaller α and greater circuit depth typically helped, while QAOA remained weaker at comparable depth and CVaR introduced a sample-cost trade-off.

  • Experimental setup: Experiments covered six combinatorial optimization problems, totaling 340 random instances and 14,280 test cases across multiple qubit sizes, α values, and circuit depths.The study used CVaR-VQE and CVaR-QAOA with separate depth ranges for VQE and QAOA.
  • Evaluation metrics: The evaluation measured the probability of sampling an optimal solution against normalized classical-optimization iterations, rather than aggregating objective-function values.Iterations were normalized by qubit count to compare problem sizes, and the optimal-state overlap was used across α values.
  • Simulation results: Increasing circuit depth and decreasing α improved CVaR-VQE and CVaR-QAOA performance across the simulated instances.Figure 4 tracked the fraction of instances reaching at least 1% or 10% optimal-state sampling probability.
  • Simulation results: For CVaR-VQE with p = 2 and α = 1%, almost all instances reached at least 1% optimal-state sampling probability within 50 normalized iterations, versus 60% with α = 100%.At α = 10%, most test problems reached 10% optimal-state probability within 50 normalized iterations; α = 1% did not reward overlap beyond 1%.
  • Simulation results: QAOA performed significantly worse than VQE at equivalent depth, which the authors associate with QAOA’s limited 2p variational parameters and relatively flat states.The authors state that improving QAOA may require greater depth, but large-depth circuits are difficult on noisy hardware because of gate errors and decoherence.
  • Scaling and hardware results: As problem size increased, CVaR with α ∈ [0.01, 0.25] showed obvious benefits, while small instances exhibited a ceiling effect.On hardware, smaller α accelerated optimal-solution sampling; α = 100% remained nearly flat, and α < 100% sped convergence toward a local optimum.
  • Scaling and hardware results: Quantum-hardware experiments reproduced the beneficial convergence effect seen in noiseless simulation, with CVaR appearing able to cope with hardware noise and errors.The proposed explanation is that CVaR can ignore low-quality samples and focus optimization on obtaining at least some low-objective-value samples.
  • Sampling trade-offs: Choosing α ∈ [0.1, 0.25] was suggested empirically, but matching expected-value accuracy may require 4–10 times more samples.The experiments used the same fixed sample count for every α and still showed significant CVaR benefits, including when CVaR estimates were noisier.

7 On the performance of QAOA

The paper analyzes why small-depth QAOA can produce flat quantum states, limiting the probability of sampling optimal solutions. The analysis links this behavior to the distribution of diagonal Hamiltonian values and circuit depth.

  • Motivation: Small-depth QAOA may produce relatively flat state vectors because it has few variational parameters.The paper formalizes this intuition under additional conditions.
  • Formal analysis: Proposition 7.1 bounds QAOA amplitudes using the Hamiltonian’s maximum eigenvalue multiplicity and the fraction of equal amplitudes.The bound also states that Δ_0 = 1, while Δ_p may decrease exponentially fast in p.
  • Empirical context: The hardware study compares objective values and optimal-solution probabilities for CVaR-VQE at α = 10%, 25%, and 100% across five runs.Each run uses 8,192 samples, and terminated runs contribute their last reported value to averages.
  • Special cases: When most diagonal Hamiltonian values are equal, depth-one QAOA necessarily produces exponentially small amplitudes, with magnitude O(1/2^(εn)).This condition is expressed through a high eigenvalue multiplicity δ ≥ 1 − 2^−n(1/2 + ε).
  • Interpretation: A Hamiltonian lacking sufficient information about objective-value distribution prevents small-depth QAOA from transferring enough probability mass to any basis state.The paper gives Grover’s needle-in-a-haystack problem and feasibility market-split problems as examples.
  • Interpretation: Increasing p can improve amplitude mixing when diagonal objective values are well-distributed, but fixed small depth risks retaining flat amplitudes.The paper notes that increasing p linearly in n can also achieve this effect.

8 Conclusions

The paper concludes that CVaR-based aggregation improves VQE and QAOA for combinatorial optimization. The reported evidence includes theoretical and empirical results, including a quantum-hardware demonstration.

  • 8 Conclusions: The paper introduces improved VQE and QAOA variants for combinatorial optimization using CVaR aggregation of trial-wavefunction samples.The contribution is evaluated through theoretical and empirical analysis.
  • 8 Conclusions: IBM quantum-hardware experiments show that the proposed algorithm can reach an optimal solution much faster.This demonstration is presented as evidence of increased performance compared with approaches in the literature.
  • 8 Conclusions: The implementation code for CVaR-VQE is available open source.The paper provides a GitHub repository for running the method.

A Implementation of QAOA

The QAOA implementation realizes mixer and cost-unitary components using native single-qubit rotations and CNOT gates. A two-CNOT construction implements the required controlled phase operation up to global phase.

  • A Implementation of QAOA: The mixer block UB is implemented by applying RX(−2β) to each qubit in Qiskit.X-rotations are natively supported in Qiskit.
  • A Implementation of QAOA: The cost-block operation e−iγσiZ is implemented up to a global phase with two CNOT gates and one RZ rotation.The gates used are natively supported in Qiskit.

B Portfolio Optimization on Quantum Device

The quantum-device experiment studies a six-asset portfolio problem on IBM Q Poughkeepsie using selected qubits with nearest-neighbor cyclic entanglement. Results compare CVaR levels and circuit depths through objective values and ground-state probabilities.

  • Problem setup: The portfolio instance uses n = 6, q = 0.5, budget B = 3, and penalty weight λ = 12.The penalty term enforces the budget constraint Σ_i x_i = B.
  • Hardware setup: The experiment uses IBM Q Poughkeepsie qubits 5, 6, 7, 10, 11, and 12 with nearest-neighbor cyclic entanglement.The selected topology is used for every variational-form layer.
  • Experimental design: The study reports depth p = 0 and p = 2 results, while the overall setup and depth p = 1 results appear in Section 6.2.This section therefore covers multiple circuit depths across the device experiments.
  • Results: At p = 0, α = 10% and α = 25% produce results similar to p = 1, whereas α = 100% reaches 5% ground-state probability before dropping close to zero.The objective improves even as the α = 100% ground-state probability declines.
  • Results: At p = 2, α = 10% reaches its target ground-state probability on average, α = 25% plateaus slightly below target, and α = 100% remains close to zero.For α = 100%, the probability decreases after an initial small increase.

C Additional plots

The additional plots compare VQE and QAOA across α values, qubit counts, and optimal-solution sampling probabilities, including quantum-hardware portfolio results.

  • Additional plots: Figure 11 varies α, the number of qubits, and the 1% optimal-solution overlap criterion.
  • Additional plots: Figure 10 reports CVaR-VQE hardware results for a six-asset portfolio with depth p = 2 and α = 10%, 25%, and 100%.The plots show objective values per iteration and the probability of sampling an optimal solution across five runs with 8,192 samples per α.

D Proof of Proposition 7.1

The proof analyzes QAOA amplitudes layer by layer by encoding the objective function in a diagonal Hamiltonian and bounding the number of distinct amplitude contributions.

  • Proof of Proposition 7.1: The induction starts at p = 0, where QAOA applies only a layer of Hadamard gates and all amplitudes have equal magnitude.
  • Proof of Proposition 7.1: For the induction step, the next QAOA layer applies UC(γ) followed by UB(β) to the state |ψp⟩.
  • Proof of Proposition 7.1: The objective Hamiltonian is treated as encoding the classical clause-satisfaction function, with Hz,z = C(z).The function assigns Ck(z) = 0 when clause k is unsatisfied and Ck(z) = 1 otherwise, while the goal is to maximize C(z).
  • Proof of Proposition 7.1: The mixer UB(β) = (e−iβX)⊗n transforms amplitudes using coefficients a00 = a11 = cos β and a01 = a10 = −i sin β.
  • Proof of Proposition 7.1: At most n(n^2/4)(2−δ−∆p)2n distinct values of αj are obtained in the counting argument.The bound combines contributions from the summations, including at most (n^2/4)(1−∆p)2n and (n^2/4)(1−δ)2n distinct values.
  • Proof of Proposition 7.1: The argument derives a lower bound ∆p+1 ≥ 1/(n(n^2/4)(2−δ−∆p)2n).The proof also uses that ∆p is decreasing in p and that ∆0 = 1.
Loading 1907.04769v3…