pith. sign in

arxiv: 2510.04736 · v2 · pith:RZTLZW3Mnew · submitted 2025-10-06 · 🪐 quant-ph · cs.CC

Quantum Subgradient Estimation for Conditional Value-at-Risk Optimization

Vasilis Skarlatos , Nikos Konofaos This is my paper

Pith reviewed 2026-05-21 21:30 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords CVaRquantum amplitude estimationsubgradient estimationVaR thresholdquery complexitytail-risk optimization
0
0 comments X

The pith

Quantum amplitude estimation estimates CVaR subgradients with O(1/ε) queries even while estimating the VaR threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper constructs a quantum subgradient oracle for Conditional Value-at-Risk optimization that relies on amplitude estimation. It proves through a tripartite proposition that the oracle uses O(1/ε) quantum queries to produce ε-accurate subgradient estimates, even though the Value-at-Risk threshold must be estimated as an intermediate step. The analysis tracks how estimation error from the threshold stage affects the final subgradient accuracy and shows that the overall query bound stays linear in 1/ε. If the bound holds, stochastic projected subgradient descent using this oracle converges faster than classical Monte Carlo methods, which require O(1/ε²) samples. The work also reports numerical simulations that match the predicted scaling.

Core claim

Via a tripartite proposition, CVaR subgradients can be estimated with O(1/ε) quantum queries even when the Value-at-Risk threshold itself must be estimated, establishing a near-quadratic improvement in query complexity over classical Monte Carlo.

What carries the argument

Quantum subgradient oracle based on amplitude estimation, together with an error-propagation analysis from VaR threshold estimation to CVaR gradient estimates.

If this is right

  • Stochastic projected subgradient descent converges at rates governed by the O(1/ε) oracle.
  • The method stays robust when threshold estimation noise is present at the level analyzed.
  • Numerical simulations on simulated quantum circuits reproduce the predicted query scaling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same oracle construction could be tested on other coherent risk measures that also involve a threshold parameter.
  • Hardware implementations would need to verify that circuit depth for amplitude estimation does not introduce additional error sources beyond the paper's model.
  • The quadratic speedup might become practically relevant for high-dimensional portfolio problems where classical sampling becomes prohibitive.

Load-bearing premise

Error propagation from VaR threshold estimation to CVaR subgradient estimates preserves the overall O(1/ε) query bound without hidden polynomial factors.

What would settle it

A quantum circuit experiment that counts the number of queries actually required to reach a target accuracy on CVaR subgradients when the VaR threshold is estimated simultaneously, to check whether the scaling remains O(1/ε).

Figures

Figures reproduced from arXiv: 2510.04736 by Nikos Konofaos, Vasilis Skarlatos.

