PaperlayerView exact revision on arXiv

Source-linked AI summary

Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study

Jack S. Baker, Santosh Kumar Radha

arXiv:2202.06782v1quant-phq-fin.CPq-fin.PM

TL;DR

Discrete portfolio optimization is an important QPU-targeted problem, but QAOA-based approaches lacked systematic application-specific benchmarking on real gate-model hardware. This paper uses Wasserstein-based solution quality η to benchmark QAOA, constraint variants, optimizers, simulators, and real QPUs. It finds budget-dependent ideal performance, generally stronger derivative-free optimization, increasing quality with depth in selected hardware and ansatz settings, and variability exceeding shot noise.

  • Problem

    Systematic benchmarking of QAOA-based MVPO, especially on real gate-model QPUs, had not been performed.

    Source: §I · p. 2

  • Method

    The study uses Wasserstein-based solution quality η to evaluate QAOA and Quantum Alternating Operator Ansatz variants across simulators, real QPUs, constraints, depths, and classical optimizers.

    Source: §I · p. 2, §VI · p. 18

  • Results

    Derivative-free optimizers generally outperform derivative-requiring optimizers, while selected real-QPU runs show increasing solution quality with depth and variability exceeding finite-shot noise.

    Source: §VI · pp. 18–19

  • Takeaways & Limitations

    η provides an application-specific benchmark for comparing solution quality and QPU variability across QAOA-based combinatorial optimization settings.

    Source: §VI · pp. 18–19

Abstract

from arXiv · show

Optimizing of a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs). We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, $\eta$, which we present in a manner to expose the QAOA as a transporter of probability. Using $\eta$ as an application specific benchmark of performance, we measure it on selection of QPUs as a function of QAOA circuit depth $p$. At $n = 2$ (2 qubits) we find peak solution quality at $p=5$ for most systems and for $n = 3$ this peak is at $p=4$ on a trapped ion QPU. Increasing solution quality with $p$ is also observed using variants of the more general Quantum Alternating Operator Ans\"{a}tz at $p=2$ for $n = 2$ and $3$ which has not been previously reported. In identical measurements, $\eta$ is observed to be variable at a level exceeding the noise produced from the finite number of shots. This suggests that variability itself should be regarded as a QPU performance benchmark for given applications. While studying the ideal execution of QAOA, we find that $p=1$ solution quality degrades when the portfolio budget $B$ approaches $n/2$ and increases when $B \approx 1$ or $n-1$. This trend directly corresponds to the binomial coefficient $nCB$ and is connected with the recently reported phenomenon of reachability deficits. Derivative-requiring and derivative-free classical optimizers are benchmarked on the basis of the achieved $\eta$ beyond $p=1$ to find that derivative-free optimizers are generally more effective for the given computational resources, problem sizes and circuit depths.

I. INTRODUCTION

MVPO is an industry-relevant discrete portfolio-selection problem that can be formulated as an NP-hard QUBO, while systematic benchmarking of QAOA-based MVPO on real QPUs had not been performed. This work benchmarks solution quality, hardware variability, constraint strategies, circuit depth, and classical optimizers using application-specific Wasserstein metrics.

I. INTRODUCTION

  • Discrete MVPO selects assets under realistic trading restrictions and becomes an NP-hard QUBO problem.The formulation seeks maximal expected returns with minimal volatility under a predefined risk appetite and budget.Source: §I · p. 1
  • Systematic benchmarking of QAOA-based MVPO on real gate-model QPUs had not previously been performed.Earlier QAOA-based MVPO studies focused on circuit simulators, whereas this work includes real hardware.Source: §I · p. 2
  • The study evaluates QAOA as a hybrid quantum-classical process, including circuit noise, depth, constraint enforcement, parameter initialization, and black-box classical optimization.For the studied resources and problem sizes, derivative-free optimizers are reported as generally most effective.Source: §I · p. 2
  • Real QPUs and ideal simulators span superconducting and trapped-ion hardware, with increasing solution quality observed at larger problem sizes and depths than previously reported.The study also reports the first deployment of the more general Quantum Alternating Operator Ansatz to real QPUs and identifies variability beyond shot noise as an application-specific benchmark.Source: §I · p. 2
  • The benchmark uses Wasserstein distance to assess solution quality independently of numerical instance details and constraint-enforcement schemes.The metric is presented as exposing QAOA as a transporter of probability and as an alternative to approximation ratios that depend on these details.Source: §I · p. 2
  • Under ideal QAOA execution, solution quality decreases near B ≈ n/2 and increases when B approaches 1 or n−1.The budget dependence follows the binomial coefficient nCB and is connected with reachability deficits.Source: §I · p. 2

