⚛️ quantum physics

Improved quantum volume estimation with transducers and amortized quantum walks

This paper presents a quantum algorithm for volume estimation that improves the query complexity to $\widetilde{O}(d^{3.5} + d^{1.75}/\varepsilon)$ by introducing a novel framework for amortizing quantum walk costs using the transducer toolkit, thereby successfully quantizing the state-of-the-art randomized algorithm by Cousins and Vempala.

Original authors: Arjan Cornelissen, Simon Apers, Sander Gribling

Published 2026-10-01

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Arjan Cornelissen, Simon Apers, Sander Gribling

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to measure the amount of space inside a complex, multi-dimensional shape. In the world of mathematics and computer science, this is known as the volume estimation problem. While it sounds simple for a cube or a sphere, the task becomes incredibly difficult when the shape is irregular and exists in dozens or hundreds of dimensions. This is not just an abstract puzzle; solving it is crucial for fields ranging from economics to physics, where researchers need to calculate probabilities and integrals in spaces too vast to visualize. For decades, the best tools available to solve this were randomized algorithms, which use chance to explore the shape and make a good guess. These methods have been refined over thirty years, becoming powerful enough to handle high dimensions, but they still require a massive number of steps to reach a precise answer.

Recently, a team of researchers has taken a significant leap forward by applying the principles of quantum computing to this classic problem. They have developed a new method that estimates the volume of these complex shapes using far fewer steps than the best classical methods. Their work does not just tweak an existing formula; it fundamentally rethinks how a computer can walk through a high-dimensional space to find its size. By combining a technique called a "quantum walk" with a new way of managing computational costs, they have created an algorithm that is provably faster than anything previously known. The result is a more efficient path to solving a problem that has long been a bottleneck in computational geometry.

To understand the achievement, one must first grasp how these algorithms typically work. The standard approach involves a process similar to a random walk. Imagine a particle moving randomly inside the shape, bouncing off walls and changing direction. Over time, if the particle moves long enough, it will visit every part of the shape in proportion to its size. By tracking where the particle goes, a computer can estimate the total volume. However, in high dimensions, this walk can get stuck in corners or move too slowly, requiring an enormous number of steps to get a reliable result. The most advanced classical algorithms, developed over the last decade, use a sophisticated version of this walk called the "speedy walk." This method is designed to move quickly through the interior of the shape, but it still struggles near the boundaries, where the shape might have sharp corners or narrow passages. To make the walk efficient, the classical algorithm uses a clever trick called amortization. It accepts that some steps will be very expensive to compute, but argues that these expensive steps are so rare that, on average, the cost per step remains low. This allows the algorithm to run efficiently in the long run, even if individual steps are difficult.

The challenge for quantum computers was that this amortization trick did not translate easily. Quantum algorithms operate on probabilities and superpositions, and the standard way of building them does not naturally support the kind of cost-sharing that makes the classical method work. If a quantum algorithm tried to mimic the classical approach directly, the errors would pile up, or the expensive steps would become too costly to ignore. The researchers in this study, Arjan Cornelissen, Simon Apers, and Sander Gribling, solved this by inventing a new framework based on a concept they call a "transducer." Think of a transducer as a machine that takes a specific input state and transforms it into a specific output state, while using a temporary helper that is restored to its original condition at the end. This is different from a standard quantum operation, which often leaves behind "garbage" or requires a fixed number of steps regardless of the input. The power of the transducer is that its cost can vary depending on the input. If the input is easy to handle, the transducer uses few resources; if it is hard, it uses more. Crucially, the researchers showed that these variable costs can be averaged out across the entire algorithm, just like in the classical case.

Using this framework, the team constructed a quantum version of the speedy walk. They designed a specific type of transducer that could reflect the quantum state of the walk around its stationary distribution—the state where the walk has settled into a stable pattern. This reflection is the core engine of the quantum walk. By carefully analyzing the geometry of the shape and the properties of the walk, they proved that the cost of these reflections could be amortized. This meant that even though some steps in the quantum walk were theoretically expensive, the average cost per step remained low. They combined this with other quantum techniques, such as quantum annealing, which helps the system move smoothly from one state to another, and quantum mean estimation, which allows for precise averaging of values. The result is a complete algorithm that estimates the volume of a convex body in a high-dimensional space.

