Efficient Quantum Circuits for Non-Unitary and Unitary Diagonal Operators with Space-Time-Accuracy trade-offs

Julien Zylberman

Sorbonne Université, Observatoire de Paris, Université PSL, CNRS, LERMA, 75005 Paris, France

Ugo Nzongani

CNRS, LIS, Aix-Marseille Université, Université de Toulon, Marseille, France
Unité de Mathématiques Appliquées, ENSTA Paris, Institut Polytechnique de Paris, 91120 Palaiseau, France

Andrea Simonetto
Unité de Mathématiques Appliquées, ENSTA Paris, Institut Polytechnique de Paris, 91120 Palaiseau, France

Fabrice Debbasch
Sorbonne Université, Observatoire de Paris, Université PSL, CNRS, LERMA, 75005 Paris, France

Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms with applications in the resolution of partial differential equations, Hamiltonian simulations, the loading of classical data on quantum computers (quantum state preparation) and many others. In this paper, we introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits. The depth, i.e., the number of layers of quantum gates of the quantum circuit, is reducible with respect either to the width, i.e., the number of ancilla qubits, or to the accuracy between the implemented operator and the target one. While exact methods have an optimal exponential scaling either in terms of size, i.e., the total number of primitive quantum gates, or width, approximate methods prove to be efficient for the class of diagonal operators depending on smooth, at least differentiable, functions. Our approach is general enough to allow any method for diagonal operators to become adjustable-depth or approximate, decreasing the depth of the circuit by increasing its width or its approximation level. This feature offers flexibility and can match with the hardware limitations in coherence time or cumulative gate error. We illustrate these methods by performing quantum state preparation and non-unitary-real-space simulation of the diffusion equation: an initial Gaussian function is prepared on a set of qubits before being evolved through the non-unitary evolution operator of the diffusion process.

§ INTRODUCTION

Gate-based quantum computing leverages the principles of quantum mechanics to perform computations that would be prohibitively challenging on classical computers. The advantage of quantum algorithms lies in the possible decomposition of $n$-qubit operations into a reasonable number of hardware feasible single- and two-qubit operations. In this context, the development of new decompositions which improve on the current ones or widen the range of operations efficiently implementable on quantum computers, to include, e.g, non-unitary operations, is crucial to achieve novel applications and to lower the amount of resources.

In this paper, we focus on implementing one of the most fundamental operations in quantum computing, i.e, the diagonal operation, be it unitary or non-unitary. In fact, the computational cost of implementing diagonal operators is a limiting factor in many quantum algorithms with applications as varied as real-space simulation of unitary and non-unitary dynamics <cit.>, quantum optimization <cit.> or quantum state preparation <cit.>.

The development of canonical decomposition of diagonal unitaries was first mentioned in the context of general unitary synthesis by A.Barenco et al. in 1996 <cit.>. Considering an $n$-qubit diagonal unitary, the authors propose to implement each eigenvalue sequentially with $2^n$ multi-controlled phase gates, each of these gates being in turn implementable with $\mathcal{O}(n^2)$ primitive quantum gates (or only $\mathcal{O}(n)$ if one uses one ancilla qubit). In 2004, S.Bullock et al. <cit.> were the first to present a quantum circuit related to the Walsh-Hadamard transform of the phases of the diagonal unitaries.

Their quantum circuits, made only of controlled-NOT gate and one qubit $z$-axis rotations, implement any diagonal unitary with $2^{n+1} -3$ gates, and are asymptotically optimal in terms of size for exact implementation. It is only in 2014 that Welch et al. <cit.> developed the first approximate quantum circuits with no exponential scalings for diagonal unitaries depending on smooth, at least once differentiable, functions. The complexity of their quantum circuits, also based on Walsh-Hadamard transform, is directly related to the maximum value of the derivative of the function, making the synthesis efficient as long as the function has small variations. The same year, Welch et al. developed efficient quantum circuits in the Clifford+T basis for diagonal unitaries with $k\ll 2^n$ distinct eigenvalues <cit.>. In 2021, approximate quantum compiling have been developed to train diagonal ansatze <cit.>. In 2023, Sun et al. <cit.> developed a recursive scheme for exact implementation of diagonal unitaries based on a particular ordering of the Walsh operators. Their method has an optimal depth scaling as $\mathcal{O}(2^n/n)$ and can be implemented with ancilla qubits to reduce the depth of the quantum circuits. In 2023 also, Zylberman et al. <cit.> implemented diagonal unitaries using sparse Walsh Series: by considering the smallest number of Walsh coefficients approximating a smooth, at least differentiable, function, they were able to reduce the depth of the associated quantum circuits. Recently, Claudon et al. <cit.> were able to revisit the initial results of Barenco et al., by developing a poly-logarithmic depth quantum circuit for multi-controlled operations, improving the circuit complexity of implementing one eigenvalue of a diagonal operator from $\mathcal{O}(n)$ to $\mathcal{O}(\log(n)^3)$ using one ancilla qubit.

All above methods can be grouped into two families: (i) the methods that use a sequential decomposition and implement one eigenvalue at a time <cit.> (ii) the methods that use a Walsh (or Walsh-Hadamard) decomposition <cit.>. All methods express diagonal unitaries as a product of simpler, efficiently implementable, diagonal unitaries. For generic diagonal unitary, exact decompositions involve an exponential amount of these simpler diagonal unitaries, leading to non-efficient quantum circuits.
The hope is then that, for many applications, the relevant diagonal unitaries are actually non generic. For example, the relevant diagonal unitaries can be sparse, i.e., only have a certain “small” number of eigenvalues different from unity, or the phases of the eigenvalues can be computed from functions with some smoothness properties, as for real-space simulations based on the implementation of evolution operators which are diagonal in a specific basis <cit.>.

In this work, we present an adjustable-depth framework to implement diagonal unitaries: from any decomposition into primitive diagonal operators, be it sparse or dense, exact or approximate, the depth of the associated quantum circuits can be reduced using an arbitrary number of ancilla qubits. The ancilla qubits are used to parallelize the implementation of the primitive diagonal operators, giving a first method to adjust the depth of the circuits. For the class of diagonal unitary depending on smooth, at least differentiable, functions, we prove that one can also adjust the depth of the circuits with respect to the approximation, giving a second tunable feature of the circuit. These contributions are summarized in different theorems:

* Full parallelization Theorem <ref> for any diagonal unitary decomposed into a product of $p$ simpler, efficiently implementable, diagonal unitaries $\hat{U}=\prod_{j=0}^{p-1}\hat{U}_j$ given a sufficient number of ancilla qubits.

* Adjustable-depth Theorem <ref> for any diagonal unitary decomposed into a product of $p$ simpler, efficiently implementable, diagonal unitaries $\hat{U}=\prod_{j=0}^{p-1}\hat{U}_j$ given a limited number of ancilla qubits.

* Approximate Theorem thm: Approximation theorem to modify any exact methods into an approximate one for any diagonal unitary associated to a smooth, at least differentiable, function.

These first results (Theorems <ref>, <ref>) are similar in spirit to those in <cit.>, but they were developed independently and they are here presented in full generality and with numerical simulations.

From now on we focus on diagonal non-unitaries. Implementing non-unitary operators with quantum computers has been often discussed in the last decades <cit.> and is crucial to broaden the range of applications accessible to quantum computing. Some algorithms of quantum state preparation (QSP) involve non-unitary operations <cit.>. Linear combination of unitaries (LCU) achieves Hamiltonian simulation by implementing the Taylor expansion of the evolution operator into a series of non-unitary operators <cit.>. Solving ordinary differential equations is also possible using non-unitary operations within the LCU framework <cit.> and many quantum partial differential equations solvers are based on non-unitary operations <cit.>. The quantum singular value transform (QSVT) makes it possible to implement polynomials of a block encoded operator and quantum algorithms such as Shor's algorithm <cit.>, quantum search <cit.> or quantum phase estimation <cit.> can be recast as a QSVT <cit.>. Most of these algorithms are based on the block-encoding of a non-unitary operator into a larger unitary one by adding ancilla qubits and the computational resources are often given as the number of queries to a block-encoded operator. In particular, the development of quantum circuits for non-unitary diagonal operators has attracted attention.

In this article, we show how to block-encode a non-unitary diagonal operator from a unitary one, keeping the adjustable properties of the quantum circuits. We present the different strategies that one can use starting from a block-encoded diagonal operator: the block-encoding may be enough for the target application, but one may also need to measure an ancilla qubit to get a renormalized qubit state on which the diagonal non-unitary operator has been performed. The probability of success depends directly on the diagonal operator and on the qubit state. Two distincts approaches are presented: a non-destructive repeat-until-success scheme and an amplitude amplification scheme for which the depth of the quantum circuit is adjustable with respect to the probability of success. Finally, we illustrate these methods with two applications: a new quantum state preparation protocols of smooth, at least differentiable, functions is presented and the real-space simulation of the diffusion equation is performed by preparing an initial Gaussian distribution which evolves through the non-unitary evolution operator of the diffusion equation. These contributions can be summarize by the following points:

* Block-encoding Theorem <ref> of non-unitary diagonal operators $\hat{D}$ using adjustable-depth quantum circuits.

* Table of complexities <ref> for unitary and non-unitary diagonal operators depending on smooth, at least differentiable, functions.

* Table of complexities <ref> for sparse unitary and non-unitary diagonal operators.

* Non-destructive repeat-until-success protocol for non-unitary diagonal operators when amplitude amplification fails.

* Efficient quantum state preparation Theorem <ref> with space-time-accuracy trade-offs to prepare quantum states depending on differentiable functions.

* Resolution of the diffusion equation, see Fig. <ref>, with high fidelity, few qubits and low depth quantum circuits.

The remainder of the paper is organized as follows. Section <ref> presents the sequential and Walsh-Hadamard decompositions and how to copy quantum registers. Section <ref> introduces the general approach to adjust the depth of the quantum circuits with respect to the number of ancilla qubits and Section <ref> with respect to the accuracy. In Section <ref>, the adjustable-depth quantum circuits for non-unitary diagonal operators are presented. Section <ref> summarizes the asymptotic scalings of the different methods for diagonal operators. Section <ref> details the amplitude amplification and the non-destructive repeat-until-success protocols. Finally, Section <ref> presents two applications: quantum state preparation and the resolution of the diffusion equation. Additional technical details are left in the Appendices.

§ PRELIMINARIES

This section introduces preliminary notions used across the paper. We present the metrics chosen to estimate the computational resources of the quantum circuits, as well as the two decompositions of diagonal unitaries, i.e., the sequential and the Walsh-Hadamard decomposition. We also introduce the copy unitary used to prepare the ancilla registers to parallelize the computations.

§.§ Depth, Size, Width, and Accuracy

Different metrics exist to evaluate the computational resources needed to implement a given quantum circuit.

Size is the number of single-qubit and two-qubit gates. Depth is the number of layers of quantum gates, and it is related to the time needed to perform the desired operation. Width is the number of ancilla qubits. A metric for accuracy for us, is the error in spectral norm between the implemented operator and the target operator. The set of primitive single-qubit and two-qubit gates considered in this article is the set of all single-qubit gates complemented by the control NOT gate (CNOT).
Other metrics such as the CNOT count or the T-count can also be estimated from the scalings provided in this paper.
A unitary operator acting on $n$ qubits is said to be efficiently implementable if there is a quantum circuit implementing it up to an error $\epsilon>0$ in spectral norm with a size, depth and width scaling at worst as $\mathcal{O}(\text{poly}(n,1/\epsilon))$[More formally, the “efficiency” is an asymptotic property that is rigorously defined on a sequence of unitaries $\{\hat{U}_n\}_{n=1}^{+\infty}$, where $\forall n$, $\hat{U}_n$ is acting on $n$ qubits. The sequence  $\{\hat{U}_n\}_{n=1}^{+\infty}$ is said to be efficiently implementable if $\forall \epsilon >0, \forall n$, there exist a quantum circuit implementing $\hat{U}_n$ up to an error $\epsilon >0$ in spectral norm with size, depth and width being $\mathcal{O}(\text{poly}(n,1/\epsilon))$.]. By extension, the quantum circuit is said efficient. A non-unitary operator is said to be efficiently implementable on a set  $\mathcal{H}$ of qubit states if the associated quantum circuit is efficient and the probability of successfully implementing the non-unitary operator on any $n$-qubit state $\ket{\psi} \in \mathcal{H}$ scales at worst as $\Omega(\text{poly}(1/n,\epsilon))$.

Some of the quantum circuits presented in this article have a depth and/or a size independent of $n$, making them particularly relevant for large scale fault-tolerant algorithms.

§.§ Sequential decomposition

The sequential decomposition expresses the diagonal unitary $\hat{U}=\sum_{x=0}^{N-1}e^{i\theta_x}\ket{x}\bra{x}$ acting on $n$ qubits (with $N=2^n$ eigenvalues) as a product of simple diagonal unitaries $\hat{U}_j=e^{i\theta_{j}}\ket{j}\bra{j}+\sum_{x\neq j} \ket{x}\bra{x}$ with $j\in\{0,...,N-1\}$, $x=\sum_{i=0}^{n-1}x_i 2^i \in \{0,...,N-1\}$, $x_i\in\{0,1\}$ and $\ket{x}=\ket{x_0}\otimes \cdots \otimes\ket{x_{n-1}}$ being the computational basis of the Hilbert space $\mathcal{H}_2^{\otimes n}$. For each $j$, the operator ${\hat U}_j$ has by construction $2^n - 1$ eigenvalues equal to unity and the other eigenvalue is $\exp(i \theta_{j})$, which is one of the eigenvalues of $\hat U$:

\begin{equation}
\hat{U}=\prod_{j=0}^{N-1}\hat{U}_j,
\end{equation}

and with the notation $\hat{U}=\text{diag}(u_0,\dots,u_{N-1})$:

\begin{equation}
\text{diag}(u_0,...,u_{N-1})=\text{diag}(u_0,1,\dots,1)\times\text{diag}(1,u_1,\dots,1)\times\cdots\times\text{diag}(1,\dots,1,u_{N-1}).
\end{equation}

Thus, each $\hat{U}_j$ is a $n$-qubit unitary which changes the phase of one of the eigenvectors of the computational basis. By denoting $j=\sum_{i=0}^{n-1}j_i2^i$ the binary decomposition of $j$  (where $ j_i\in\{0,1\}$ for all values of $i$), one can show that $\hat{U}_j$ corresponds to applying the phase $e^{i\theta_j}$ on one of the $n$ qubits if all the qubits are in state $\ket{j_i}$. The operator $\hat{U}_j$ can therefore be written as a $(n-1)$-controlled phase gate $\hat{P}(\theta_j)=\ket{0}\bra{0}+e^{i\theta_j}\ket{1}\bra{1}$ if $j_{n-1}=1$, or $e^{i\theta_j}\ket{0}\bra{0}+\ket{1}\bra{1}=\hat{X}\hat{P}(\theta_j)\hat{X}$ if $j_{n-1}=0$, which is controlled by the qubits $i\in \{0,...,n-2\}$ for which $j_i=1$ and anti-controlled by the qubits $i$ for which $j_i=0$. The anti-controls can be rewritten as control operations using $\hat{X}$-Pauli gates:

\begin{equation}
\hat{U}_j=(\hat{X}_0^{j_0}\otimes...\otimes\hat{X}_{n-1}^{j_{n-1}})\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))(\hat{X}_0^{j_0}\otimes...\otimes\hat{X}_{n-1}^{j_{n-1}}).
\label{sequential decomposition}
\end{equation}

with $\Lambda_{\{1,...,n-1\}}(\hat{P}(\theta_j))$ a $(n-1)$-controlled $\hat{P}(\theta_j)$ gates and $\hat{X}_i^{j_i}$ the $\hat{X}$-Pauli gate applied on qubit $i$ if $j_i=1$.

Let $k_j$ be the number of $1$'s in the binary decomposition of $j$. Each $\hat{U}_j$ is implementable using $2k_j$ $\hat{X}$-Pauli gates and a $(n-1)$-multi-controlled gate.  The recent work of Claudon et al. <cit.> introduces polylogarithmic-depth quantum circuits to implement $(n-1)$-multi-controlled gates by breaking it down into smaller multi-controlled gates which are implemented in parallel. Their approximate method implements the gate $\Lambda_{\{1,...,n-1\}}(\hat{P}(\theta_j))$  up to an error $\epsilon>0$ with a quantum circuit of depth $\mathcal{O}(\log(n)^3\log(1/\epsilon))$, size $\mathcal{O}(n\log(n)^4\log(1/\epsilon))$ and without ancilla qubits (Proposition 2 in <cit.>). One can also implement exactly the $n$-control gate using one ancilla qubit (zeroed or borrowed[ Zeroed ancilla qubits are initially in state $\ket{0}$ and reset to $\ket{0}$ at the end of the computation. Borrowed ancilla qubits are in an arbitrary state $\ket{\psi}$ potentially entangled with other qubits and are restored to their initial state afterwards.]) with a depth $\mathcal{O}(\log(n)^3)$ and a size $\mathcal{O}(n\log(n)^4)$ (Corollary 1 in <cit.>) or without ancilla qubits with a linear depth $\mathcal{O}(n)$ and a linear size $\mathcal{O}(n)$ <cit.>.

Being diagonal operators, the ${\hat U}_j$'s commute with one another. It thus makes sense to wonder if there is an optimal order in which to implement these operators.

It is possible to use a Gray code order <cit.>, i.e., from two following operators $\hat{U}_j$ and $\hat{U}_{j'}$ only one bit differs from the binary decomposition of $j$ and $j'$, which cancels a maximum number of $\hat{X}$-Pauli gates from two consecutive operators. Thus, only one $\hat{X}$-Pauli gate remains between each multi-controlled gate, reducing the overall cost of the implementation (see Appendix <ref> for examples of quantum circuits with and without Gray code ordering).

§.§ Walsh-Hadamard decomposition

The exact synthesis of quantum circuits for diagonal unitaries has been proven asymptotically optimal in terms of size (up to a factor $2$) using $2^{n+1}-3$ CNOT and $\hat{R}_Z$ quantum gates <cit.>. As shown by Welch et al. <cit.>, this construction is directly related to the Walsh-Hadamard representation of a set of $N=2^n$ data points: a $N$-Walsh Series can represent exactly a set $\{\theta_k\}$ of $N$ data points through the Walsh-Hadamard transform.

Walsh Series and Walsh functions were first introduced by Walsh in 1923 <cit.>. The Walsh function of order $j \in \{0,1,...,N-1\}$ is defined on $[0,1]$ by

\begin{equation}
\label{Walsh function definition}
\end{equation}

where $j_i$ is the $i$-th bit in the binary expansion $j=\sum_{i=0}^{n-1}j_i2^{i}$ and $x_i$ is the $i$-th bit in the dyadic expansion $x=\sum_{i=0}^{\infty} x_i/ 2^{i+1}$.

Walsh functions only take $\pm1$ values depending on their order $j$ and are naturally implementable on quantum computers through their associated $\hat{Z}$-Pauli operators:

\begin{equation}
\hat{w}_j = \bigotimes_{i=0}^{n-1}(\hat{Z}_i)^{j_i}.
\end{equation}

To implement the diagonal unitary $\hat{U}=\sum_{k=0}^{N-1} e^{i\theta_k}\ket{k}\bra{k}$, which depends on the $N$ real values $\{\theta_k\}$, one first defines the Walsh coefficients:

\begin{equation}
a_j=\frac{1}{N}\sum_{k=0}^{N-1}\theta_k w_{j}(k/N),
\end{equation}

and write

\begin{equation}
\hat{U} = \prod_{j=0}^{N-1}\hat{W}_{j},
\label{walsh decomposition}
\end{equation}

where $\hat{W}_j=e^{ia_j\hat{w}_j}$.

Using the fact that a tensor product of $\hat{Z}$-Pauli gates can be rewritten using two CNOT stairs and one $\hat{Z}$-Pauli gate, one can show that each of the operators $\hat{W}_j$ can be implemented using one $\hat{R}_Z$ gate and $2k_j$ CNOT gates, with $k_j$ the number of bit equals to unity in the binary decomposition of $j$. For $j=\sum_{i=0}^{p-1}j_i2^{i}$ with $1\leq p\leq n$ and $j_{p-1}=1$, the operator $\hat{W}_j$ acts on the $p$-th qubits $0,...,p-1$ as:

\begin{equation}
\hat{W}_j=\left(\prod_{i=0}^{p-2}\widehat{CNOT}_{i\rightarrow p-1}^{j_i}\right)\left(\hat{I}_2^{\otimes(p-1)} \otimes \hat{R}_Z(a_j))
\right)\left(\prod_{i=0}^{p-2}\widehat{CNOT}_{i\rightarrow p-1}^{j_i}\right)^{-1},
\label{eq: exp of walsh operator}
\end{equation}

where $\widehat{CNOT}_{i\rightarrow p-1}^{j_i}$ is the CNOT gate controlled by the $i$-th qubit and applied on the $(p-1)$-th qubit if $j_i=1$, the symbol $\prod_{i=0}^{p-2}\hat{A}_i=\hat{A}_0...\hat{A}_{p-2}$ is the product of operator $\hat{A}_i$ with indexes in increasing order, $\hat{I}_2^{\otimes (p-1)}$ is the identity operator on the qubits $0$ to $p-2$ and $\hat{R}_Z(a_j)=e^{i a_j}\ket{0}\bra{0}+e^{-i a_j}\ket{1}\bra{1}$ acts on the qubit $p-1$. The operator $\hat{W}_0(a_0)=e^{ia_0}\hat{I}_2^{\otimes n}$ is a phase encoding the average value of the $\{\theta_k\}$.

Being diagonal operators, the $\hat{W}_j$ commute with one another. Similarly to the sequential decomposition, one can choose a Gray code ordering to cancel a maximum of CNOT gates from two consecutive $\hat{W}_j$ operator (see Appendix <ref> for examples of quantum circuit with and without Gray code ordering).

Note that sparse Walsh-Hadamard decomposition, i.e., diagonal unitary expressed with only a number $s < N$ of  $\hat{W}_j$ operators, are particularly efficient to approximate diagonal unitaries depending on smooth, at least once differentiable, functions <cit.>. In this case, the Gray code ordering may not be efficient to cancel a maximum of CNOT gates.

§.§ Preparation of the ancilla registers

The main results of this article use ancilla qubits to adjust the depth of the quantum circuits by parallelizing the implementation of the diagonal unitaries $\hat{U}_j$ or $\hat{W}_j$. This is possible by “copying”[The name “copy” does not refer to the cloning operation $\ket{\psi}\otimes\ket{0}\rightarrow \ket{\psi}\otimes \ket{\psi}$ which is forbidden by the no-cloning theorem.] the bit value of each of the $n$ qubits into other ancilla qubits. Consider the $i$-th qubit in an arbitrary state $\ket{\psi}_i=\alpha\ket{0}_i+\beta\ket{1}_i$ and a register of $m_i$ zeroed ancilla qubit in state $\ket{0}^{\otimes m_i}$. The copy unitary $\hat{C}_i$ copies acts as:

\begin{equation}
\hat{C}_i(\alpha\ket{0}_i+\beta\ket{1}_i) \otimes \ket{0}^{\otimes m_i}=\alpha\ket{0}^{\otimes (m_i+1)}+\beta\ket{1}^{\otimes (m_i+1)}.
\end{equation}

This operation has already been introduced for other quantum circuit synthesis <cit.>. We state and prove clearly the complexity associated to the copy operation with the following lemma.

The “copy” unitary $\hat{C}_i$ acting on $m_i+1$ qubits can be implemented using $m_i$ CNOT gates with a depth $\lceil \log_2(m_i+1) \rceil$.

Note first that a set of $q$ CNOT gates applied to different qubits can be implemented in parallel and therefore has a depth $1$. Define $k=\lceil \log_2(m_i+1) \rceil$. A direct recursion on $k'=1,...,k-1$ proves that the copy unitary doubles the number of “copied” qubit at each step, so each newly copied qubit can be used to copy another one at the next step as

