**Proof.** Lemma C.1 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1 □

**Corollary C.12** (Partially parallelized block-encoding with exact sequential decomposition using polylogarithmic depth decomposition). For any $\alpha \ge 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)$.

**Proof.** Lemma C.2 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1 □

**Corollary C.13** (Partially parallelized block-encoding with exact Walsh-Hadamard decomposition). For any $\alpha \ge 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}(n 2^n + m)$ using $m$ ancilla qubits with $m = \Omega(n)$ and $m = \mathcal{O}(2^n/n)$.

**Proof.** Lemma C.3 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1. □

**Corollary C.14** (Lemma 11 [16] + block-encoding). For any $\alpha \ge 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.

**Proof.** The Lemma 11 [16] associated with the block-encoding Theorem V.1 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 [16]. 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. □

**Corollary C.15** (Lemma 20 [16] + block-encoding). For any $\alpha \ge 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}(n 2^n)$ using $m$ ancilla qubits with $m = \Omega(n)$ and $m = \mathcal{O}(2^n/n)$.

**Proof.** Lemma 20 [16] associated to the block-encoding Theorem V.1. □

**Corollary C.16** (Lemma 20 [16] with a maximum number of ancilla qubits + block-encoding). For any $\alpha \ge 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}(n 2^n)$ using $m = \mathcal{O}(2^n/n)$ ancilla qubits.

**Proof.** Lemma 20 [16] associated with the block-encoding Theorem V.1. □

## 2. Approximate methods

### a. 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)} |x\rangle\langle x|$, with $N = 2^n$ depending on a real-valued function $f$ defined on $[0, 1]$ with bounded first derivative.

**Corollary C.17** (Approximate sequential decomposition without ancilla). 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.

**Proof.** This corollary is a direct consequence of Lemma C.1 and the approximate Theorem IV.1. □

**Corollary C.18** (Approximate sequential decomposition with one ancilla). 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.

**Proof.** This corollary is a direct consequence of Lemma C.2 and the approximate Theorem IV.1. □

**Corollary C.19** (Approximate Walsh-Hadamard decomposition without ancilla [14]). 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.

**Proof.** This corollary is a direct consequence of Lemma C.3 and the approximate Theorem IV.1. □
**Proof.** Lemma C.1 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1 □

**Corollary C.12** (Partially parallelized block-encoding with exact sequential decomposition using polylogarithmic depth decomposition). For any $\alpha \ge 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)$.

**Proof.** Lemma C.2 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1 □

**Corollary C.13** (Partially parallelized block-encoding with exact Walsh-Hadamard decomposition). For any $\alpha \ge 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}(n 2^n + m)$ using $m$ ancilla qubits with $m = \Omega(n)$ and $m = \mathcal{O}(2^n/n)$.

**Proof.** Lemma C.3 with the partial parallelization Theorem III.2 and the block-encoding Theorem V.1. □

**Corollary C.14** (Lemma 11 [16] + block-encoding). For any $\alpha \ge 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.

**Proof.** The Lemma 11 [16] associated with the block-encoding Theorem V.1 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 [16]. 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. □

**Corollary C.15** (Lemma 20 [16] + block-encoding). For any $\alpha \ge 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}(n 2^n)$ using $m$ ancilla qubits with $m = \Omega(n)$ and $m = \mathcal{O}(2^n/n)$.

**Proof.** Lemma 20 [16] associated to the block-encoding Theorem V.1. □

**Corollary C.16** (Lemma 20 [16] with a maximum number of ancilla qubits + block-encoding). For any $\alpha \ge 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}(n 2^n)$ using $m = \mathcal{O}(2^n/n)$ ancilla qubits.

**Proof.** Lemma 20 [16] associated with the block-encoding Theorem V.1. □

## 2. Approximate methods

### a. 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)} |x\rangle\langle x|$, with $N = 2^n$ depending on a real-valued function $f$ defined on $[0, 1]$ with bounded first derivative.

**Corollary C.17** (Approximate sequential decomposition without ancilla). 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.

**Proof.** This corollary is a direct consequence of Lemma C.1 and the approximate Theorem IV.1. □

**Corollary C.18** (Approximate sequential decomposition with one ancilla). 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.

**Proof.** This corollary is a direct consequence of Lemma C.2 and the approximate Theorem IV.1. □

**Corollary C.19** (Approximate Walsh-Hadamard decomposition without ancilla [14]). 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.

**Proof.** This corollary is a direct consequence of Lemma C.3 and the approximate Theorem IV.1. □
**Corollary C.20** (Fully parallelized approximate sequential decomposition). 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.

