Introduction
Hello, we present our project on implementing a quantum algorithm for simulating a Galton Board (QGB) with exponential speedup. Our approach leverages a quantum circuit design that computes $2n^2$ trajectories using only $\mathcal{O}(n^2)$ quantum gates, including Hadamard, X, controlled-SWAP, CNOT, and reset operations. The design models physical ball-peg interactions through a modular "quantum peg" circuit, efficiently simulating classical Galton board dynamics on a quantum computer. This is the reference paper : Universal Statistical Simulator
Paper summary
A quantum circuit for simulating a Galton Board (GB) is introduced, demonstrating exponential speedup by computing 2n trajectories with $mathcal{O}(n^2)$ resources using Hadamard, X, and controlled-SWAP gates, supplemented by CNOT and resets. The methodology is centered on modeling physical ball-peg interactions through a modular "quantum peg" circuit.
In the basic approach, qubits are initialized to |0⟩, with the middle qubit inverted via an X gate to represent the "ball". A control qubit is placed in superposition using a Hadamard gate. Controlled-SWAP operations are applied to simulate left or right deflections, followed by an inverted CNOT to stabilize the control qubit, and another SWAP to achieve the desired state, yielding a 50% probability split.
For scaling to an n-level Quantum Galton Board (QGB), the peg module is replicated successively, with mid-circuit resets on the control qubit and additional CNOTs to rebalance probabilities. An n-level QGB requires 2n qubits (n working, n ancilla) and up to $2n^2$ + 5n + 2 gates, producing outputs with a single '1' that necessitate post-processing to form binomial distributions.
Biased QGBs are constructed by replacing Hadamard gates with Rx(θ) rotations, allowing control over deflection probabilities (e.g., 75%:25% via θ = 2π/3). Fine-grained per-peg bias is achieved through iterative application, incorporating extra resets and corrective CNOTs at row ends, resulting in approximately $3n^2$ + 3n + 1 gates.
Possible use case
Probability Distribution simulation: It enables simulation of various statistical distributions (e.g., Hadamar, Gaussian) by adjusting bias angles and peg configurations, useful in statistical modeling and Monte Carlo methods.
Implementation plan (qmod function)
def quantum_galton_board(layers, classical, global_bias, bias_angles=[]):
Parameters:
- layers: Number of Galton board layers
- classical: Boolean to indicate whether to add resets between layers
- global_bias: Angle to apply a global bias rotation to the circuit
- bias_angles: List of dictionaries specifying per-peg bias for each containing layer, peg position, and rotation angle
Example bias settings:
- Default bias angle = π/2
- Peg count = 50
- Specific biases:
- (layer 3, peg 6) → π/3
- (layer 4, peg 8) → 2π/3
Example output circuit:
Simulation result:
Contributor
@KaziMuktadirAhmed
@Tasfia-007
@asif-saad
Introduction
Hello, we present our project on implementing a quantum algorithm for simulating a Galton Board (QGB) with exponential speedup. Our approach leverages a quantum circuit design that computes$2n^2$ trajectories using only $\mathcal{O}(n^2)$ quantum gates, including Hadamard, X, controlled-SWAP, CNOT, and reset operations. The design models physical ball-peg interactions through a modular "quantum peg" circuit, efficiently simulating classical Galton board dynamics on a quantum computer. This is the reference paper : Universal Statistical Simulator
Paper summary
A quantum circuit for simulating a Galton Board (GB) is introduced, demonstrating exponential speedup by computing 2n trajectories with$mathcal{O}(n^2)$ resources using Hadamard, X, and controlled-SWAP gates, supplemented by CNOT and resets. The methodology is centered on modeling physical ball-peg interactions through a modular "quantum peg" circuit.
In the basic approach, qubits are initialized to |0⟩, with the middle qubit inverted via an X gate to represent the "ball". A control qubit is placed in superposition using a Hadamard gate. Controlled-SWAP operations are applied to simulate left or right deflections, followed by an inverted CNOT to stabilize the control qubit, and another SWAP to achieve the desired state, yielding a 50% probability split.$2n^2$ + 5n + 2 gates, producing outputs with a single '1' that necessitate post-processing to form binomial distributions.
For scaling to an n-level Quantum Galton Board (QGB), the peg module is replicated successively, with mid-circuit resets on the control qubit and additional CNOTs to rebalance probabilities. An n-level QGB requires 2n qubits (n working, n ancilla) and up to
Biased QGBs are constructed by replacing Hadamard gates with Rx(θ) rotations, allowing control over deflection probabilities (e.g., 75%:25% via θ = 2π/3). Fine-grained per-peg bias is achieved through iterative application, incorporating extra resets and corrective CNOTs at row ends, resulting in approximately$3n^2$ + 3n + 1 gates.
Possible use case
Probability Distribution simulation: It enables simulation of various statistical distributions (e.g., Hadamar, Gaussian) by adjusting bias angles and peg configurations, useful in statistical modeling and Monte Carlo methods.
Implementation plan (qmod function)
def quantum_galton_board(layers, classical, global_bias, bias_angles=[]):Parameters:
Example bias settings:
Example output circuit:
Simulation result:
Contributor
@KaziMuktadirAhmed
@Tasfia-007
@asif-saad