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: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

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 1 citation
arXivHTMLPDF

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.

Little sign of AI-generated textMissing comparison

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

Related papers

Hermitian Matrix Function Synthesis without Block-Encoding

Anuradha Mahasinghe, Kaushika De Silva, Xavier Cadet +3 more

Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.

quant-pharXiv:2512.18249•Dec 23, 2025•2 citations

Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits

Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin +1 more

We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|ψ\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle$ for all $j\in\{1,\dots,m\}$. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of $f(H)$. It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with $H$ and $|ψ\rangle$ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from $H$, $f$, and $|ψ\rangle$ without prior knowledge of the observables or explicit preparation of the target state proportional to $f(H)|ψ\rangle$. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.

quant-pharXiv:2609.40167•Oct 1, 2026•0 citations

Randomized Quantum Singular Value Transformation

Xinzhao Wang, Yuxin Zhang, Hazra, Soumyabrata +3 more

We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.

arXiv:2510.06851•Oct 8, 2025•13 citations

Logarithmic-depth quantum state preparation of polynomials

Baptiste Claudon, Alexis Lucas, Jean-Philip Piquemal +2 more

Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree$-d$ polynomial, using circuits with logarithmic depth in the number $n$ of qubits and only $\mathcal O(n)$ ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only $n$ terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state $|1\rangle$. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using $14$ qubits and more than $500$ primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.

quant-pharXiv:2603.16527•Mar 18, 2026•4 citations

Quantum State Preparation without Coherent Arithmetic

Sam McArdle, András Gilyén, Mario Berta

We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function. Unlike existing approaches, our method does not require handcrafted reversible arithmetic circuits, or quantum table reads, to encode the function values. Instead, we use a template quantum eigenvalue transformation circuit to convert a low-cost block encoding of the sine function into the desired function. Our method uses only four ancilla qubits (three if the approximating polynomial has definite parity), providing order-of-magnitude qubit count reductions compared to state-of-the-art approaches, while using a similar number of gates if the function can be well represented by a polynomial or Fourier approximation. We demonstrate the algorithmic utility of our method, including preparing Gaussian and Kaiser window states.

arXiv:2210.14892•Physical Review Letters•Jun 18, 2026•105 citations

Quantum Circuit for General Unitary: Improved T-count via Block Flattening and Dilation

Pei Yuan, Shengyu Zhang, Wei Zi

Synthesizing arbitrary $n$-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+$T$ quantum circuit construction that approximately implements any classically specified unitary to within error $ε$ and achieves a worst-case $T$-count with leading exponential scaling of $2^{5n/4}$ whenever $\log(1/ε)=\operatorname{poly}(n)$. This improves upon the best previous $2^{4n/3}$ scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.

quant-pharXiv:2608.17846•Aug 19, 2026•2 citations
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 nnn qubits, constructing and storing the alias table requires both classical and quantum resources exponential in nnn. We show that when the amplitudes are samples of a polynomial of degree at most ddd, the table can be represented and evaluated coherently with cost polynomial in nnn, ddd, exponentially reduced from Θ(2n)Θ(2^n)Θ(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+TTT with a complete gate count of O~(ndB+B2)\tilde{O}(ndB+B^2)O~(ndB+B2), where arithmetic width B=O~(dn+dlog⁡(d+1))B=\tilde{O}(dn+d\log(d+1))B=O~(dn+dlog(d+1)). In the high precision limit for state fidelity εεε with fixed nnn and ddd, it is sufficient have B=Θ(log⁡(1/ε))B=Θ(\log(1/ε))B=Θ(log(1/ε)) and the complete gate count becomes O(log⁡3(1/ε)log⁡log⁡(1/ε))O(\log^3(1/ε)\log\log(1/ε))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.
The paper asks whether coherent alias sampling can prepare clean polynomial-amplitude states without constructing an exponentially large alias table. The target is an nnn-qubit state with amplitudes proportional to samples of a real degree-ddd polynomial on a 2n2^n2n-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)O(d)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(β+dn+dlog⁡(d+1))B=O(\beta+dn+d\log(d+1))B=O(β+dn+dlog(d+1)). The representation occupies O(d(n+B))O(d(n+B))O(d(n+B)) bits, has polynomial-time classical preprocessing, and supports coherent entry evaluation in O~(ndB)\tilde O(ndB)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+TTT preparation costs O~(ndB+B2)\tilde O(ndB+B^2)O~(ndB+B2) at inverse-polynomial accuracy in BBB, with joint output error bounded by ϵ\epsilonϵ. For fixed grid and degree, refining coefficients gives O(log⁡3(1/ϵ)log⁡log⁡(1/ϵ))O(\log^3(1/\epsilon)\log\log(1/\epsilon))O(log3(1/ϵ)loglog(1/ϵ)) 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.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state ∣ψ⟩|ψ\rangle∣ψ⟩, a Hermitian matrix HHH, a polynomial fff, and a set of observables {O1,…,Om}\{O_1,\dots,O_m\}{O1​,…,Om​}, the goal is to estimate ⟨ψ∣f(H)†Ojf(H)∣ψ⟩\langleψ|f(H)^{\dagger}O_j f(H)|ψ\rangle⟨ψ∣f(H)†Oj​f(H)∣ψ⟩ for all j∈{1,…,m}j\in\{1,\dots,m\}j∈{1,…,m}. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of f(H)f(H)f(H). It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with HHH and ∣ψ⟩|ψ\rangle∣ψ⟩ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from HHH, fff, and ∣ψ⟩|ψ\rangle∣ψ⟩ without prior knowledge of the observables or explicit preparation of the target state proportional to f(H)∣ψ⟩f(H)|ψ\ranglef(H)∣ψ⟩. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.
We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d-d−d polynomial, using circuits with logarithmic depth in the number nnn of qubits and only O(n)\mathcal O(n)O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only nnn terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩|1\rangle∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 141414 qubits and more than 500500500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.
We introduce a versatile method for preparing a quantum state whose amplitudes are given by some known function. Unlike existing approaches, our method does not require handcrafted reversible arithmetic circuits, or quantum table reads, to encode the function values. Instead, we use a template quantum eigenvalue transformation circuit to convert a low-cost block encoding of the sine function into the desired function. Our method uses only four ancilla qubits (three if the approximating polynomial has definite parity), providing order-of-magnitude qubit count reductions compared to state-of-the-art approaches, while using a similar number of gates if the function can be well represented by a polynomial or Fourier approximation. We demonstrate the algorithmic utility of our method, including preparing Gaussian and Kaiser window states.
Synthesizing arbitrary nnn-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+TTT quantum circuit construction that approximately implements any classically specified unitary to within error εεε and achieves a worst-case TTT-count with leading exponential scaling of 25n/42^{5n/4}25n/4 whenever log⁡(1/ε)=poly⁡(n)\log(1/ε)=\operatorname{poly}(n)log(1/ε)=poly(n). This improves upon the best previous 24n/32^{4n/3}24n/3 scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.