Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation
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 Θ(2n) 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 Õ(ndB+B2), where arithmetic width B=Õ(dn+dlog(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(log3(1/ε)loglog(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.
Related
- Random Garbage Separates XOR from Forward-Only Queries
- Exponentially long evaporation of noncommutative black hole
- Chiral quantum chaos around exponentially many zero modes in the quantum breakdown model
- Avoiding Exponentially Large Groups with Open Quantum System Technology
- A quantum double-bracket algorithm for imaginary-time evolution with exponentially shorter depth
BibTeX
@misc{liu2026exponentially,
title = {{Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation}},
author = {Diyi Liu and Hanyu Wang and Shuchen Zhu and Jason Cong and Wibe Albert de Jong and David Williams-Young and Chao Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03800},
eprint = {2610.03800},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03800},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation
AU - Diyi Liu
AU - Hanyu Wang
AU - Shuchen Zhu
AU - Jason Cong
AU - Wibe Albert de Jong
AU - David Williams-Young
AU - Chao Yang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.03800
UR - https://arxiv.org/abs/2610.03800
AB - 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 Õ(ndB+B^2), where arithmetic width B=Õ(dn+dlog(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/ε)loglog(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.
ER -