Abstract
We propose a novel quantum algorithm for the general approximate simulation of Galton machines with polynomial depth in terms of the number of qubits and with bounded error, obtaining exponential quantum advantage over the corresponding classical algorithm. This work enables the efficient preparation of input distributions, which is particularly important in quantum algorithms for tasks ranging from option pricing to machine learning. To this end, we prove that the proposed procedure may be directly used to efficiently load normal distributions into quantum registers. Moreover, to the best of our knowledge, our work is the first to leverage the power of Mid-Circuit Measurement and Reuse (MCMR) technology in a way that is broadly applicable to a range of state-preparation problems, including those relating to finance. Specifically, our algorithm employs a repeat-until-success scheme, and only requires a constant-bounded number of repetitions in expectation. Furthermore, the algorithm is provably resistant to both phase-flip and bit-flip errors, leading to a first-of-its-kind empirical demonstration on a real quantum computer, the MCMR-enabled Honeywell System Model H0.
Introduction
Many high-impact quantum algorithms—such as those for option pricing, principal component analysis, and machine learning—require an initial probability distribution (like a Gaussian/normal distribution) to be loaded into a quantum register. However, preparing an arbitrary quantum state typically requires circuits of exponential depth, creating a massive computational bottleneck in the Noisy Intermediate-Scale Quantum (NISQ) era. Previous methods either required excessive ancillary qubits or suffered from high error accumulation. Researchers at JPMorgan Chase have addressed this by developing a novel quantum algorithm that simulates a "Galton Machine" to efficiently prepare normal distributions with polynomial circuit depth and built-in noise resistance.
Methodology: The Quantum Galton Machine
The proposed algorithm draws inspiration from the classical Galton Machine (or bean machine). In this classical device, balls drop through a peg board, moving left or right with equal probability at each peg. According to the Central Limit Theorem, the final distribution of balls at the bottom approximates a normal distribution.
To translate this into the quantum domain, the authors utilize several key techniques:
- Non-Unitary Transformations via MCMR: Mid-Circuit Measurement and Reuse (MCMR) allows for a "repeat-until-success" scheme. By measuring a single ancilla qubit and reusing it, the algorithm implements non-unitary transition matrices that simulate the "left or right" shifts of the Galton machine without requiring a new ancilla for every row.
- Qubit Scaling and Fourier Adders: To maintain polynomial circuit depth ($O(n^2)$), the algorithm iteratively refines a low-resolution distribution by adding qubits and applying correction steps using Quantum Fourier Transform (QFT) based adders.
- Amplitude Cancellation: A critical discovery is that the "incorrect" states associated with failed measurements undergo destructive interference. As the number of qubits increases, the probability of failure vanishes, ensuring high efficiency.
Experimental Validation and Results
The algorithm was evaluated using numerical simulations and hardware execution on the Honeywell System Model H0, a trapped-ion quantum computer supporting MCMR.
Key findings include:
- Resource Efficiency: The MCMR approach uses $2\times$ fewer total qubits and $6\times$ fewer ancillary qubits compared to traditional "MCMR-free" implementations.
- Noise Resistance: The "repeat-until-success" nature of the algorithm provides inherent error detection. Hardware noise typically pushes the system into a "discard" state (ancilla measured as $|1\rangle$) rather than corrupting the final distribution.
- Hardware Performance: On the Honeywell H0, the team successfully generated a 4-qubit normal distribution. Despite a post-selection success rate of ~21.28% (lower than the theoretical ~31.86% due to noise), the resulting distribution closely matched the target Gaussian.
Conclusion
This work demonstrates an efficient, noise-resistant method for state preparation on near-term quantum hardware. While the current implementation effectively generates centered normal distributions, it is subject to boundary conditions due to modulo $2^n$ arithmetic. Future research will explore generalizing this framework to other distribution families and assessing its performance on different hardware architectures, such as superconducting circuits, where measurement speeds and coherence times may vary.
Summary updated