*Proof.* This corollary is a direct consequence of corollary C.1 associated with the approximate Theorem IV.1. □

**Corollary C.21** (Fully parallelized approximate Walsh-Hadamard decomposition). 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 C.2 with the approximate Theorem IV.1.

**Corollary C.22** (Partially parallelized approximate sequential decomposition using linear depth decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.3 with the approximate Theorem IV.1. □

**Corollary C.23** (Partially parallelized approximate sequential decomposition using polylogarithmic depth decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.4 with the approximate Theorem IV.1. □

**Corollary C.24** (Partially parallelized approximate Walsh-Hadamard decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.5 with the approximate Theorem IV.1. □

**Corollary C.25** (Walsh-recursive). 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.

*Proof.* This corollary is a direct consequence of Lemma 11 [16] with the approximate Theorem IV.1. □

**Corollary C.26** (Walsh-optimized adjustable-depth). 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)))$.

*Proof.* This corollary is a direct consequence of Lemma 20 [16] with the approximate Theorem IV.1. □

**Corollary C.27** (Walsh-optimized fully parallelized). 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.

*Proof.* This corollary is a direct consequence of Lemma 20 [16] for a maximum number of ancilla qubits with the approximate Theorem IV.1. □
**Corollary C.20** (Fully parallelized approximate sequential decomposition). 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.

*Proof.* This corollary is a direct consequence of corollary C.1 associated with the approximate Theorem IV.1. □

**Corollary C.21** (Fully parallelized approximate Walsh-Hadamard decomposition). 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 C.2 with the approximate Theorem IV.1.

**Corollary C.22** (Partially parallelized approximate sequential decomposition using linear depth decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.3 with the approximate Theorem IV.1. □

**Corollary C.23** (Partially parallelized approximate sequential decomposition using polylogarithmic depth decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.4 with the approximate Theorem IV.1. □

**Corollary C.24** (Partially parallelized approximate Walsh-Hadamard decomposition). 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)$.

*Proof.* This corollary is a direct consequence of corollary C.5 with the approximate Theorem IV.1. □

**Corollary C.25** (Walsh-recursive). 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.

*Proof.* This corollary is a direct consequence of Lemma 11 [16] with the approximate Theorem IV.1. □

**Corollary C.26** (Walsh-optimized adjustable-depth). 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)))$.

*Proof.* This corollary is a direct consequence of Lemma 20 [16] with the approximate Theorem IV.1. □

**Corollary C.27** (Walsh-optimized fully parallelized). 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.

*Proof.* This corollary is a direct consequence of Lemma 20 [16] for a maximum number of ancilla qubits with the approximate Theorem IV.1. □
b. 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) |x\rangle\langle 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$.

**Corollary C.28** (Approximate block-encoding using a sequential decomposition and one ancilla qubit). 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 $O(\log(1/\epsilon)/\epsilon)$ and size $O(\log(1/\epsilon)/\epsilon)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of corollary C.17 applied on $\hat{U} = \sum_{x=0}^{N-1} e^{ig(x/N)} |x\rangle\langle x|$ with $g(x) = \arcsin(f(x)/(\alpha\|f\|_{\infty}))$ such that $\|g'\|_{\infty} \le \|f'\|_{\infty}/(\|f\|_{\infty}\sqrt{\alpha^2 - 1})$ and the block-encoding Theorem V.1. $\square$

