Improved quantum volume estimation with transducers and amortized quantum walks
Abstract
The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential algorithmic techniques related to Markov Chain Monte Carlo and simulated annealing, and the problem connects to several important geometrical results, like the KLS conjecture. In this work, we quantize the state-of-the-art Õ(d3.5+d3/ε2)-query randomized algorithm developed by Cousins and Vempala, and obtain a Õ(d3.5 + d1.75/ε)-query quantum algorithm, improving over the Õ(d3.5 + d2.25/ε) state-of-the-art bound. Our key technical contribution is a framework for amortizing the cost of a quantum walk. The framework is based on the recent transducer toolkit introduced by Belovs, Jeffery and Yolcu. It is this amortized quantum walk framework that allows us to exploit the amortized analysis of the ball walk by Cousins and Vempala, thus overcoming the key barrier that previously barred its quantum implementation.
Related
- Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- Quantum Spectral Estimation with Multiple Initial States: Improved Error and Cost Scaling
- Compiling the 2D Fermi-Hubbard ground-state energy estimation algorithm for active volume quantum architectures
- Improved Quantum Algorithms for Rényi Entropies Estimation
- Improved Adaptive Estimation of Quantum Partition Functions with Heisenberg Scaling
BibTeX
@misc{cornelissen2026improved,
title = {{Improved quantum volume estimation with transducers and amortized quantum walks}},
author = {Arjan Cornelissen and Simon Apers and Sander Gribling},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40217},
eprint = {2609.40217},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05780943v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved quantum volume estimation with transducers and amortized quantum walks
AU - Arjan Cornelissen
AU - Simon Apers
AU - Sander Gribling
PY - 2026
DA - 2026/10/05
PB - HAL
DO - 10.48550/arxiv.2609.40217
UR - https://hal.science/hal-05780943v1
AB - The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential algorithmic techniques related to Markov Chain Monte Carlo and simulated annealing, and the problem connects to several important geometrical results, like the KLS conjecture. In this work, we quantize the state-of-the-art Õ(d^3.5+d^3/ε^2)-query randomized algorithm developed by Cousins and Vempala, and obtain a Õ(d^3.5 + d^1.75/ε)-query quantum algorithm, improving over the Õ(d^3.5 + d^2.25/ε) state-of-the-art bound. Our key technical contribution is a framework for amortizing the cost of a quantum walk. The framework is based on the recent transducer toolkit introduced by Belovs, Jeffery and Yolcu. It is this amortized quantum walk framework that allows us to exploit the amortized analysis of the ball walk by Cousins and Vempala, thus overcoming the key barrier that previously barred its quantum implementation.
ER -