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:2303.02131 · Quantum

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

Kaiwen Gui, Alexander M. Dalzell, Alessandro Achille, Martin Suchara, Frederic T. Chong

Published Feb 15, 2024• 35 citations
arXivHTMLPDF

Abstract

We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an N -dimensional state in depth O(log⁡(N)) and spacetime allocation (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) O(N) , which are both optimal. When compiled into the {H,S,T,CNOT} gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error ϵ with optimal depth of O(log⁡(N)+log⁡(1/ϵ)) and spacetime allocation O(Nlog⁡(log⁡(N)/ϵ)) , improving over O(log⁡(N)log⁡(log⁡(N)/ϵ)) and O(Nlog⁡(N/ϵ)) , respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead – O(N) ancilla qubits are reused efficiently to prepare a product state of w N -dimensional states in depth O(w+log⁡(N)) rather than O(wlog⁡(N)) , achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.

DOI
10.22331/q-2024-02-15-1257

Related papers

Low-depth measurement-based deterministic quantum state preparation

Roselyn Nmaju, F. C. Speirits, Sarah Croke

We present a low-depth amplitude encoding method for arbitrary quantum state preparation. Building on the foundation of an existing divide-and-conquer algorithm, we propose a method to disentangle the ancilla qubits from the final state. Our method is measurement-based but deterministic, and offers an alternative approach to existing state preparation algorithms. It has circuit depth $Θ(n^2)$ and requires $Θ(2^n)$ ancilla qubits. The resulting spacetime allocation is $Θ(2^n)$, which is optimal. Furthermore, we go beyond scaling arguments to precisely quantify the resources needed for any $n$. We illustrate our method through detailed worked examples of both a ``dense'' state and a W-state. Finally, we demonstrate how to combine this method with existing methods to construct hybrid algorithms with varying space and circuit depth complexities.

arXiv:2510.08267•Oct 9, 2025•3 citations

Polylogarithmic-depth controlled-NOT gates without ancilla qubits

Baptiste Claudon, Julien Zylberman, César Feniou +3 more

Abstract Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(X) circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. Three distinct decompositions are presented: an exact one using one borrowed ancilla with a circuit depth $$\Theta (\log {(n)}^{3})$$ Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth $${{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))$$ O ( log ( n ) 3 log ( 1 / ϵ ) ) and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as $${{{{{{{\mathcal{O}}}}}}}}(\log {(n/\lfloor m/2\rfloor )}^{3}+\log (\lfloor m/2\rfloor ))$$ O ( log ( n / ⌊ m / 2 ⌋ ) 3 + log ( ⌊ m / 2 ⌋ ) ) . The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.

arXiv:2312.13206•Nature Communications•Jul 13, 2024•30 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

Trading T gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low, Vadym Kliuchnikov, Luke Schaeffer

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ⁡ ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ⁡ ( log ⁡ N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log ⁡ N ϵ log ⁡ log ⁡ N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.

arXiv:1812.00954•Quantum•Jun 17, 2024•157 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 with optimal T-count

David Gosset, Robin Kothari, Kewen Wu

How many T gates are needed to approximate an arbitrary n -qubit quantum state to within error ε ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ ( 2 n log ⁡ ( 1 / ε ) + log ⁡ ( 1 / ε ) ) if we allow ancilla qubits. We also show that this is the optimal T -count for implementing an arbitrary diagonal n -qubit unitary to within error ε . We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.

arXiv:2411.04790•Quantum•Jul 22, 2026•29 citations
We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an N -dimensional state in depth O(log⁡(N)) and spacetime allocation (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) O(N) , which are both optimal. When compiled into the {H,S,T,CNOT} gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error ϵ with optimal depth of O(log⁡(N)+log⁡(1/ϵ)) and spacetime allocation O(Nlog⁡(log⁡(N)/ϵ)) , improving over O(log⁡(N)log⁡(log⁡(N)/ϵ)) and O(Nlog⁡(N/ϵ)) , respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead – O(N) ancilla qubits are reused efficiently to prepare a product state of w N -dimensional states in depth O(w+log⁡(N)) rather than O(wlog⁡(N)) , achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.
We present a low-depth amplitude encoding method for arbitrary quantum state preparation. Building on the foundation of an existing divide-and-conquer algorithm, we propose a method to disentangle the ancilla qubits from the final state. Our method is measurement-based but deterministic, and offers an alternative approach to existing state preparation algorithms. It has circuit depth Θ(n2)Θ(n^2)Θ(n2) and requires Θ(2n)Θ(2^n)Θ(2n) ancilla qubits. The resulting spacetime allocation is Θ(2n)Θ(2^n)Θ(2n), which is optimal. Furthermore, we go beyond scaling arguments to precisely quantify the resources needed for any nnn. We illustrate our method through detailed worked examples of both a ``dense'' state and a W-state. Finally, we demonstrate how to combine this method with existing methods to construct hybrid algorithms with varying space and circuit depth complexities.
Abstract Controlled operations are fundamental building blocks of quantum algorithms. Decomposing n-control-NOT gates (Cn(X)) into arbitrary single-qubit and CNOT gates, is a crucial but non-trivial task. This study introduces Cn(X) circuits outperforming previous methods in the asymptotic and non-asymptotic regimes. Three distinct decompositions are presented: an exact one using one borrowed ancilla with a circuit depth Θ(log⁡(n)3)\Theta (\log {(n)}^{3})Θ(log(n)3) Θ ( log ( n ) 3 ) , an approximating one without ancilla qubits with a circuit depth O(log⁡(n)3log⁡(1/ϵ)){{{{{{{\mathcal{O}}}}}}}}(\log {(n)}^{3}\log (1/\epsilon ))O(log(n)3log(1/ϵ)) O ( log ( n ) 3 log ( 1 / ϵ ) ) and an exact one with an adjustable-depth circuit which decreases with the number m≤n of ancilla qubits available as O(log⁡(n/⌊m/2⌋)3+log⁡(⌊m/2⌋)){{{{{{{\mathcal{O}}}}}}}}(\log {(n/\lfloor m/2\rfloor )}^{3}+\log (\lfloor m/2\rfloor ))O(log(n/⌊m/2⌋)3+log(⌊m/2⌋)) O ( log ( n / ⌊ m / 2 ⌋ ) 3 + log ( ⌊ m / 2 ⌋ ) ) . The resulting exponential speedup is likely to have a substantial impact on fault-tolerant quantum computing by improving the complexities of countless quantum algorithms with applications ranging from quantum chemistry to physics, finance and quantum machine learning.
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.
Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ⁡ ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ⁡ ( log ⁡ N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log ⁡ N ϵ log ⁡ log ⁡ N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.
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.
How many T gates are needed to approximate an arbitrary n -qubit quantum state to within error ε ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ ( 2 n log ⁡ ( 1 / ε ) + log ⁡ ( 1 / ε ) ) if we allow ancilla qubits. We also show that this is the optimal T -count for implementing an arbitrary diagonal n -qubit unitary to within error ε . We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.