Conditional-value-at-risk objective

What it fills

• Minimise the objective over the parameters

  Search the parameters of a fixed circuit family for the ones that minimise a chosen objective, given that every evaluation of that objective is a noisy estimate someone paid shots for. The output is a routine that prepares one particular state — the family collapsed to a member.

When it applies

Restricted, by the authors' own argument, to classical optimization problems — the ones "which yield diagonal Hamiltonians". Barkoutsos et al. are explicit that expectation-value aggregation "is fully justified for quantum mechanical observables such as molecular energies" and that it is the diagonal case where "aggregating the samples in a different way than the expected value is more natural". So this belongs to the combinatorial branch of the variational family and not to the chemistry branch that the rest of this region is drawn from. The evidence offered is empirical — "using classical simulation as well as quantum hardware" — over the problems in that study, alongside analytical results explaining the differences observed.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  parameterized circuit family  U(theta)|0> = |psi(theta)>
           = sum_j alpha_j(theta) |j>
       problem Hamiltonian H, diagonal in the computational basis (a QUBO
           Hamiltonian), so |j> is an eigenstate of H with eigenvalue H_jj
       confidence level alpha, with 0 < alpha <= 1                   (Eq. 11)
       shot budget K per evaluation of theta

requires  H diagonal -- the authors justify replacing the sample mean only
    for classical optimization problems, "which yield diagonal
    Hamiltonians"; for a quantum-mechanical observable such as a molecular
    energy they say the ordinary sample mean "is fully justified" and do
    not extend this construction to that case         (Abstract -- Sec. 4
    restates the restriction in its own words, not in these phrases)

# --- one CVaR evaluation, at a fixed theta ----------------------------------
prepare |psi(theta)> and measure it K times in the computational basis
    x_1, ..., x_K  ->  H_1, ..., H_K
        # Hk is read off each bitstring by a parity check over the Pauli-Z
        #   terms of H, not by an extra circuit or extra state prep     (Sec. 2)
        # the batch samples the random variable X(theta), with outcomes H_jj
        #   and  Prob(X(theta) = H_jj) = |alpha_j(theta)|^2 -- though the
        #   paper defines X(theta) only later, when analysing the
        #   landscape, not where CVaR is introduced                     (Sec. 5)

sort the batch so H_1 <= H_2 <= ... <= H_K
    # "without loss of generality" -- the paper's own framing            (Sec. 4)

CVaR_alpha = (1 / ceil(alpha*K)) * sum_{k=1}^{ceil(alpha*K)} H_k        (Eq. 12)
    # USE THIS FORM. The paper prints the same sum from k=0, over a batch
    #   it has just indexed k=1,...,K -- H_0 is not a member of that batch,
    #   so Eq. 12 as printed is undefined; k=1 is taken here because it is
    #   the substitution that makes the number of summed terms match the
    #   ceil(alpha*K) divisor                                           (Sec. 4)
    # this is the EMPIRICAL estimator over K samples, NOT the population
    #   quantity CVaR_alpha(X) = E[X | X <= F_X^-1(alpha)], the mean of
    #   the lower alpha-tail, which is what the paper defines           (Eq. 11)
    # its variance is cited as O(1/(K*alpha^2)) from ref. [13], which the
    #   authors note establishes that dependence only for CONTINUOUS
    #   distributions; they expect it to approximate the discrete,
    #   finite-batch case well as the qubit count grows                 (Sec. 5)
    # alpha approaching 0 recovers min{H_1,...,H_K}; alpha = 1 recovers the
    #   ordinary sample mean (Eq. 5) -- CVaR generalizes both           (Sec. 4)

