Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

AIMS Mathematics

A rigorous and self-contained proof of the Grover-Rudolph state preparation algorithm

Antonio Falcó, Departamento de Matemáticas, Física y Ciencias Tecnológicas, Universidad Cardenal Herrera-CEU, CEU Universities San Bartolomé 55, 46115 Alfara del Patriarca (Valencia), Spain, Daniela Falco-Pomares, Hermann G. Matthies, Grupo de Investigación Bisite Universidad de Salamanca Calle Espejo s/n, 37007 Salamanca, Spain

Published Jan 1, 2026• 1 citation
Publisher

Abstract

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.

DOI
10.3934/math.2026672

Related papers

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

Antonio Falco, Daniela Falco-Pomares, Hermann G. Matthies

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.

quant-pharXiv:2601.17930•Jan 27, 2026•0 citations

Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

Debora Ramacciotti, Martin Steinbach, Bence Temesi +2 more

Sparse quantum state preparation is a common subroutine in quantum algorithms, where classical data with few nonzero entries must be loaded into a quantum state. In this work, we consider the Grover-Rudolph algorithm, which has recently been shown to efficiently prepare sparse states, and we propose two improvements. First, we extend an existing gate-merging procedure by allowing rotations to merge with virtual zero-angle gates on unreachable branches of the preparation tree, reducing the number of CNOTs and control qubits. Second, we introduce an approximate variant in which rotations with similar but not identical angles are merged at the cost of a small, controllable error in the prepared state. We derive a classically computable estimate of the resulting overlap with the target state, which is used to guide the merging decisions.

quant-pharXiv:2604.24973•Apr 29, 2026•0 citations

On the encoding complexity of quantum numerical integration: an angle-structure characterization

Francisco Chinesta, Antonio Falco, Daniela Falco-Pomares

We study numerical integration on $[0,1]$ by quantum amplitude estimation (QAE), with emphasis on the cost of constructing the amplitude oracle. We introduce a hierarchy of grid functions $\mathcal{G}_n^{(d)}$ whose angle map $Θ_g:\{0,1\}^n\to[0,π]$ is multilinear of degree at most $d$. Membership is classically checkable in $O(n2^n)$ time by the Walsh--Hadamard transform, and each $g\in\mathcal{G}_n^{(d)}$ admits a canonical encoding circuit with $\sum_{k=0}^d\binom{n}{k}$ multi-controlled $R_Y$ gates. Combining this circuit bound with classical discretisation estimates, we obtain a depth-versus-accuracy trade-off: for $g\in C^α[0,1]$, total gate count $O((\log(1/\varepsilon))^d\varepsilon^{-1})$ suffices for $\varepsilon$-accuracy with constant probability; in the affine case $d=1$ this is $O(\varepsilon^{-1}\log(1/\varepsilon))$ at fixed discretisation. We also show that encoding degree and Sobolev smoothness are independent: for every $s\in(0,1/2)$, $\mathcal{G}_n^{(1)}$ contains restrictions of functions in $W^{s',2}(0,1)$ for all $s'<s$ but not in $W^{s,2}(0,1)$. Experiments on the SpinQ Triangulum (NMR) and IBM Kingston (superconducting) processors at $n=2$ validate the predicted hierarchy: affine encodings run reliably on both platforms, while quadratic encodings exceed the Triangulum coherence budget but execute on Kingston.

quant-pharXiv:2604.24289•Apr 28, 2026•0 citations

An extention of Grover's quantum search algorithm (Foundations of Computer Science)

Keisuke Tanaka

Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time $O(\sqrt{N})$ with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where $N=2^{n}$ , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is $\Omega(N)$ .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in $O(\sqrt{N})$ time.

数理解析研究所講究録•Apr 1, 2000•0 citations

Efficient quantum state preparation with Walsh series

Julien Zylberman, Fabrice Debbasch

An approximate quantum state preparation method is introduced, called the Walsh series loader (WSL). The WSL approximates quantum states defined by real-value functions of single real variables with a depth independent of the number $n$ of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at $O(1/\sqrt{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the precision of the approximation in terms of infidelity. The circuit depth is also $O(1/\sqrt{\ensuremath{\epsilon}})$, the size is $O(n+1/\sqrt{\ensuremath{\epsilon}})$, and only one ancilla qubit is needed. The second method accurately represents quantum states with sparse Walsh series. The WSL loads $s$-sparse Walsh series into $n$ qubits with a depth doubly sparse in $s$ and $k$, the maximum number of bits with value 1 in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh series up to an error $\ensuremath{\epsilon}$ with a depth $O(sk)$, a size $O(n+sk)$, and one ancilla qubit. In both cases, the protocol is a repeat-until-success procedure with a probability of success $P=\mathrm{\ensuremath{\Theta}}(\ensuremath{\epsilon})$, giving an averaged total time of $O(1/{\ensuremath{\epsilon}}^{3/2})$ for the WSL and $O(sk/\ensuremath{\epsilon})$ for the sparse WSL. Amplitude amplification can be used to reach a probability of success $P=\mathrm{\ensuremath{\Theta}}(1)$, modifying the quantum circuit size to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+1/\sqrt{\ensuremath{\epsilon}})/\sqrt{\ensuremath{\epsilon}})$ and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+sk)/\sqrt{\ensuremath{\epsilon}})$ and the depth to $O([log{(n)}^{3}+1/\sqrt{\ensuremath{\epsilon}}]/\sqrt{\ensuremath{\epsilon}})$ and $O([log{(n)}^{3}+sk]/\sqrt{\ensuremath{\epsilon}})$, respectively. Amplitude amplification reduces by a factor $O(1/\sqrt{\ensuremath{\epsilon}})$ the total time dependence on $\ensuremath{\epsilon}$ but increases the size and depth of the associated quantum circuits, making them linearly dependent on $n$. These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-value, multivariate, almost-everywhere-differentiable function. The repeat-until-success Walsh series loader is so far the only method that prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.