**Corollary C.29** (Approximate sequential block-encoding with two ancilla qubits). 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 $O(\log(\log(1/\epsilon))^3/\epsilon)$ and size $O(\log(1/\epsilon)(\log(\log(1/\epsilon))^4/\epsilon)$ using two ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.18 and the block-encoding Theorem V.1. $\square$

**Corollary C.30** (Approximate Walsh-Hadamard block-encoding with one ancilla). 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 $O(1/\epsilon)$ and size $O(1/\epsilon)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of corollary C.19 and the block-encoding Theorem V.1. $\square$

**Corollary C.31** (Fully parallelized block-encoding with approximate sequential decomposition). 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 $O(\log(1/\epsilon))$ and size $O(\log(1/\epsilon)/\epsilon)$ using $m = O(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.20 and the block-encoding Theorem V.1. $\square$

**Corollary C.32** (Fully parallelized block-encoding with approximate Walsh-Hadamard decomposition). 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 $O(\log(1/\epsilon))$ and size $O(\log(1/\epsilon)/\epsilon)$ using $m = O(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.21 and the block-encoding Theorem V.1. $\square$

**Corollary C.33** (Partially parallelized block-encoding with approximate sequential decomposition). 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 $O(\log(1/\epsilon)^2/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.22 and the block-encoding Theorem V.1. $\square$

**Corollary C.34** (Partially parallelized block-encoding with approximate sequential decomposition using polylogarithmic depth decomposition). 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 $O(\log(1/\epsilon)\log(\log(1/\epsilon))^3/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)\log(\log(1/\epsilon))^4/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.23 and the block-encoding Theorem V.1. $\square$

**Corollary C.35** (Partially parallelized block-encoding with approximate Walsh-Hadamard decomposition). 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 $O(\log(1/\epsilon)^2/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.24 and the block-encoding Theorem V.1. $\square$
b. 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) |x\rangle\langle 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$.

**Corollary C.28** (Approximate block-encoding using a sequential decomposition and one ancilla qubit). 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 $O(\log(1/\epsilon)/\epsilon)$ and size $O(\log(1/\epsilon)/\epsilon)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of corollary C.17 applied on $\hat{U} = \sum_{x=0}^{N-1} e^{ig(x/N)} |x\rangle\langle x|$ with $g(x) = \arcsin(f(x)/(\alpha\|f\|_{\infty}))$ such that $\|g'\|_{\infty} \le \|f'\|_{\infty}/(\|f\|_{\infty}\sqrt{\alpha^2 - 1})$ and the block-encoding Theorem V.1. $\square$

**Corollary C.29** (Approximate sequential block-encoding with two ancilla qubits). 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 $O(\log(\log(1/\epsilon))^3/\epsilon)$ and size $O(\log(1/\epsilon)(\log(\log(1/\epsilon))^4/\epsilon)$ using two ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.18 and the block-encoding Theorem V.1. $\square$

**Corollary C.30** (Approximate Walsh-Hadamard block-encoding with one ancilla). 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 $O(1/\epsilon)$ and size $O(1/\epsilon)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of corollary C.19 and the block-encoding Theorem V.1. $\square$

**Corollary C.31** (Fully parallelized block-encoding with approximate sequential decomposition). 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 $O(\log(1/\epsilon))$ and size $O(\log(1/\epsilon)/\epsilon)$ using $m = O(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.20 and the block-encoding Theorem V.1. $\square$

**Corollary C.32** (Fully parallelized block-encoding with approximate Walsh-Hadamard decomposition). 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 $O(\log(1/\epsilon))$ and size $O(\log(1/\epsilon)/\epsilon)$ using $m = O(\log(1/\epsilon)/\epsilon)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.21 and the block-encoding Theorem V.1. $\square$

**Corollary C.33** (Partially parallelized block-encoding with approximate sequential decomposition). 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 $O(\log(1/\epsilon)^2/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.22 and the block-encoding Theorem V.1. $\square$

**Corollary C.34** (Partially parallelized block-encoding with approximate sequential decomposition using polylogarithmic depth decomposition). 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 $O(\log(1/\epsilon)\log(\log(1/\epsilon))^3/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)\log(\log(1/\epsilon))^4/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.23 and the block-encoding Theorem V.1. $\square$

**Corollary C.35** (Partially parallelized block-encoding with approximate Walsh-Hadamard decomposition). 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 $O(\log(1/\epsilon)^2/(\epsilon m) + \log(m/\log(1/\epsilon)))$ and size $O(\log(1/\epsilon)/\epsilon + m)$ using $m$ ancilla qubits with $m = \Omega(\log(1/\epsilon))$ and $m = O(\log(1/\epsilon)/\epsilon)$.

*Proof.* This corollary is a direct consequence of corollary C.24 and the block-encoding Theorem V.1. $\square$
**Corollary C.36 (Walsh-recursive).** 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.

*Proof.* This corollary is a direct consequence of corollary C.25 and the block-encoding Theorem V.1. $\square$

**Corollary C.37 (Walsh-optimized adjustable-depth).** 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)))$.

*Proof.* This corollary is a direct consequence of corollary C.26 and the block-encoding Theorem V.1. $\square$

**Corollary C.38 (Walsh-optimized fully parallelized).** 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.

*Proof.* This corollary is a direct consequence of corollary C.27 and the block-encoding Theorem V.1. $\square$

### 3. Sparse diagonal operators

#### a. 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.

**Lemma C.7 (Sparse sequential decomposition without ancilla).** 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.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [36]. It is an exact method for multi-controlled gates with size and depth linear in $n$ without using ancilla qubits. $\square$

**Lemma C.8 (Approximate sparse sequential decomposition without ancilla).** 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}(s n \log(n)^4 \log(s/\epsilon))$ without using ancilla qubits.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [17]) 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))$. $\square$

