PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking the performance of portfolio optimization with QAOA

Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia, Thomas Wellens

arXiv:2207.10555v1quant-ph

TL;DR

The paper addresses practical gaps in applying QAOA to cardinality-constrained portfolio optimization. It studies implementation choices and performance across mixer variants, instances, and noise conditions, finding that the best mixer results depend on the setting.

  • Problem

    Practical issues in applying QAOA to portfolio optimization, including implementation choices and error effects, have not all been addressed in prior literature.

    Source: §1 · pp. 3–4

  • Method

    The authors formulate portfolio selection as constrained quadratic binary optimization and benchmark QAOA variants, parameter-optimization strategies, instance characteristics, and noise effects.

    Source: §1 · p. 3, §3.2 · p. 10, §3.2.3 · p. 12

  • Results

    For B = 5 of n = 10 assets at depth p = 7, the full XY mixer and QAMPA each find the optimal portfolio with probability P ≃ 0.6; instance statistics relate to performance, and noise affects mixers differently.

    Source: §1 · p. 4, §5 · p. 24

  • Takeaways & Limitations

    Mixer selection should account for the expected noise levels of the target platform, and benchmark instances should be chosen with attention to their statistics.

    Source: §1 · p. 4, §5 · p. 24

    The study is limited to small asset counts where brute force can determine required quantities exactly; larger instances require efficient classical approximations.

    Source: §2.3 · p. 7

Abstract

from arXiv · show

We present a detailed study of portfolio optimization using different versions of the quantum approximate optimization algorithm (QAOA). For a given list of assets, the portfolio optimization problem is formulated as quadratic binary optimization constrained on the number of assets contained in the portfolio. QAOA has been suggested as a possible candidate for solving this problem (and similar combinatorial optimization problems) more efficiently than classical computers in the case of a sufficiently large number of assets. However, the practical implementation of this algorithm requires a careful consideration of several technical issues, not all of which are discussed in the present literature. The present article intends to fill this gap and thereby provide the reader with a useful guide for applying QAOA to the portfolio optimization problem (and similar problems). In particular, we will discuss several possible choices of the variational form and of different classical algorithms for finding the corresponding optimized parameters. Viewing at the application of QAOA on error-prone NISQ hardware, we also analyze the influence of statistical sampling errors (due to a finite number of shots) and gate and readout errors (due to imperfect quantum hardware). Finally, we define a criterion for distinguishing between "easy" and "hard" instances of the portfolio optimization problem

1 Introduction

The paper examines practical choices for applying QAOA to portfolio optimization, including parameter optimization, constraint handling, and hardware noise. It compares algorithm variants and studies how instance characteristics and noise relate to performance.

1 Introduction

  • QAOA is often proposed as a candidate for quantum advantage, but such an advantage has not been rigorously proven, and parameter optimization has exponential cost.The paper builds on evidence that parameter initialization can affect performance and optimization time.Source: §1 · p. 2
  • The paper provides implementation guidance, proposes an easy-versus-hard instance criterion, and analyzes how errors modify QAOA performance.The guide is intended for portfolio optimization and similar problems.Source: §1 · p. 3
  • The study covers soft-constraint and XY-mixer approaches, cost-function scaling, and four heuristics for initializing QAOA parameters as depth increases.It also modifies the approximation-ratio definition to be independent of how the constraint is implemented and discusses selecting the penalty factor.Source: §1 · p. 3
  • Two of five XY mixers converge fastest toward the optimum as depth p increases in ideal simulations; similar results hold with finite-shot sampling noise.The comparison uses real-market portfolio instances based on DAX data.Source: §1 · p. 3
  • Noise of varying strengths affects different mixers differently, so the expected noise levels of the target quantum platform should inform the QAOA version selected.The analysis considers both error-affected optimization landscapes and final optimization outcomes.Source: §1 · p. 4

2 Definition of the portfolio optimization problem

The portfolio problem is formulated with binary asset choices and a fixed number of assets, using historical market data to construct its return and covariance inputs. The section defines performance measures and describes how to select a penalty for soft constraint handling, including the scope of the classical search used.

2 Definition of the portfolio optimization problem

  • Binary weights encode whether each stock is selected, while budget B fixes the number of assets and distinguishes feasible from unfeasible portfolios.The objective balances expected return and risk according to the investor’s risk-preference factor q.Source: §2 · p. 4

2.1 Covariances and returns

  • Historical daily prices are converted to daily percentage changes and used to calculate annualized returns and covariance matrices for randomly selected DAX assets.The data cover 2016–2020; the study uses n = 5 with B = 2 or n = 10 with B = 5, and sets q = 1/3.Source: §2.1 · p. 5