\begin{equation}
\begin{split}
(\alpha\ket{0}+\beta&\ket{1})\otimes \ket{0}^{\otimes m_i} \xrightarrow{\widehat{CNOT}_{0\rightarrow1}} (\alpha\ket{0}^{\otimes 2}+\beta\ket{1}^{\otimes 2})\otimes \ket{0}^{\otimes m_i-1} \\ & \xrightarrow{\widehat{CNOT}_{0\rightarrow2}\otimes \widehat{CNOT}_{1\rightarrow3}} (\alpha\ket{0}^{\otimes 4}+\beta\ket{1}^{\otimes 4})\otimes \ket{0}^{\otimes m_i-3} \\ & \vdots
\\ & \xrightarrow{\otimes_{j=0}^{2^{k'}-1}\widehat{CNOT}_{j\rightarrow (j+2^{k'})}} \alpha\ket{0}^{\otimes2^{k'+1}}+\beta\ket{1}^{\otimes 2^{k'+1}}\otimes \ket{0}^{(m_i-(2^{k'+1}-1))},
\end{split}
\end{equation}

where $\widehat{CNOT}_{j\rightarrow (j+2^{k'})}$ is the CNOT gate controlled by the $j$-th qubit and applied on $(j+2^{k'})$-th zeroed qubit. After $k-1$ steps, the qubit state is $(\alpha\ket{0}^{\otimes2^{k-1}}+\beta\ket{1}^{\otimes 2^{k-1}})\otimes\ket{0}^{\otimes(m_i-(2^{k-1}-1))}$. A last layer of CNOT gates suffices to produce the state $\alpha\ket{0}^{\otimes(m_i+1)}+\beta\ket{1}^{\otimes (m_i+1)}$.

[2]Main register     2[4,steps=2,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]depth=1         4[8,steps=4,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]depth=1

2         4

[2]1st ancilla register                      4

[2]2nd ancilla register

[2]3rd ancilla register

Quantum circuit to copy a register of 2 qubits into 3 ancilla registers. The qubits of the ancilla registers are in the $\ket{0}$ state. The operations framed together can be executed in parallel as they act on different qubits. The depth of the circuit scales logarithmically in the number of copies as the number of copying qubits doubles at each step.

A direct corollary of this lemma adresses the copy of a register of $n$ qubits, where each of the $n$ qubits is copied on $m_i$ other qubits. This operation is performed by implementing each $\hat{C}_i$ in parallel through the operator $\widehat{\text{copy}}=\bigotimes_{i=0}^{n-1} \hat{C}_i$. Its size is given by $\sum_{i=0}^{n-1}m_i$ CNOT gates and its depth is $\lceil \log_2(m+1) \rceil$ where $m=\max_{i=0,...,n-1} m_i$.  A small instance of the copy unitary is shown in Fig. <ref> where a register of 2 qubits gets copied into 3 ancilla registers of 2 qubits each.

§ ADJUSTABLE-DEPTH FRAMEWORK USING ANCILLA QUBITS

In this section, we present an approach to adjust the depth of a quantum circuit implementing a diagonal unitary. Let $\hat{U}$ be a diagonal unitary acting on $n$ qubits with a decomposition $\hat{U}=\prod_{j=0}^{p-1}\hat{U}_j$ where each $\hat{U}_j$ acts on $k_j\leq n$ qubits and is implementable with a quantum circuit of size $s_j$ and depth $d_j$. The $\hat{U}_j$ can be sequential operators (<ref>) as well as exponential of Walsh operators (<ref>). Without ancilla qubits, one can implement $\hat{U}$ by performing each $\hat{U}_j$ one by one, leading to a quantum circuit of size $s=\sum_{j=0}^{p-1} s_j$ and depth $d=\sum_{j=0}^{p-1} d_j$.  With ancilla qubits, one can parallelize the implementation of a maximum number of $\hat{U}_j$ operators. The parallelization can be partial or total, reducing the depth proportionally to the number of ancilla qubits available at the cost of preparing the ancilla registers with copy unitaries.

First, suppose one has enough available ancilla qubits to prepare $p-1$ registers:

\begin{equation}
\begin{split}
\ket{x}\ket{0}^{\otimes k} \xrightarrow{\widehat{\text{copy}}}  \ket{x}\ket{\tilde{x}}_1...\ket{\tilde{x}}_{p-1},
\end{split}
\end{equation}

where each register $\ket{\tilde{x}}_j$ contains only a copy of the $k_j$ qubits on which $\hat{U}_j$ is acting non-trivially and $k=\sum_{j=1}^{p-1} k_j$. More formally, if one defines the support of $\hat{U}_j$ as the set of qubits on which $\hat{U}_j$ does not act like the identity, the state $\ket{\tilde{x}}_j$ contains only a copy of the qubits in the support of $\hat{U}_j$.

One can then implement each of the $p$ diagonal unitaries $\hat{U}_j=\sum_{x=0}^{N-1}e^{i\theta_j(x)}\ket{x}\bra{x}$ on a different register of qubits:

\begin{equation}
\begin{split}
\ket{x}\ket{\tilde{x}}_1...\ket{\tilde{x}}_{p-1}  \xrightarrow{ \bigotimes _{j=0}^{p-1} \hat{U}_j } &\hat{U}_0\ket{x}\hat{U}_1\ket{\tilde{x}}_{1}...\hat{U}_{p-1}\ket{\tilde{x}}_{p-1}
\\ =& e^{i\theta_{0}(x)}e^{i\theta_1(x)}...e^{i\theta_{p-1}(x)}\ket{x}\ket{\tilde{x}}_{1}...\ket{\tilde{x}}_{p-1}
\\=&e^{i\theta(x)}\ket{x}\ket{\tilde{x}}_{1}...\ket{\tilde{x}}_{p-1}
\end{split}
\end{equation}

with $e^{i\theta(x)}=e^{i\sum_{j=0}^{p-1}\theta_j(x)}$ being the eigenvalue of $\hat{U}$ associated to the $\ket{x}$ eigenvector.
Finally, the inverse copy operation resets the ancilla qubits in the state $\ket{0}$:

\begin{equation}
\begin{split}
\xrightarrow{ \widehat{\text{copy}}^{-1}}  e^{i\theta(x)}\ket{x}\ket{0}^{\otimes k}.
\end{split}
\end{equation}

The full parallelization protocol has the following complexity:

The implementation of the diagonal operator $\hat{U}=\prod_{j=0}^{p-1}\hat{U}_j$ can be fully parallelized with a quantum circuit using $k=\sum_{j=1}^{p-1}k_j$ ancilla qubits, with a size $s+2k$ and a depth bounded by $\max_{j}(d_j)+2\lceil \log_2(p) \rceil$.

The size of the quantum circuit is given by the sum of the size of each $\hat{U}_j$ and the size of the $\widehat{\text{copy}}$ and $\widehat{\text{copy}}^{-1}$ unitaries: one controlled-NOT gate is applied on each of the $k$ ancilla qubits for the $\widehat{\text{copy}}$ and a second time for $\widehat{\text{copy}}^{-1}$, giving a final size of $s+2k$. The depth corresponds to the sum of the depths of the two copy unitaries which, in the worst case of a qubit copied $p$ times, is bounded by $2\lceil \log_2(p) \rceil$, and by the depth of the parallelized $\hat{U}_j$, which is given by the maximum of the depths of the $\hat{U}_j$'s.

[4]$n$     [4]Û

[5]$n$     [4]Û_0         [2]Û_2

[3]Û_1         [3]Û_3

[4]$n$     [8] copy[8,steps=1,style=dashed,rounded corners,color=white, inner xsep=-10pt, inner ysep=-6pt,background]$\overbrace{}^{\mathcal{O}(\log m/n)}$     [4]Û_0         [8] copy^-1[8,steps=1,style=dashed,rounded corners,color=white, inner xsep=-10pt, inner ysep=-6pt,background]$\overbrace{}^{\mathcal{O}(\log m/n)}$

[4]$m$         [2]Û_2

[4]$n$     [12] copy[12,steps=1,style=dashed,rounded corners,color=white, inner xsep=-10pt, inner ysep=-6pt,background]$\overbrace{}^{\mathcal{O}(\log m'/n)}$     [4]Û_0     [12] copy^-1[12,steps=1,style=dashed,rounded corners,color=white, inner xsep=-10pt, inner ysep=-6pt,background]$\overbrace{}^{\mathcal{O}(\log m'/n)}$

[8]$m'$         [3]Û_1

Adjustable-depth quantum circuit for a diagonal unitary $\hat{U}=\prod_{j=0}^3\hat{U}_j$ using ancilla qubits. The main register is composed of $n$ qubits, the depth of the circuit is reduced by adding ancilla qubits. The “copy” operations are performed with a depth logarithmic in $m/n$.

If the number $m$ of available ancilla qubits is smaller than $k$, one can gather the $\hat{U}_j$'s into $p'<p$ groups and implement the groups in parallel to each other.

Figure fig:adjustable_depth_qc gives an example of a diagonal unitary composed of $p=4$ efficiently implementable diagonal operators which are implementable sequentially or in parallel depending on the number of ancilla qubits available.  For $m=n$, one can implement half of the $\hat{U}_j$'s in parallel to the others, reducing at best by a factor of $2$ the depth of the circuit (but doubling its width).  The following Theorem <ref> gives an upper bound for the depth of the adjustable-depth protocol which decreases with the number of ancilla qubits, at the cost of performing the $ \widehat{\text{copy}}$ and $ \widehat{\text{copy}}^{-1}$ unitaries.

Let $m\ge n$ be the number of ancilla qubits and $m'=\lceil m/n \rceil$. The diagonal unitary $\hat{U}=\prod_{j=0}^{p-1}\hat{U}_j$ can be implemented with a quantum circuit of size $s+2m$ and depth $d$ bounded as:

\begin{equation}
d\leq \sum_{j=0}^{\lceil p/m' \rceil-1 } d_j +2\lceil \log_2(m') \rceil \leq \lceil \frac{p}{m'} \rceil \max_{j}(d_j) +2\lceil \log_2(m') \rceil,
\end{equation}

where the $\hat{U}_j$ are ordered to have decreasing depth $d_0\ge d_1\ge...\ge d_{p-1}$.

Similarly to the fully parallelized theorem, the size of the quantum circuit is given by the size $s$ of the circuits implementing the $\hat{U}_j$'s added to the number $2m$ of controlled-NOT gates needed to perform the $ \widehat{\text{copy}}$ and $\widehat{\text{copy}}^{-1}$ unitaries. The first inequality is given by the worst case scenario where the $\hat{U}_j$'s act non-trivially on $n$ qubits, in which case one needs at least $m\ge n$ ancilla qubits to reduce the depth of the quantum circuit. In this situation, the number of groups that can be implemented in parallel is $m'=\lfloor m/n \rfloor +1$ (the $+1$ term comes from the $n$ initial qubits, i.e., $m'=\lceil m/n\rceil$). It is always possible to create $m'$ random groups of at most $\lceil p/m' \rceil$ operators. In the worst case, the maximum depth of the groups is the sum from $j=0$ to $\lceil p/m' \rceil-1$ of the maximum depths of the $\hat{U}_j$'s: $\sum_{j=0}^{\lceil p/m' \rceil -1} d_j$. Since the depths of the two copy steps $2\lceil \log_2(m')\rceil$, one thus arrives at the first inequality. The second inequality trivially comes from the fact that $\forall j$, $d_j\leq \max_{j'}(d_{j'})$.

This adjustable-depth protocol does not deal with finding an optimal strategy to group the $\hat{U}_j$'s. Such a strategy needs to consider the depth $d_j$ of each operator and to group them in order to minimize the maximum depth of the groups. Finding this optimal solution or a “good” solution can take some classical time and it is in general a difficult combinatorial problem (even though some tailored algorithmic techniques may exist) <cit.>. We do not look into this here, however, the upper bound is reached for a diagonal unitary made only of sequential operators (<ref>) acting non-trivially on $n$ qubits with identical depth. For a diagonal unitary given by a Walsh-Hadamard decomposition, it is possible to group the unitaries with distinct support first, before parallelizing them.

Overall, the parallelization approach reduces the depth of the quantum circuit while increasing the width, making it possible to adjust the quantum circuit to the constraints of the hardware, e.g., the decoherence time and the number of available qubits. Numerical results illustrating the trade-off between depth and width are given in the application section in Fig. <ref> for the quantum state preparation of Gaussian states.

§ ADJUSTABLE-DEPTH FRAMEWORK USING APPROXIMATIONS

This section presents two efficient methods to approximate diagonal unitaries $\hat{U}_f=e^{i\hat{f}}$ which depend on smooth or, at least, once differentiable functions $f$. The first method transforms any exact quantum circuit for diagonal unitaries into an efficient approximate one. The second method computes a good approximation of $f$ using sparse Walsh Series. Both methods exploit the specific structure of $\hat{U}_f$ to get an efficient approximate quantum circuit, while exact methods suffer from exponential scalings either in terms of depth or width <cit.>. These two approximating methods have efficient scalings with a depth and size asymptotically independent of the number of qubits $n$. By comparison, approximate quantum compiling <cit.> does not provide any guarantees to reach a given accuracy in the large $n$ limit.

Let $f$ be a smooth, at least once differentiable, function defined on $[0,1]$, $\hat{U}_{f,n}=e^{i\hat{f}_n}=\sum_{x=0}^{N-1} f(x/N)\ket{x}\bra{x}$ be the target unitary acting on $n$ qubits and $\hat{U}_{f,m}=\sum_{x=0}^{M-1} f(x/M)\ket{x}\bra{x}$ be the restriction $\hat{U}_{f,n}$ to $m<n$ qubits (with $M=2^m$). The following theorem states that implementing $\hat{U}_{f,m}$ using an exact method gives an efficient quantum circuit approximating the target unitary $\hat{U}_{f,n}$ up to an error $\epsilon>0$ in spectral norm:

Given a quantum circuit implementing exactly any $n$-qubit diagonal unitary with size $s(n)$, depth $d(n)$ and width $w(n)$, one can $\epsilon$-approximate $\hat{U}_{f,n}$ with a quantum circuit of size $s(m)$, depth $d(m)$ and width $w(m)$ with $m=\lceil \log_2(||f'||_{\infty,[0,1]}/\epsilon) \rceil$.

The proof is based on the Walsh-Hadamard representation of the target unitary, independently of its method of implementation. First, we prove that implementing exactly the diagonal unitary $\hat{U}_{f,m}$ on $m=\lceil \log_2(||f'||_{\infty,[0,1]}/\epsilon) \rceil$ qubits gives an $\epsilon$-approximation of $\hat{U}_{f,n}$ in spectral norm.   Define $S_{f,M}=\sum_{j=0}^{M-1}a_j^fw_j$ as the $M$-Walsh Series of $f$,  with $a_j^f=\frac{1}{M}\sum_{x=0}^{M-1}f(x/M)w_{j}(x/M)$ the $j$-th Walsh coefficients associated to the function $f$ and $M=2^m$. The $M$-Walsh Series $S_{f,M}$ of $f$ is a piecewise function taking at most $M$ different values and defined by $\forall x \in [k/M, (k+1)/M[$, $S_{f,M}(x)=S_{f,M}(k/2^m)=f(k/2^m)$ with $k\in\{0,...,M-1\}$ (see Lemma 1.1 of <cit.>). Thus, the $n$-qubit operator $\hat{S}_{f,M}=\sum_{x=0}^{N-1}S_{f,M}(x/N)\ket{x}\bra{x}$ has at most $M$ distinct eigenvalues and can be rewritten as:

\begin{equation}
\begin{split}
\hat{S}_{f,M}&=\sum_{x_0,...,x_{n-1}=0}^1S_{f,M}\left(\sum_{i=0}^{n-1} x_i/ 2^{i+1}\right)\ket{x_0,...,x_{n-1}}\bra{x_0,...,x_{n-1}}\\
&=\sum_{x_0,...,x_{m-1}=0}^1S_{f,M}\left(\sum_{i=0}^{m-1} x_i/ 2^{i+1}\right)\ket{x_0,...,x_{m-1}}\bra{x_0,...,x_{m-1}} \\& \otimes \sum_{x_m,...,x_{n-1}=0}^1\ket{x_m,...,x_{n-1}}\bra{x_m,...,x_{n-1}}
\\ &= \hat{f}_m \otimes  \hat{I}_2^{\otimes n-m},
\end{split}
\end{equation}

where  $\hat{f}_m=\sum_{x=0}^{M-1}f(x/M)\ket{x}\bra{x}$ is an $m$-qubit operator.

Thus, $\hat{U}_{f,m} \otimes \hat{I}_2^{\otimes n-m}=e^{i\hat{f}_m\otimes \hat{I}_2^{\otimes n-m}}=e^{i\hat{S}_{f,M}}=\hat{U}_{S_{f,M},n}$, which is the diagonal unitary with eigenvalues associated to the $M$-Walsh series of $f$. Furthermore, $M$-Walsh Series approximate the function itself up to an error depending on the maximum value of the derivative of $f$ and decreasing linearly with $M$ <cit.>: $||f-S_{f,M}||_{\infty,[0,1]}\leq \frac{||f'||_{\infty,[0,1]}}{2^m}$. In terms of spectral norm $||.||_2$, this implies that $\hat{U}_{S_{M,f},n}$ is an approximation of the target diagonal unitary $\hat{U}_{f,n}$:

\begin{equation}
||\hat{U}_{f,n}-\hat{U}_{S_{f,M},n}||_{2}\leq \frac{||f'||_{\infty,[0,1]}}{2^m}.
\end{equation}

Finally, one can choose  $m=\lceil \log_2(||f'||_{\infty,[0,1]}/\epsilon) \rceil$ of qubits to implement the target unitary $\hat{U}_{f,n}$ up to a given error $\epsilon>0$ in spectral norm with a quantum circuit of size $s(m)$, depth $d(m)$ and width $w(m)$.

In the particular case $m\geq n$, one implements exactly the diagonal unitary on $n$ qubits and the error vanishes. On the contrary, for a given $\epsilon>0$, this method gives a quantum circuit which approximates diagonal unitaries with complexities asymptotically independent of the number of qubits $n$.

A second way to approximate efficiently a diagonal unitary defined through a given function $f$ is to consider a sparse Walsh series.

For instance, by retaining only the largest coefficients in the $M$-Walsh Series, one can reach a given infidelity with quantum circuits
of smaller size and depth <cit.>. More generally, the problem of finding the “best” Walsh series with the smallest number of terms approximating up to a given $\epsilon>0$ a function $f$ is called the minimax problem <cit.>. While the minimax problem has no known canonical solutions, sparse Walsh series appear numerically as the most efficient method to approximate smooth, at least differentiable, functions.

Numerical results illustrating the trade-off between depth and accuracy are given in the application section, for the quantum state preparation of Gaussian states, see Fig. <ref>. The trade-off is presented for the approximate method using an $M$-Walsh series and for a sparse Walsh-Series.

§ IMPLEMENTATION OF NON-UNITARY DIAGONAL OPERATORS

In this section, we outline first the process of implementing a non-unitary diagonal operator from two diagonal unitaries using one ancilla qubit. Then, the methods introduced previously are adapted to deliver ways of implementing non-unitary diagonal operators with adjustable-depth quantum circuits.

Consider the non-unitary diagonal operator $\hat{D}=\text{diag}(d_0,...,d_{N-1})$, $N=2^n$ with real eigenvalues $\{d_x\}_{x=0}^{N-1}$. The block encoding approach consists in implementing $\hat{D}$ in a larger unitary operator $\hat{U}$ using additional ancilla qubits as:

\begin{equation}
\hat{U}_D=\begin{pmatrix} \hat{D} & * \\ * & *
\end{pmatrix},
\end{equation}

where the other block “$*$” are chosen to ensure that $\hat{U}_b$ is unitary.

More formally, $\hat{U}_D$ is said to be a $(\alpha,m,\epsilon)$-block encoding of $\hat{D}$ with $\alpha >0$ and $\epsilon>0$ if

\begin{equation}
\|\frac{1}{\alpha}\hat{D}-(\bra{0}^{\otimes m}\otimes \hat{I}_N ) \hat{U}_D (\ket{0}^{\otimes m}\otimes \hat{I}_N) \|_2 \leq \epsilon,
\end{equation}

in spectral norm. Note that $\alpha$ is often the largest eigenvalue of $\hat{D}$ and $m$ is the number of additional qubits used to block-encode $\hat{D}$ into a unitary operator. In the case where the block-encoding is exact, we note that $\hat{U}_D$ is a $(\alpha,m)$-block encoding of $\hat{D}$.

[wires=1]$\begin{matrix} \text{Ancilla} \\ \text{qubit} \end{matrix} \ket{q_A=0}$    Ĥ        1        1    Ĥ    P̂

[3,nwires=2]e^-iθ̂        [3,nwires=2]e^iθ̂    [wires=3]$\frac{\hat{D}\ket{\psi}}{\|\hat{D}\ket{\psi}\|}$

Quantum circuit to block-encode a non-unitary diagonal operator $\hat{D}=\text{diag}(d_0,...,d_{2^n-1})$ using $\hat{\theta}=\arcsin(\hat{D}/d_{\max})$, with $d_{\max}=\max_{i=0,...,2^n-1}|d_i|$.

Figure <ref> depicts the sequence of unitary operations needed to block-encode a non-unitary diagonal operator using two controlled diagonal unitaries and one ancilla qubit without using parallelization protocols. From a qubit state $\ket{\psi}$ and an ancilla qubit $\ket{0}$, one obtains:

\begin{equation}
\begin{split}
\ket{\psi}\ket{0}\xrightarrow{\hat{H}} \ket{\psi}\frac{\ket{0}+\ket{1}}{\sqrt{2}} & \xrightarrow{e^{i\hat{\theta}\otimes\hat{Z}}} \frac{e^{i\hat{\theta}}\ket{\psi}\ket{0}+e^{-i\hat{\theta}}\ket{\psi}\ket{1}}{\sqrt{2}} \\& \xrightarrow{\hat{P}\hat{H}} -i\cos(\hat{\theta})\ket{\psi}\ket{0}+\sin(\hat{\theta})\ket{\psi}\ket{1}.
\end{split}
\end{equation}

The gate $\hat{P}=\begin{pmatrix} 1 & 0 \\ 0 & -i \end{pmatrix}$ is optional and only serves to suppress a factor $i$ in the final state. The operator $\hat{\theta}$ encodes the eigenvalues of $\hat{D}$ as $\hat{\theta}=\arcsin(\hat{D}/d_{\max})$, where $d_{\max}=\max_{x=0,...,N-1}|d_x|$ is the largest eigenvalue of $\hat{D}$. Without measuring the ancilla, this quantum circuit is an exact $(d_{\max},1)$ block-encoding of $\hat{D}$. This block-encoding is sufficient for some applications but one may need to output only the state proportionate to $\hat{D}\ket{\psi}$ by measuring the ancilla qubit in state $\ket{1}$:

\begin{equation}\label{eq:final_state_qsp}
\ket{\phi}=-i\sqrt{\hat{I}-\left(\frac{\hat{D}}{d_{\max}}\right)^2}\ket{\psi}\ket{0}+\frac{\hat{D}}{d_{\max}}\ket{\psi}\ket{1}  \xrightarrow{\text{if } \ket{q_A}=\ket{1}} \frac{\hat{D}\ket{\psi} }{\| \hat{D}\ket{\psi}\|},
\end{equation}

with a probability of success given by

\begin{equation}
\mathbb{P}(1)=\| \frac{\hat{D}}{d_{\max}}\ket{\psi}\|^2=|\bra{\psi}(\frac{\hat{D}}{d_{\max}})^2\ket{\psi}|=\sum_{x=0}^{2^n-1}d_x^2|\psi_x|^2/d_{\max}^2.
\label{eq: proba success}
\end{equation}

The specific structures of $\hat{D}$ and $\ket{\psi}$ directly affect the probability of success. When the diagonal operator $\hat{D}$ and the qubit state $\ket{\psi}$ depend on continuous real-valued functions $f$ and $g$ defined on $[0,1]$, i.e., $\hat{D}=\sum_{x=0}^{N-1} f(x/N)\ket{x}\bra{x}$ and $\ket{\psi}=\frac{1}{||g||_{2,N}}\sum_{x=0}^{N-1} g(x/N)\ket{x}$, the probability of success tends to an $n$-independent limit, enabling an efficient implementation:

\begin{equation}
\mathbb{P}(1)=\frac{\|fg\|_{2,[0,1]}^2}{\|g\|_{2,[0,1]}^2\|f\|_{\infty}^2}=\Theta(1),
\label{eq: proba of success continue}
\end{equation}

with $\|fg\|_{2,[0,1]}^2=\int_0^1f(x)^2g(x)^2\textrm{d}x$, $\|g\|_{2,[0,1]}^2=\int_0^1g(x)^2\textrm{d}x$ and $\|f\|_{\infty}=\sup_{x\in [0,1]}|f(x)|$. The notation $\mathbb{P}(1)=\Theta(1)$ means that the probability of success is bounded by two constants $0<C_1\leq \mathbb{P}(1)\leq C_2 \leq1$ in the large $n$ limit.

[2]Copies of $q_A$         [3] copy     4     4                     ⋯                    [3] copy^-1

6     6             ⋯

$\ket{q_A}$     Ĥ                                 ⋯            8     8         Ĥ     P̂

[3]Main register $\ket{\psi}$         [10,nwires=7] copy     [3]Û_0     [3]Û_0^†                     ⋯                    [10,nwires=7] copy^-1             [3]$\ket{\psi}=\frac{\hat{D}\ket{\psi}}{||\hat{D}\ket{\psi}||}$

[3]1st register                     [3]Û_1     [3]Û_1^†             ⋯

$\vdots$     ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋱    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮

[3]$p$-th register                                     ⋯            [3]Û_p     [3]Û_p^†

Adjustable-depth quantum circuit for the implementation of non-unitary diagonal operator $\hat{D}$. The main register $\ket{\psi}$ is composed of $n$ qubits. The ancilla qubit is $\ket{q_A}$. The upper register is composed of ancilla qubits that store the bit value of $\ket{q_A}$, it is used to perform several controls simultaneously. The $p$ ancilla registers below the main register are used to parallelize the implementation of $\hat{U}$. If the output of the measurement of $\ket{q_A}$ is 0, the target state has been successfuly implemented.

When the diagonal operator $\hat{D}$ is $s$-sparse, i.e., $\hat{D}=\sum_{x \in S} d_x \ket{x}\bra{x}$, with $S \subseteq \{0,1,...,N-1\}$ and $|S|=s$, and the qubit state depends on a continuous function, i.e., $\ket{\psi}=\frac{1}{||g||_{2,N}}\sum_{x=0}^{N-1} g(x/N)\ket{x}$, the probability of success diminishes exponentially with the number of qubits:

\begin{equation}
\mathbb{P}(1)=\frac{1}{||g||_{2,N}}\sum_{x \in S} \frac{d_x^2}{d_{\max}^2}g(x/N)^2=\Theta(1/N),
\label{eq: proba success sparse}
\end{equation}

with $N=2^n$.
In the other cases, for instance for a sparse qubit state and a non-sparse diagonal operator, no general formula garantees a significant probability of success in the large $n$ limit. The probability of success can also be improved using amplitude amplification as discussed in Section <ref>.

Now, consider the problem of implementing a non-unitary diagonal operator $\hat{D}$ using an adjustable-depth quantum circuit associated to a Walsh or a sequential decomposition of $\hat{U}=e^{ i \arcsin(\hat{D}/d_{\max})}=\prod_{j=0}^{p-1}\hat{U}_j$.  In Fig. <ref>, the controls of $\hat{U}$ and $\hat{U}^{\dagger}$ do not preserve the adjustable-depth feature of the methods presented in the previous sections since one ancilla qubit cannot control several blocks at the same time. In order to overcome this issue, one can use $p$ copies of the ancilla qubit $\ket{q_A}$ to control $p$ blocks in parallel at the same time. That is why, one needs to prepare a copy register of $\ket{q_A}$ before the control of the diagonal operators. The following theorem states and proves that Fig. <ref> represents an adjustable-depth quantum circuit for a block-encoding of $\hat{D}$ up to the measurement of the ancilla qubit $\ket{q_A}$.

Let $\hat{D}$ be a non-unitary diagonal operator and $\hat{U}=e^{ i \arcsin(\hat{D}/(\alpha d_{\max}))}$ with $\alpha \geq 1$. Suppose there is a decomposition $\tilde{U}=\prod_{j=0}^{p-1} \hat{U}_j$ approximating $\hat{U}$ up to an error $\epsilon>0$ in spectral norm, where each $\hat{U}_j$ is a diagonal unitary acting on $k_j\leq n$ qubits. Then, the quantum circuit defined Fig. <ref>[without the measurement.] is an $(\alpha d_{\max}, k+p, \epsilon)$-block-encoding of $\hat{D}$, where $k=\sum_{j=1}^{p-1}k_j$.

The proof is presented in Appendix <ref>.

In terms of complexity, copying the ancilla qubit $\ket{q_A}$ always requires less controlled-not gates than copying the main register.  Additionally, controlling an operator $\hat{U}_j$ has the same asymptotic cost than implementing $\hat{U}_j$: remark that for any operator of the form $\hat{V}^{-1}\hat{U}\hat{V}$, the controlled operation is given by $C(\hat{V}^{-1}\hat{U}\hat{V})=\hat{V}^{-1}C(\hat{U})\hat{V}$. Therefore, if $\hat{U}_j$ is a sequential operator given by Eq. (<ref>), one only needs to transform the $(n-1)$-controlled phase gate into a $n$-controlled phase gate and if $\hat{U_j}$ is a Walsh-Hadamard operator given by Eq. (<ref>), one only needs to control the $\hat{R}_{Z}$ gates. As a consequence, the asymptotic cost in terms of size and depth of implementing a diagonal operator $\hat{D}$ is directly given by the cost of implementing the unitary $e^{ i \arcsin(\hat{D}/d_{\max})}$ up to the same error.

§ EFFICIENT-ADJUSTABLE-DEPTH METHODS

In this section, we combine the previous theorems to obtain the overall complexities for the efficient-adjustable-depth quantum circuits for unitary and non-unitary diagonal operators without exponential scalings.

§.§ Unitary and non-unitary diagonal operators defined in terms of smooth functions

Consider a diagonal unitary $\hat{U}=\sum_{x=0}^{N-1} e^{if(x/N)}\ket{x}\bra{x}$ defined in terms of a smooth, at least differentiable, function $f$. For each decomposition of $\hat{U}$, sequential or Walsh-Hadamard, the combination of the adjustable-depth Theorem <ref> or the fully parallelized Theorem <ref> gives three possibilities: without ancilla, adjustable-depth with a given number $p>0$ of ancilla and fully parallelized. Then, the efficiency is achieved by approximating the diagonal unitary up to an error $\epsilon>0$ using Theorem <ref> and the associated method.

For a non-unitary diagonal operator $\hat{D}=\sum_{x=0}^{N-1} f(x/N)\ket{x}\bra{x}$ defined in terms of a smooth, at least differentiable, function $f$, the previous section guarantees that the asymptotic cost of implementing $\hat{D}$ is given by the cost of implementing $\hat{U}=e^{i \arcsin(\hat{D}/(\alpha d_{\max}))}$. The parameter $\alpha>1$ has been introduced to ensure that the function $\arcsin(f/(\alpha \|f\|_{\infty}))$ is differentiable[ $\alpha$ can be taken constant equal to $1.1$ with the only backward of reducing the probability of success by a factor $\alpha^2$.] and that the approximation Theorem <ref> can be applied.

The complexities for each of these methods are presented in Table <ref> and proven in Appendix <ref>.

4|c|Efficient quantum circuit for diagonal operators depending on differentiable functions

Method     Depth     Size     Ancilla

Sequential     $\tilde{\mathcal O}(1/\epsilon)$     $\tilde{\mathcal O}(1/\epsilon)$     $0$ or $1$

Sequential adjustable-depth         $\tilde{\mathcal O}(\frac{1}{\epsilon m}+\log(m))$      $\tilde{\mathcal O}(1/\epsilon+m)$    $m=\Omega(\log(1/\epsilon))$

Sequential fully parallelized     $\mathcal{O}(\log(1/\epsilon))$     $\tilde{\mathcal O}(1/\epsilon)$     $\tilde{O}(1/\epsilon)$

Walsh-Hadamard     $\mathcal{O}(1/\epsilon)$     $\mathcal{O}(1/\epsilon)$     $0$ or $1$

Walsh-Hadamard adjustable-depth         $\tilde{\mathcal O}(\frac{1}{\epsilon m}+\log(m))$      $\tilde{\mathcal O}(1/\epsilon+m)$    $m=\Omega(\log(1/\epsilon))$

Walsh-Hadamard fully parallelized      $\mathcal{O}(\log(1/\epsilon))$     $\tilde{\mathcal O}(1/\epsilon)$     $\tilde{\mathcal O}(1/\epsilon)$

Walsh-recursive        $\mathcal{O}(\frac{1}{\epsilon\log(1/\epsilon)})$     $\mathcal{O}(1/\epsilon)$     $0$ or $\mathcal{O}(\log(1/\epsilon))$

Walsh-optimized adjustable-depth      $\mathcal{O}(\frac{1}{\epsilon m}+\log m)$     $\tilde{\mathcal O}(1/\epsilon+m)$     $ m=\Omega(\log(1/\epsilon)) $

Walsh-optimized fully parallelized     $\mathcal{O}(\log(1/\epsilon))$     $\mathcal{O}(1/\epsilon)$     $\mathcal{O}(\frac{1}{\epsilon\log(1/\epsilon)})$

Table of depth, size and $m$-ancilla qubits for different efficient quantum circuits to implement, up to an error $\epsilon>0$ in spectral norm, $n$-qubit unitary and non-unitary diagonal operators associated to real-valued function $f$ with bounded first derivative. All the scalings are proven in Appendix <ref> for diagonal unitaries and in Appendix <ref> for non-unitary diagonal operators. The notation $\tilde{\mathcal O}(\cdot)$ stands for $\mathcal{O}(\cdot)$ up to a polylogarithmic factor.

The last three lines of the Table <ref> are obtained by using the approximation Theorem <ref> and the block-encoding Theorem <ref> with the exact methods developed in <cit.>. When no ancilla qubits are available, they provide a recursive scheme for diagonal unitaries with a complexity which is optimal in terms of depth as $\mathcal{O}(2^n/n)$. However, the size is not optimal and is only bounded by $2^{n+3}+\mathcal{O}(\log(n^2/\log(n)))$ (Lemma 24 of <cit.>). A second method uses a number $2n \leq m \leq 2^n/n$ of ancilla qubits to parallelize the Walsh operators in an order which optimizes the number of CNOT gates, achieving a depth $\mathcal{O}(2^n/m+\log(m))$ and a size $\mathcal{O}(2^n)$ (Lemma 10 in <cit.>).

§.§ Sparse unitary and non-unitary diagonal operators

Sparsity makes diagonal operators efficiently implementable. Sparse diagonal operators either possess $s$ eigenvalues different from unity, or they are made of a product of $s$ Walsh operators $\hat{W}_j$ defined in Eq. (<ref>). Using the full parallelization Theorem <ref> and the adjustable-depth Theorem <ref>, we summarize all the complexities to implement sparse diagonal operators be it unitary or non-unitary in Table <ref>.

4|c|Efficient quantum circuit for sparse diagonal operators

Method     Depth     Size     Ancilla

Sequential no ancilla exact    $\mathcal O (ns)$     $\mathcal O (ns)$     0 or 1

Sequential no ancilla approximated     $\mathcal O(s\log^3(n)\log(\frac{s}{\epsilon}))$     $\mathcal O(ns\log^4(n)\log(\frac{s}{\epsilon}))$     0 or 1

Sequential one ancilla exact     $\mathcal O (s\log^3(n))$     $\mathcal O (ns\log^4(n))$     1 or 2

Sequential Adjustable-depth       $\mathcal{O}(\frac{s\log^3(n)}{ (m/n)}+\log(m/n))$      $\mathcal{O}(ns\log^4(n)+m)$    $m =\Omega(n)$

Sequential fully parallelized     $\mathcal{O}(\log(s)+\log^3(n))$     $\mathcal{O}(ns)$     $\mathcal{O}(ns)$

Walsh no ancilla      $\mathcal{O}(sk)$     $\mathcal{O}(sk)$     0 or 1

Walsh Adjustable-depth        $\mathcal{O}(\frac{sk}{(m/k)}+\log(m/k))$      $\mathcal{O}(sk+m)$    $m =\Omega(k)$

Walsh fully parallelized     $\mathcal{O}(k+\log(s))$     $\mathcal{O}(sk)$     $\mathcal{O}(sk)$

Table of depth, size and $m$-ancilla qubits for different quantum circuits implementing unitary or non-unitary $n$-qubit diagonal operators with sparse decompositions. $s$ is the number of sequential or Walsh-Hadamard operators in the decomposition of the diagonal operator. All scalings are proven in Appendix <ref> for diagonal unitaries and Appendix <ref> for non-unitary diagonal operators.

Sparse Walsh-Hadamard decompositions are particularly efficient to implement diagonal unitaries depending on real-valued functions with bounded first derivative see Fig. <ref> and Fig. <ref> or for bounded piecewise continuous functions (see Appendix A 3 in <cit.>). In particular, to reach a given accuracy, sparse Walsh-Hadamard decompositions are often more efficient than $M$-Walsh series (presented in Table <ref>) when the most significant Walsh coefficients are implemented before the others.

§ AMPLITUDE AMPLIFICATION AND NON-DESTRUCTIVE REPEAT-UNTIL-SUCCESS PROTOCOLS

Amplitude amplification enables to increase the probability of success of performing a non-unitary diagonal operator $\hat{D}$ on a given state $\ket{\psi}$. When the cost of preparing the state $\ket{\psi}$ from $\ket{0}^{\otimes n}$ is not prohibitively high, one can perform the usual amplitude amplification protocol <cit.>, otherwise one can perform either the oblivious amplitude amplification protocol <cit.> or a repeat-until-success scheme where, at each failure, the “wrong” state is corrected to become the “good” state up to a new probability of success.

The amplitude amplification protocol increases the probability of success of measuring the ancilla qubit in state $\ket{1}$ by making repeated reflexions composed of the unitary $\hat{U}_\psi$ preparing the state $\ket{\psi}$ from $\ket{0}^{\otimes n}$ and of the unitary $\hat{U}_D$ which block-encodes $\hat{D}$. Considering the final state $\ket{\phi}=\hat{U}_D\ket{\psi}\otimes \ket{0}_{q_A}=\hat{U}_D(\hat{U}_\psi\otimes \hat{I}_2)\ket{0}^{\otimes n} \otimes \ket{0}_{q_A}$ defined in Eq. (<ref>), the amplitude amplification protocol is composed of $\hat{U}_{\phi}=\hat{I}-2\ket{\phi}\bra{\phi}$ and $\hat{U}_P=-(\hat{I}-2\hat{P})$ with $\hat{P}$ the projector on the good subspace:  $\hat{P}=\hat{I}_2\otimes\cdots\otimes \hat{I}_2 \otimes \ket{1}_{q_A}\bra{1}_{q_A}$. The unitary $\hat{U}_{\phi}$ can be rewritten as $\hat{U}_{\phi}=\hat{U_D}^{-1}(\hat{U_ \psi}^{-1}\otimes \hat{I}_2)\Lambda_{1,...,n\rightarrow q_A}(-\hat{Z})(\hat{U_\psi}\otimes \hat{I}_2)\hat{U_D}$ with $\Lambda_{1,...,n\rightarrow q_A}(-\hat{Z})$ an anti-controlled minus $\hat{Z}$-Pauli gate and

$\hat{U}_P=\hat{I}_2\otimes\cdots\otimes \hat{I}_2 \otimes (-\hat{Z})$. The scheme of the quantum circuit associated to a step of amplitude amplification is shown on Fig. <ref>. The number $k$ of steps needed to perform the amplitude amplification is given by $k=\lfloor \pi/(4\beta) \rfloor$ with $\beta=\arcsin(\sqrt{\mathbb{P}(1)})$. The number $k$ can be estimated from $\mathbb{P}(1)$ using one of the formula $(\ref{eq: proba success}, \ref{eq: proba of success continue}, \ref{eq: proba success sparse})$. In the case where the diagonal unitary and the qubit state are associated to continuous functions, the number of amplitude amplification steps needed to reach $\mathbb{P}(1)\simeq 1$ is asymptotically independent of the number of qubits $n$. The amplitude amplification protocol is illustrated Fig. <ref> for the quantum state preparation of Gaussian states proving numerically that the probability of success reaches $\mathbb{P}(1)\simeq 1$ in a number $k=\lfloor \pi/(4\beta) \rfloor$ of steps.

$\ket{q_A}$     -Ẑ[6,steps=6,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]Amplitude amplification step     [6,nwires=4]Û_D^†        -Ẑ         [6,nwires=4]Û_D

$\ket{q_0}$           [5,nwires=3]Û_ψ^†     -1    [5,nwires=3]Û_ψ

$\ket{q_1}$               -1

⋮    ⋮    ⋮    ⋮    ⋮    ⋮    ⋮

$\ket{q_{n-2}}$               0

$\ket{q_{n-1}}$               -1
Quantum circuit for amplitude amplification. Note that for QSP, operator $\hat{U}_\psi$ is an Hadamard tower on the register $\ket{q}$, i.e., $\hat{U}_\psi= \hat{H}^{\otimes n}$. Operator $\hat{U}_D$ is the block-encoding of the non-unitary diagonal operator $\hat{D}$.

Conversely, a repeat-until-success protocol is relevant when the cost of preparing the state $\ket{\psi}$ from $\ket{0}^{\otimes n}$ is prohibitively high.  Here we propose a non-destructive repeat-until-success protocol: consider the diagonal unitary  $e^{i\arcsin(\hat{D}/(\alpha  d_{\max}))}$ where a constant parameter $\alpha>1$ ensures that the failure operator  $\hat{D}'=\sqrt{\hat{I}-(\hat{D}/(\alpha d_{\max}))^2}$ is invertible. If a failure occurs, one can implement the non-unitary diagonal operator $\hat{D}(\hat{D}'^{-1})$ using the unitary operator  $e^{i\arcsin(\hat{D}(\hat{D}'^{-1})/(\alpha d_{\max}'))}$ with $d_{\max}'=\max_{i=0,...,N-1}|d_i|/(\sqrt{1-(d_i/(\alpha d_{\max}))^2})$. Applying this operator on the state $\frac{\hat{D}'\ket{\psi}}{\| \hat{D}'\ket{\psi} \|}$ leads to the target state $\frac{\hat{D}\ket{\psi}}{\| \hat{D}\ket{\psi} \|}$ with  a probability of success $\mathbb{P}'(1)=\frac{\| \hat{D}\ket{\psi}\|^2 }{\alpha^2 d_{\max}'^2 \| \hat{D'}\ket{\psi} \|^2}$. This protocol can be implemented until a success is reached, avoiding destroying and preparing again the state $\ket{\psi}$. Figure <ref> illustrates this protocol for the quantum state preparation of Gaussian states, showing that the probability of success after $k$ failures reaches a constant value. Therefore, the average number of failures is finite and can be estimated numerically.

§ APPLICATIONS

We apply the methods previously presented to two problems. The first one is the quantum state preparation problem for which we improve the current state of the art of preparing qubit-state depending on continuous, differentiable function $f$ and we provide new methods with space-time-accuracy trade-offs. The second major application is the resolution of partial differential equation where the associated evolution operator is implementable using diagonal operators and the Quantum Fourier Transform. As an example, we solve the diffusion equation, also called heat equation, which possesses a non-unitary evolution.

§.§ Quantum State Preparation

The quantum state preparation problem consists in loading a set of classical data $\{y_x\}_{x=0}^{2^n-1}$ into a $n$-qubit state $\ket{\psi}=\frac{1}{\mathcal{N}}\sum_{x=0}^{2^n-1}y_x\ket{x}$  up to a normalization factor $\mathcal{N}$. In the following we provide an efficient quantum state preparation algorithm for $n$-qubit states depending on a differentiable function $f$ is defined by:

\begin{equation}
\ket{f}=\frac{1}{||f||_{2,N}}\sum_{x=0}^{N-1} f(x/N)\ket{x},
\label{eq: target state}
\end{equation}

with $||f||_{2,N}=\sqrt{\sum_{x=0}^{N-1} |f(x/N)|^2}$ and $N=2^n$.
Now, consider the non-unitary operator $\hat{D}=\sum_{x=0}^{N-1}f(x/N)\ket{x}\bra{x}$. The quantum state preparation can be performed by implementing $\hat{D}$ with one of the method previously presented Table <ref> and applying $\hat{D}$ on the uniform superposition of all states $\ket{s}=\hat{H}^{\otimes n} \ket{0}^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}$. The following Theorem summarizes this result:

Let $f$ be a real-valued differentiable function in $L^2([0,1])$, $n$ the number of qubits and $\epsilon>0$. There is a quantum circuit that efficiently prepare the state $\ket{f}$ defined in Eq. (<ref>) up to an infidelity $\epsilon>0$ using $p\geq 1$ ancilla qubits with a depth scaling at worst as $\mathcal{O}(1/(p\sqrt{\epsilon})+\log(p))$, size $\mathcal{O}(n+1/(p\sqrt{\epsilon}))$ and a probability of success $\mathbb{P}(1)=\|f\|_{2,[0,1]}^2/\|f\|^2_\infty=\Theta(1)$.

This theorem is a direct consequence of the scaling given in Table <ref>. The associated quantum circuits are the same as the one for the non-unitary diagonal operator. Only a one-depth layer of $n$ Hadamard gates needs to be added to prepare the uniform  superposition $\ket{s}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}$. The probability of success is given by Eq. (<ref>) for the uniform function $g=1$ and $\mathbb{P}(1)=\|f\|_{2,[0,1]}^2/\|f\|^2_\infty=\Theta(1)$.

In the case of a small probability of success, one can still perform a constant number $k=\lfloor \pi/(4\arcsin (\sqrt{\mathbb{P}(1)})) \rfloor$ of amplitude amplification steps to reach $\mathbb{P}(1)\simeq 1$.

In Figure <ref>, the quantum state preparation of Gaussian states is performed and the probability of success is presented as a function of the number of qubits, showing an independent of $n$ limit. The amplitude amplification protocol is also illustrated, proving numerically the efficiency of our method. The space-time trade-off is illustrated in Fig. <ref> for an exact Walsh-Hadamard decomposition, an approximate one using a $M$-Walsh series and using a sparse Walsh series. The trade-off is particularly efficient for a small number of ancilla where one diminishes by several order the depth of the circuits. Note that increasing the number of ancilla qubits, increases the cost of the copy operations as well. As a consequence, for a large number of ancilla qubits, adding some ancilla qubits may not improve anymore the depth of the circuit. The trade-off between time and accuracy is illustrated in Fig. <ref> for the quantum state preparation of Gaussian states. The infidelity of the prepared states decreases with the number of operators one implements as stated in the approximation Theorem <ref>. Furthermore, sparse Walsh-Hadamard decomposition allows to reach a given infidelity with smaller depth quantum circuits than $M$-Walsh Series.

In <cit.>, $n$-qubit states are implemented using the Taylor expansion of the operator $\hat{I}-e^{i\hat{f}\epsilon_0} \simeq \hat{f}\epsilon_0$ with $\hat{f}=\sum_{x=0}^{2^n-1}f(x)\ket{x}\bra{x}$. In comparison, the methods presented here implement directly $\hat{f}$ using $e^{\pm i \arcsin(\hat{f}/(\alpha f_{\max}))}$ avoiding an additional error coming from the Taylor expansion. Theorem <ref> also improves the probability of success which is scaling with $\epsilon$ in <cit.> while here it reaches a constant value.

Quantum state preparation (upper-left) of Gaussian state $f(x)\propto e^{-0.5(x-0.5)^2/\sigma^2}$ for $\sigma=0.05, 0.1$ and $0.15$ on $n=12$ qubits using respectively $s=30, 45, 90$ of Walsh-Hadamard operators with 2-norm error between the qubit state and the target state of $0.0054, 0.0052, 0.0054$  respectively. Probability of success of the QSP protocol as a function of the number of qubits (upper right), as a function of the number of the number of amplitude amplification steps (lower left) and probability of success after $k$ failures for the non-destructive repeat-until-success scheme (lower right). The numerical values of $\mathbb{P}(1)$ reach their theoretical asymptotic limit $\|f\|^2_{L^2}/ \|f\|_{\infty}^2$  even for a small number of qubits and the number of amplitude amplification steps needed to reach the first pic of probability verify $k=\lfloor \pi/(4\arcsin (\sqrt{\mathbb{P}(1)})) \rfloor = 1, 1, 2$ respectively. For the non-destructive repeat-until-success scheme, the average number of failures before reaching a success are $6, 10, 22$ respectively.

Depth as a function of the number of ancilla qubits for the quantum state preparation of a Gaussian state $f(x)\propto e^{-0.5(x-0.5)^2/\sigma^2}$ with $\sigma=0.1$ on $n=10$ qubits for three different Walsh-Hadamard decompositions: exact with $2{10}$ operators, approximate with $2^8$ operators and an infidelity $1-F=5.96\times10^{-5}$ and sparse with 70 Walsh-Hadamard operators and an infidelity $1-F=6.06\times10^{-5}$.

Infidelity as a function of the depth of the quantum circuit associated to the quantum state preparation of Gaussian states $f(x)\propto e^{-0.5(x-0.5)^2/\sigma^2}$ with $\sigma=0.05, 0.1, 0.15$ on $n=12$ qubits without ancilla qubits. The dots from upper left to lower right correspond to the $M$-Walsh Series with $M=2^m$ Walsh-Hadamard operators (full lines) and to the sparse Walsh Series composed of the $2^m$ Walsh-Hadamard operators with the largest coefficients in absolute value with $m=2,3,\hdots,10$.

§.§ Real-space simulation of the Heat equation

As an illustration of the methods presented in this article, we solve the following one-dimensional diffusion equation for a given initial condition $f_0$ defined on $[0,1]$ and a constant diffusion coefficient $\kappa$:

\begin{equation}
\partial_t f = \kappa \partial_{xx} f,
\label{eq : heat equation}
\end{equation}

where $f$ is a function of the time $[0,T]$ and space $[0,1]$. For simplicity, we consider periodic boundary conditions. The numerical resolution is based on a real-space simulation where the space $[0,1]$ of the simulation is discretized into $N$ equi-length intervals. The spatial derivatives are discretized using a central finite difference $\partial_x f \rightarrow \frac{f(x+\Delta x)-f(x-\Delta x)}{2\Delta x}$ with $\Delta x=1/N$ the length of a space interval.

The real space encoding consists in approximating the solution $f$ of Eq. (<ref>) at the $N=2^n$ spatial points $\mathcal{X}_n=\{0,1/N,...,(N-1)/N\}$ and at each time $t>0$ by an $n$-qubit state $\ket{\tilde{f}}_t$ solution of the discretized diffusion equation:

\begin{equation}
\begin{split}
\partial_t \ket{\tilde{f}}_t &= \kappa\frac{(\hat{S}-\hat{S}^\dagger)^2}{4\Delta x^2} \ket{\tilde{f}}_t \\
\ket{\tilde{f}}_{t=0}&=\ket{f_0}
\end{split},
\end{equation}

where $\frac{(\hat{S}-\hat{S}^\dagger)^2}{4\Delta x^2}$ is the discretized Laplacian operator with $\hat{S}=\sum_{x\in \mathcal{X}_n}\ket{x+1}\bra{x}$ the shift operator, also called increment operator[with $\ket{n+1}=\ket{0}$ due to the periodic boundary conditions.]. The solution $\ket{\tilde{f}}_t$ is given by the evolution operator applied on the initial condition $\ket{f_0}$:

\begin{equation}
\ket{\tilde{f}}_t=e^{\frac{\kappa t }{4\Delta x^2} (\hat{S}-\hat{S}^\dagger)^2}\ket{f_0}.
\end{equation}

The evolution operator of the diffusion equation can be diagonalized in Fourier space using the Quantum Fourier Transform <cit.> thanks to the fact that the shift operators are circulant matrices which are diagonal in Fourier space <cit.>. The diagonal operator is non-unitary and depends on a smooth function $f(x)=e^{-\frac{\kappa}{\Delta x^2} \sin(2\pi x)^2 t}$, so the evolution is given by:

\begin{equation}
\ket{\tilde{f}}_t=\widehat{QFT}^{-1}e^{-\frac{\kappa t}{\Delta x^2} \sin(2\pi \hat{x})^2 }\widehat{QFT}\ket{f_0},
\label{eq: solution quantum numerical}
\end{equation}

where $\hat{x}=\sum_{x\in \mathcal{X}_n}x\ket{x}\bra{x}$ is the position operator.

The initial condition $\ket{f_0}$ is encoded in an $n$-qubit state thanks to the QSP protocol presented in the previous section (Theorem <ref>) and the non-unitary diagonal operator is implemented using a sequential decomposition. Figure <ref> presents an $n=10$-qubit simulation where the initial Gaussian state $f_0(x)=e^{-0.5(x-0.5)^2/\sigma^2}$ with $\sigma=0.1$  evolves through the heat equation. The amplitude of the numerical solution $\ket{\tilde{f}}_t$ is shown as a function of the position for different times $t$ and compared with the analytical solution $f$ of Eq. (<ref>) computed as a Fourier Series:

\begin{equation}
f(x,t)=\sum_{q=0}^{+\infty}e^{-4\kappa q^2 \pi^2t} (\alpha_q \cos(2q\pi (x-0.5))+\beta_q \sin(2q\pi (x-0.5))),
\label{eq: analytical solution}
\end{equation}

with the Fourier coefficients, for $q\ge 1$:

\begin{equation}
\begin{split}
\alpha_q &= 2\int_0^1 f_0(x)\cos(2q\pi (x-0.5)) \textrm{d}x \\
\beta_q &= 2\int_0^1 f_0(x)\sin(2q\pi (x-0.5)) \textrm{d}x
\end{split},
\end{equation}

and $\alpha_0=\int_0^1 f_0(x)\textrm{d}x$, $\beta_0=0$.

The number of sequential operators needed for the simulation is very small (14, 8, 6 and 1) due to the particular structure of the non-unitary evolution operator which is increasingly sparse with the time $t$ (in Fourier space).

Resolution of the heat equation at given times $t$ by computing the $n=8$ qubit state given by Eq. (<ref>) (dashed lines) and comparison with the analytical solution (full line) given by Eq. (<ref>) for an initial condition $f_0(x)=e^{-0.5(x-0.5)^2/\sigma^2}$ for $\sigma=0.1$. The number of sequential operators used in the implementation of the non-unitary diagonal operator is $s=14,8,6,1$ respectively for time $t=0.005,0.02,0.05,1$. The infidelity between the analytical solution and the implemented qubit states are $1-F=8.5\times10^{-4}, 1.8\times10^{-3}, 3.1\times10^{-4}, 3.5\times10^{-4}, 1.7\times10^{-15}$ respectively for time $t=0.005,0.02,0.05,1$.

§ CONCLUSION

In conclusion, efficient quantum circuits for unitary and non-unitary diagonal operator exist when the diagonal operators have some structure (depending on differentiable functions or sparse). The quantum circuits we introduced offer trade-offs between the depth, the number of ancilla qubits and the error between the implemented operator and the target one. These particular properties enable the user to design quantum circuits adjusted to the characteristic of the hardware, such as the coherence time of the qubits, the number of available qubits or the cumulative error per gate. Numerical evidence show that these results are generalizable to diagonal operators depending on bounded, continuous functions even when the function is not differentiable <cit.> but additional work remains to prove it. Also, current work investigates how to apply these quantum circuits to other partial differential equations.

§ ACKNOWLEDGEMENTS

The authors would like to thank G.Di Molfetta, B.Claudon and C.Feniou for their useful feedbacks on the form and content of this manuscript. The quantum circuit diagrams were generated with the quantikz package <cit.>. U.Nzongani acknowledges support from the PEPR EPiQ ANR-22-PETQ-0007, by the ANR
JCJC DisQC ANR-22-CE47-0002-01.

§ EXAMPLES OF QUANTUM CIRCUITS

In this section, illustrative examples of quantum circuits are presented for both the sequential and Walsh-Hadamard decompositions with $n=3$ qubits. First, the non-optimized circuits are displayed, then the optimize one with a Gray code ordering to reduce the number of gates. Finally, the quantum circuit associated to the parallelization scheme, shown on Fig. <ref>, with $p=3$ ancilla qubits is presented.
Consider the $3$-qubit diagonal unitary:

\begin{equation}
\hat{U}_\theta=e^{i\hat{\theta}}=
\begin{pmatrix}
e^{i\theta_0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & e^{i\theta_1} & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & e^{i\theta_2} & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & e^{i\theta_3} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & e^{i\theta_4} & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & e^{i\theta_5} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & e^{i\theta_6} & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & e^{i\theta_7}
\end{pmatrix},
\end{equation}

where each $e^{i\theta_x}$ corresponds to the eigenvalue of basis state eigenvector $\ket{x}$. The main register of the following quantum circuits is $\ket{q=q_{n-1}\dots q_1q_0}$ where $q_i\in\{0,1\}$ and $q=\sum_{j=0}^{n-1}q_j2^j$.

§.§ Sequential decomposition

The sequential decomposition of diagonal unitaries leads to quantum circuits composed of multi-controlled phase and NOT gates. Figure <ref> gives an example of an exact decomposition of an arbitrary $3$-qubit diagonal unitary where the multi-controlled gate are implemented in decimal ordering.

$\ket{q_0}$          P̂_0              P̂_1              P̂_2              P̂_3              P̂_4              P̂_5              P̂_6          P̂_7     [3]$e^{i\hat{\theta}}\ket{q}$

$\ket{q_1}$          -1               -1              -1             -1              -1               -1              -1         -1

$\ket{q_2}$          -1              -1               -1               -1              -1             -1             -1         -1

Sequential decomposition without Gray code for $n=3$ qubits with the phase gates $\hat{P}_x=\hat{P}(\theta_x)=\begin{pmatrix}
1 & 0 \\ 0 & e^{i\theta_x}
\end{pmatrix}$ with $x\in [0,7]$.

A significant number of NOT gates cancel out. One can use a Gray code <cit.> to maximise the number of cancellation. The Gray code, also called reflected binary code, was first introduced by Frank Gray in 1953. It is a way to enumerate a set of binary element such that the Hamming distance of two neighboring element is equal to 1, i.e., there is only a one bit difference between two neighboring bit strings. For instance, the 3-bits Gray code is shown on Table <ref>.

Decimal with Gray code ordering     Binary representation

0     000

1     001

3     011

2     010

6     110

7     111

5     101

4     100

3-bits Gray code.

The quantum circuit implementing an arbitrary $3$-qubit diagonal unitary using a Gray code ordering is represented Fig. <ref>.

$\ket{q_0}$          P̂_0          P̂_1         P̂_3          P̂_2         P̂_6          P̂_7         P̂_5          P̂_4          [3]$e^{i\hat{\theta}}\ket{q}$

$\ket{q_1}$          -1         -1          -1         -1         -1         -1          -1         -1

$\ket{q_2}$          -1         -1         -1         -1          -1         -1         -1         -1

Sequential decomposition with Gray code for $n=3$ qubits the phase gates $\hat{P}_x=\hat{P}(\theta_x)=\begin{pmatrix}
1 & 0 \\ 0 & e^{i\theta_x}
\end{pmatrix}$ with $x\in [0,7]$.

Lastly, we show the quantum circuit implementing the adjustable-depth sequential decomposition of $e^{i\hat{f}}$ on Fig. <ref>.

$\ket{q_0}$     3[6,steps=3,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]$\widehat{\text{copy}}$                  P̂_0          P̂_1         P̂_3          P̂_2          [6,steps=3,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]$\widehat{\text{copy}}^{-1}$        3     [3]$e^{i\hat{f}}\ket{q}$

$\ket{q_1}$         3              -1         -1          -1         -1             3

$\ket{q_2}$             3          -1         -1         -1         -1          3

$\ket{q'_0=0}$                       P̂_6          P̂_7         P̂_5          P̂_4                       $\ket{q'_0=0}$

$\ket{q'_1=0}$                      -1         -1          -1         -1                       $\ket{q'_1=0}$

$\ket{q'_2=0}$                      -1         -1        -1        -1                      $\ket{q'_2=0}$

Adjustable-depth quantum circuit implementing the sequential decomposition with Gray code for $n=3$ qubits with $p=3$ ancilla qubits.

§.§ Walsh-Hadamard decomposition

Diagonal unitaries can be exactly implemented as a product of Walsh-Hadamard decomposition $\hat{U}=\prod \hat{W}_j$ is implemented with a quantum circuit composed of CNOT and $\hat{R}_Z$ gates. Its naïve form is shown on Fig. <ref>.

$\ket{q_0}$     e^ia_0Î     R̂_1         1         1         2         2                 2                 2         [3]$e^{i\hat{\theta}}\ket{q}$

$\ket{q_1}$             R̂_2          R̂_3                          1         1         1         1

$\ket{q_2}$                             R̂_4          R̂_5               R̂_6                    R̂_7

Walsh decomposition with no Gray code for $n=3$ qubits with $\hat{R}_x\equiv \hat{R}_Z(-2a_x)$ with $x\in [1,7]$. This circuit is shown on Fig. 5 of <cit.>. The first gate corresponds to the global phase gate $e^{ia_0} \hat{I}=\begin{pmatrix}
e^{ia_0} & 0 \\ 0 & e^{ia_0}
\end{pmatrix}$.

As with the sequential decomposition, the number of CNOTs can be reduced by changing the order of the operator using Gray code <cit.>. The obtained circuit is shown on Fig. <ref>.

$\ket{q_0}$     e^ia_0 Î     R̂_1     1         1                 2                 2             [3]$e^{i\hat{\theta}}\ket{q}$

$\ket{q_1}$                  R̂_3          R̂_2     1                 1

$\ket{q_2}$                                  R̂_6          R̂_7          R̂_5          R̂_4

Walsh decomposition with Gray code for $n=3$ qubits with $\hat{R}_x\equiv \hat{R}_Z(-2a_x)$ with $x\in [1,7]$. This circuit is shown on Fig. 5 of <cit.>. The first gate corresponds to the global phase gate $e^{ia_0} \hat{I}=\begin{pmatrix}
e^{ia_0} & 0 \\ 0 & e^{ia_0}
\end{pmatrix}$.

Finally, we show the quantum circuit implementing the adjustable-depth Walsh-Hadamard decomposition of $e^{i\hat{f}}$ on Fig. <ref>.

$\ket{q_0}$     3[6,steps=3,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]$\widehat{\text{copy}}$             e^ia_0Î     R̂_1     1         1                 [6,steps=3,style=dashed,rounded corners,color=blue,inner xsep=2pt,background]$\widehat{\text{copy}}^{-1}$         3         [3]$e^{i\hat{\theta}}\ket{q}$

$\ket{q_1}$         3                      R̂_3          R̂_2                 3

$\ket{q_2}$             3                                     3

$\ket{q'_0=0}$                          2                 2                          $\ket{q'_0=0}$

$\ket{q'_1=0}$                  1                 1                                  $\ket{q'_1=0}$

$\ket{q'_2=0}$                       R̂_6          R̂_7          R̂_5          R̂_4                      $\ket{q'_2=0}$

Adjustable-depth quantum circuit implementing the Walsh decomposition with Gray code for $n=3$ qubits with $p=3$ ancilla qubits.

§ PROOF OF THEOREM <REF>

Consider a decomposition $\tilde{U}=\prod_{j=0}^{p-1} \hat{U}_j$ where each $\hat{U}_j$ acts on $k_j\leq n$ qubits and consider a number $k+p$ ancilla qubits, with $k=\sum_{j=1}^{p-1}k_j$. The registers of ancilla qubits are denoted by $R_1,\hdots, R_{p-1}$ and each $R_j $ contains $k_j$ qubits that will serve to copy only the qubits on which $\hat{U}_j$ is acting non-trivially. The register $R_{q_A}$ contains $p-1$ qubits on which $q_A$ will be copied.
The proof of correctness of the quantum circuit Fig. <ref> starts by considering a state $\ket{x}$ of the computational basis of the main register. For simplicity, tensor products between the qubit states and tensor products with identity operators are omitted:

\begin{equation}
\begin{split}
&\ket{x} \ket{0}^{\otimes k} \ket{0}_{q_A} \ket{0}^{\otimes (p-1)}  \\ &\xrightarrow{\hat{H}}  \ket{x} \ket{0}^{\otimes k} \frac{1}{\sqrt{2}}(\ket{0}_{q_A}+\ket{1}_{q_A}) \ket{0}^{\otimes (p-1)} \\
&\xrightarrow{\widehat{\text{copy}}_{R\rightarrow R_1\cup \hdots \cup R_{p-1}} \otimes \widehat{\text{copy}}_{q_A\rightarrow R_{q_A} }}
\ket{x} \ket{\tilde{x}_1}\hdots \ket{\tilde{x}_{p-1}}  \frac{1}{\sqrt{2}}(\ket{0}^{\otimes p}+\ket{1}^{\otimes p}) \\
&\xrightarrow{\bigotimes_{j=0}^{p-1} \hat{C}_{\bar{q}_j\rightarrow R_j}(\hat{U}_j)} \frac{1}{\sqrt{2}}(\hat{U}_0\ket{x} \hat{U}_1 \ket{\tilde{x}_1}\hdots \hat{U}_{p-1}\ket{\tilde{x}_{p-1}}\ket{0}^{\otimes p}\\&+\ket{x} \ket{\tilde{x}_1}\hdots \ket{\tilde{x}_{p-1}}\ket{1}^{\otimes p}) \\
&\xrightarrow{\bigotimes_{j=0}^{p-1} \hat{C}_{q_j\rightarrow R_j}(\hat{U}_j^{\dagger})}
\frac{1}{\sqrt{2}}(\hat{U}_0\ket{x} \hat{U}_1 \ket{\tilde{x}_1}\hdots \hat{U}_{p-1}\ket{\tilde{x}_{p-1}}\ket{0}^{\otimes p}\\&+\hat{U}_0^{\dagger}\ket{x} \hat{U}_1^{\dagger}\ket{\tilde{x}_1}\hdots \hat{U}_{p-1}^{\dagger}\ket{\tilde{x}_{p-1}}\ket{1}^{\otimes p}) \\
= \frac{1}{\sqrt{2}}(e^{i\tilde{\theta}_x}\ket{x} \ket{\tilde{x}_1}\hdots\ket{\tilde{x}_{p-1}}\ket{0}^{\otimes p}+e^{-i\tilde{\theta}_x}\ket{x}  \ket{\tilde{x}_1}\hdots \ket{\tilde{x}_{p-1}}\ket{1}^{\otimes p}) \\
& \xrightarrow{\widehat{\text{copy}}_{R\rightarrow R_1\cup \hdots \cup R_{p-1}}^{-1} \otimes \widehat{\text{copy}}_{q_A\rightarrow R_{q_A}}^{-1}}  \frac{1}{\sqrt{2}}(e^{i\tilde{\theta}_x}\ket{x} \ket{0}^{\otimes k} \ket{0}_{q_A}+e^{-i\tilde{\theta}_x}\ket{x}  \ket{0}^{\otimes k}\ket{1}_{q_A})\ket{0}^{\otimes(p-1)} \\
& \xrightarrow{\hat{P}\hat{H}} (-i\cos(\theta_x)\ket{x} \ket{0}^{\otimes k} \ket{0}_{q_A}+\sin(\theta_x)\ket{x}  \ket{0}^{\otimes k}\ket{1}_{q_A})\ket{0}^{\otimes(p-1)}
\end{split}
\end{equation}

with $\tilde{\theta}_x=\sum_{j=0}^{p-1} \theta_j(x)$ and $\hat{U}_j=\sum_{x=0}^{N-1}e^{i\theta_j(x)}\ket{x}\bra{x}$. The operator $\hat{C}_{\bar{q}_j\rightarrow R_j}(\hat{U}_j)$ is defined as the unitary $\hat{U}_j$ applied on the register $R_j$ and anti-controlled by the $j$-th qubit of $R_{q_A}$ ($q_0$ denotes $q_A$) and the operator $\hat{C}_{q_j\rightarrow R_j}(\hat{U}_j^{\dagger})$ is defined as the unitary $\hat{U}_j^\dagger$ applied on the register $R_j$ and controlled by the $j$-th qubit of $R_{q_A}$. The unitary $\widehat{\text{copy}}_{R\rightarrow R_1\cup \hdots \cup R_{p-1}}$ corresponds to the copy of main register $R$ into the copy registers $R_1,\hdots, R_{p-1}$ and $\widehat{\text{copy}}_{q_A\rightarrow R_{q_A}}$ corresponds to the copy of $q_A$ into the register $R_{q_A}$.

The unitary $\hat{U}_D$ corresponding to the previous operations (i.e. Fig. <ref>) is a $(\alpha d_{\max},k+p,\epsilon)$-block encoding of $\hat{D}=\sum_{x=0}^N d_x\ket{x}\bra{x}$:

\begin{equation}
\begin{split}
&\|\frac{1}{\alpha d_{\max}}\hat{D}-(\bra{0}^{\otimes k}\bra{1}_{q_A}\bra{0}^{\otimes(p-1)}\otimes \hat{I}_R)\hat{U}_D(\ket{0}^{\otimes k}\ket{1}_{q_A}\ket{0}^{\otimes(p-1)}\otimes \hat{I}_R) \|_2 \\
&=\|\sum_{x=0}^{N-1}\frac{d_x}{\alpha d_{\max}}\ket{x}\bra{x}-\sum_{x=0}^{N-1}\sin(\tilde{\theta}_x)\ket{x}\bra{x} \|_2 \\
&=\max_x \| \frac{d_x}{\alpha d_{\max}}-\sin(\tilde{\theta}_x) \| \leq \epsilon
\end{split}
\end{equation}

The inequality comes from the hypothesis that $\tilde{U}=\sum_{x=0}^N e^{i\tilde{\theta}_x}\ket{x}\bra{x}$ is an $\epsilon$ approximation of $\hat{U}=e^{i\arcsin(\hat{D}/(\alpha d_{\max}))}$ in spectral norm.

§ SCALINGS OF THE DIFFERENT QUANTUM CIRCUITS

§.§ Exact methods

§.§.§ Diagonal unitaries

The following Lemmas and corollaries summarize the complexity of implementing exactly any $n$-qubit diagonal unitary.

Any $n$-qubit diagonal unitary is implementable through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(n2^n)$ and size $\mathcal{O}(n2^n)$ without using ancilla qubits.

The quantum circuit is composed of $2^n$ operator $\hat{U}_j$ defined in Eq. (<ref>). Thanks to the fact that the unitaries $\hat{U}_j$ commute with each other, one can choose the order of implementation of the $\hat{U}_j$ which cancels a maximum number of $\hat{X}$ gates. This is achieved using a Gray code <cit.>: between two following $\hat{U}_j$, $\hat{U}_{j'}$, only one bit changes in the binary decomposition of $j$ and $j'$. This leads to an ordering where only one $\hat{X}$ gate remains between two consecutive $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))$, $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_{j'})$. Then, each of the $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))$ is implemented using the scheme of <cit.> which is an exact scheme with size and depth linear in $n$ without using ancilla qubits.

Any $n$-qubit diagonal unitary is implementable through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(n)^3 2^{n})$ and size $\mathcal{O}(n\log(n)^4 2^{n})$ using one ancilla qubit.

Similarly than previously, the $2^n$ sequential operator $\hat{U}_j$ are implemented in a gray-code order. Then, each of them is implemented with scheme presented in <cit.> which uses one ancilla qubit to achieve a polylogarithmic depth $\mathcal{O}(\log(n)^3)$ to implement any $n$-controlled operations at the cost of a size $\mathcal{O}(n\log(n)^4)$ (see Corollary 1 in <cit.>). Therefore, the overall depth for an exact implementation of a given arbitrary diagonal unitary is $\mathcal{O}(\log(n)^3 2^n)$ and size $\mathcal{O}(n\log(n)^4 2^n)$ using one ancilla qubit.

Any $n$-qubit diagonal unitary is implementable through its Walsh-Hadamard decomposition with a quantum circuit of depth $\mathcal{O}(2^n)$ and size $\mathcal{O}(2^n)$ without using ancilla qubits.

Any $n$-qubit diagonal unitary is implementable through its sequential decomposition with a fully parallelized quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(n2^n)$ using $\mathcal{O}(n2^n)$ ancilla qubits.

Lemma <ref> or lemma <ref> associated to the full parallelization Theorem <ref>.

Any $n$-qubit diagonal unitary is implementable through its Walsh-Hadamard decomposition with a fully parallelized quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(n2^n)$ without using $\mathcal{O}(n2^n)$ ancilla qubits.

Lemma <ref> with the full parallelization Theorem <ref>.

Any $n$-qubit diagonal unitary is implementable through its sequential decomposition with a partially parallelized quantum circuit of depth $\mathcal{O}(n^2 2^n/m+\log(m/n))$ and size $\mathcal{O}(n2^n+m)$ using $ m \in [n, \mathcal{O}(n2^n)]$ ancilla qubits.

Lemma <ref> with the partial parallelization Theorem <ref>.

Any $n$-qubit diagonal unitary is implementable through its sequential decomposition with a partially parallelized quantum circuit of depth $\mathcal{O}(n \log(n)^3 2^n/m+\log(m/n))$ and size $\mathcal{O}(n\log(n)^4 2^n+m)$ using $ m \in [n+2, \mathcal{O}(n2^n)]$ ancilla qubits.

Lemma <ref> with the partial parallelization Theorem <ref>.

Any $n$-qubit diagonal unitary is implementable through its Walsh-Hadamard decomposition with a partially parallelized quantum circuit of depth $\mathcal{O}(n^2 2^n/m+\log(m/n))$ and size $\mathcal{O}( n2^n+m)$  using $ m \in [n, \mathcal{O}(n2^n)]$ ancilla qubits.

Lemma <ref> with the partial parallelization Theorem <ref>.

Any $n$-qubit diagonal unitary can be implemented by a quantum circuit of depth $\mathcal{O}(2^n/n)$ and size $\mathcal{O}(2^n)$ without ancillary qubits.

For any $m\in [2n, 2^n/n]$, any $n$-qubit diagonal unitary can be implemented by a quantum circuit of depth $\mathcal{O}(2^n/m +\log(m))$ and size $\mathcal{O}(2^n+nm)$ with $m$ ancillary qubits.

Any $n$-qubit diagonal unitary can be implemented by a quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(2^n)$ with $m=2^n/n$ ancillary qubits.

§.§.§ Non-unitary diagonal operators

The following corollaries summarize the complexity of implementing exactly a block-encoding $\hat{U}_D$ of any $n$-qubit non-unitary diagonal operator $\hat{D}$ through the controlled-diagonal unitaries $e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ with $\alpha \geq 1$.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},1,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n2^{n})$ and size $\mathcal{O}(n2^{n})$ using one ancilla qubit.

Lemma <ref> and the block-encoding Theorem <ref>.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},2,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(n)^3 2^{n})$ and size  $\mathcal{O}(n\log(n)^4 2^{n})$ using two ancilla qubits.

