A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911709696884736 |
|---|---|
| author | Falco, Antonio Falco-Pomares, Daniela Matthies, Hermann G. |
| author_facet | Falco, Antonio Falco-Pomares, Daniela Matthies, Hermann G. |
| contents | 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}\ket{k}$ via a hierarchy of controlled $\RY$ 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 $η$ changes the output distribution by at most $\min(1,nη)$ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $b\ge\log_2(2nπ/\varepsilon)$ bits and $S\ge 2^{n+1}\log(2/δ)/\varepsilon^2$ shots suffice to achieve accuracy $\varepsilon$ with confidence $1-δ$. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $\{\RY(\cdot),X,\CNOT\}$ via Gray-code ladders and a Walsh--Hadamard angle transform. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17930 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm Falco, Antonio Falco-Pomares, Daniela Matthies, Hermann G. Quantum Physics Numerical Analysis 81P68, 81P65 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}\ket{k}$ via a hierarchy of controlled $\RY$ 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 $η$ changes the output distribution by at most $\min(1,nη)$ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $b\ge\log_2(2nπ/\varepsilon)$ bits and $S\ge 2^{n+1}\log(2/δ)/\varepsilon^2$ shots suffice to achieve accuracy $\varepsilon$ with confidence $1-δ$. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $\{\RY(\cdot),X,\CNOT\}$ via Gray-code ladders and a Walsh--Hadamard angle transform. |
| title | A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm |
| topic | Quantum Physics Numerical Analysis 81P68, 81P65 |
| url | https://arxiv.org/abs/2601.17930 |