arXiv:2610.03800
Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation
Diyi Liu, Hanyu Wang, Shuchen Zhu, Jason Cong, Wibe Albert de Jong, David Williams-Young, Chao Yang
Abstract
Coherent alias sampling implement an important subroutine for block encoding and qubitization based quantum simulation using quantum lookup table. Related constructions exploit data lookup and matrix structure to implement block encodings for use in quantum singular value transformation. For a state on $n$ qubits, constructing and storing the alias table requires both classical and quantum resources exponential in $n$. We show that when the amplitudes are samples of a polynomial of degree at most $d$, the table can be represented and evaluated coherently with cost polynomial in $n$, $d$, exponentially reduced from $Θ(2^n)$ classical and quantum cost. We construct a quantum circuit for coherently computing the alias table for polynomial states using reversible integer arithmetic. By employing fast arithmetic, we construct a deterministic circuit for preparing polynomial states over Clifford+$T$ with a complete gate count of $\tilde{O}(ndB+B^2)$, where arithmetic width $B=\tilde{O}(dn+d\log(d+1))$. In the high precision limit for state fidelity $ε$ with fixed $n$ and $d$, it is sufficient have $B=Θ(\log(1/ε))$ and the complete gate count becomes $O(\log^3(1/ε)\log\log(1/ε))$. Additionally, the effective representation of the alias table can also be used for classical sampling algorithms. Furthermore, we develop a novel technique for uncomputing the auxilary register generated by coherent alias sampling. This technique opens a research direction in sampling based initial state preparation.
AI Summary
The paper asks whether coherent alias sampling can prepare clean polynomial-amplitude states without constructing an exponentially large alias table. The target is an $n$-qubit state with amplitudes proportional to samples of a real degree-$d$ polynomial on a $2^n$-point uniform grid. Standard coherent alias sampling retains an entangled sampling record; discarding it produces a diagonal mixture rather than the desired pure state. An ordered alias table is represented through cumulative deficits and surpluses relative to uniform probability. Polynomial structure limits the light/heavy classification to $O(d)$ contiguous groups, while finite-difference formulas evaluate cumulative squared amplitudes exactly. Classical root isolation determines group boundaries. For integer coefficient bit length $\beta$, sufficient arithmetic width is $B=O(\beta+dn+d\log(d+1))$. The representation occupies $O(d(n+B))$ bits, has polynomial-time classical preprocessing, and supports coherent entry evaluation in $\tilde O(ndB)$ gates. To remove garbage, reversible ranking maps each sampling fiber to consecutive integers. Inverse ranking clears the source registers, and output-controlled inverse uniform-state preparation clears the rank. Including angle arithmetic and rotation synthesis, deterministic Clifford+$T$ preparation costs $\tilde O(ndB+B^2)$ at inverse-polynomial accuracy in $B$, with joint output error bounded by $\epsilon$. For fixed grid and degree, refining coefficients gives $O(\log^3(1/\epsilon)\log\log(1/\epsilon))$ gates. The exponential reduction is relative to explicit alias tables, not other polynomial-state preparation methods or classical sampling. No advantage over cumulative inversion or direct conditional rotations is established. Arithmetic constants may be large, and finite-precision cleanup is approximate.
Error found: The abstract's arithmetic-width bound omits the coefficient bit length beta, although the exact construction requires B=O(beta+dn+d log(d+1)). The abstract's complete gate count tilde-O(ndB+B²) needs an accuracy qualification: the body establishes this simplification for inverse-polynomial accuracy in B, while its general bound retains explicit dependence on log(1/epsilon).
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 33 pages, 6 figures