Lemma <ref> and the block-encoding Theorem <ref>: the $(n-1)$-controlled phase gates are controlled by one ancilla qubit, becoming $n$-controlled phase gates. The last ancilla qubit is used to implement the $n$-controlled phase gates exactly with Corollary 1 of <cit.>.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},1,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(2^n)$ and size  $\mathcal{O}(2^n)$ using one ancilla qubit.

Lemma <ref> and the block-encoding Theorem <ref>

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(n2^{n})$ using $m=\mathcal{O}(n2^n)$ ancilla qubits.

Lemma <ref> or Lemma <ref> associated to the full parallelization Theorem <ref>  and the block-encoding Theorem <ref>

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(n2^{n})$ using $m=\mathcal{O}(n2^n)$ ancilla qubits.

Lemma <ref> with the full parallelization Theorem <ref> and the block-encoding Theorem <ref>.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n^2 2^n/m+\log(m/n))$ and size $\mathcal{O}(n2^n+m)$ using $ m \in [\Omega(n), \mathcal{O}(n2^n)]$ ancilla.

Lemma <ref> with the partial parallelization Theorem <ref> and the block-encoding Theorem <ref>

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n \log(n)^3 2^n/m+\log(m/n))$ and size $\mathcal{O}(n\log(n)^4 2^n+m)$ using $m$ ancilla qubits with $m=\Omega(n)$ and $m=\mathcal{O}(2^n/n)$.