arXiv:2307.08384•Physical Review A•Apr 1, 2024•28 citations

Ensemble Engineering to Overcome Destructive Cancellation in Quantum Measurements

Myeongsu Kim, Manas Sajjan, Sabre Kais

Quantum state preparation can shape how positive and negative contributions combine in correlation measurements, providing a route to control cancellation through ensemble engineering. We develop a framework for relating this control to the prepared distribution, using the infinite-temperature trace of the same operator product as a uniform-weight reference for ensemble-dependent correlators. For diagonal observables, resolving both projector sectors separates each sector's probability mass from its conditional sign alignment and determines their contributions to the full correlator. A worked example shows what a selected-sector description can miss, and a simple bound limits the error from omitting the complementary contribution. We use two complementary preparations: Grover-type amplitude amplification to redistribute probability toward a specified target, and oracle-free shallow circuits to shape the distribution at low depth. Zero-time benchmarks combine noiseless simulations with finite-shot sampling and IBM Quantum demonstrations on up to 20 qubits. Sector statistics distinguish low occupation from cancellation within an occupied sector, while comparisons with noiseless simulations show that characteristic features of the engineered cumulative patterns persist on hardware. We also extend the analysis to multi-qubit diagonal observables and connect their sign and sector rules to explicit preparation choices. These results provide a basis for designing and assessing structured ensembles through their operator-resolved contributions to quantum correlation measurements.