# --- outer loop: classical optimization over theta --------------------------
repeat until the classical optimizer's own stopping rule fires:
    theta <- one step of a classical optimizer minimizing CVaR_alpha(X(theta))
        # this objective is Eq. 13, min_theta CVaR_alpha(X(theta)), stated
        #   in the analysis section rather than in the section that
        #   introduces CVaR                                    (Eq. 13; Sec. 5)
        # the paper places no bound on the number of outer iterations; its
        #   own experiments use COBYLA as one concrete, empirical choice,
        #   not as part of the method's definition                      (Sec. 6)

return  the single bitstring, among ALL measurements taken at ALL theta
        visited during the run, with the smallest Hk seen -- this is NOT
        the CVaR estimate at the final theta                            (Sec. 2)
    # stated in Sec. 2 for the plain sample-mean algorithm; the paper obtains
    #   the CVaR variants "simply by replacing the sample mean (5) with
    #   CVaR_alpha in the classical optimization algorithm" and never
    #   re-states the reporting rule for them, so carrying it over is an
    #   inference from that sentence, not a quoted claim                (Sec. 4)

# a local minimum of the CVaR objective (13) need not be a local minimum of
#   the expectation objective (1), and vice versa -- proved by a two-qubit
#   counterexample with H = diag(0,1,1,2), so minimizing CVaR_alpha is NOT
#   shown to preserve the landscape of the objective it replaces   (Prop. 5.1)

Cost, as the source states it

Barkoutsos, Nannicini, Robert, Tavernelli and Woerner charge $K$ samples per objective evaluation, taken in one circuit and one computational-basis measurement, since diagonal $H$ makes every bitstring a sample of every term (Sec. 2); only the $\lceil \alpha K \rceil$ smallest enter $\mathrm{CVaR}_\alpha$ (Sec. 4, Eq. 12). To match the expected value's accuracy they call for $K/\alpha$ samples, a factor of $[4,10]$ at their recommended $\alpha \in [0.1,0.25]$ (Sec. 5, restated end of Sec. 6.2), though the $O(1/(K\alpha^2))$ variance they cite from Hong, proved only for continuous distributions, would imply $K/\alpha^2$. On hardware they instead fix $K$ at 8,192, five runs at each of $\alpha = 10\%, 25\%, 100\%$ (Sec. 6.2); the simulated runs state no shot count. Nothing bounds the outer loop, and the convergence gain is measured, not proved: at $p = 2$, $\alpha = 1\%$, almost all of 340 simulated instances on 6 to 16 qubits with all-to-all entanglement reach 1% ground-state sampling probability within 50 normalized iterations (iterations per qubit), against 60% at $\alpha = 100\%$. Smaller $\alpha$ also caps the prize: the objective rewards no overlap beyond $\alpha$.

Implementations