Lemma <ref> with the partial parallelization Theorem <ref> and the block-encoding Theorem <ref>

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n^2 2^n/m+\log(m/n))$ and size $\mathcal{O}(n2^n+m)$ using $m$ ancilla qubits with $m=\Omega(n)$ and $m=\mathcal{O}(2^n/n)$.

Lemma <ref> with the partial parallelization Theorem <ref> and the block-encoding Theorem <ref>.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(2^n/n)$ and size $\mathcal{O}(2^n)$ using $n$ ancilla qubits.

The Lemma 11 <cit.> associated with the block-encoding Theorem <ref> where each $\hat{U}_j$ is not a sequential or Walsh-Hadamard operator, but a primitive quantum gates of the decomposition given by the quantum circuits of <cit.>. Indeed, any $n$-qubit unitary operation with size $s(n)$ and depth $d(n)$ can be controlled by a qubit $q_A$ with size $\mathcal{O}(s(n)+n)$ and depth $d(n)+\mathcal{O}(log(n))$ using $n-1$ copies of $q_A$ to control in parallel the different gates.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(2^n/m +\log(m))$ and size $\mathcal{O}(n2^n)$ using $m$ ancilla qubits with $m=\Omega(n)$ and $m=\mathcal{O}(2^n/n)$.

Lemma 20  <cit.>  associated to the block-encoding Theorem <ref>.