The performance of this new algorithm is a marked improvement over the state of the art. The best classical randomized algorithm requires a number of steps that grows roughly with the dimension of the space raised to the power of 3.5, plus a term involving the desired precision. The previous best quantum algorithm improved this slightly, but the new method presented in this paper reduces the complexity significantly. Specifically, the new quantum algorithm requires a number of steps that grows with the dimension raised to the power of 3.5, but the term involving the precision is reduced from a power of 2.25 down to 1.75. In practical terms, this means that for a given level of accuracy, the quantum computer can solve the problem with substantially fewer queries to the shape than any previous method. The researchers did not just propose this idea; they provided a rigorous mathematical proof that their algorithm works and that the cost analysis holds true. They also addressed the practical issue of how to handle the continuous nature of the space by showing how to discretize the problem without losing the essential properties of the walk.

This work represents a successful quantization of a complex classical algorithm that was previously thought to be difficult to adapt. By overcoming the barrier of amortization, the researchers have opened the door to more efficient quantum solutions for other problems that rely on similar random walk techniques. The paper explicitly rules out the idea that a simple, direct translation of the classical algorithm would work; instead, it demonstrates that a new structural approach using transducers is necessary to achieve the speedup. The findings are presented as a proven theorem, backed by detailed mathematical arguments and a clear separation of the algorithm's components. While the paper does not claim to have solved every aspect of volume estimation or to have eliminated all open questions, it establishes a new benchmark for what is possible in this field. The authors suggest that their framework could be applied to other areas, but they focus their current claims on the volume estimation problem, where the results are concrete and verified.

The significance of this work lies in its ability to bridge the gap between classical efficiency and quantum speed. It shows that quantum computers can do more than just speed up simple searches; they can handle complex, iterative processes that require careful management of resources. By proving that the amortized analysis of the classical speedy walk can be translated into the quantum realm, the researchers have provided a blueprint for future algorithms. The paper concludes by noting that while there are still open questions, such as whether the rounding step of the algorithm can be further improved, the core contribution of the quantum walk framework is a solid and proven advancement. For anyone interested in the limits of computation, this work offers a clear example of how quantum mechanics can be harnessed to solve problems that have resisted efficient solutions for decades.

Technical Summary: Improved Quantum Volume Estimation with Transducers and Amortized Quantum Walks

Problem Statement

The volume estimation problem is a fundamental task in computational geometry, requiring the estimation of the volume of a convex body $K \subseteq \mathbb{R}^d$ given access to a membership oracle. The goal is to output an estimate $\tilde{V}$ such that $|\tilde{V}/\text{Vol}(K) - 1| \leq \varepsilon$ .

In the randomized setting, the state-of-the-art query complexity is $\tilde{O}(d^{3.5} + d^3/\varepsilon^2)$ , achieved by Cousins and Vempala [CV18] through a combination of body rounding and Markov Chain Monte Carlo (MCMC) methods, specifically utilizing the "speedy walk." In the quantum setting, prior work by Cornelissen and Hamoudi [CH23] achieved a complexity of $\tilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ by quantizing an earlier algorithm based on the hit-and-run walk. A significant barrier to improving the quantum bound to match the efficiency of the Cousins-Vempala algorithm was the lack of a suitable quantum amortized analysis for the speedy walk, particularly regarding the Metropolis filter and local conductance.

Methodology

This work introduces a framework for amortized quantum walks based on the transducer toolkit developed by Belovs, Jeffery, and Yolcu [BJY24]. A transducer is a unitary operation that maps a source state to a target state while preserving a catalyst state, with a complexity defined by the norm of the catalyst. This framework allows for input-dependent complexity analysis, which is crucial for amortization.

The methodology proceeds in two main phases:

1. The Amortized Quantum Walk Framework

The authors develop novel transducers for key algorithmic primitives:

Amplitude Amplification Transducer: An error-free transducer for amplitude amplification that avoids the accumulation of errors typical in bounded-error circuit compositions. This allows for exact state preparation and reflection without garbage states.
Quantum Walk Reflection Transducer: A construction that reflects through the stationary distribution of a random walk. By leveraging the connection between random walks and electrical networks, the authors show that the cost of reflecting through the stationary state can be amortized over the input distribution. The complexity is charged as an average over the relevant distributions rather than a worst-case bound.
Handling Metropolis Filters: To address the difficulty of implementing Metropolis filters (which require rejecting proposals) in a quantum setting without garbage, the authors modify the walk to act on a bipartite graph. This "bipartite speedy walk" allows for the construction of star states and reflections without the need to explicitly reject and undo operations, preserving the spectral gap of the original walk.

2. Quantum Volume Estimation Algorithm

The authors quantize the Cousins-Vempala [CV18] algorithm:

Discretization: Since transducers are defined on finite-dimensional Hilbert spaces, the continuous state space of the speedy walk is discretized onto a grid. The authors prove that this discretization preserves the spectral gap and stationary distribution properties up to negligible perturbations.
Annealing: The algorithm estimates the volume by computing a telescoping product of partition function ratios $Z(\beta_{j+1})/Z(\beta_j)$ along a cooling schedule. The authors construct a quantum annealing transducer that maps the stationary state of the speedy walk at one inverse temperature $\beta_j$ to the next $\beta_{j+1}$ .
Amortization: By combining the quantum walk reflection transducer with the amplitude amplification transducer, the authors demonstrate that the cost of preparing and reflecting through the Gibbs distributions is constant in an amortized sense. This overcomes the previous barrier where the cost of the speedy walk steps (dependent on local conductance) was too high to quantize efficiently.

Key Contributions

Amortized Quantum Walk Framework: The primary technical contribution is a general framework for amortizing the cost of quantum walks using transducers. This framework successfully handles the input-dependent costs associated with local conductance in the speedy walk.
Error-Free Transducers for Amplitude Amplification: The paper provides a construction for amplitude amplification transducers that do not produce garbage states, a necessary condition for the composition of quantum walk operators in this context.
Bipartite Walk Construction: A method to implement Metropolis filters via bipartite walks, enabling efficient quantum reflection through star states without the overhead of rejection sampling garbage.
Discretization of Continuous Walks: A rigorous analysis showing that the speedy walk on a convex body can be discretized onto a grid while maintaining the necessary spectral properties for quantum speedups.

Results

The paper presents a bounded-error quantum algorithm for volume estimation with the following query complexity:
$\tilde{O}\left(d^{3.5} + \frac{d^{1.75}}{\varepsilon}\right)$
This improves upon the previous state-of-the-art quantum bound of $\tilde{O}(d^{3.5} + d^{2.25}/\varepsilon)$ by Cornelissen and Hamoudi [CH23].

Specifically, the algorithm achieves a quadratic speedup in the dependence on $1/\varepsilon$ (from $1/\varepsilon^2$ in the classical randomized case to $1/\varepsilon$ in the quantum case) and improves the polynomial dependence on the dimension $d$ in the error term from $d^{2.25}$ to $d^{1.75}$ . The $d^{3.5}$ term arises from the classical rounding procedure (specifically the algorithm by Jia, Laddha, Lee, and Vempala [JLLV26] used to ensure the body is well-rounded), while the improved term stems from the quantum speedup in the volume estimation phase.

Additionally, the authors provide a quantum subroutine for generating a uniform superposition over a convex body with transduction complexity $\tilde{O}((dR + d^2)\log(1/\eta))$ , improving upon the classical randomized bound of $\tilde{O}(d^2R^2 + d^3)$ .

Significance

The paper claims that the key significance of this work lies in overcoming the "key barrier" that previously prevented the quantization of the Cousins-Vempala algorithm: the absence of a suitable amortized analysis in the quantum setting. By utilizing the transducer framework, the authors successfully port the efficient classical "speedy walk" analysis to the quantum domain.

The work demonstrates that the transducer toolkit is not merely a theoretical proxy but a practical framework for designing quantum algorithms that require complex amortization of costs. The authors note that while their approach yields a significant improvement, further quadratic speedups over the classical algorithm (e.g., reducing the $d^{3.5}$ term) would require new ideas, such as quantizing the rounding procedure or further optimizing the cooling schedule, which are left as open questions. The paper also highlights that their result matches the bound one might expect from quantizing the hit-and-run walk if recent classical improvements to its mixing time were applied, suggesting that the amortized approach is conceptually robust and competitive with alternative strategies.