Quantum algorithms improve geometric volume estimation efficiency
Improved quantum volume estimation with transducers and amortized quantum walks
Computational GeometryData Structures and Algorithms
Summary
Estimating the volume of a shape is a tough problem that has many uses in computer science and math. The authors improved the best existing quantum algorithm to estimate this volume more quickly by developing a new technique that speeds up a specific process called a quantum walk. They built on previous classical methods and modern quantum tools to overcome barriers that had blocked progress before. This results in faster quantum computation for volume estimation, especially in higher-dimensional spaces.
What this means in practice
- •For quantum algorithm developers: Develop faster quantum subroutines for estimating complex geometric volumes used in scientific computing and optimization.
- •For optimization software engineers: Integrate improved quantum volume estimation techniques to speed up simulations relying on geometric sampling.
Authors
Arjan Cornelissen, Simon Apers, Sander Gribling
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 recently-resolved 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.