For any $\alpha \geq 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$ can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(n)$ and size $\mathcal{O}(n2^n)$ using $m=\mathcal{O}(2^n/n)$ ancilla qubits.

Lemma 20  <cit.> associated with the block-encoding Theorem <ref>.

§.§ Approximate methods

§.§.§ For diagonal unitaries depending on differentiable functions

In the following, we consider a $n$-qubit diagonal unitary $\hat{U}=\sum_{x=0}^{N-1}e^{if(x/N)}\ket{x}\bra{x}$, with $N=2^n$ depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ without ancilla qubits.

This corollary is a direct consequence of Lemma <ref> and the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(\log(1/\epsilon))^3/\epsilon)$ and size $\mathcal{O}(\log(1/\epsilon)\log(\log(1/\epsilon))^4/\epsilon)$ using one ancilla qubit.

This corollary is a direct consequence of Lemma <ref> and the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its Walsh-Hadamard decomposition with a quantum circuit of depth $\mathcal{O}(1/\epsilon)$ and size $\mathcal{O}(1/\epsilon)$ without ancilla qubit.

This corollary is a direct consequence of Lemma <ref> and the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> associated with the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its Walsh-Hadamard decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> with the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)^2/(\epsilon m)+\log(m/\log(1/\epsilon)))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon+m)$ using $m$ ancilla qubits with  $m=\Omega(\log(1/\epsilon))$ and $m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary <ref> with the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its sequential decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)\log(\log(1/\epsilon))^3/(\epsilon m)+\log(m/\log(1/\epsilon)))$ and size $\mathcal{O}(\log(1/\epsilon)\log(\log(1/\epsilon))^4/\epsilon+m)$ using $m$ ancilla qubits with  $m=\Omega(\log(1/\epsilon))$ and $m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary <ref> with the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm through its Walsh-Hadamard decomposition with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)^2/(\epsilon m)+\log(m/\log(1/\epsilon)))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon+m)$ using $m$ ancilla qubits with  $m=\Omega(\log(1/\epsilon))$ and $m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary  <ref> with the approximate Theorem <ref>.