• The 340-instance CVaR-VQE / CVaR-QAOA simulation sweep (Sec. 6.1)

  • Improving Variational Quantum Optimization using CVaR

  Section 6 states the purpose in its first two sentences: "The preceding analysis shows that CVaR optimization may improve certain properties of the classical optimization problem solved in VQE and QAOA. To verify if this is the case from an empirical point of view, we test the proposed on multiple random instances of six CO problems: maximum stable set, maximum 3-satisfiability, number partitioning, maximum cut, market split, and portfolio optimization." **The choice of yardstick is itself an argument.** The arms of the sweep minimise different objectives, so the paper refuses to compare them on objective value — "comparing algorithms with respect to the average objective function value (or CVaR with a different $\alpha$) would not be informative" — and scores every arm on the probability of sampling an optimal solution instead, "i.e., the overlap with ground state". The horizontal axis is a normalized iteration count: "To make the number of iterations comparable for problems of different sizes, we normalize it dividing by the number of qubits."

  "For every instance, we run CVaR-VQE and CVaR-QAOA for $\alpha \in \{1\%, 5\%, 10\%, 25\%, 50\%, 75\%, 100\%\}$ and $p = 0, 1, 2$ for VQE and $p = 1, 2, 3$ for QAOA. In total, this leads to 340 random problem instances and 14,280 test cases" (Sec. 6). The expectation-value baseline is not a separate experiment: $\alpha = 100\%$ recovers the ordinary sample mean, so it is one arm of the same sweep. "Following [17], we use the classical optimizer COBYLA to determine the parameters of the trial wave function." The VQE variational form is the one drawn in Fig. 1 for $n = 3$, $p = 2$: alternating layers of parametrized $Y$-rotations and controlled-$Z$ gates, which "leads to $n(1 + p)$ parametrized Y-rotations, and $\frac{n(n-1)}{2}p$ controlled Z-gates", of total circuit depth $O(np)$ "although the number of gates is quadratic in $n$"; Fig. 4's runs use all-to-all entanglement. QAOA's form is Eq. (9), with $2p$ parameters against VQE's $n(1+p)$. **Sec. 6.1 states no shot count.** It works from "the exact quantum state resulting from simulation", which "allows us to precisely characterize the performance metrics that we use", and Sec. 6.2 refers back to it as "the noiseless simulation results". What is absent is a stated number, not sampling itself: the closing paragraph of Sec. 6.2 says of the study as a whole that "our empirical evaluation uses the same, fixed number of samples across all $\alpha$", without saying what that number is for the simulated half.

  "For each problem except Max3Sat, we generate ten random instances on 6, 8, 10, 12, 14, and 16 qubits. Our formulation of Max3Sat requires the number of qubits to be a multiple of three, thus we use 6, 9, 12, and 15 qubits" (Sec. 6). The generation procedure is inherited rather than defined here: "A more detailed discussion of the instance generation and the mapping to a Hamiltonian can be found in [17] for all problems except portfolio optimization, which is discussed in Appendix B", and [17] is Nannicini's *Performance of hybrid quantum/classical variational heuristics for combinatorial optimization*. Portfolio optimization is the paper's own: Appendix B's penalised QUBO $\max_{x \in \{0,1\}^n} \sum_{i=1}^{n} \mu_i x_i - q\sum_{i,j=1}^{n}\sigma_{ij}x_i x_j - \lambda\left(B - \sum_{i=1}^{n} x_i\right)^2$, "where we subtract a penalty term weighted by $\lambda$ to enforce the budget constraint $\sum_{i=1}^{n} x_i = B$". No instance file is released and no instance of the sweep is printed: the only $\mu$ and $\sigma$ anywhere in the paper are the six-asset pair of Appendix B, which belongs to the hardware run, and the $q$, $B$ and $\lambda$ given there are stated for that instance only.

  "The numerical experiments discussed in this paper are implemented in the open-source library Qiskit [2], and executed on classical quantum simulators as well as IBM's quantum hardware" (Sec. 1). The Code Availability section releases one artefact — "A notebook providing the code to run CVaR-VQE is available open source at https://github.com/stefan-woerner/cvar_quantum_optimization/". That notebook builds the six-asset portfolio instance of Appendix B; it carries no instance generator for the other five problem classes and no driver for the sweep, pointing the reader at `qiskit.optimization.ising` for their translators.

  The headline comparison is between two arms of the same algorithm: "For CVaR-VQE, using $p = 2$ and $\alpha = 1\%$, within 50 normalized iterations we achieve at least 1% probability of sampling an optimal state for almost all instances. In contrast, with $\alpha = 100\%$ (i.e., the expected value), we reach the same probability of sampling an optimum only for 60% of the test problems" (Sec. 6.1, Fig. 4). The same section prints the cost of a small $\alpha$: "for $\alpha = 10\%$ we reach 10% probability to sample an optimal solution for most of the test problems in less than 50 normalized iterations, but with $\alpha = 1\%$ we reach 10% probability only in a small fraction of problems". Fig. 5 is the size scan: "for a small number of qubits there is a ceiling effect, i.e., all methods perform similarly because the problem is easy for all methods, but as soon as problem size increases, the benefits of CVaR optimization (with $\alpha \in [0.01, 0.25]$) are obvious in the plots." A second finding is about QAOA rather than about CVaR: "QAOA's performance appears significantly worse than that of VQE for equivalent depth (where we compare depth $p$ for VQE to depth $p+1$ for QAOA)", which Sec. 7 then turns into Prop. 7.1. **Hardware: none.** These figures come from classical simulation of the exact quantum state, implemented in Qiskit — "the numerical experiments discussed in this paper are implemented in the open-source library Qiskit" (Sec. 1), "quantum states resulting from classical simulation" (Figs. 4 and 5 captions). The paper names no simulator backend anywhere for them.