quant-pharXiv:2605.03729•Physical Review A•May 6, 2026•0 citations
We give a rigorous and self-contained analysis of the Grover-Rudolph quantum state-preparation algorithm, which encodes a probability distribution {pk}\{p_k\}{pk​} as an nnn-qubit amplitude state ∑kpk∣k⟩\sum_k\sqrt{p_k}|k\rangle∑k​pk​​∣k⟩ via a hierarchy of controlled Ry\mathrm{R}_yRy​ 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η)\min(1, n\eta)min(1,nη) in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: b≥log⁡2(2nπ/ε)b\ge\log_2(2n\pi/\varepsilon)b≥log2​(2nπ/ε) bits and S≥2n+1log⁡(2/δ)/ε2S\ge 2^{n+1}\log(2/\delta)/\varepsilon^2S≥2n+1log(2/δ)/ε2 shots suffice to achieve accuracy ε\varepsilonε with confidence 1−δ1-\delta1−δ. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into {Ry(⋅),X,CNOT}\{ \mathrm{R}_y(\cdot), X, \mathrm{CNOT}\}{Ry​(⋅),X,CNOT} via Gray-code ladders and a Walsh-Hadamard angle transform.
We give a rigorous and self-contained analysis of the Grover--Rudolph quantum state-preparation algorithm, which encodes a probability distribution {pk}\{p_k\}{pk​} as an nnn-qubit amplitude state ∑kpk∣k⟩\sum_k\sqrt{p_k}\ket{k}∑k​pk​​∣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η)\min(1,nη)min(1,nη) in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: b≥log⁡2(2nπ/ε)b\ge\log_2(2nπ/\varepsilon)b≥log2​(2nπ/ε) bits and S≥2n+1log⁡(2/δ)/ε2S\ge 2^{n+1}\log(2/δ)/\varepsilon^2S≥2n+1log(2/δ)/ε2 shots suffice to achieve accuracy ε\varepsilonε with confidence 1−δ1-δ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.
Sparse quantum state preparation is a common subroutine in quantum algorithms, where classical data with few nonzero entries must be loaded into a quantum state. In this work, we consider the Grover-Rudolph algorithm, which has recently been shown to efficiently prepare sparse states, and we propose two improvements. First, we extend an existing gate-merging procedure by allowing rotations to merge with virtual zero-angle gates on unreachable branches of the preparation tree, reducing the number of CNOTs and control qubits. Second, we introduce an approximate variant in which rotations with similar but not identical angles are merged at the cost of a small, controllable error in the prepared state. We derive a classically computable estimate of the resulting overlap with the target state, which is used to guide the merging decisions.
We study numerical integration on [0,1][0,1][0,1] by quantum amplitude estimation (QAE), with emphasis on the cost of constructing the amplitude oracle. We introduce a hierarchy of grid functions Gn(d)\mathcal{G}_n^{(d)}Gn(d)​ whose angle map Θg:{0,1}n→[0,π]Θ_g:\{0,1\}^n\to[0,π]Θg​:{0,1}n→[0,π] is multilinear of degree at most ddd. Membership is classically checkable in O(n2n)O(n2^n)O(n2n) time by the Walsh--Hadamard transform, and each g∈Gn(d)g\in\mathcal{G}_n^{(d)}g∈Gn(d)​ admits a canonical encoding circuit with ∑k=0d(nk)\sum_{k=0}^d\binom{n}{k}∑k=0d​(kn​) multi-controlled RYR_YRY​ gates. Combining this circuit bound with classical discretisation estimates, we obtain a depth-versus-accuracy trade-off: for g∈Cα[0,1]g\in C^α[0,1]g∈Cα[0,1], total gate count O((log⁡(1/ε))dε−1)O((\log(1/\varepsilon))^d\varepsilon^{-1})O((log(1/ε))dε−1) suffices for ε\varepsilonε-accuracy with constant probability; in the affine case d=1d=1d=1 this is O(ε−1log⁡(1/ε))O(\varepsilon^{-1}\log(1/\varepsilon))O(ε−1log(1/ε)) at fixed discretisation. We also show that encoding degree and Sobolev smoothness are independent: for every s∈(0,1/2)s\in(0,1/2)s∈(0,1/2), Gn(1)\mathcal{G}_n^{(1)}Gn(1)​ contains restrictions of functions in Ws′,2(0,1)W^{s',2}(0,1)Ws′,2(0,1) for all s′<ss'<ss′<s but not in Ws,2(0,1)W^{s,2}(0,1)Ws,2(0,1). Experiments on the SpinQ Triangulum (NMR) and IBM Kingston (superconducting) processors at n=2n=2n=2 validate the predicted hierarchy: affine encodings run reliably on both platforms, while quadratic encodings exceed the Triangulum coherence budget but execute on Kingston.
Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time O(N)O(\sqrt{N})O(N​) with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where N=2nN=2^{n}N=2n , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is Ω(N)\Omega(N)Ω(N) .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in O(N)O(\sqrt{N})O(N​) time.
An approximate quantum state preparation method is introduced, called the Walsh series loader (WSL). The WSL approximates quantum states defined by real-value functions of single real variables with a depth independent of the number nnn of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at $O(1/\sqrt{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the precision of the approximation in terms of infidelity. The circuit depth is also $O(1/\sqrt{\ensuremath{\epsilon}})$, the size is $O(n+1/\sqrt{\ensuremath{\epsilon}})$, and only one ancilla qubit is needed. The second method accurately represents quantum states with sparse Walsh series. The WSL loads sss-sparse Walsh series into nnn qubits with a depth doubly sparse in sss and kkk, the maximum number of bits with value 1 in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh series up to an error $\ensuremath{\epsilon}$ with a depth O(sk)O(sk)O(sk), a size O(n+sk)O(n+sk)O(n+sk), and one ancilla qubit. In both cases, the protocol is a repeat-until-success procedure with a probability of success $P=\mathrm{\ensuremath{\Theta}}(\ensuremath{\epsilon})$, giving an averaged total time of $O(1/{\ensuremath{\epsilon}}^{3/2})$ for the WSL and $O(sk/\ensuremath{\epsilon})$ for the sparse WSL. Amplitude amplification can be used to reach a probability of success $P=\mathrm{\ensuremath{\Theta}}(1)$, modifying the quantum circuit size to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+1/\sqrt{\ensuremath{\epsilon}})/\sqrt{\ensuremath{\epsilon}})$ and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+sk)/\sqrt{\ensuremath{\epsilon}})$ and the depth to $O([log{(n)}^{3}+1/\sqrt{\ensuremath{\epsilon}}]/\sqrt{\ensuremath{\epsilon}})$ and $O([log{(n)}^{3}+sk]/\sqrt{\ensuremath{\epsilon}})$, respectively. Amplitude amplification reduces by a factor $O(1/\sqrt{\ensuremath{\epsilon}})$ the total time dependence on $\ensuremath{\epsilon}$ but increases the size and depth of the associated quantum circuits, making them linearly dependent on nnn. These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-value, multivariate, almost-everywhere-differentiable function. The repeat-until-success Walsh series loader is so far the only method that prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.
Quantum state preparation can shape how positive and negative contributions combine in correlation measurements, providing a route to control cancellation through ensemble engineering. We develop a framework for relating this control to the prepared distribution, using the infinite-temperature trace of the same operator product as a uniform-weight reference for ensemble-dependent correlators. For diagonal observables, resolving both projector sectors separates each sector's probability mass from its conditional sign alignment and determines their contributions to the full correlator. A worked example shows what a selected-sector description can miss, and a simple bound limits the error from omitting the complementary contribution. We use two complementary preparations: Grover-type amplitude amplification to redistribute probability toward a specified target, and oracle-free shallow circuits to shape the distribution at low depth. Zero-time benchmarks combine noiseless simulations with finite-shot sampling and IBM Quantum demonstrations on up to 20 qubits. Sector statistics distinguish low occupation from cancellation within an occupied sector, while comparisons with noiseless simulations show that characteristic features of the engineered cumulative patterns persist on hardware. We also extend the analysis to multi-qubit diagonal observables and connect their sign and sector rules to explicit preparation choices. These results provide a basis for designing and assessing structured ensembles through their operator-resolved contributions to quantum correlation measurements.