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

Quantum sampling algorithms for quantum state preparation and matrix block-encoding

Jessica Lemieux, Matteo Lostaglio, Sam Pallister, William Pol, Seetharam, Karthik, Sukin Sim, Şahinoğlu, Burak

Published May 19, 2024• 0 citations
arXivHTMLPDF

Abstract

The problems of quantum state preparation and matrix block-encoding are ubiquitous in quantum computing: they are crucial parts of various quantum algorithms for the purpose for initial state preparation as well as loading problem relevant data. We first present an algorithm based on QRS that prepares a quantum state $|ψ_f\rangle \propto \sum^N_{x=1} f(x)|x\rangle$. When combined with efficient reference states the algorithm reduces the cost of quantum state preparation substantially, if certain criteria on $f$ are met. When the preparation of the reference state is not the dominant cost, and the function $f$ and relevant properties are efficiently computable or provided otherwise with cost $o(N)$, the QRS-based method outperforms the generic state preparation algorithm, which has cost $O(N)$. We demonstrate the detailed performance (in terms of the number of Toffoli gates) of the QRS-based algorithm for quantum states commonly appearing in quantum applications, e.g., those with coefficients that obey power law decay, Gaussian, and hyperbolic tangent, and compare it with other methods. Then, we adapt QRS techniques to the matrix block-encoding problem and introduce a QRS-based algorithm for block-encoding a given matrix $A = \sum_{ij} A_{ij} |i\rangle \langle j|$. We work out rescaling factors for different access models, which encode how the information about the matrix is provided to the quantum computer. We exemplify these results for a particular Toeplitz matrix with elements $A_{\mathbf{ij}}= 1/\|{\mathbf{i}}-{\mathbf{j}}\|^2$, which appears in quantum chemistry, and PDE applications, e.g., when the Coulomb interaction is involved. Our work unifies, and in certain ways goes beyond, various quantum state preparation and matrix block-encoding methods in the literature, and gives detailed performance analysis of important examples that appear in quantum applications.

DOI
10.48550/arxiv.2405.11436

Related papers

Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