**Lemma C.9 (Sparse sequential decomposition with one ancilla).** 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}(s n \log(n)^4)$ using one ancilla qubit.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [17]) with depth $\mathcal{O}(\log(n)^3)$, size $\mathcal{O}(n \log(n)^4)$ using one ancilla qubit. $\square$

**Corollary C.39 (Adjustable-depth sparse sequential decomposition).** 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}(s n \log(n)^4 + m)$ using $m \ge n + 2$ ancilla qubits.

*Proof.* This corollary is a direct consequence of Lemma C.9 and the adjustable-depth Theorem III.2. $\square$

**Corollary C.40 (Fully parallelized sparse sequential decomposition).** 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}(s n \log(n)^4)$ using $m = \mathcal{O}(ns)$ ancilla qubits.
**Corollary C.36 (Walsh-recursive).** 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.

*Proof.* This corollary is a direct consequence of corollary C.25 and the block-encoding Theorem V.1. □

**Corollary C.37 (Walsh-optimized adjustable-depth).** 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)))$.

*Proof.* This corollary is a direct consequence of corollary C.26 and the block-encoding Theorem V.1. □

**Corollary C.38 (Walsh-optimized fully parallelized).** 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.

*Proof.* This corollary is a direct consequence of corollary C.27 and the block-encoding Theorem V.1. □

### 3. Sparse diagonal operators

#### a. 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.

**Lemma C.7 (Sparse sequential decomposition without ancilla).** 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.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [36]. It is an exact method for multi-controlled gates with size and depth linear in $n$ without using ancilla qubits. □

**Lemma C.8 (Approximate sparse sequential decomposition without ancilla).** 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}(s n \log(n)^4 \log(s/\epsilon))$ without using ancilla qubits.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [17]) 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))$. □

**Lemma C.9 (Sparse sequential decomposition with one ancilla).** 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}(s n \log(n)^4)$ using one ancilla qubit.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{U}_j$ defined in Eq. (3). 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 [17]) with depth $\mathcal{O}(\log(n)^3)$, size $\mathcal{O}(n \log(n)^4)$ using one ancilla qubit. □

**Corollary C.39 (Adjustable-depth sparse sequential decomposition).** 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}(s n \log(n)^4 + m)$ using $m \ge n + 2$ ancilla qubits.

*Proof.* This corollary is a direct consequence of Lemma C.9 and the adjustable-depth Theorem III.2. □

**Corollary C.40 (Fully parallelized sparse sequential decomposition).** 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}(s n \log(n)^4)$ using $m = \mathcal{O}(ns)$ ancilla qubits.
**Proof.** This corollary is a direct consequence of lemma C.9 and the fully parallelized Theorem III.1. □

**Lemma C.10 (Sparse Walsh-Hadamard decomposition without ancilla).** 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.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{W}_j$ defined in Eq. (8) 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 \le n$ is independent of $n$. □

**Corollary C.41 (Adjustable-depth sparse Walsh-Hadamard decomposition).** 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 \ge k$ ancilla qubits, where $k$ is the maximum number of 1 in the binary decomposition of the indexes $j$ of the Walsh-Hadamard operators.

*Proof.* This corollary is a direct consequence of lemma C.10 and the adjustable-depth Theorem III.2. □

**Corollary C.42 (Fully-parallelized sparse Walsh-Hadamard decomposition).** 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.

*Proof.* This corollary is a direct consequence of lemma C.10 and the fully parallelized Theorem III.1. □

b. 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$.

**Corollary C.43 (Block-encoding of sparse sequential decomposition with one ancilla).** For any $\alpha \ge 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.

*Proof.* This corollary is a direct consequence of lemma C.7 and the block-encoding Theorem V.1. 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. □

**Corollary C.44 (Block-encoding of approximate sparse sequential decomposition with one ancilla).** For any $\alpha \ge 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.

*Proof.* This corollary is a direct consequence of lemma C.8 and the block-encoding Theorem V.1. □

**Corollary C.45 (Block-encoding of sparse sequential decomposition with two ancilla qubits).** For any $\alpha \ge 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 qubits.

*Proof.* This corollary is a direct consequence of lemma C.9 and the block-encoding Theorem V.1. □

**Corollary C.46 (Adjustable-depth sparse sequential decomposition).** For any $\alpha \ge 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)$.

*Proof.* This corollary is a direct consequence of corollary C.39 and the block-encoding Theorem V.1. □

