We give a rigorous and self-contained analysis of the Grover-Rudolph quantum state-preparation algorithm, which encodes a probability distribution $ \{p_k\} $ as an $ n $-qubit amplitude state $ \sum_k\sqrt{p_k}|k\rangle $ via a hierarchy of controlled $ \mathrm{R}_y $ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most $ \eta $ changes the output distribution by at most $ \min(1, n\eta) $ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $ b\ge\log_2(2n\pi/\varepsilon) $ bits and $ S\ge 2^{n+1}\log(2/\delta)/\varepsilon^2 $ shots suffice to achieve accuracy $ \varepsilon $ with confidence $ 1-\delta $. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $ \{ \mathrm{R}_y(\cdot), X, \mathrm{CNOT}\} $ via Gray-code ladders and a Walsh-Hadamard angle transform.
Citation: Antonio Falcó, Daniela Falcó-Pomares, Hermann G. Matthies. A rigorous and self-contained proof of the Grover-Rudolph state preparation algorithm[J]. AIMS Mathematics, 2026, 11(6): 16366-16394. doi: 10.3934/math.2026672
We give a rigorous and self-contained analysis of the Grover-Rudolph quantum state-preparation algorithm, which encodes a probability distribution $ \{p_k\} $ as an $ n $-qubit amplitude state $ \sum_k\sqrt{p_k}|k\rangle $ via a hierarchy of controlled $ \mathrm{R}_y $ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most $ \eta $ changes the output distribution by at most $ \min(1, n\eta) $ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $ b\ge\log_2(2n\pi/\varepsilon) $ bits and $ S\ge 2^{n+1}\log(2/\delta)/\varepsilon^2 $ shots suffice to achieve accuracy $ \varepsilon $ with confidence $ 1-\delta $. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $ \{ \mathrm{R}_y(\cdot), X, \mathrm{CNOT}\} $ via Gray-code ladders and a Walsh-Hadamard angle transform.
| [1] |
V. Bergholm, J. J. Vartiainen, M. Möttönen, M. M. Salomaa, Quantum circuits with uniformly controlled one-qubit gates, Phys. Rev. A, 71 (2005), 052330. https://doi.org/10.1103/PhysRevA.71.052330 doi: 10.1103/PhysRevA.71.052330
|
| [2] |
G. Brassard, P. Høyer, M. Mosca, A. Tapp, Quantum amplitude amplification and estimation, Contemp. Math., 305 (2002), 53–74. https://doi.org/10.1090/conm/305/05215 doi: 10.1090/conm/305/05215
|
| [3] |
J. González-Conde, T. W. Watts, P. Rodriguez-Grasa, M. Sanz, Efficient quantum amplitude encoding of polynomial functions, Quantum, 8 (2024), 1297. https://doi.org/10.22331/q-2024-03-21-1297 doi: 10.22331/q-2024-03-21-1297
|
| [4] | L. K. Grover, T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv: quant-ph/0208112. https://doi.org/10.48550/arXiv.quant-ph/0208112 |
| [5] |
W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Stat. Assoc., 58 (1963), 13–30. https://doi.org/10.1080/01621459.1963.10500830 doi: 10.1080/01621459.1963.10500830
|
| [6] | J. Luo, G. Li, L. Li, Space-time tradeoff for sparse quantum state preparation, arXiv: 2506.16964. https://doi.org/10.48550/arXiv.2506.16964 |
| [7] |
R. Mao, G. Tian, X. Sun, Toward optimal circuit size for sparse quantum state preparation, Phys. Rev. A, 110 (2024), 032439. https://doi.org/10.1103/PhysRevA.110.032439 doi: 10.1103/PhysRevA.110.032439
|
| [8] |
G. Marín-Sánchez, J. González-Conde, M. Sanz, Quantum algorithms for approximate function loading, Phys. Rev. Res., 5 (2023), 033114. https://doi.org/10.1103/PhysRevResearch.5.033114 doi: 10.1103/PhysRevResearch.5.033114
|
| [9] | M. Möttönen, J. J. Vartiainen, V. Bergholm, M. M. Salomaa, Transformation of quantum states using uniformly controlled rotations, Quant. Inf. Comp., 5 (2005), 467–473. |
| [10] |
D. Ramacciotti, A. I. Lefterovici, A. F. Rotundo, A simple quantum algorithm to efficiently prepare sparse states, Phys. Rev. A, 110 (2024), 032609. https://doi.org/10.1103/PhysRevA.110.032609 doi: 10.1103/PhysRevA.110.032609
|
| [11] |
X. Zhang, T. Li, X. Yuan, Quantum state preparation with optimal circuit depth: implementations and applications, Phys. Rev. Lett., 129 (2022), 230504. https://doi.org/10.1103/PhysRevLett.129.230504 doi: 10.1103/PhysRevLett.129.230504
|
Figures(7) / Tables(4)
Antonio Falcó, Daniela Falcó-Pomares, Hermann G. Matthies. A rigorous and self-contained proof of the Grover-Rudolph state preparation algorithm[J]. AIMS Mathematics, 2026, 11(6): 16366-16394. doi: 10.3934/math.2026672
DownLoad: