Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation

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+d (d+1)). In the high precision limit for state fidelity ε with fixed n and d, it is sufficient have B=Θ((1/ε)) and the complete gate count becomes O(3(1/ε) (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.