• CVaR-VQE on IBM Q Poughkeepsie, six-asset portfolio optimization (Sec. 6.2 and Appendix B)

  • Improving Variational Quantum Optimization using CVaR

  "To test CVaR optimization on quantum hardware, we consider an instance of the portfolio optimization problem with 6 assets mapped to 6 qubits, see Appendix B. We choose portfolio optimization because the problems of this class are some of the most difficult of our testbed" (Sec. 6.2). The question this run answers is narrower than the simulation sweep's and the paper says which one: whether the convergence advantage survives device noise. "In addition to the improved convergence behavior already demonstrated in Sec. 6.1 using classical simulation, the CVaR objective function also seems to be able to cope with the noise and errors introduced by the quantum hardware."

  "We test CVaR-VQE on the IBM Q Poughkeepsie 20-qubit quantum computer, with COBYLA as the classical optimizer" (Sec. 6.2). CVaR-QAOA is not run: "We use CVaR-VQE rather than CVaR-QAOA because for the same circuit depth it leads to better solutions, as discussed in Sec. 6.1." **The ansatz is changed to fit the chip, and that change is stated rather than hidden.** "In this section we apply nearest neighbor entanglement instead of all-to-all entanglement. We choose 6 qubits on the device that are connected in a ring (qubits 5, 6, 7, 10, 11, and 12), thus achieving a cyclic entanglement without additional swap operations"; the chip's connectivity and the selected qubits are drawn in Fig. 8. "We run CVaR-VQE with depth $p = 1$ and $\alpha = 10\%, 25\%, 100\%$, repeating each experiment five times. We gather 8,192 samples from each trial wavefunction". Appendix B repeats the same protocol at $p = 0$ (Fig. 9) and $p = 2$ (Fig. 10). "To reduce variance in the experiments, we fix the initial variational parameters to $\theta = 0$." Fig. 6's caption states how the five runs are averaged: "Since COBYLA converges after a different number of iterations in each run, we assume that the contribution of each run to the average value after termination of that run is its last reported value."

  One instance, printed in full. Appendix B fixes the QUBO's parameters — "We choose $n = 6$, $q = 0.5$, $B = 3$, and $\lambda = 12$" — and gives the instance itself: "The used return vector $\mu$ and positive semidefinite covariance matrix $\sigma$ were generated randomly", with $\mu = (0.7313,\ 0.9893,\ 0.2725,\ 0.8750,\ 0.7667,\ 0.3622)$ and a $6 \times 6$ $\sigma$ whose first row is $(0.7312,\ -0.6233,\ 0.4689,\ -0.5452,\ -0.0082,\ -0.3809)$. There is no market data behind these numbers and the paper does not claim any; the random draw is the provenance. "The corresponding Hamiltonian can be constructed as described e.g. in Sec. 2 and the references mentioned therein." The same $\mu$ and $\sigma$ are hard-coded in the released notebook under the comment `# instance from paper`.

  The paper's Code Availability section: "A notebook providing the code to run CVaR-VQE is available open source at https://github.com/stefan-woerner/cvar_quantum_optimization/". The repository holds three files — `README.md`, `requirements.txt` and `cvar_quantum_optimization.ipynb` — is described on GitHub as "Supporting material for https://arxiv.org/abs/1907.04769", carries **no licence file**, and its own notebook says it "provides an implementation to reproduce the results published in https://arxiv.org/abs/1907.04769". It is Python in a Jupyter notebook, pinned by `requirements.txt` to `qiskit==0.29.0`, `qiskit-terra==0.18.1`, `qiskit-aer==0.8.2`, `qiskit-optimization==0.2.2` and `qiskit-finance==0.2.0`. **It reproduces the instance, not the experiment.** The notebook builds the same six-asset problem via `PortfolioOptimization(mu, sigma, q, budget)` with `q = 0.5`, `budget = n // 2` and `penalty = 12`, and then departs from the run in three ways. The ansatz is `RealAmplitudes(n, reps=1)`, which in the pinned `qiskit-terra==0.18.1` is "alternating layers of $Y$ rotations and $CX$ entanglements" with `entanglement` defaulting to `full`, where Sec. 2's variational form uses controlled-$Z$ gates and Sec. 6.2 restricts them to the ring of qubits 5, 6, 7, 10, 11 and 12. The starting point is `initial_point = np.random.rand(m)`, one shared random draw for all three $\alpha$, where the run fixes $\theta = 0$. And the objective is computed from exact probabilities returned by `Aer.get_backend('statevector_simulator')` — with `qasm_simulator` offered as a commented alternative and no hardware backend in the file — where the run drew 8,192 samples per evaluation on the device. It uses `COBYLA(maxiter=100)` and sweeps `alphas = [1.0, 0.25, 0.10]`.

  "We see that the smaller the $\alpha$, the earlier the probability of sampling an optimal solution increases. For $\alpha = 100\%$, the probability stays almost flat and makes little progress" (Sec. 6.2, Fig. 6, $p = 1$, on the IBM Q Poughkeepsie 20-qubit device). The sharper statement is the one about all five repetitions: "For $\alpha = 10\%, 25\%$ the probability of finding the optimal solution attains the corresponding $\alpha$-level in all 5 experiments, whereas for $\alpha = 100\%$ the probability remains very small." That $\alpha$-level statement is for $p = 1$, and Appendix B is not uniformly favourable: at $p = 2$ (Fig. 10) the probability of sampling a ground state at $\alpha = 10\%$ "is not always exceeding $\alpha$ as before" though "it reaches that level on average", and at $\alpha = 25\%$ it "does not reach $\alpha$ anymore, but plateaus slightly below". The conclusion drawn is a transfer claim, not a new number: "on quantum hardware we observe the same beneficial effect on the speed of convergence that was observed in the noiseless simulation results." **The $p = 0$ run in Appendix B is the one that shows why the objective was changed at all**: "for $\alpha = 100\%$ the probability of sampling a ground state first increases to 5% on average, then it drops close to zero, even though the objective function improves. This is an example where improving the objective value does not necessarily imply getting a better overall solution (i.e., binary string), and highlights our motivation of using CVaR as the objective in contrast to the expected value."

