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:2307.08384 · Physical Review A

Efficient quantum state preparation with Walsh series

Julien Zylberman, Fabrice Debbasch

Published Apr 1, 2024• 39 citations
arXivHTMLPDF

Abstract

An approximate quantum state preparation method is introduced, called the Walsh series loader (WSL). The WSL approximates quantum states defined by real-value functions of single real variables with a depth independent of the number $n$ of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at $O(1/\sqrt{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the precision of the approximation in terms of infidelity. The circuit depth is also $O(1/\sqrt{\ensuremath{\epsilon}})$, the size is $O(n+1/\sqrt{\ensuremath{\epsilon}})$, and only one ancilla qubit is needed. The second method accurately represents quantum states with sparse Walsh series. The WSL loads $s$-sparse Walsh series into $n$ qubits with a depth doubly sparse in $s$ and $k$, the maximum number of bits with value 1 in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh series up to an error $\ensuremath{\epsilon}$ with a depth $O(sk)$, a size $O(n+sk)$, and one ancilla qubit. In both cases, the protocol is a repeat-until-success procedure with a probability of success $P=\mathrm{\ensuremath{\Theta}}(\ensuremath{\epsilon})$, giving an averaged total time of $O(1/{\ensuremath{\epsilon}}^{3/2})$ for the WSL and $O(sk/\ensuremath{\epsilon})$ for the sparse WSL. Amplitude amplification can be used to reach a probability of success $P=\mathrm{\ensuremath{\Theta}}(1)$, modifying the quantum circuit size to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+1/\sqrt{\ensuremath{\epsilon}})/\sqrt{\ensuremath{\epsilon}})$ and $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+sk)/\sqrt{\ensuremath{\epsilon}})$ and the depth to $O([log{(n)}^{3}+1/\sqrt{\ensuremath{\epsilon}}]/\sqrt{\ensuremath{\epsilon}})$ and $O([log{(n)}^{3}+sk]/\sqrt{\ensuremath{\epsilon}})$, respectively. Amplitude amplification reduces by a factor $O(1/\sqrt{\ensuremath{\epsilon}})$ the total time dependence on $\ensuremath{\epsilon}$ but increases the size and depth of the associated quantum circuits, making them linearly dependent on $n$. These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-value, multivariate, almost-everywhere-differentiable function. The repeat-until-success Walsh series loader is so far the only method that prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.

DOI
10.1103/physreva.109.042401

Related papers

On the Correct Implementation of the Walsh Series Loader

Riccardo Pellini, Maurizio Ferrari Dacrema

Quantum state preparation is a preliminary step needed by quantum algorithms that require a specific input state. Exact state preparation methods scale exponentially with the number of qubits, making them impractical on noisy intermediate-scale quantum (NISQ) devices. Approximate approaches offer therefore more flexible and scalable alternatives. In this paper, we discuss the Walsh Series Loader (WSL), a recently proposed approximate algorithm for state preparation. In particular, we observe that the paper does not describe how to implement the term of order zero of the operator WSL is based on. While this does not affect the theoretical validity of WSL, it poses obstacles for practitioners aiming to use WSL because, as we show in our experiments, an incorrect implementation leads to states with very poor fidelity. In this paper, we describe how to implement the full quantum circuit required by WSL, including the term of order zero, releasing our source code online, and show that the algorithm works correctly. Finally, we empirically show how, as was theoretically demonstrated in the original article, truncated WSL does not prepare well highly entangled states.

arXiv:2502.05193•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 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•45 citations

Novel oracle constructions for quantum random access memory

Ákos Nagy, Cindy Zhang

We present new designs for quantum random access memory. More precisely, for each function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct oracles, $\mathcal{O}_f$, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of $f$, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of $f$, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be $ε$-approximated so that the Clifford + $T$ depth is $O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)$, where $\mathcal{W}_f$ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is $O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)$, using $n + d \mathcal{W}_f$ qubit. The connectivity of these circuits is also only logarithmic in $\mathcal{W}_f$. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as $2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}$.

arXiv:2405.20225•May 30, 2024•6 citations

Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Giacomo Belli, Michele Amoretti

The preparation of $n$-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when $m$ ancillary qubits are available. The reduction in complexity is due to the use of a single operator $Λ$ for each uniformly controlled gate, instead of the three in the original decomposition. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.

quant-pharXiv:2602.06535•Feb 9, 2026•1 citation

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 with Optimal Circuit Depth: Implementations and Applications

Xiao‐Ming Zhang, Tongyang Li, Xiao Yuan

Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.

