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

• URL: http://arxiv.org/abs/2601.17930v1
• Date: Sun, 25 Jan 2026 18:00:48 GMT
• Title: A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm
• Authors: Antonio Falco, Daniela Falco-Pomares, Hermann G. Matthies,
• Abstract summary: We show that each Grover--Rudolph stage is a uniformly controlled $RY$ rotation on an active register.<n>We also show that each Grover--Rudolph stage is an explicit ancilla-free transpilation into the gate dictionary $RY(cdot),X,CNOT(cdottocdot)$ using Gray-code ladders and a Walsh--Hadamard angle transform.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
  Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem.<n>We show that Grover's algorithm matches the speedup of $O(qrstN)$ achieved by Grover's algorithm.
  arXiv  Detail & Related papers  (2025-12-09T10:01:55Z)
• Deterministic Cryptographic Seed Generation via Cyclic Modular Inversion over $\mathbb{Z}/3^p\mathbb{Z}$ [0.0]
  We present a framework for cryptographic seed generation based on cyclic modular inversion over $mathbbZ/3pmathbbZ$.<n>The mapping yields entropy-rich, cycle-complete seeds well-suited for cryptographic primitives such as DRBGs, KDFs, and post-quantum schemes.
  arXiv  Detail & Related papers  (2025-07-02T00:17:55Z)
• A new approximate Eastin-Knill theorem [0.0]
  We show that a quantum error correcting code can support a universal set of gates and approximately correct for local erasure.<n>In particular, we show that a quantum error correcting code can support a universal set of gates if and only if the conditional min-entropy of the Choi state of the encoding and noise channel is upper bounded by a function of the worst-case error probability.
  arXiv  Detail & Related papers  (2025-05-01T09:56:26Z)
• Architectures and random properties of symplectic quantum circuits [0.0]
  Parametrized and random unitary $n$-qubit circuits play a central role in quantum information. We present a universal set of generators $mathcalG$ for the symplectic algebra $imathfraksp(d/2)$. We find that the operators in $mathcalG$ cannot generate arbitrary local symplectic unitaries. We then review the Schur-Weyl duality between the symplectic group and the Brauer algebra, and use tools from Weingarten calculus to prove that Pauli measurements can converge
  arXiv  Detail & Related papers  (2024-05-16T17:15:39Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Implementing the Grover Algorithm in Homomorphic Encryption Schemes [0.25782420501870296]
  We apply quantum homomorphic encryption schemes suitable for circuits with a decryption number of $T/Tdagger$-gates to Grover's algorithm. The $T/Tdagger$ gate complexity of Grover's algorithm is also analysed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner.
  arXiv  Detail & Related papers  (2024-03-07T22:13:14Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
  Kitaev's quantum double model based on a finite group $G$. We describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement.
  arXiv  Detail & Related papers  (2022-05-04T08:10:36Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.