2.2 Performance measures

  • The modified approximation ratio assigns 1 to the optimal portfolio and 0 to the worst feasible or an unfeasible portfolio, independently of constraint implementation.The probability of obtaining the optimum is an alternative measure, but it does not account for near-optimal portfolios.Source: §2.2 · p. 6

2.3 Penalty factor

  • For soft constraints, penalty A is added to the objective and should separate infeasible solutions from the feasible optimum without being unnecessarily large.The procedure begins at A = 0 and increases A until the minimum infeasible objective is not too close to the feasible minimum.Source: §2.3 · pp. 6–7
  • The study uses small asset counts, where brute force can determine the required extrema exactly; larger instances require efficient classical methods to estimate them.If the chosen penalty is too small and QAOA returns a constraint-violating optimum, the algorithm can be rerun with a larger penalty.Source: §2.3 · p. 7

3 QAOA algorithm

The QAOA objective is converted into a quantum operator and evaluated by a parameterized circuit. Measurements supply an expectation value that a classical routine uses to update the circuit parameters.

3 QAOA algorithm

  • The objective function becomes an operator built from single- and two-qubit terms, with a positive scale factor λ.Identity and Pauli-Z operators act on individual qubits.Source: §3 · p. 7
  • At depth p, the circuit alternates phase-separation and mixer operations, parameterized by γ and β, from an initial state.The initial state and mixer operator depend on the mixer choice.Source: §3 · pp. 7–8
  • Measurements estimate the objective expectation, which a classical optimizer uses to choose new γ and β values for minimization.The circuit is motivated by adiabatic quantum computing, though finite-depth optimal angles may yield a non-adiabatic path.Source: §3 · p. 8

3.1 Mixer

The standard mixer uses single-qubit rotations, while XY mixers preserve the asset-count constraint by exchanging excitations between qubits. The paper also describes several XY layouts and a QAMPA variant that reduces CNOT count.

3.1.1 Standard QAOA

  • The standard QAOA mixer applies single-qubit rotations to a uniform superposition initial state.That state is the smallest-eigenvalue eigenstate of the standard mixing operator.Source: §3.1.1 · p. 8

3.1.2 XY-mixers

  • XY mixers exchange |01⟩ and |10⟩, preserving the total number of excitations and thus the portfolio budget constraint.The initial state is a uniform superposition of states satisfying the budget.Source: §3.1.2 · p. 8
  • XY variants apply the exchange operation to different qubit-pair sets, including ring, parity-ring, and full layouts.The full layout schedules commuting operations in subsets to minimize circuit depth.Source: §3.1.2 · p. 9
  • QAMPA contracts mixer and phase-separation gates pairwise and reduces CNOT count by a factor of 3/4 versus the full XY mixer.Because CNOT gates are identified as a major error source in current NISQ devices, the authors expect greater error resilience.Source: §3.1.2 · pp. 9–10

3.2 Optimization of the QAOA parameters

The parameter-optimization procedure addresses parameter scaling, initialization across depths, and optimizer choice. It uses multiple starts to reduce the risk of a local minimum and adapts optimizers to sampling noise.

3.2.1 Global scaling factor

  • Scaling the objective can improve classical optimization by keeping γ and β parameters at similar magnitudes; the authors set λ = ΔM/ΔF.For XY mixers, ΔF is the effective width over feasible states; for the standard mixer, the width also accounts for constraint-violating states.Source: §3.2.1 · pp. 10–11, §3.2 · p. 10

3.2.2 Initial values of parameters for p = 1

  • For p = 1, the authors search 100 logarithmically spaced parameter pairs and choose the start giving the lowest linear-ansatz objective at maximum depth.Several local minima appear at p = 1, but only one pronounced minimum remains at p = 7.Source: §3.2.2 · pp. 11–12, Figure 1 · p. 12

3.2.3 Initial values of parameters for larger p

  • For each larger depth, four optimization starts are tested, with the lowest-expectation run selected before moving to the next depth.The additional starts address the possibility of becoming trapped in a local minimum; one start extrapolates the prior-depth parameters.Source: §3.2.3 · pp. 12–13
  • The procedure rescales the objective and γ angles between depths so γ and β remain at similar orders of magnitude.The selected run's objective is used before proceeding to depth p + 1.Source: §3.2.3 · p. 13

3.2.4 Classical optimizers

  • SLSQP performs well with the exact statevector simulator, while gradient-based GD and SGD perform less well than SLSQP for XY mixers.GD and SGD show similar performance to SLSQP for the standard mixer.Source: §3.2.4 · p. 13
  • With finite-shot sampling noise, gradient-free Nelder-Mead is chosen because noise prevents precise gradient evaluation.The simulations use 1000 shots; the initial simplex size is 0.5 and the iteration limit is ten times the parameter count.Source: §3.2.4 · pp. 13–14

4 Results