Any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon>0$ in spectral norm with a quantum circuit of depth $\mathcal{O}(1/(\epsilon \log(1/\epsilon)))$ and size $\mathcal{O}(1/\epsilon)$ without ancilla qubits.

This corollary is a direct consequence of Lemma 11 <cit.> with the approximate Theorem <ref>.

For any $\epsilon>0$, any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon$ in spectral norm with a quantum circuit of depth $\mathcal{O}(1/(\epsilon m)+\log(m))$ and size $\mathcal{O}(1/\epsilon+\log(1/\epsilon)m)$ using $m$ ancilla qubits with $m =\Omega(\log(1/\epsilon))$ and $m=\mathcal{O}(1/(\epsilon \log(1/\epsilon)))$.

This corollary is a direct consequence of Lemma 20 <cit.> with the approximate Theorem <ref>.

For any $\epsilon>0$, any $n$-qubit diagonal unitary depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative is implementable up to an error $\epsilon$ in spectral norm with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(1/\epsilon)$ with $m=\mathcal{O}(1/(\epsilon \log(1/\epsilon)))$ ancilla qubits.

This corollary is a direct consequence of Lemma 20 <cit.> for a maximum number of ancilla qubits with the approximate Theorem <ref>.

§.§.§ For non-unitary diagonal operators depending on differentiable functions