Samson Wang, Sam McArdle, Mario Berta

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For $N\times N$ Hermitian matrices, the space cost is $\log(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.

arXiv:2302.01873•Feb 3, 2023•1 citation

Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra

Samson Wang, Sam McArdle, Mario Berta

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N × N Hermitian matrices, the space cost is log  ( N ) + 1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O ( N 2 ) , when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems. Published by the American Physical Society 2024

PRX Quantum•Apr 30, 2024•20 citations

Fast Black-Box Quantum State Preparation

Johannes Bausch

Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage.In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in O(N) rounds of amplitude amplification, up to only O(1) many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ( log2⁡g vs g+2 in the bit precision g ), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ( g+log2⁡g ) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.

arXiv:2009.10709•Quantum•Aug 4, 2022•27 citations

Efficient Gaussian State Preparation in Quantum Circuits

Yichen Xie, Nadav Ben-Ami

Gaussian states hold a fundamental place in quantum mechanics, quantum information, and quantum computing. Many subfields, including quantum simulation of continuousvariable systems, quantum chemistry, and quantum machine learning, rely on the ability to accurately and efficiently prepare states that reflect a Gaussian profile in their probability amplitudes. Although Gaussian states are natural in continuousvariable systems, the practical interest in digital, gate-based quantum computers demands discrete approximations of Gaussian distributions over a computational basis of size$2^{n}$. Because of the exponential scaling of naive amplitude-encoding approaches and the cost of certain block-encoding or Hamiltonian simulation techniques, a resource-efficient preparation of approximate Gaussian states is required. In this work, we propose and analyze a circuit-based approach that starts with singlequbit rotations to form an exponential amplitude profile and then applies the quantum Fourier transform to map those amplitudes into an approximate Gaussian distribution. We demonstrate that this procedure achieves high fidelity with the target Gaussian state while allowing optional pruning of small controlled-phase angles in the quantum Fourier transform, thus reducing gate complexity to near-linear in$\mathcal{O}(n)$. We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware and to pave the way for scalable implementations on future devices. The implementation of this algorithm is available at the Classiq library: https://github.com/classiq/classiq-library.

arXiv:2507.20317•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•3 citations

Quantum element-wise transforms

Zane M. Rossi, Rahul Sarkar

Quantum algorithms for basic numerical linear algebraic tasks have proven essential for translating diverse problems to a unified quantum computational context. Many of these tasks---e.g., applying a function to the spectrum of a matrix embedded in a unitary process (a so-called block encoding), or taking linear combinations of block encodings---are well-addressed by techniques like quantum singular value transformation or linear combination of unitaries. However, there exist useful matrix transforms whose realization is unclear or inefficient. In this work we construct improved quantum algorithms for some of these transforms, the simplest of which is a polynomial function applied element-wise. We show the space required to compute quantum element-wise transforms (QEWTs) can be reduced exponentially in the degree of the applied function compared to prior work, and rectify errors in previous constructions. We prove novel space and query lower bounds for QEWTs, construct useful function families nearly saturating these bounds, and establish the hardness of QEWT dequantization. This represents the first sound theoretical treatment of QEWTs, and brings their resource requirements on par with other practical block encoding techniques. We present our algorithms alongside concrete applications to machine learning inference and signal processing.

quant-pharXiv:2606.06456•Jun 5, 2026•0 citations

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

Diyi Liu, Hanyu Wang, Shuchen Zhu +4 more

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.

quant-pharXiv:2610.03800•Oct 2, 2026•0 citations
The problems of quantum state preparation and matrix block-encoding are ubiquitous in quantum computing: they are crucial parts of various quantum algorithms for the purpose for initial state preparation as well as loading problem relevant data. We first present an algorithm based on QRS that prepares a quantum state ∣ψf⟩∝∑x=1Nf(x)∣x⟩|ψ_f\rangle \propto \sum^N_{x=1} f(x)|x\rangle∣ψf​⟩∝∑x=1N​f(x)∣x⟩. When combined with efficient reference states the algorithm reduces the cost of quantum state preparation substantially, if certain criteria on fff are met. When the preparation of the reference state is not the dominant cost, and the function fff and relevant properties are efficiently computable or provided otherwise with cost o(N)o(N)o(N), the QRS-based method outperforms the generic state preparation algorithm, which has cost O(N)O(N)O(N). We demonstrate the detailed performance (in terms of the number of Toffoli gates) of the QRS-based algorithm for quantum states commonly appearing in quantum applications, e.g., those with coefficients that obey power law decay, Gaussian, and hyperbolic tangent, and compare it with other methods. Then, we adapt QRS techniques to the matrix block-encoding problem and introduce a QRS-based algorithm for block-encoding a given matrix A=∑ijAij∣i⟩⟨j∣A = \sum_{ij} A_{ij} |i\rangle \langle j|A=∑ij​Aij​∣i⟩⟨j∣. We work out rescaling factors for different access models, which encode how the information about the matrix is provided to the quantum computer. We exemplify these results for a particular Toeplitz matrix with elements Aij=1/∥i−j∥2A_{\mathbf{ij}}= 1/\|{\mathbf{i}}-{\mathbf{j}}\|^2Aij​=1/∥i−j∥2, which appears in quantum chemistry, and PDE applications, e.g., when the Coulomb interaction is involved. Our work unifies, and in certain ways goes beyond, various quantum state preparation and matrix block-encoding methods in the literature, and gives detailed performance analysis of important examples that appear in quantum applications.
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N×NN\times NN×N Hermitian matrices, the space cost is log⁡(N)+1\log(N)+1log(N)+1 qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O(N2)O(N^2)O(N2), when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N × N Hermitian matrices, the space cost is log  ( N ) + 1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O ( N 2 ) , when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems. Published by the American Physical Society 2024
Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage.In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in O(N) rounds of amplitude amplification, up to only O(1) many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ( log2⁡g vs g+2 in the bit precision g ), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ( g+log2⁡g ) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.
Gaussian states hold a fundamental place in quantum mechanics, quantum information, and quantum computing. Many subfields, including quantum simulation of continuousvariable systems, quantum chemistry, and quantum machine learning, rely on the ability to accurately and efficiently prepare states that reflect a Gaussian profile in their probability amplitudes. Although Gaussian states are natural in continuousvariable systems, the practical interest in digital, gate-based quantum computers demands discrete approximations of Gaussian distributions over a computational basis of size2n2^{n}2n. Because of the exponential scaling of naive amplitude-encoding approaches and the cost of certain block-encoding or Hamiltonian simulation techniques, a resource-efficient preparation of approximate Gaussian states is required. In this work, we propose and analyze a circuit-based approach that starts with singlequbit rotations to form an exponential amplitude profile and then applies the quantum Fourier transform to map those amplitudes into an approximate Gaussian distribution. We demonstrate that this procedure achieves high fidelity with the target Gaussian state while allowing optional pruning of small controlled-phase angles in the quantum Fourier transform, thus reducing gate complexity to near-linear inO(n)\mathcal{O}(n)O(n). We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware and to pave the way for scalable implementations on future devices. The implementation of this algorithm is available at the Classiq library: https://github.com/classiq/classiq-library.
Quantum algorithms for basic numerical linear algebraic tasks have proven essential for translating diverse problems to a unified quantum computational context. Many of these tasks---e.g., applying a function to the spectrum of a matrix embedded in a unitary process (a so-called block encoding), or taking linear combinations of block encodings---are well-addressed by techniques like quantum singular value transformation or linear combination of unitaries. However, there exist useful matrix transforms whose realization is unclear or inefficient. In this work we construct improved quantum algorithms for some of these transforms, the simplest of which is a polynomial function applied element-wise. We show the space required to compute quantum element-wise transforms (QEWTs) can be reduced exponentially in the degree of the applied function compared to prior work, and rectify errors in previous constructions. We prove novel space and query lower bounds for QEWTs, construct useful function families nearly saturating these bounds, and establish the hardness of QEWT dequantization. This represents the first sound theoretical treatment of QEWTs, and brings their resource requirements on par with other practical block encoding techniques. We present our algorithms alongside concrete applications to machine learning inference and signal processing.
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.