B. Discrete MVPO as a QUBO/Ising problem

The discrete buy/hold portfolio problem is encoded as a QUBO and then as a diagonal Ising Hamiltonian for QAOA. Canonical QAOA alternates cost and mixing unitaries over a uniform initial state while a classical optimizer tunes the variational parameters.

B. Discrete MVPO as a QUBO/Ising problem

  • Buy/hold MVPO uses binary portfolio weights and can be represented as a QUBO on the complete graph K_n.Selecting an asset contributes a linear term, selecting an asset pair contributes a quadratic term, and exactly B vertices must be chosen.Source: B. Discrete MVPO as a QUBO/Ising problem · p. 3, Figure 2 · p. 4
  • The binary QUBO becomes a quadratic Ising model through x_i = (s_i + 1)/2, with a constant term that does not affect optimization.The resulting cost can be encoded in a Hamiltonian diagonal in the computational basis.Source: B. Discrete MVPO as a QUBO/Ising problem · p. 3

C. The Canonical QAOA

  • Canonical QAOA initializes the qubits in a uniform superposition and applies p layers of parameterized cost and mixing unitaries.The variational parameters γ and β are vectors of length p.Source: C. The Canonical QAOA · p. 4
  • A classical minimization routine varies γ and β to minimize the expected cost ⟨H_C⟩ and obtain the best parameter vectors.The global minimum yields the minimum expected cost M_p and corresponding optimal parameters.Source: C. The Canonical QAOA · p. 4
  • Increasing circuit depth cannot worsen the ideal variational minimum because M_{p−1} is a constrained version of M_p with two added parameters fixed to zero.Thus M_{p−1} ≥ M_p, and the minimum expected cost approaches the optimal cost as p increases.Source: C. The Canonical QAOA · p. 4

D. Extensions to the QAOA and enforcing constraints

The Quantum Alternating Operator Ansatz broadens QAOA unitaries to enforce portfolio budget constraints either softly through penalties or hard through constraint-preserving initialization and mixers. The study compares these approaches while accounting for circuit-depth and hardware-noise trade-offs.

D. Extensions to the QAOA and enforcing constraints

  • Soft constraints add a penalty K scaled by α, leaving constraint-violating states in the search space but making them disfavored.The study tests α = α_min and α = 100.Source: D. Extensions to the QAOA and… · pp. 4–5
  • Hard constraints initialize only budget-satisfying states and use mixers that preserve the Hamming-weight subspace.Random Hamming-weight-B states and Dicke states are used for initialization.Source: D. Extensions to the QAOA and… · p. 5
  • The ring mixer preserves Hamming weight by exchanging neighboring qubits, while the complete-graph mixer couples all qubit pairs within the viable subspace.Both mixers are designed to keep the search restricted to states satisfying the equality constraint.Source: D. Extensions to the QAOA and… · p. 5
  • The complete-graph mixer had previously outperformed the ring mixer under ideal execution for graph coloring and ternary portfolio optimization [32].The present hardware comparison remains motivated by the ring mixer’s lower gate requirements.Source: D. Extensions to the QAOA and… · p. 5
  • General ring and complete-graph mixer implementations may require truncated Trotter expansions, creating a trade-off between Trotter error and hardware noise.The study uses a low-order expansion with fixed step size ε = 0.25 to keep circuit depth low.Source: D. Extensions to the QAOA and… · p. 5
  • Hard-constraint implementations use Dicke-state initialization with a complete-graph mixer or random Hamming states with a ring mixer.The Dicke-state approach is expected to perform best ideally, while the ring approach uses fewer total gates and may suit current NISQ hardware.Source: D. Extensions to the QAOA and… · p. 5

III. MEASURING SOLUTION QUALITY

The paper introduces a Wasserstein-based, application-specific framework for evaluating solution distributions from constrained and unconstrained combinatorial optimization, especially QAOA. The normalized complementary Wasserstein distance η ranks solutions independently of the numerical cost scale, while its interpretation and computational use have clear limits.

Wasserstein solution-quality framework

  • The Wasserstein framework evaluates the quality of probability distributions produced by combinatorial optimization algorithms, including constrained and unconstrained problems.It interprets solution quality as the work required to transport probability from non-optimal ranked solutions to the optimum.Source: §III · pp. 5–6

Motivation for η

  • The metric avoids unfair comparisons that approximation ratios can create when penalty factors or constraint-enforcement schemes change the objective function.The same output distribution can receive different approximation ratios under different penalty factors, whereas the proposed metric is agnostic to those numerical details.Source: §III · p. 6

