Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization

Abstract

Variational Quantum Algorithms (VQAs) rely heavily on classical optimization routines to navigate high-dimensional, noisy parameter landscapes. However, the evaluation of analytical gradients via the parameter-shift rule requires 𝒪(p) circuit executions, rendering this approach computationally prohibitive for deep circuits. While simultaneous perturbation methods provide an 𝒪(1) alternative, their gradient estimates suffer from severe 𝒪(p) spatial variance, which impedes convergence. To resolve this tension, we introduce the Cached Recycled Variance-Reduced Gradient (CRVG) by leveraging variance reduction techniques. We formulate two variants: a 3-Circuit (1-Sided) Non-Recursive CRVG and a Recursive CRVG. By introducing a center-point caching mechanism, the 3-Circuit CRVG mathematically recycles quantum measurements to reduce the inner-loop circuit complexity by 25\% across both variants. We establish a theoretical separation between the two routing paths to achieve an ε²-stationary point: the non-recursive variant reaches a sample complexity of 𝒪(max{p/ε², p^2/3/ε^10/3}), while the recursive variant achieves an improved complexity of 𝒪(max{p/ε², √p/ε³}). Empirically, extensive evaluations on MaxCut and Maximum Independent Set (MIS) benchmarks validate these findings. While standard simultaneous perturbation remains a robust baseline across varying depths, CRVG demonstrates targeted advantages in specific amortizable regimes, such as the non-recursive variant on EfficientSU2 circuits and both variants on depth-three QAOA, yielding superior energy minimums and tighter output variances. Ultimately, CRVG establishes a principled bias-throughput trade-off for scaling near-term quantum optimization.

Exact Tail Laws for Nonlinear SGD with Infinite-Variance Gradients
Xiaoli Li, Qianqian Lei, Ziyang Wei +1
arXiv16 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Breaking the Likelihood Trap: Variance-Calibrated Modulation for Large Language Model Decoding
Yuanhao Ding, Meimingwei Li, Esteban Garces Arias +3
arXiv2 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv
Breaking the Infinite Barrier in the 1/3--2/3 Conjecture
Max Aires, Swee Hong Chan, Igor Pak +1
arXiv28 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Lowest-known Energy Configuration of N=100 000 Coulomb Charges in a Disk: Breaking the 10⁵ Barrier
Georgiy K. Lavrov, Eduard G. Nikonov
arXiv25 Sep 2026PreprintarXiv licenceFull textMathematical physics Optimisation & controlarXiv
Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani +1
arXiv31 Aug 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{nguyen2026breaking,
  title = {{Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization}},
  author = {Lam M. Nguyen and Sumanta Mukherjee and Dzung T. Phan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38800},
  eprint = {2609.38800},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38800},
}

RIS

TY  - UNPB
TI  - Breaking the Shot-Noise Barrier: Cached Recycled Variance-Reduced Gradients for Quantum Optimization
AU  - Lam M. Nguyen
AU  - Sumanta Mukherjee
AU  - Dzung T. Phan
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38800
UR  - https://arxiv.org/abs/2609.38800
AB  - Variational Quantum Algorithms (VQAs) rely heavily on classical optimization routines to navigate high-dimensional, noisy parameter landscapes. However, the evaluation of analytical gradients via the parameter-shift rule requires 𝒪(p) circuit executions, rendering this approach computationally prohibitive for deep circuits. While simultaneous perturbation methods provide an 𝒪(1) alternative, their gradient estimates suffer from severe 𝒪(p) spatial variance, which impedes convergence. To resolve this tension, we introduce the Cached Recycled Variance-Reduced Gradient (CRVG) by leveraging variance reduction techniques. We formulate two variants: a 3-Circuit (1-Sided) Non-Recursive CRVG and a Recursive CRVG. By introducing a center-point caching mechanism, the 3-Circuit CRVG mathematically recycles quantum measurements to reduce the inner-loop circuit complexity by 25\% across both variants. We establish a theoretical separation between the two routing paths to achieve an ε^2-stationary point: the non-recursive variant reaches a sample complexity of 𝒪(max{p/ε^2, p^2/3/ε^10/3}), while the recursive variant achieves an improved complexity of 𝒪(max{p/ε^2, √p/ε^3}). Empirically, extensive evaluations on MaxCut and Maximum Independent Set (MIS) benchmarks validate these findings. While standard simultaneous perturbation remains a robust baseline across varying depths, CRVG demonstrates targeted advantages in specific amortizable regimes, such as the non-recursive variant on EfficientSU2 circuits and both variants on depth-three QAOA, yielding superior energy minimums and tighter output variances. Ultimately, CRVG establishes a principled bias-throughput trade-off for scaling near-term quantum optimization.
ER  -

Abstract

Related

Cite