arXiv preprint ·
Improved quantum volume estimation with transducers and amortized quantum walks
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\widetilde{O}(d^{3.5}+d^3/\varepsilon^2)$-query randomized algorithm developed by Cousins and Vempala, and obtain a $\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$-query quantum algorithm, improving over the $\widetilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
A differentiability framework for zigzag persistent homology via linear interpolation
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fréchet distance
Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model
A Unified Dual Method for Matching Problems
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.