Solution ranking

  • Ranking viable and non-viable solutions before constructing P(˜C) makes bin distances uniform and independent of the numerical details of C.The construction separates constraint satisfaction from objective value, then concatenates the resulting ordered sequences for ranking.Source: §III · p. 6

NCWD limits

  • The normalized complementary Wasserstein distance η maps perfect, worst, and random distributions to η = 1, η = 0, and η = 0.5, respectively.η is obtained by normalizing the Wasserstein distance and taking its complement; W may instead be more informative for studying scaling with problem size.Source: §III · pp. 6–7

Relationship to existing metrics

  • η and the approximation ratio r can have the same number of minima but differ in their parameter locations, so optimizing r does not guarantee optimizing η.The paper also notes small differences between their optima and distinguishes the two measures as separate landscapes.Source: §III · p. 7, Figure 3 · p. 7

Computational limitation

  • Using η requires exhaustive enumeration and storage of all 2^n solutions, limiting the benchmark to problems small enough for classical computation.The paper concludes that η, r, and r_b will require replacement once QPUs address problem sizes beyond classical computation.Source: §III · p. 7

A. Random problem instances at p = 1

At p = 1, solution quality varies systematically with the portfolio budget: it is highest near extremal B and lowest near B/n = 0.5, a trend reproduced across constraint variants and related to nCB.

Experimental setup

  • The experiments use 200 random instances per setting and exact statevector simulation after a 50 × 25 grid search over γ1 and β1.The setup estimates ideal p = 1 performance while limiting optimizer-dependent variation.Source: A. Random problem instances at p = 1 · pp. 7–8

Random instances

Constraint robustness

Combinatorial interpretation

  • Fitting η(B) with −aΓ_nCB(B)+c reproduces the observed trend, linking minimum solution quality near B/n = 0.5 to the peak number of viable solutions.The interpretation resembles reachability deficits, but the soft-constraint mechanism differs because all clauses remain active while the penalized eigenvalues change.Source: A. Random problem instances at p = 1 · pp. 8–9

B. Real market data beyond p = 1

Beyond p = 1, the study evaluates representative market-data portfolios across n = 2–10 and p = 1–5, while noting that representativity is assessed only through η optima.

Market-data setup

  • Representative market-data instances are selected for n = 2–10, with B chosen near the budgets expected to yield the lowest η and λ fixed at 0.5.The portfolios use April 2021 returns and covariance data from up to ten named technology stocks.Source: B. Real market data beyond p = 1 · p. 9

Representativity check

  • The selected instances fall within the random-instance spread for p = 1 in every tested case, supporting representativity by optimum magnitude.This check does not establish representativity for other cost-landscape properties such as roughness.Source: B. Real market data beyond p = 1 · pp. 9–10

1. Black box classical optimization

The optimizer benchmark compares derivative-free, derivative-requiring, and random methods under fixed circuit-evaluation budgets across simulator and constraint settings.

Benchmark protocol

  • The study uses exact statevector and 2048-shot simulation across four constraint-enforcement schemes.The schemes include two soft-constraint settings and hard constraints based on Dicke initialization with different mixers.Source: §1 · p. 10, Figure 6 · p. 11
  • Each optimizer minimizes ⟨HC⟩ using 500 circuit evaluations from random angles, with repeated runs differing between soft and hard constraints.Soft constraints use 50 repeats and hard constraints use 10; finite differences approximate required derivatives.Source: §1 · p. 10

Resource assumptions

  • The 500-evaluation budget is chosen as a compromise between finding good local minima and maintaining plausibility for present QPU access constraints.The authors describe it as near the upper limit of a reasonable cloud-queued optimization wait under current NISQ conditions.Source: §1 · pp. 10–11

Optimizer selection

  • The benchmark compares Random Search with Nelder-Mead, COBYLA, Powell, Gradient Descent, Adam, and SQP.The derivative-free methods are Nelder-Mead, COBYLA, and Powell; SQP requires first and second derivatives.Source: §1 · p. 10, Figure 6 · p. 11

2. Optimizer performance analysis

Derivative-free optimizers generally provide better η outcomes than derivative-requiring methods within the tested budgets, but performance depends strongly on noise, constraints, dimensionality, and initialization.

Overall optimizer comparison

  • Derivative-free optimizers more often outperform derivative-requiring optimizers in best η for both exact and shot-based simulations.SQP is a notable exception with statevector simulation, while shot noise widens the performance gap and can stall SQP for hard constraints.Source: §2 · pp. 11–12, Figure 7 · p. 12

