REVIEW
Creating superpositions that correspond to efficiently integrable probability distributions
Quantum Physics · Submitted 15 Aug 2002 · 5 references
Pith's verdict: This is the paper that invented recursive state preparation, the circuit is correct, and the only real soft spot is the unqualified word 'efficient' in the abstract.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Grover and Rudolph show that any probability density a classical computer can integrate can be loaded, piece by piece, into a quantum superposition whose amplitudes are the square roots of the discretized probabilities.
The reading
What carries the argument
The load-bearing device is the conditional half-split: the function $f(i) = int_{x_i^L}^{(x_i^R - x_i^L)/2} p(x)dx / int_{x_i^L}^{x_i^R} p(x)dx$, the probability that $x$ lies in the left half of its region given that it lies in the region at all. Encoding $theta_i = arccos sqrt(f(i))$ in an ancilla and rotating a fresh qubit through it converts a classical integral ratio into a quantum amplitude ratio, and uncomputing the ancilla makes the step reversible and repeatable. The whole efficiency claim rests on this one primitive being cheap and coherent.
Extended reading notes
Core claim
The central claim is that the evolution $sqrt(p^{(m)}_i)|i> -> sqrt(alpha_i)|i>|0> + sqrt(beta_i)|i>|1>$ (equation 3) can be carried out efficiently, where $alpha_i$ and $beta_i$ are the probabilities of $x$ falling in the left and right halves of region $i$. The authors achieve it by computing, into an ancilla register, the angle $theta_i = arccos sqrt(f(i))$ where $f(i)$ is the ratio of the left-half integral of $p$ to the whole-region integral, applying a controlled rotation of that angle on a fresh qubit, and then uncomputing the ancilla. Because the integrals are assumed classically computable, the ratio is available; because the rotation is conditioned on it, the new qubit carries exactly the split the recursion needs. Iterating $n = log N$ times produces the full superposition, so state preparation reduces to a sequence of integral evaluations rather than to any special property of the distribution itself.
Load-bearing premise
The construction assumes the classical integration subroutine can be run reversibly and coherently to whatever precision each of the $log N$ recursion levels needs, and that the accumulated error stays controlled — a point the paper disposes of in a single sentence about pre-loading random bits into an ancilla, without stating a precision requirement or an error budget.
Editorial extensions
If this is right
- Any distribution whose cumulative integrals can be computed in polynomial time — log-concave families such as Gaussian and exponential among them — can be prepared as a quantum superposition in polynomially many gates, with $n = log N$ rounds of subdivision.
- Quantum search can be started from a non-uniform prior rather than a flat one, so that a guess about where the solution is likely to lie can be built into the initial amplitude distribution.
- A Hadamard transform on the prepared state yields the distribution $q_j = (1/N)(sum_i (-1)^{i dot j} sqrt(p_i))^2$, which need not be log-concave, giving a way to sample interference-generated distributions that have no classical sampling counterpart.
- Combined with efficient Fourier transforms and amplitude estimation, the prepared state supports estimating the magnitude of a chosen Fourier component with the quadratic speedup amplitude estimation provides.
Reading between the lines
- The paper's efficiency claim is really a claim about the cost of reversible arithmetic: the number of bits of precision needed in the ancilla grows with the recursion depth, and the authors never total that cost, so a careful reader should treat the polynomial bound as conditional on a resource count that is not carried out here.
- The construction suggests a clean separation worth testing: distributions that are classically integrable but not classically samplable cheaply would be exactly the ones where this state-preparation route buys something a classical sampler cannot, and that boundary is not mapped in the paper.
- Because the ancilla is uncomputed at every level, the method composes naturally with amplitude amplification, so one could in principle prepare a posterior-like state by iterating preparation and a filtering unitary, an extension the paper gestures at with its interference discussion but does not develop.
- The single sentence about running a probabilistic classical integrator coherently by pre-loading its random bits quietly assumes a fixed random seed; whether a fixed seed preserves the accuracy the recursion needs at every level is an open accounting question rather than a settled one.
Original abstract
We give a simple and efficient process for generating a quantum superposition of states which form a discrete approximation of any efficiently integrable (such as log concave) probability density functions.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
We give a simple and efficient process for generating a quantum superposition of states which form a discrete approximation of any efficiently integrable (such as log concave) probability density functions.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We give a simple and efficient process for generating a quantum superposition of states which form a discrete approximation of any efficiently integrable (such as log concave) probability density functions. | contribution 0.96 | 0.93 | 0.85 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
How later papers used it
155 later papers cite it
1 later paper by other authors is listed below: 1 used its method or tool.
Uses its method or tool 1 of 44 papers with this label
-
The circuit proposed as an ansatz, $U(θ)$, for our model is based on the Grover-Rudolph circuit [ref] .
Quantum algorithms for approximate function loading (2021) · Ansatz · 0.98
How the literature uses it
150 arXiv papers cite this in 238 sentences
Papers citing it · 141 sentences without a confident label
Contests it 1 paper
-
The Grover-Rudolph method of state preparation has frequently been cited as evidence of this equivalence [ref] , however in an earlier work we showed that, owing to the reliance on (classical) MCI in the Grover-Rudolph method, this represents a false economy [ref] .
A Modular Engine for Quantum Monte Carlo Integration · The problem with Grover-Rudolph state preparation · contest 0.87
Builds on it 2 papers
-
This can be done by the multivariate extension of the method of [ref] for univariate distributions.
Pricing multi-asset derivatives by finite difference method on a quantum computer · Generating the probability vector · 0.80
-
In addition to this, we here explain some details, which were not explicitely explained in [ref] .
Quantum Pricing with a Smile: Implementation of Local Volatility Model on Quantum Computer · implementation of the SN gate · 0.92
Uses its method or tool 41 papers
-
Thus, we can use the method [ref] to obtain an efficient circuit for the quantum update.
Efficient Circuits for Quantum Walks · Introduction · 0.99
-
As in the initialization procedure of Section III, we use the methods of [ref] to obtain the state $|χ_c⟩=1/√(A_c)∑_j=1^M∑_j=1^M_c x_c,j - μ_c |c⟩|j⟩| x_c,j - μ_c ⟩| x_c,j - μ_c ⟩$.
Quantum Discriminant Analysis for Dimensionality Reduction and Classification · Algorithm · 1.00
-
In particular, the preparation of this state is achieved by a parallelized quantum circuit at depth $O(Dlog(1/Δ))$ to run a quantum algorithm of [ref] , where the QRAM is queried at each time step, in total $O(Dlog(1/Δ))$ times [ref] .
Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning · A feasible implementation of the input model of the quantum algorithm in our setting · 0.98
Compares with it 1 paper
-
Our inequality-testing-based method is more practical than the Zalka-Grover-Rudolph method [ref] , i.e., the standard state-preparation method, and can be used broadly in the state-preparation subroutine of quantum-simulation algorithms.
Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory · Conclusions · 0.86
Cites it as support 1 paper
-
It is important to remark that, as found in Refs. [ref] , in order to describe a function with a fine grid we only need a logarithmically small number of qubits $n=O(log_2(1/Δx)).$ This advantage translates to the scaling of approximation errors in the overall method, as discussed in Sec. [ref].
Quantum Fourier analysis for multivariate functions and applications to a class of Schr\"odinger-type partial differential equations · Position space discretization · 0.96
Cites it as background 34 papers
-
A particularly influential and widely reused state-preparation procedure is due to Grover and Rudolph [ref] .
A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm · Introduction · 0.86
-
There exists a unitary $_p$ on $n_q + (1)$ qubits[The $(1)$ ancilla qubits are scratch space used internally by the oracle's circuit and returned to $|0⟩$ at the end of the computation; they do not appear in the output state.] with [equation] This is the standard access model in quantum distribution testing and Monte Carlo [ref] .
Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence · The oracle model · 0.87
-
Several approaches have already been presented in the literature for implementing the amplitude embedding, many requiring a huge (exponential) number of resources (ancillas and gates) [ref] , oracles [ref] , sparsity in the quantum state [ref] , training variational circuits [ref] , truncating a series expansion [ref] , use the quantum singular value transformation [ref] or matrix product states [ref] .
Efficient quantum amplitude encoding of polynomial functions · Introduction · 0.80
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.