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

arXiv:2601.17930 · AIMS Mathematics

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

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

quant-phmath.NASubmitted Jan 25, 2026• Announced Jan 27, 2026• 2 citations• Revised May 22, 2026 (v2)
v1 · Jan 25, 2026v2 · May 22, 2026
arXivHTMLPDF

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}\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.

Related papers

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•1 citation

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

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

Hierarchical Fourier Approximation for Variational Quantum Distribution Learning

Taha Hoseinpour Asli, Sajjad Hashemian, Ebrahim Ardeshir-Larijani

We study variational quantum distribution learning through a hierarchy of Walsh--Fourier approximations on the Boolean cube. At each level, a selected set of target Fourier coefficients defines a spectral truncation, which is projected onto the probability simplex and used as the target of a quantum circuit Born machine. Parameters learned at one level initialize the next through a warm-start map. We prove an end-to-end expected learning guarantee where the approximation term is determined by the omitted Fourier mass, while a normalized unbiased estimator yields an explicit statistical bound for empirical truncations. We then instantiate the abstract discrepancy conditions for total variation distance and relate the resulting distributional error to quantum-state fidelity. The total-variation specialization incurs the explicit factor $2^{n-1}$ under our normalized $\ell_2$ convention and is therefore informative only for sufficiently concentrated Fourier tails. The framework does not establish global trainability or eliminate barren plateaus; rather, it identifies the conditions under which low-to-high spectral training admits a approximation--estimation--optimization analysis.

quant-pharXiv:2609.06307•Sep 8, 2026•0 citations

Efficient Gaussian State Preparation in Quantum Circuits

Yichen Xie, Nadav Ben-Ami

Gaussian states hold a fundamental place in quantum mechanics, quantum information, and quantum computing. Many subfields, including quantum simulation of continuousvariable systems, quantum chemistry, and quantum machine learning, rely on the ability to accurately and efficiently prepare states that reflect a Gaussian profile in their probability amplitudes. Although Gaussian states are natural in continuousvariable systems, the practical interest in digital, gate-based quantum computers demands discrete approximations of Gaussian distributions over a computational basis of size$2^{n}$. Because of the exponential scaling of naive amplitude-encoding approaches and the cost of certain block-encoding or Hamiltonian simulation techniques, a resource-efficient preparation of approximate Gaussian states is required. In this work, we propose and analyze a circuit-based approach that starts with singlequbit rotations to form an exponential amplitude profile and then applies the quantum Fourier transform to map those amplitudes into an approximate Gaussian distribution. We demonstrate that this procedure achieves high fidelity with the target Gaussian state while allowing optional pruning of small controlled-phase angles in the quantum Fourier transform, thus reducing gate complexity to near-linear in$\mathcal{O}(n)$. We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware and to pave the way for scalable implementations on future devices. The implementation of this algorithm is available at the Classiq library: https://github.com/classiq/classiq-library.

arXiv:2507.20317•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•7 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}\ket{k}∑k​pk​​∣k⟩ via a hierarchy of controlled \RY\RY\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(⋅),X,\CNOT}\{\RY(\cdot),X,\CNOT\}{\RY(⋅),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.
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.
We study variational quantum distribution learning through a hierarchy of Walsh--Fourier approximations on the Boolean cube. At each level, a selected set of target Fourier coefficients defines a spectral truncation, which is projected onto the probability simplex and used as the target of a quantum circuit Born machine. Parameters learned at one level initialize the next through a warm-start map. We prove an end-to-end expected learning guarantee where the approximation term is determined by the omitted Fourier mass, while a normalized unbiased estimator yields an explicit statistical bound for empirical truncations. We then instantiate the abstract discrepancy conditions for total variation distance and relate the resulting distributional error to quantum-state fidelity. The total-variation specialization incurs the explicit factor 2n−12^{n-1}2n−1 under our normalized ℓ2\ell_2ℓ2​ convention and is therefore informative only for sufficiently concentrated Fourier tails. The framework does not establish global trainability or eliminate barren plateaus; rather, it identifies the conditions under which low-to-high spectral training admits a approximation--estimation--optimization analysis.
Gaussian states hold a fundamental place in quantum mechanics, quantum information, and quantum computing. Many subfields, including quantum simulation of continuousvariable systems, quantum chemistry, and quantum machine learning, rely on the ability to accurately and efficiently prepare states that reflect a Gaussian profile in their probability amplitudes. Although Gaussian states are natural in continuousvariable systems, the practical interest in digital, gate-based quantum computers demands discrete approximations of Gaussian distributions over a computational basis of size2n2^{n}2n. Because of the exponential scaling of naive amplitude-encoding approaches and the cost of certain block-encoding or Hamiltonian simulation techniques, a resource-efficient preparation of approximate Gaussian states is required. In this work, we propose and analyze a circuit-based approach that starts with singlequbit rotations to form an exponential amplitude profile and then applies the quantum Fourier transform to map those amplitudes into an approximate Gaussian distribution. We demonstrate that this procedure achieves high fidelity with the target Gaussian state while allowing optional pruning of small controlled-phase angles in the quantum Fourier transform, thus reducing gate complexity to near-linear inO(n)\mathcal{O}(n)O(n). We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware and to pave the way for scalable implementations on future devices. The implementation of this algorithm is available at the Classiq library: https://github.com/classiq/classiq-library.