The following corollaries summarize the complexity of implementing approximately a block-encoding $\hat{U}_D$ of a $n$-qubit non-unitary diagonal operator $\hat{D}=\sum_{x=0}^{N-1}f(x/N)\ket{x}\bra{x}$, depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative, through the controlled-diagonal unitaries $e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ with $\alpha > 1$.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using one ancilla qubit.

This corollary is a direct consequence of corollary <ref> applied on $\hat{U}=\sum_{x=0}^{N-1}e^{ig(x/N)}\ket{x}\bra{x}$ with $g(x)=\arcsin(f(x)/(\alpha \|f\|_{\infty}))$ such that $\|g'\|_{\infty}\leq \|f'\|_{\infty}/(\|f\|_{\infty} \sqrt{\alpha^2-1})$ and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(\log(1/\epsilon))^3/\epsilon)$ and size $\mathcal{O}(\log(1/\epsilon)(\log(\log(1/\epsilon))^4/\epsilon)$ using two ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(1/\epsilon)$ and size $\mathcal{O}(1/\epsilon)$ using one ancilla qubit.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using $m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using $m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

This corollary is a direct consequence of corollary  <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)^2/(\epsilon m) +\log(m/\log(1/\epsilon)) )$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon+m)$ using $m$ ancilla qubits with $m=\Omega(\log(1/\epsilon))$ and $ m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary  <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)\log(\log(1/\epsilon))^3/(\epsilon m) +\log(m/\log(1/\epsilon)))$ and size $\mathcal{O}(\log(1/\epsilon)\log(\log(1/\epsilon))^4/\epsilon+m)$ using $m$ ancilla qubits with  $m=\Omega(\log(1/\epsilon))$ and $ m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary  <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon)^2/(\epsilon m) +\log(m/\log(1/\epsilon)))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon+m)$ using $m$ ancilla qubits with $m=\Omega(\log(1/\epsilon))$ and $ m=\mathcal{O}(\log(1/\epsilon)/\epsilon)$.

This corollary is a direct consequence of corollary  <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(1/(\epsilon \log(1/\epsilon) ))$ and size $\mathcal{O}(1/\epsilon)$ using $m=\mathcal{O}(\log(1/\epsilon))$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(1/(\epsilon m)+\log(m))$ and size $\mathcal{O}(\log(1/\epsilon)/\epsilon)$ using $m$ ancilla qubits with $m=\Omega(\log(1/\epsilon))$ and $ m=\mathcal{O}(1/(\epsilon \log(1/\epsilon)))$.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha > 1$, any $n$-qubit non-unitary diagonal operator $\hat{D}$  depending on a real-valued function $f$ defined on $[0,1]$ with bounded first derivative can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(1/\epsilon))$ and size $\mathcal{O}(1/\epsilon)$ using $m=\mathcal{O}(1/(\epsilon \log(1/\epsilon)))$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

§.§ Sparse diagonal operators

§.§.§ Sparse diagonal unitaries

The following Lemmas and corollaries summarize the complexity of implementing any $n$-qubit diagonal unitary with a decomposition containing only $s$ sequential operators or $s$ Walsh-Hadamard operators.

Any $n$-qubit diagonal unitary with a $s$-sparse sequential decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(ns)$ and size $\mathcal{O}(ns)$ without using ancilla qubits.

The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (<ref>). Each of the $s$ sequential operator contains at worst $2n$ $\hat{X}$-Pauli gates and one $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))$ which is implemented using the scheme of C.Gidney <cit.>. It is an exact method for multi-controlled gates with size and depth linear in $n$ without using ancilla qubits.

Any $n$-qubit diagonal unitary with a $s$-sparse sequential decomposition is implementable up to an error $\epsilon>0$ with a quantum circuit of depth $\mathcal{O}(s\log(n)^3\log(s/\epsilon))$ and size $\mathcal{O}(sn\log(n)^4\log(s/\epsilon))$ without using ancilla qubits.

The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (<ref>). Each of the $s$ sequential operator contains at worst $2n$ $\hat{X}$-Pauli gates and one $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))$. Each of the $s$ multi-controlled phase gate is implemented using the approximative method of Claudon et al. (Proposition 2 in <cit.>) with error $\epsilon'=\epsilon/s$,  depth $\mathcal{O}(\log(n)^3\log(s/\epsilon))$ and size $\mathcal{O}(n\log(n)^4\log(s/\epsilon))$.

Any $n$-qubit diagonal unitary with a $s$-sparse sequential decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(s\log(n)^3)$ and size $\mathcal{O}(sn\log(n)^4)$ using one ancilla qubit.

The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (<ref>). Each of the $s$ sequential operator contains at worst $2n$ $\hat{X}$-Pauli gates and one $\Lambda_{\{0,...,n-2\}}(\hat{P}(\theta_j))$. Each of the $s$ multi-controlled phase gate is implemented using the exact method of Claudon et al. (Corollary 1 in <cit.>) with  depth $\mathcal{O}(\log(n)^3)$, size $\mathcal{O}(n\log(n)^4)$ using one ancilla qubit.

Any $n$-qubit diagonal unitary with a $s$-sparse sequential decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(s\log(n)^3/(m/n) + \log(m/n))$ and size $\mathcal{O}(sn\log(n)^4+m)$ using $m\geq n+2$ ancilla qubits.

This corollary is a direct consequence of Lemma <ref> and the adjustable-depth Theorem <ref>.

Any $n$-qubit diagonal unitary with a $s$-sparse sequential decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(\log(n)^3+\log(s))$ and size $\mathcal{O}(sn\log(n)^4)$ using $m=\mathcal{O}(ns)$ ancilla qubits.

This corollary is a direct consequence of lemma <ref> and the fully parallelized Theorem <ref>.

Any $n$-qubit diagonal unitary with a $s$-sparse Walsh-Hadamard decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(sk)$ and size $\mathcal{O}(sk)$ without using ancilla qubits, where $k$ is the maximum number of $1$ in the binary decomposition of the indexes $j$ of the Walsh-Hadamard operators.

The quantum circuit is composed of $s$ operator $\hat{W}_j$ defined in Eq. (<ref>) for $j\in S \subseteq \{0,1,...,2^n-1\}$, with $\|S\|=s$. Each Walsh-Hadamard operator $\hat{W}_j$ for $j=\sum_{i=0}^{n-1}j_i 2^i \in S$ contains exactly $2k_j$ controlled-NOT gates and one $\hat{R}_Z$ gate where $k_j$ is the number of $1$ in the binary decomposition of $j$, a.k.a. $k_j=\sum_{i=0}^{n-1}j_i$. By defining $k=\max_{j\in S} k_j$, the size of the quantum circuit is bounded by $\mathcal{O}(sk)$ and the depth is also bounded by $\mathcal{O}(sk)$ where $k\leq n$ is independant of $n$.

Any $n$-qubit diagonal unitary with a $s$-sparse Walsh-Hadamard decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(sk/(m/k)+\log(m/k))$ and size $\mathcal{O}(sk+m)$ without using $m\geq k$ ancilla qubits, where $k$ is the maximum number of $1$ in the binary decomposition of the indexes $j$ of the Walsh-Hadamard operators.

This corollary is a direct consequence of lemma <ref> and the adjustable-depth Theorem <ref>.

Any $n$-qubit diagonal unitary with a $s$-sparse Walsh-Hadamard decomposition is exactly implementable with a quantum circuit of depth $\mathcal{O}(k+\log(s))$ and size $\mathcal{O}(sk)$ without using $m=\mathcal{O}(sk)$ ancilla qubits, where $k$ is the maximum number of $1$ in the binary decomposition of the indexes $j$ of the Walsh-Hadamard operators.

This corollary is a direct consequence of lemma <ref> and the fully parallelized Theorem <ref>.

§.§.§ Sparse non-unitary diagonal operators

The following corollaries summarize the complexity of implementing any $n$-qubit non-unitary diagonal operators $\hat{D}$ with an associated $s$-sparse operator $e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$, with $\alpha > 1$.

For any $\alpha\geq 1$, any $n$-qubit non-unitary diagonal operator with a $s$-sparse sequential decomposition can be $(\alpha d_{\max},1,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(ns)$ and size $\mathcal{O}(ns)$ using one ancilla qubit.

This corollary is a direct consequence of lemma <ref> and the block-encoding Theorem <ref>. Remark that if $\hat{D}$ has $s$ non-zero real eigenvalues, then $\hat{U}^=e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ has at most $s$ eigenvalues different than $1$.

For any $\alpha\geq 1$, any $n$-qubit non-unitary diagonal operator with a $s$-sparse sequential decomposition can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(s\log(n)^3\log(s/\epsilon))$, size $\mathcal{O}(sn\log(n)^4\log(s/\epsilon))$ using one ancilla qubit.

This corollary is a direct consequence of lemma <ref> and the block-encoding Theorem <ref>.

For any $\alpha\geq 1$, any $n$-qubit non-unitary diagonal operator with a $s$-sparse sequential decomposition can be $(\alpha d_{\max},2,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(s\log(n)^3)$, size $\mathcal{O}(sn\log^4(n))$ using two ancilla qubit.

This corollary is a direct consequence of lemma <ref> and the block-encoding Theorem <ref>.

For any $\alpha\geq 1$, any $n$-qubit non-unitary diagonal operator with a $s$-sparse sequential decomposition can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(s\log(n)^3/(m/n) + \log(m/n))$, size $\mathcal{O}(sn\log^4(n)+m)$ using $m$ ancilla qubits with $m=\Omega(n)$ and $m=\mathcal{O}(ns)$.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

For any $\alpha\geq 1$, any $n$-qubit non-unitary diagonal operator with a $s$-sparse sequential decomposition can be $(\alpha d_{\max},m,0)$-block-encoded with a quantum circuit of depth $\mathcal{O}(\log(n)^3+ \log(s))$, size $\mathcal{O}(sn\log^4(n))$ using $m=\mathcal{O}(ns)$ ancilla qubits.

This corollary is a direct consequence of Corollary <ref> and the block-encoding Theorem <ref>.

Any $n$-qubit non-unitary diagonal $\hat{D}$ with real eigenvalues such that $\hat{U}^=e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ has an $\epsilon>0$ approximative $s$-sparse Walsh-Hadamard decomposition can be $(\alpha d_{\max},1,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(sk)$, size $\mathcal{O}(sk)$ using one ancilla qubit.

This corollary is a direct consequence of lemma <ref> and the block-encoding Theorem <ref>.

Any $n$-qubit non-unitary diagonal $\hat{D}$ with real eigenvalues such that $\hat{U}^=e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ has an $\epsilon>0$ approximative $s$-sparse Walsh-Hadamard decomposition can be $(\alpha d_{\max},m,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(sk/(m/k)+\log(m/k))$, size $\mathcal{O}(sk+m)$ using $m=\Omega(k)$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.

Any $n$-qubit non-unitary diagonal $\hat{D}$ with real eigenvalues such that $\hat{U}^=e^{\pm i\arcsin(\hat{D}/(\alpha d_{\max}))}$ has an $\epsilon>0$ approximative $s$-sparse Walsh-Hadamard decomposition can be $(\alpha d_{\max},m,\epsilon)$-block-encoded with a quantum circuit of depth $\mathcal{O}(k+\log(s))$, size $\mathcal{O}(sk)$ using $m=\mathcal{O}(sk)$ ancilla qubits.

This corollary is a direct consequence of corollary <ref> and the block-encoding Theorem <ref>.