Constraint effects

  • Hard-constraint ansätze are generally easier to optimize, while soft constraints with α = αmin more often beat Random Search than α = 100.The authors associate this pattern with rougher, more locally multimodal landscapes under large penalties.Source: §2 · pp. 12–13

Mean performance

  • Random Search can outperform other optimizers in mean η at low n and p, but becomes less effective as n and p increase.For n ≥5 and p ≥2, its η(p) decreases, consistent with the growing 2p-dimensional parameter space.Source: §2 · pp. 12–13

Variability

  • Optimizer reliability is often poor: derivative-free methods can achieve good η yet show large standard deviations across randomized cold starts.Gradient Descent is reliably poor at high n and p, whereas Adam is both poor on average and highly variable.Source: §2 · p. 13

Probability transport

  • Decreasing W(p) indicates probability transport toward better solutions, and the results show strong reductions with small increases in p despite W ∝ 2^n at fixed p.The study uses crossings below worst-case p = 1 W to assess whether additional depth overcomes scaling with problem size.Source: Figure 8 · p. 13

3. Comparing constraint enforcement schemes and problem size scaling

Constraint-enforcement schemes produce different solution-quality trends, with hard constraints often appearing strongest in best-run comparisons but soft constraints showing depth-dependent improvements and scaling limits.

Comparing constraint enforcement schemes

  • Hard constraints can appear to produce the best solutions overall, but this is partly because the random initial state often equals the optimal state for small n.This effect is not scalable and is already visible by n = 5.Source: §3 · p. 13
  • W ≈0 occurs for all p with hard constraints, whereas soft constraints reach comparable quality only at higher depths depending on α.For α = αmin, comparable quality appears at p = 5; for α = 100, at p = 3.Source: §3 · p. 14
  • For n ⪅5, α = 100 generally improves more with increasing p than α = αmin, but this trend reverses near n = 9 and 10.At larger n, α = 100 can show increasing W for p > 3.Source: §3 · p. 14

Problem-size scaling

  • For n > 3 with |DB_n⟩&H_K, increasing p from 1 to 2 gives the strongest W reduction, followed by gradual or marginal improvements.This identifies an early-depth regime of diminishing returns.Source: §3 · p. 14
  • At fixed p, W scales exponentially with n in soft constraints and hard |DB_n⟩&H_K cases, yet increasing p can overcome this wall within the simulated range.For example, n = 5 falls below the worst-case W for n = 4 when p ≥ 3.Source: §3 · p. 14

V. SOLUTION QUALITY USING REAL GATE-MODEL QPUS

The real-QPU benchmarks use application-specific η measurements under deliberately standardized, minimally optimized conditions across several hardware providers and constraint settings.

Benchmark design

  • The benchmarks intentionally omit micro-optimization and error mitigation, using provider defaults to establish a comparable baseline across QPUs.This includes no user-controlled transpilation optimization or pulse-level gate control.Source: §V · p. 14
  • The study benchmarks cloud-accessible IBM, Rigetti, and IonQ QPUs across superconducting and trapped-ion hardware with different connectivity topologies.The evaluated range is 2 ≤ n ≤ 5 and 1 ≤ p ≤ 5.Source: §V · p. 14
  • Each QPU is warm-started from ideal-simulator angles and receives only 10 COBYLA circuit evaluations using 2048 shots per evaluation.The limited re-optimization corrects small mismatches between ideal and experimental cost landscapes.Source: §V · p. 14

Benchmark scope

  • For n = 6 and p = 1, α = αmin soft constraints produce distributions indistinguishable from random, with η ≈0.5 on all QPUs.The QPU study repeats soft-constraint runs five times, except for IonQ’s 11-qubit machine, which is repeated twice.Source: §V · p. 14

A. Solution quality and fidelity versus depth

Real-QPU solution quality depends strongly on circuit depth, constraint implementation, hardware, and application-specific behavior rather than general hardware benchmarks alone.

Solution quality and fidelity

  • The benchmarks compare raw η(p) with η/ηideal fidelity, where fidelity measures hardware solution quality relative to ideal-simulator quality as a function of API-gate count.API gates are distinct from native gates after vendor transpilation.Source: A. Solution quality and fidelity… · pp. 15–16

Solution quality versus depth

  • At n = 2, α = αmin soft constraints can improve monotonically through p = 5, while at n = 3 peaks occur at p = 2 or 4 and no QPU improves with p at n = 4 or 5.Nevertheless, n = 5 remains better than random guessing through p = 5.Source: A. Solution quality and fidelity… · p. 15

