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.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.06535Feb 9, 20260 citations

ON THE DESIGN OF EFFICIENT QUANTUM ALGORITHMS

Tetsuro Nishino

May 1, 20010 citations

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$ . The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$ , where $s=α\|A^{-1}b\|$ . Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$ , we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$ . The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686Sep 29, 20260 citations

Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

Pei Yuan, Shengyu Zhang

As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of | i ⟩ | 0 n ⟩ → | i ⟩ | ψ i ⟩ for all i ∈ { 0 , 1 } k for the given n -qubit states | ψ i ⟩ . In this paper, we construct a quantum circuit for implementing CQSP, with depth O ( n + k + 2 n + k n + k + m ) and size O ( 2 n + k ) for any given number m of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters m , k ≥ 0 and n ≥ 1 . When k = 0 , the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation | 0 n ⟩ | 0 m ⟩ → | ψ ⟩ | 0 m ⟩ . This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to Θ ( n + 2 n / ( n + m ) ) and its size complexity to Θ ( 2 n ) for anyAs a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of | i ⟩ | 0 n ⟩ → | i ⟩ | ψ i ⟩ for all i ∈ { 0 , 1 } k for the given n -qubit states | ψ i ⟩ . In this paper, we construct a quantum circuit for implementing CQSP, with depth O ( n + k + 2 n + k n + k + m ) and size O ( 2 n + k ) for any given number m of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters m , k ≥ 0 and n ≥ 1 . When k = 0 , the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation | 0 n ⟩ | 0 m ⟩ → | ψ ⟩ | 0 m ⟩ . This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to Θ ( n + 2 n / ( n + m ) ) and its size complexity to Θ ( 2 n ) for any

arXiv:2202.11302QuantumMar 20, 202335 citations

Towards practical quantum optimization

András Czégel

Sep 18, 20260 citations

Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

Tongyang Li, Fengning Ou, Xinzhao Wang +3 more

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove that the optimal $\mathrm{T}$ count is $Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)$ . Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+ $\mathrm{T}$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $\mathrm{T}$ -count bounds $Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$ for $s$ -sparse state preparation and $Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)$ for block encoding of $s$ -sparse matrices, where $\varepsilon$ and $\varepsilon_{\rm BE}$ are the precision of state preparation and block encoding, respectively.Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove that the optimal $\mathrm{T}$ count is $Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$\mathrm{T}$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $\mathrm{T}$-count bounds $Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$ for $s$-sparse state preparation and $Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\rm BE}$ are the precision of state preparation and block encoding, respectively.

quant-pharXiv:2607.28260Jul 31, 20260 citations

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.

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle

U_A

and the right-hand side through a state-preparation oracle

U_b

. The optimal query complexities of these two oracles are known separately:

O(κ\log(1/\varepsilon))

queries to

U_A

and

O(κ/s)

queries to

U_b

, where

s=α\|A^{-1}b\|

. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of

s

, we give a quantum linear-system algorithm that prepares the normalized solution to error

\varepsilon

using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to

U_A

and

O\left(κ/{s}\right)

queries to

U_b

. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both

Ω(κ\log(1/\varepsilon))

matrix queries and

Ω(κ/s)

state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the

\mathrm{T}

count of sparse QROM, in which only

s

of the

2^n

addresses store nonzero data. We prove that the optimal

\mathrm{T}

count is

Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)

. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+

\mathrm{T}

circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching

\mathrm{T}

-count bounds

Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)

for

s

-sparse state preparation and

Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)

for block encoding of

s

-sparse matrices, where

\varepsilon

and

\varepsilon_{\rm BE}

are the precision of state preparation and block encoding, respectively.