Figure 1
Figure 1. Figure 1: CVaR gradient ℓ2 error versus budget. MC shows 1/ √ N decay. QAE-style follows 1/M, with the dotted MC curve plotted at N = M2 for slope comparison. Method Budget Gradient ℓ2 Error MC 100 0.31862 MC 215 0.14953 MC 464 0.09620 MC 1000 0.09827 MC 2154 0.05187 MC 4641 0.03030 MC 10000 0.01753 QAE-style 10 0.36073 QAE-style 21 0.19755 QAE-style 46 0.07822 QAE-style 100 0.01017 QAE-style 215 0.01352 QAE-style 4… view at source ↗
Figure 2
Figure 2. Figure 2: Projected CVaR minimization trajectories as a function of iterations. Both MC and QAE-style estimators [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Projected CVaR minimization plotted against cumulative queries. QAE-style achieves comparable CVaR with [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
read the original abstract

Conditional Value-at-Risk (CVaR) is a leading tail-risk measure in finance, central to both regulatory and portfolio optimization frameworks. Classical estimation of CVaR and its gradients relies on Monte Carlo simulation, incurring $O(1/\epsilon^2)$ sample complexity to achieve $\epsilon$-accuracy. In this work, we design and analyze a quantum subgradient oracle for CVaR minimization based on amplitude estimation. Via a tripartite proposition, we show that CVaR subgradients can be estimated with $O(1/\epsilon)$ quantum queries, even when the Value-at-Risk (VaR) threshold itself must be estimated. We further quantify the propagation of estimation error from the VaR stage to CVaR gradients and derive convergence rates of stochastic projected subgradient descent using this oracle. Our analysis establishes a near-quadratic improvement in query complexity over classical Monte Carlo. Numerical experiments with simulated quantum circuits confirm the theoretical rates and illustrate robustness to threshold estimation noise. This constitutes the first rigorous complexity analysis of quantum subgradient methods for tail-risk minimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to construct a quantum subgradient oracle for CVaR minimization via amplitude estimation. It asserts via a tripartite proposition that CVaR subgradients can be estimated to accuracy ε using O(1/ε) quantum queries even when the VaR threshold must itself be estimated by amplitude estimation; the work quantifies error propagation from the VaR stage, derives convergence rates for stochastic projected subgradient descent under this oracle, and reports numerical confirmation on simulated circuits, establishing a near-quadratic improvement over classical Monte Carlo O(1/ε²) sample complexity.

Significance. If the error-propagation analysis is rigorous, the result would be a meaningful contribution to quantum algorithms for risk-sensitive optimization. It supplies the first explicit query-complexity bound for quantum subgradient methods on a tail-risk objective and demonstrates that standard amplitude-estimation primitives can be composed without destroying the quadratic speedup, which is relevant for portfolio-optimization applications where CVaR appears in regulatory and risk-management settings.

major comments (2)
  1. [Section 3] Tripartite proposition (Section 3): the argument that VaR estimation error with precision δ propagates to an O(ε) error in the CVaR subgradient without introducing extra polynomial factors in 1/ε must be made fully explicit. In particular, the sensitivity of the indicator 1_{X≥VaR} and the conditional tail expectation to threshold misestimation should be bounded so that δ = O(ε) (or δ = O(ε / log(1/ε))) suffices; otherwise the total query cost could acquire an extra ε^{-c} factor that would undermine the claimed O(1/ε) bound.
  2. [Section 5] Convergence analysis (Section 5): the theorem relating oracle accuracy to optimization convergence rate assumes an unbiased O(ε)-accurate subgradient oracle, but the combined bias and variance introduced by simultaneous VaR and CVaR estimation must be tracked through the entire stochastic projected subgradient iteration to confirm that the total number of quantum queries remains O(1/ε²) (or better) for ε-optimal solutions.
minor comments (2)
  1. [Abstract] The abstract states that numerical experiments 'confirm the theoretical rates' but does not report circuit depth, number of qubits, or the precise simulation model used; adding these details would improve reproducibility.
  2. [Section 2] Notation for the quantum amplitude-estimation circuit (e.g., the precise definition of the Grover operator and the number of repetitions) should be introduced before the tripartite proposition to avoid forward references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments highlight important points on rigor in error propagation and convergence analysis, which we address below. We have revised the manuscript to incorporate clarifications and extensions as described.

read point-by-point responses

  1. Referee: [Section 3] Tripartite proposition (Section 3): the argument that VaR estimation error with precision δ propagates to an O(ε) error in the CVaR subgradient without introducing extra polynomial factors in 1/ε must be made fully explicit. In particular, the sensitivity of the indicator 1_{X≥VaR} and the conditional tail expectation to threshold misestimation should be bounded so that δ = O(ε) (or δ = O(ε / log(1/ε))) suffices; otherwise the total query cost could acquire an extra ε^{-c} factor that would undermine the claimed O(1/ε) bound.

    Authors: We agree that the propagation argument benefits from greater explicitness. The tripartite proposition already uses a first-order sensitivity analysis under the assumption of a distribution with bounded density ρ at the VaR level, yielding |∇CVaR(VaR + δ) - ∇CVaR(VaR)| ≤ O(δ) + O(ε) with no higher-order polynomial blow-up in 1/ε. To make this fully rigorous, we have added Lemma 3.2 that bounds the difference in the indicator expectation by ∫_{VaR}^{VaR+δ} ρ(x) dx ≤ ||ρ||_∞ δ and similarly for the conditional tail, confirming that δ = Θ(ε) preserves the O(1/ε) query bound. The revised Section 3 now states this lemma and its proof explicitly. revision: yes

  2. Referee: [Section 5] Convergence analysis (Section 5): the theorem relating oracle accuracy to optimization convergence rate assumes an unbiased O(ε)-accurate subgradient oracle, but the combined bias and variance introduced by simultaneous VaR and CVaR estimation must be tracked through the entire stochastic projected subgradient iteration to confirm that the total number of quantum queries remains O(1/ε²) (or better) for ε-optimal solutions.

    Authors: We thank the referee for this observation. Theorem 5.1 is stated for an unbiased oracle, but the actual implementation introduces a controllable bias of O(ε) from the VaR stage (with δ = O(ε)) and variance bounded by the amplitude-estimation concentration. We have extended the proof to include a bias-variance decomposition: the bias term contributes an additive O(ε) to the convergence bound via standard results on inexact subgradient methods, while the variance remains O(1) per iteration. Consequently, the total quantum query complexity for ε-optimality stays O(1/ε²), matching the classical rate up to the quadratic improvement in the oracle. A new remark and corollary in Section 5 now track these quantities explicitly through the iteration. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard quantum amplitude estimation with independent error-propagation analysis.

full rationale

The paper's central claim rests on applying quantum amplitude estimation (a standard, externally established primitive) to CVaR subgradient estimation, followed by a tripartite proposition that quantifies VaR-to-CVaR error propagation to preserve the O(1/ε) query bound. No step reduces the target complexity to a fitted parameter, self-defined quantity, or load-bearing self-citation whose validity depends on the present work. The analysis is self-contained against external benchmarks (prior quantum query complexity results) and does not rename known empirical patterns or smuggle ansatzes via internal citations. The skeptic concern about hidden polynomial factors in error propagation is a question of proof correctness rather than circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard quantum computing assumptions and convexity of CVaR without introducing new free parameters or postulated entities; the tripartite proposition invokes amplitude estimation applicability to both threshold and expectation estimation.

axioms (1)
  • domain assumption Quantum amplitude estimation applies directly to estimating both the VaR threshold and the conditional expectation in CVaR with the stated query complexity
    Invoked in the design of the quantum subgradient oracle and the tripartite proposition.

pith-pipeline@v0.9.0 · 5717 in / 1311 out tokens · 82623 ms · 2026-05-21T21:30:29.286456+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Tyrrell Rockafellar and Stanislav Uryasev

    R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk.Journal of Risk, 2(3):21– 41, 2000

    work page 2000

  2. [2]

    Tyrrell Rockafellar and Stanislav Uryasev

    R. Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distributions.Journal of Banking & Finance, 26(7):1443–1471, 2001

    work page 2001

  3. [3]

    Nemirovski, A

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming.SIAM Journal on Optimization, 19(4):1574–1609, 2009

    work page 2009

  4. [4]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. InContemporary Mathematics, volume 305, pages 53–74. American Mathematical Society, 2002

    work page 2002

  5. [5]

    Stefan Woerner and Daniel J. Egger. Quantum risk analysis.npj Quantum Information, 5(1):15, 2019

    work page 2019

  6. [6]

    Quantum speedup of monte carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015

    Ashley Montanaro. Quantum speedup of monte carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015

    work page 2015

  7. [7]

    Benchmarking portfolio optimization with qaoa

    Rudolf Brandhofer, Nikolaos Diamandis, Matthias Rosenkranz, and Alexey Galda. Benchmarking portfolio optimization with qaoa. InProceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE), pages 469–479, 2022

    work page 2022

  8. [8]

    Quantum approaches to portfolio optimisation.Quantum Information Processing, 22(4):131, 2023

    Francesco Buonaiuto, Oscar Cespedes, Andrew Lord, Michal Krelina, and Ross Duncan. Quantum approaches to portfolio optimisation.Quantum Information Processing, 22(4):131, 2023

    work page 2023

  9. [9]

    Quantum algorithms for portfolio optimization

    Iordanis Kerenidis, Anupam Prakash, and Dorian Szilágyi. Quantum algorithms for portfolio optimization. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies (AFT), pages 147–155. ACM, 2019

    work page 2019

  10. [10]

    Amplitude estimation without phase estimation

    Yoshitaka Suzuki, Shumpei Uno, Rudy Raymond, Takaki Tanaka, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation without phase estimation. InQuantum Information Processing (QIP), 2020

    work page 2020

  11. [11]

    Fast convex optimization with quantum gradient methods.arXiv preprint arXiv:2503.17356, 2025.https://arxiv.org/abs/2503.17356

    Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, and Marco Pistoia. Fast convex optimization with quantum gradient methods.arXiv preprint arXiv:2503.17356, 2025.https://arxiv.org/abs/2503.17356

    work page arXiv 2025

  12. [12]

    Portfolio construction using a sampling-based variational quantum scheme

    Gabriele Agliardi, Dimitris Alevras, Vaibhaw Kumar, Roberto Lo Nardo, Gabriele Compostella, Sumit Kumar, Manuel Proissl, and Bimal Mehta. Portfolio construction using a sampling-based variational quantum scheme. arXiv preprint arXiv:2508.13557, 2025

    work page arXiv 2025

  13. [13]

    Barkoutsos, Giacomo Nannicini, Alberto Robert, and Ivano Tavernelli

    Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Alberto Robert, and Ivano Tavernelli. Improving varia- tional quantum optimization using cvar.Quantum, 4:256, 2020. https://quantum-journal.org/papers/ q-2020-04-20-256/. A Preliminaries We consider a portfolio of d assets with weight vector w∈ W ⊆R d, where W denotes the feasible set (e.g., the probability si...

    work page 2020

  14. [14]

    The logical qubit requirements of QAE-style CVaR estimation scale only logarithmically with portfolio discretization and polynomially with target precision, making the algorithm theoretically scalable

    work page

  15. [15]

    This places near-term implementation out of reach but provides a concrete target for hardware roadmaps

    However, current fault-tolerant overheads inflate the physical qubit count into the tens of thousands even for modest instances. This places near-term implementation out of reach but provides a concrete target for hardware roadmaps. C.4 Perspective While tens of thousands of physical qubits are beyond today’s devices, several technology trends can reduce ...

    work page 2000