• CVaR aggregation in Qiskit's SamplingVQE and QAOA

  • Improving Variational Quantum Optimization using CVaR

  The method has a library home that is not the paper's own code. Qiskit's sampling-based variational solvers expose the confidence level as a constructor argument and cite this paper for it: the docstring of `SamplingVQE` says that a float `aggregation` "specifies the $\alpha \in [0,1]$ parameter for a CVaR expectation value [1]", and its References block gives [1] as "Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., and Woerner, S., 'Improving Variational Quantum Optimization using CVaR' arXiv:1907.04769". This entry records the released library, not a study — it is what a reader who wants to run the method from code today actually calls, with the caveat the repository states about itself: the README opens "Qiskit Algorithms is no longer officially supported by IBM", adding "Like any other Apache 2 licensed code, you are free to use it or/and extend it, but please be aware that it is under your own risk."

  `SamplingVQE(sampler, ansatz, optimizer, aggregation=alpha)` replaces the expectation value in the classical loop with the CVaR aggregate; `QAOA` inherits it (`class QAOA(SamplingVQE)`, passing `aggregation` straight through to `super().__init__`), so CVaR-QAOA is the same code path with a problem-derived ansatz. The aggregation itself is `_get_cvar_aggregation` in `diagonal_estimator.py`: it rejects any `alpha` outside $[0,1]$, treats `alpha=None` as $1$, short-circuits to the plain weighted mean `sum(probability * value for probability, value in measurements)` when `alpha` is close to $1$, and otherwise sorts the measurements by value, accumulates `value * min(probability, alpha - accumulated_percent)` until the accumulated mass reaches `alpha`, and returns `cvar / alpha`. **Read against Eq. (12), that is the population $\mathrm{CVaR}_\alpha$ rather than the paper's sorted-batch estimator** — that comparison is a reading of the loop against the equation, not a claim either source makes. The function consumes `(probability, value)` pairs and clips the last one at the $\alpha$ boundary, where Eq. (12) averages the $\lceil \alpha K \rceil$ smallest of $K$ drawn samples; on equally weighted outcomes with $\alpha K$ an integer the two coincide, and where $\lceil \alpha K \rceil > \alpha K$ the paper takes one whole extra sample while this code takes a fraction of it. `aggregation` also accepts an arbitrary callable over `[(probability, objective_value)]`, of which CVaR is one case.

  `qiskit-algorithms` — Python, Apache License 2.0, at https://github.com/qiskit-community/qiskit-algorithms, described there as "A library of quantum algorithms for Qiskit." The three files that carry this method are `qiskit_algorithms/minimum_eigensolvers/sampling_vqe.py` (the `aggregation` argument and the citation), `qiskit_algorithms/minimum_eigensolvers/qaoa.py` (the QAOA subclass) and `qiskit_algorithms/minimum_eigensolvers/diagonal_estimator.py` (`_get_cvar_aggregation`). The repository's own `test_aggregation` in `test/minimum_eigensolvers/test_sampling_vqe.py` declares $\alpha = 0.4$ and loops over it, but passes `aggregation=best_measurement` in both subtests, so the float CVaR path is not exercised there. Read from the `main` branch; this entry does not claim a release version, and the sibling `qiskit-optimization` and `qiskit-finance` packages that the paper's own notebook pins are separate distributions.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