Across mixer comparisons, instance-hardness analyses, and depolarizing-noise tests, QAOA performance varies with the mixer, asset-instance statistics, and noise strength. The best mixer in these simulations depends on the setting and the noise level.

4.1 Different Mixers

  • Full XY and QAMPA converge fastest and reach r > 99% without measurement noise for n = 5; for n = 10, they reach r ≃ 0.98 and P ≃ 0.6.At p = 1, XY-mixers already outperform the standard mixer; the qasm simulation with 1000 shots shows slower convergence for XY-mixers at larger p.Source: §4.1 · pp. 14–16, Figure 2 · p. 15

4.2 Easy and Hard Instances

  • Performance correlates with the variances of returns and correlations and with the mean and variance of the energy landscape; similar distributions were found using MDAX 50 historical data.The authors suggest higher asset-statistic variances may make the classical optimization landscape more distinct, while noting that covariance-matrix eigenvalue spectra did not distinguish good- and bad-performing instances.Source: §4.2 · p. 18

4.3.1 Employed Noise Model

  • The noise tests apply a depolarizing channel after every single-qubit or two-qubit gate in the QAOA ansatz circuit.The evaluated instance has n = 5 assets, budget B = 2, and risk-return factor q = 1/3.Source: §4.3 · p. 18, §4.3.1 · p. 19

4.3.2 Optimization Landscape of QAOA under Noise

  • In the error-free landscape, ring XY has the lowest expectation value (−2.90), but the ordering changes with normalized noise: full XY leads at ˜η = 1, standard leads at ˜η = 2 and 4, and all landscapes are noise-dominated by ˜η ≥ 10.At ˜η ≥ 1, landscapes flatten and become less regular; this impairs optimizer convergence, with XY-mixers deteriorating more strongly than the standard mixer at the same normalized noise.Source: §4.3.2 · p. 20
  • The standard mixer has a less complex optimization landscape with less pronounced deterioration as noise increases, which may allow faster convergence at higher noise levels.The paper describes this faster convergence as a possibility, not a guaranteed outcome.Source: §4.3.2 · pp. 20–21

4.3.3 Evaluation of QAOA at specific noise strengths

  • At p = 1, XY-mixers outperform the standard mixer across considered noise strengths, but at larger p the standard mixer overtakes them above η ≈ 0.003, 0.002, and 0.001 for p = 3, 5, and 7.The crossover threshold decreases as p increases; the authors attribute this in part to the larger XY circuits and their additional noisy gates.Source: §4.3.3 · pp. 21–22
  • For ground-state probability, parity ring XY performs best at p = 1; at p = 3, 5, and 7, the standard mixer overtakes XY-mixers at η = 0.008, 0.005, and 0.003.Among XY-mixers, parity ring performs better under noise; the paper also links XY-mixers' noise sensitivity to their reliance on Dicke states and more complex state preparation.Source: §4.3.3 · pp. 22–23

5 Conclusion

The conclusion finds that XY mixers perform best in sufficiently low-noise settings, but their greater noise sensitivity can make the standard mixer preferable on noisier hardware. It also links instance difficulty to the distributions of returns and correlations, emphasizing careful instance selection in QAOA benchmarks.

5 Conclusion

  • The implementation uses increasing-depth optimization with extrapolated initial parameters and additional linear, quadratic, and zero-angle initializations.It recommends gradient-based optimization for ideal simulations and gradient-free methods under finite-shot measurement noise.Source: §5 · p. 23
  • The study investigates 20 randomly chosen portfolio instances with n = 5 and n = 10 assets.The best results are attributed to the greater qubit-permutation symmetry of full XY and QAMPA compared with the two ring mixers.Source: §5 · pp. 23–24
  • XY mixers outperform the standard mixer in noise-free analysis, but their greater noise sensitivity means the choice can reverse on noisier hardware.For selecting B = 5 of n = 10 assets at p = 7, full XY and QAMPA each find the optimal portfolio with probability P ≃0.6.Source: §5 · p. 24
  • Broader distributions of returns and correlations are associated with a more pronounced energy landscape and simpler classical optimization.The authors recommend carefully selecting instance statistics when benchmarking QAOA.Source: §5 · p. 24
  • Ancillary files provide annualized covariance matrices and returns for the German DAX 30, calculated from data between 2016 and 2021.The files support the instance used in Sec. 4.3.Source: Supplementary information · p. 24

A Decomposition of mixer operators

The appendix compares circuit decompositions for XY mixing and ZZ phase separation. The reshuffled XY mixer combines these operations with fewer CNOT gates than the full XY mixer.

A Decomposition of mixer operators

B Data for covariances and returns

The appendix provides covariance and return data for the portfolio optimization instance used in Sec. 4.3, including tables for five German DAX 30 assets.

B Data for covariances and returns

Loading 2207.10555v1…