Constraint enforcement

  • Hard constraints generally underperform soft constraints because their implementations require nearly an order of magnitude more API gates, although small-n cases can reach η ≈1.Beyond n = 4, p = 1, hard-constraint results tend toward η ≈0.5.Source: A. Solution quality and fidelity… · p. 16

Benchmark limitations

  • For Rigetti’s Aspen-10 and IonQ’s 11-Q machines, high-depth hard-constraint benchmarks were incomplete because cloud-side circuit transpilation timed out: Aspen-10 beyond n = 4, p = 1; 11-Q beyond n = 2, p = 5 and n = 3, p = 4.Source: A. Solution quality and fidelity… · p. 17

Solution quality versus depth

  • The first real-hardware hard-constraint implementations show increasing solution quality with p in some cases, including p = 1 to 2, although hardware fidelity to ideal results remains low.For some observed increases, ideal η is exactly 1 at every depth, so the hardware trend is not inherited from ideal execution.Source: A. Solution quality and fidelity… · p. 17

Hardware-specific behavior

  • Aspen-10 performs successfully for hard constraints at n = 3, plausibly because its native XY gates match the mixing operators, while IonQ’s 11-Q machine benefits from complete connectivity but exhibits non-monotonic peaks.These hardware-specific observations do not yield a universal predictor of performance.Source: A. Solution quality and fidelity… · p. 17

Application-specific benchmarking

  • Among IBM QPUs, ibmq lima achieves the best average soft-constraint η despite having the lowest quantum volume, showing that QV and topology alone do not predict QAOA performance.Structured application circuits can expose noise characteristics that generalized benchmarks miss.Source: A. Solution quality and fidelity… · p. 17

B. Variability in solution quality

Repeated identical QPU runs show variability substantially larger than finite-shot noise, motivating variability as an additional application-specific benchmark alongside solution quality.

B. Variability in solution quality

  • Repeated QPU measurements vary far more than shot-based stochastic noise, with IonQ’s 11-Q showing deviations up to 19% between two repeats.The main repeated-run analysis uses five repeats per QPU, excluding 11-Q from equivalent statistical comparisons because it has only two.Source: B. Variability in solution quality · p. 17, Figure 11 · p. 18
  • The authors propose judging QPUs not only by η but also by variability across identical application runs.Possible contributors include changing qubit assignments, calibration drift, system degradation, and time-varying coherence times.Source: B. Variability in solution quality · pp. 17–18

VI. CONCLUSIONS

  • The Wasserstein-based η metric compares solution quality independently of numerical problem details and constraint-enforcement schemes for algorithms producing solution distributions.This enables application-specific benchmarking across QAOA implementations and QPUs.Source: §VI · p. 18
  • At p = 1, solution quality is highest when B/n approaches 1 or n−1 and lowest near B/n = 0.5, tracking the binomial coefficient nCB.The authors connect this pattern to the number of viable solutions and reachability deficits.Source: §VI · p. 18
  • For 2 ≤ n ≤ 10 and 1 ≤ p ≤ 5, derivative-free optimizers generally outperform derivative-requiring optimizers at fixed circuit-evaluation budgets.Shot noise often makes optimizer performance comparable to random search, while soft constraints exhibit many local minima.Source: §VI · p. 18
  • On real QPUs, the best cases reach peak quality at p = 5 for n = 2 and p = 4 for n = 3, while performance varies more than finite-shot noise.A lower-QV IBM device can outperform higher-QV devices, reinforcing the need for application-specific and variability benchmarks.Source: §VI · pp. 18–19

Supplemental Material

The supplemental material documents API-gate and QPU data, supports limited warm-started re-optimization, and adds optimizer-performance and reliability comparisons.

1 Number of API gates and QPU data summary

  • Supplementary tables tabulate average and optimal-angle API-gate counts and summarize properties of the QPUs studied.The tables compare API-gate usage with ideal ansatz requirements and provide a QPU data summary.Source: §1 · p. 22

2 Justifying the limited re-optimization on QPUs

  • Ten warm-started circuit evaluations generally match the results of 500 evaluations, while 500 evaluations perform worse for n = 3 on ibmq lima.The supplement attributes this to warm-start angles already lying near the hardware basin of attraction and to machine variability exceeding re-optimization benefits.Source: §2 · p. 22

3 Additional black-box optimization data

  • Additional figures compare mean and standard-deviation η against random search for exact statevector and shot-based simulators.For reliability, the supplemental figures invert the color scale, so larger standard deviation than random search indicates worse performance.Source: §3 · p. 23

Related papers

Loading 2202.06782v1…