• Analytic-gradient parameter search

  Get the gradient of the objective exactly, rather than by finite differences, by running the same circuit again at shifted parameter values. The direction is then not an estimate of a slope taken from two noisy numbers; it is the slope, estimated to whatever precision the shots allow.

• Minimise the energy variance

  Minimise how much the energy fluctuates rather than the energy itself. Any eigenstate has zero variance, so the objective's own value tells you whether you have arrived — which the energy never does, since a low number is only low relative to a minimum nobody knows.

• Follow the steepest descent in the state's own geometry

  Take the step that moves the state fastest, not the one that moves the parameters fastest. The two differ because equal changes in parameters do not make equal changes in the state, and the metric measuring that difference has to be estimated before every step.

• Grow the circuit a layer at a time while training it

  Do not settle the circuit before optimising it. Start shallow, train what is there, then hold most of it fixed and add the next layer on top — so every step of the search runs on a shallow circuit with few free parameters, which is where a gradient is still large enough to follow.

• Simultaneous-perturbation optimization

  Perturb every parameter at once, in one random direction, and take the difference of two objective evaluations as the gradient estimate. The estimate is bad in any single round and unbiased across rounds, so the cost of a step stops growing with the number of parameters.

In the Atlas

• CVaR-VQE objective

  Conditional value-at-risk averages only a selected low-energy tail of samples for combinatorial objectives.

Sources

• Improving Variational Quantum Optimization using CVaR↗Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, Stefan Woerner · 2019theory yes · simulation yes · hardware yes