**Corollary C.47 (Fully parallelized sparse sequential decomposition).** For any $\alpha \ge 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.

*Proof.* This corollary is a direct consequence of Corollary C.40 and the block-encoding Theorem V.1. □
*Proof.* This corollary is a direct consequence of lemma C.9 and the fully parallelized Theorem III.1. □

**Lemma C.10 (Sparse Walsh-Hadamard decomposition without ancilla).** Any $n$-qubit diagonal unitary with a $s$-sparse Walsh-Hadamard decomposition is exactly implementable with a quantum circuit of depth $O(sk)$ and size $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.

*Proof.* The quantum circuit is composed of $s$ operator $\hat{W}_j$ defined in Eq. (8) 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 $O(sk)$ and the depth is also bounded by $O(sk)$ where $k \le n$ is independent of $n$. □

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

*Proof.* This corollary is a direct consequence of lemma C.10 and the adjustable-depth Theorem III.2. □

**Corollary C.42 (Fully-parallelized sparse Walsh-Hadamard decomposition).** Any $n$-qubit diagonal unitary with a $s$-sparse Walsh-Hadamard decomposition is exactly implementable with a quantum circuit of depth $O(k + \log(s))$ and size $O(sk)$ without using $m = 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.

*Proof.* This corollary is a direct consequence of lemma C.10 and the fully parallelized Theorem III.1. □

b. 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$.

**Corollary C.43 (Block-encoding of sparse sequential decomposition with one ancilla).** For any $\alpha \ge 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 $O(ns)$ and size $O(ns)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of lemma C.7 and the block-encoding Theorem V.1. 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. □

**Corollary C.44 (Block-encoding of approximate sparse sequential decomposition with one ancilla).** For any $\alpha \ge 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 $O(s \log(n)^3 \log(s/\epsilon))$, size $O(sn \log(n)^4 \log(s/\epsilon))$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of lemma C.8 and the block-encoding Theorem V.1. □

**Corollary C.45 (Block-encoding of sparse sequential decomposition with two ancilla qubits).** For any $\alpha \ge 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 $O(s \log(n)^3)$, size $O(sn \log^4(n))$ using two ancilla qubits.

*Proof.* This corollary is a direct consequence of lemma C.9 and the block-encoding Theorem V.1. □

**Corollary C.46 (Adjustable-depth sparse sequential decomposition).** For any $\alpha \ge 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 $O(s \log(n)^3/(m/n) + \log(m/n))$, size $O(sn \log^4(n)+m)$ using $m$ ancilla qubits with $m = \Omega(n)$ and $m = O(ns)$.

*Proof.* This corollary is a direct consequence of corollary C.39 and the block-encoding Theorem V.1. □

**Corollary C.47 (Fully parallelized sparse sequential decomposition).** For any $\alpha \ge 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 $O(\log(n)^3 + \log(s))$, size $O(sn \log^4(n))$ using $m = O(ns)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of Corollary C.40 and the block-encoding Theorem V.1. □
**Corollary C.48** (Sparse Walsh-Hadamard decomposition with one ancilla). 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 $O(sk)$, size $O(sk)$ using one ancilla qubit.

*Proof.* This corollary is a direct consequence of lemma C.10 and the block-encoding Theorem V.1. $\square$

<figure><img src="image_17.png" /></figure>

**Corollary C.49** (Adjustable-depth sparse Walsh-Hadamard decomposition). 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 $O(sk/(m/k) + \log(m/k))$, size $O(sk+m)$ using $m = \Omega(k)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.41 and the block-encoding Theorem V.1. $\square$

<figure><img src="image_18.png" /></figure>

**Corollary C.50** (Fully-parallelized sparse Walsh-Hadamard decomposition). 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 $O(k + \log(s))$, size $O(sk)$ using $m = O(sk)$ ancilla qubits.

*Proof.* This corollary is a direct consequence of corollary C.50 and the block-encoding Theorem V.1. $\square$

<figure><img src="image_19.png" /></figure>
**Corollary C.48** (Sparse Walsh-Hadamard decomposition with one ancilla). 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.

*Proof.* This corollary is a direct consequence of lemma C.10 and the block-encoding Theorem V.1. □

**Corollary C.49** (Adjustable-depth sparse Walsh-Hadamard decomposition). 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.

*Proof.* This corollary is a direct consequence of corollary C.41 and the block-encoding Theorem V.1. □

**Corollary C.50** (Fully-parallelized sparse Walsh-Hadamard decomposition). 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.

*Proof.* This corollary is a direct consequence of corollary C.50 and the block-encoding Theorem V.1. □