arXiv:2201.11495•Physical Review Letters•Nov 30, 2022•255 citations
An approximate quantum state preparation method is introduced, called the Walsh series loader (WSL). The WSL approximates quantum states defined by real-value functions of single real variables with a depth independent of the number nnn of qubits. Two approaches are presented. The first one approximates the target quantum state by a Walsh series truncated at O(1/\ensuremathϵ)O(1/\sqrt{\ensuremath{\epsilon}})O(1/\ensuremathϵ​), where \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ is the precision of the approximation in terms of infidelity. The circuit depth is also O(1/\ensuremathϵ)O(1/\sqrt{\ensuremath{\epsilon}})O(1/\ensuremathϵ​), the size is O(n+1/\ensuremathϵ)O(n+1/\sqrt{\ensuremath{\epsilon}})O(n+1/\ensuremathϵ​), and only one ancilla qubit is needed. The second method accurately represents quantum states with sparse Walsh series. The WSL loads sss-sparse Walsh series into nnn qubits with a depth doubly sparse in sss and kkk, the maximum number of bits with value 1 in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh series up to an error \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ with a depth O(sk)O(sk)O(sk), a size O(n+sk)O(n+sk)O(n+sk), and one ancilla qubit. In both cases, the protocol is a repeat-until-success procedure with a probability of success P=\ensuremathΘ(\ensuremathϵ)P=\mathrm{\ensuremath{\Theta}}(\ensuremath{\epsilon})P=\ensuremathΘ(\ensuremathϵ), giving an averaged total time of O(1/\ensuremathϵ3/2)O(1/{\ensuremath{\epsilon}}^{3/2})O(1/\ensuremathϵ3/2) for the WSL and O(sk/\ensuremathϵ)O(sk/\ensuremath{\epsilon})O(sk/\ensuremathϵ) for the sparse WSL. Amplitude amplification can be used to reach a probability of success P=\ensuremathΘ(1)P=\mathrm{\ensuremath{\Theta}}(1)P=\ensuremathΘ(1), modifying the quantum circuit size to O\ifmmode~\else˜\fi((n+1/\ensuremathϵ)/\ensuremathϵ)\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+1/\sqrt{\ensuremath{\epsilon}})/\sqrt{\ensuremath{\epsilon}})O\ifmmode~\else˜\fi​((n+1/\ensuremathϵ​)/\ensuremathϵ​) and O\ifmmode~\else˜\fi((n+sk)/\ensuremathϵ)\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}((n+sk)/\sqrt{\ensuremath{\epsilon}})O\ifmmode~\else˜\fi​((n+sk)/\ensuremathϵ​) and the depth to O([log(n)3+1/\ensuremathϵ]/\ensuremathϵ)O([log{(n)}^{3}+1/\sqrt{\ensuremath{\epsilon}}]/\sqrt{\ensuremath{\epsilon}})O([log(n)3+1/\ensuremathϵ​]/\ensuremathϵ​) and O([log(n)3+sk]/\ensuremathϵ)O([log{(n)}^{3}+sk]/\sqrt{\ensuremath{\epsilon}})O([log(n)3+sk]/\ensuremathϵ​), respectively. Amplitude amplification reduces by a factor O(1/\ensuremathϵ)O(1/\sqrt{\ensuremath{\epsilon}})O(1/\ensuremathϵ​) the total time dependence on \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ but increases the size and depth of the associated quantum circuits, making them linearly dependent on nnn. These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-value, multivariate, almost-everywhere-differentiable function. The repeat-until-success Walsh series loader is so far the only method that prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.
Quantum state preparation is a preliminary step needed by quantum algorithms that require a specific input state. Exact state preparation methods scale exponentially with the number of qubits, making them impractical on noisy intermediate-scale quantum (NISQ) devices. Approximate approaches offer therefore more flexible and scalable alternatives. In this paper, we discuss the Walsh Series Loader (WSL), a recently proposed approximate algorithm for state preparation. In particular, we observe that the paper does not describe how to implement the term of order zero of the operator WSL is based on. While this does not affect the theoretical validity of WSL, it poses obstacles for practitioners aiming to use WSL because, as we show in our experiments, an incorrect implementation leads to states with very poor fidelity. In this paper, we describe how to implement the full quantum circuit required by WSL, including the term of order zero, releasing our source code online, and show that the algorithm works correctly. Finally, we empirically show how, as was theoretically demonstrated in the original article, truncated WSL does not prepare well highly entangled states.
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.
We present new designs for quantum random access memory. More precisely, for each function, f:F2n→F2df : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^df:F2n​→F2d​, we construct oracles, Of\mathcal{O}_fOf​, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of fff, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of fff, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be εεε-approximated so that the Clifford + TTT depth is O((n+log⁡2(dε))Wf)O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)O((n+log2​(εd​))Wf​), where Wf\mathcal{W}_fWf​ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is O(n+log⁡2(dε))O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)O(n+log2​(εd​)), using n+dWfn + d \mathcal{W}_fn+dWf​ qubit. The connectivity of these circuits is also only logarithmic in Wf\mathcal{W}_fWf​. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as 2O~(nlog⁡2(n))2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}2O(n​log2​(n)).
The preparation of nnn-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when mmm ancillary qubits are available. The reduction in complexity is due to the use of a single operator ΛΛΛ for each uniformly controlled gate, instead of the three in the original decomposition. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.
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.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.