A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm

Abstract

Preparing quantum states whose amplitudes encode classical probability distributions is a fundamental primitive in quantum algorithms based on amplitude encoding and amplitude estimation. Given a probability distribution $\{p_k\}_{k=0}^{2^n-1}$, the Grover--Rudolph procedure constructs an $n$-qubit state $\ketψ=\sum_{k=0}^{2^n-1}\sqrt{p_k}\ket{k}$ by recursively applying families of controlled one-qubit rotations determined by a dyadic refinement of the target distribution. Despite its widespread use, the algorithm is often presented with informal correctness arguments and implicit conventions on the underlying dyadic tree. In this work we give a rigorous and self-contained analysis of the Grover--Rudolph construction: we formalize the dyadic probability tree, define the associated angle map via conditional masses, derive the resulting trigonometric factorizations, and prove by induction that the circuit prepares exactly the desired measurement law in the computational basis. As a complementary circuit-theoretic contribution, we show that each Grover--Rudolph stage is a uniformly controlled $\RY$ rotation on an active register and provide an explicit ancilla-free transpilation into the gate dictionary $\{\RY(\cdot),X,\CNOT(\cdot\to\cdot)\}$ using Gray-code ladders and a Walsh--Hadamard angle transform.