# Nonlinear transformation of complex amplitudes via quantum singular value
transformation

Naixu Guo<EMAIL_ADDRESS>Graduate School of Engineering Science,
Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan  Kosuke
Mitarai<EMAIL_ADDRESS>Graduate School of Engineering
Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan
Center for Quantum Information and Quantum Biology, Osaka University, Japan
JST PRESTO, Japan  Keisuke Fujii<EMAIL_ADDRESS>Graduate School
of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka
560-8531, Japan  Center for Quantum Information and Quantum Biology, Osaka
University, Japan  Center for Emergent Matter Science, RIKEN, Wako Saitama
351-0198, Japan

###### Abstract

Due to the linearity of quantum operations, it is not straightforward to
implement nonlinear transformations on a quantum computer, making some
practical tasks like a neural network hard to be achieved. In this work, we
define a task called nonlinear transformation of complex amplitudes and
provide an algorithm to achieve this task. Specifically, we construct a block-
encoding of complex amplitudes from a state preparation oracle. This allows us
to transform the complex amplitudes by using quantum singular value
transformation. We evaluate the required overhead in terms of input dimension
and precision, which reveals that the algorithm depends on the roughly square
root of input dimension and achieves an exponential speedup on precision
compared with previous work. We also discuss its possible applications to
quantum machine learning, where complex amplitudes encoding classical or
quantum data are processed by the proposed method. This paper provides a
promising way to introduce highly complex nonlinearity of the quantum states,
which is essentially missing in quantum mechanics.

##  I Introduction

Quantum mechanics is fundamentally linear. Quantum operations are all
unitaries in matrix representation, and the measurement is the only way in
which we can produce the nonlinearity. If deterministic nonlinear operations
are allowed, quantum computers can solve NP-hard problems in polynomial time
[1]. This result implies the difficulty of nonlinear quantum operations.
However, nonlinearity plays an essential role in applications such as
nonlinear differential equations and machine learning. It is important to
consider how to implement a nonlinear transformation on a quantum computer,
even if it can only be applied probabilistically.

The key idea for applying probabilistic nonlinear operations is to use a post-
selection, i.e., the desired transformation is applied on target subsystems if
ancilla qubits are measured in a certain state. The Harrow-Hassidim-Lloyd
(HHL) algorithm [2], for example, used this idea to provide an exponential
speedup for solving linear systems of equations compared with classical
computers.

In recent years, methods for performing nonlinear operations have been
developed rapidly. Quantum signal processing [3] is a technique to perform
desired nonlinear functions on eigenvalues of a unitary operator. Quantum
singular value transformation (QSVT) [4] is its generalization to perform
nonlinear functions on singular values of a matrix encoded in a unitary.
Existing quantum algorithms can be reconstructed in terms of QSVT [4, 5],
which unifies the disparate problems like Hamiltonian simulation [6, 7, 3, 8],
linear equation solving [2, 9] and amplitude amplification techniques [10, 11,
12], implying the importance of developing tools to introduce nonlinearity on
quantum computers.

Here, we consider how to perform nonlinear transformations on the state
amplitudes directly, rather than the nonlinear transformation of matrices
described in the previous work [4]. We call this task nonlinear transformation
of complex amplitudes (NTCA), which is defined as follows. Assume we have
access to a state preparation oracle

$\displaystyle U:\ket{0}\rightarrow\sum_{k=1}^{N}c_{k}\ket{k},$ (1)

which encodes a complex vector $\vec{c}=\\{c_{1},\cdots,c_{N}\\}$. We also
assume having access to its adjoint and their controlled versions. For given
nonlinear functions $P,Q:\mathbb{R}\rightarrow\mathbb{C}$, NTCA is a task to
prepare a quantum circuit such that its output state is

$\displaystyle\frac{1}{\sqrt{c}}\sum_{k=1}^{N}\left(P(x_{k})+Q(y_{k})\right)\ket{k},$
(2)

where $x_{k}+iy_{k}=c_{k}$ and $c$ is a normalization factor.

In this work, we provide an algorithm for NTCA based on QSVT. To achieve this,
we develop a method called block-encoding of amplitudes, where a unitary
operator constructed from the state preparation oracle encodes a Hermitian
matrix, whose singular values are the real or imaginary parts of amplitudes,
into its subspace. We show that if functions $P$ and $Q$ can be approximated
by $d$-degree polynomials $P^{\prime}$ and $Q^{\prime}$, NTCA can be
implemented using controlled-$U$ and controlled-$U^{\dagger}$

$\mathcal{O}\left(d\sqrt{N/\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}\right)$

times in expectation. We also provide a discussion about how to exploit this
algorithm for quantum machine learning. More specifically, we consider how to
perform a neural network on the quantum computer and discuss its possible
applications. This work opens up a way to implement nonlinear operations on a
quantum computer and may contribute to the field of quantum machine learning.

This paper is organized as follows. We define the task NTCA and summarize
existing important subroutines in Section II. In Section III.1, we introduce
the block-encoding of amplitudes. Combining this method with QSVT, we
construct an algorithm to perform NTCA in Section III.2. In Section IV, we
provide the application of this algorithm and show that NTCA provides us a way
to perform the neural network task directly on a quantum computer.

##  II Preliminary

In this section, we first define a task called NTCA and summarize some
subroutines from existing works. Throughout this paper, $N$ denotes the
dimension of data, $n=\lceil\log_{2}(N)\rceil$, and $\mathcal{I}_{s}$ denotes
the identity operator for $s$ qubits. A quantum state $\ket{\psi}$ represented
in the form $\ket{\psi}=c_{a}\ket{a}+\cdots$ means that we focus on the term
$c_{a}\ket{a}$ and the residual term is orthogonal to the first term.

First, we formally define NTCA as follows:

######  Definition 1 (Nonlinear transformation of complex amplitudes (NTCA)).

Assume we have access to a state preparation oracle $U$ such that
$U\ket{0}=\sum_{k=1}^{N}c_{k}\ket{k}$, where $c_{k}=x_{k}+iy_{k}$ and
$x_{k},y_{k}$ are real numbers. We also assume having access to its adjoint
and their controlled versions. For nonlinear functions
$P,Q:\mathbb{R}\rightarrow\mathbb{C}$ bounded on the interval $[-1,1]$, output
a quantum state $\frac{1}{\sqrt{c^{\prime}}}\sum_{k=1}^{N}b_{k}\ket{k}$ such
that it is an $\varepsilon$-approximation to the
$\frac{1}{\sqrt{c}}\sum_{k=1}^{N}\left(P(x_{k})+Q(y_{k})\right)\ket{k}$. Here,
$c,c^{\prime}$ are the normalization coefficients, and
$\varepsilon$-approximation means that, for all $k$ and
$x_{k},y_{k}\in[-1,1]$,

$\displaystyle|b_{k}-P(x_{k})-Q(y_{k})|\leq\frac{\varepsilon}{N}.$ (3)

To achieve NTCA, we utilize QSVT, which is a technique to apply nonlinear
functions on singular values of a matrix. It exploits the so-called block-
encoding of a target matrix defined as follows.

######  Definition 2 (Block-encoding [8, 13]).

Suppose that A is an n-qubit operator, $\alpha,\varepsilon\in\mathbb{R}_{+}$
and $a\in\mathbb{N}$. Then we say that the $(a+n)$-qubit unitary $U$ is an
$(\alpha,a,\varepsilon)$-block-encoding of A if

$\displaystyle\|A-\alpha(\bra{0}^{\otimes a}$
$\displaystyle\otimes\mathcal{I}_{n})U(\ket{0}^{\otimes
a}\otimes\mathcal{I}_{n})\|\leq\varepsilon.$ (4)

Using the block-encoding, QSVT can implement $P(A)$ of a Hermitian matrix $A$
for any polynomial $P$. More formally, we can achieve the following.

######  Lemma 3 (Polynomial eigenvalue transformation of arbitrary parity [4,
Theorem 56]).

Suppose that $U$ is an $(\alpha,a,\varepsilon)$-block-encoding of a Hermitian
matrix $A$. If $\delta\geq 0$ and $P:\mathbb{R}\rightarrow\mathbb{C}$ is a
degree-d polynomial satisfying that

$\displaystyle\mathrm{for\ all}\ x\in[-1,1]:\left|P(x)\right|\leq\frac{1}{4},$
(5)

then there is a quantum circuit $\tilde{U}$, which is an
$(1,a+3,4d\sqrt{\varepsilon/\alpha}+N\delta)$-block-encoding of $P(A/\alpha)$,
and consists of d applications of $U$ and $U^{\dagger}$ gates, a single
application of controlled-U and $\mathcal{O}(ad)$ other one- and two-qubit
gates. Moreover we can compute a description of such a circuit with a
classical computer in time
$\mathcal{O}(\operatorname{poly}(d,\log(1/\delta)))$.

We note that this theorem is not exactly Theorem 56 of Ref. [4] but a slightly
generalized version which is mentioned in Ref. [4]. The original theorem is a
similar claim for real polynomial $P_{\Re}:\mathbb{R}\to\mathbb{R}$ requiring
two ancilla qubits instead of three in the above theorem.

##  III Result

###  III.1 Block-encoding of amplitudes

In this subsection, we describe a method that we call block-encoding of
amplitudes. Using the state preparation oracle $U$ as Definition 1, we
construct $(1,1,0)$-block-encodings $\tilde{G}$ and $\tilde{G^{\prime}}$ of
$(2n+1)$-qubit Hermitian matrices, whose eigenvalues include respectively the
real and imaginary part of amplitudes, i.e.,

$\displaystyle(\bra{0}\otimes\mathcal{I}_{2n+1})\tilde{G}(\ket{0}\otimes\mathcal{I}_{2n+1})=\sum_{k=1}^{N}x_{k}|\varphi_{k}\rangle\langle\varphi_{k}|+\cdots,$
(6)
$\displaystyle(\bra{0}\otimes\mathcal{I}_{2n+1})\tilde{G^{\prime}}(\ket{0}\otimes\mathcal{I}_{2n+1})=\sum_{k=1}^{N}y_{k}|\varphi^{\prime}_{k}\rangle\langle\varphi^{\prime}_{k}|+\cdots,$
(7)

where $\ket{\varphi_{k}}$ and $\ket{\varphi^{\prime}_{k}}$ are mutually
orthogonal $(2n+1)$-qubit states. Concrete forms of $\ket{\varphi_{k}}$ and
$\ket{\varphi^{\prime}_{k}}$ will be described later. The result is summarized
as the following theorem.

######  Theorem 4 (Block-encoding of real part amplitudes).

Given a state preparation oracle $U$ as Definition 1, we can construct a
unitary $\tilde{G}$ and $\tilde{G}^{\prime}$ which satisfy Eq. (6) and (7)
respectively by using controlled-$U$, controlled-$U^{\dagger}$ four times, and
$\mathcal{O}(n)$ one- and two-qubit gates.

Figure 1: Definition of operation $W$ in Theorem 4 Figure 2: Definition of
operation $G$ in Theorem 4 Figure 3: Definition of operation $\tilde{G}$ in
Theorem 4

###### Proof.

The construction is partly based on the previous work [14]. First, we
construct a unitary whose eigenvalues encode the information of $x_{k}$. Let
$W$ be a sequence of unitary operations as shown in Fig. 1. Note that,

$\displaystyle W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}$
$\displaystyle=\frac{\ket{k}}{2}_{\mathrm{ad}}\biggl{(}\bigl{(}\sum_{j=1}^{N}c_{j}\ket{j}+\ket{k}\bigl{)}_{\mathrm{da}}\ket{0}_{\mathrm{B}}$
$\displaystyle+\bigl{(}\sum_{j=1}^{N}c_{j}\ket{j}-\ket{k}\bigl{)}_{\mathrm{da}}\ket{1}_{\mathrm{B}}\biggl{)}.$
(8)

See Appendix A.1 for detail. Let $S_{0}:=\mathcal{I}_{n+1}-2|0\rangle\langle
0|_{\mathrm{da,B}}$ be a conditional phase-shift gate on the data qubits and
ancilla qubit B, and $Z_{\mathrm{B}}$ be the $Z$ gate acting on the ancilla
qubit B. With these operations, we define

$\displaystyle G:=WS_{0}W^{\dagger}Z_{\mathrm{B}},$ (9)

which is shown in Fig. 2. For $k\in\\{1,\dots,N\\}$, we define the following
normalized states

$\displaystyle\ket{\Psi_{k0}}_{\mathrm{da,B}}:=\frac{1}{2\alpha_{k}}\biggl{(}$
$\displaystyle\sum_{j}c_{j}\ket{j}+\ket{k}\biggl{)}_{\mathrm{da}}\ket{0}_{\mathrm{B}}$
(10)
$\displaystyle\ket{\Psi_{k1}}_{\mathrm{da,B}}:=\frac{1}{2\beta_{k}}\biggl{(}$
$\displaystyle\sum_{j}c_{j}\ket{j}-\ket{k}\biggl{)}_{\mathrm{da}}\ket{1}_{\mathrm{B}},$
(11)

where $\alpha_{k}=\sqrt{\frac{1}{2}(1+x_{k})}$,
$\beta_{k}=\sqrt{\frac{1}{2}(1-x_{k})}$. As shown in Appendix A.2,
eigenvectors of $G$ are

$\displaystyle\ket{k}_{\mathrm{ad}}\ket{\Psi_{k\pm}}_{\mathrm{da,B}}:=\frac{1}{\sqrt{2}}\ket{k}_{\mathrm{ad}}\left(\ket{\Psi_{k0}}\pm\ket{\Psi_{k1}}\right)_{\mathrm{da,B}},$
(12)

with the corresponding eigenvalues $-x_{k}\pm i\sqrt{1-x_{k}^{2}}$. We neglect
other eigenstates of $G$ since we are only interested in the subspace which
encodes amplitudes. However, since our target is to achieve an operator as Eq.
(6), we need to remove the imaginary part of eigenvalues.

We achieve this by the circuit in Fig. 3 where we use controlled versions of
$G$ and $G^{\dagger}$. The idea is that the imaginary part of eigenvalues can
be canceled by implementing $\frac{1}{2}(G+G^{\dagger})$. Define $\tilde{G}$
as shown in Fig. 3. We then have

$\displaystyle(\bra{0}\otimes\mathcal{I}_{2n+1})\ \tilde{G}\
(\ket{0}\otimes\mathcal{I}_{2n+1})=-\frac{1}{2}(G+G^{\dagger}).$ (13)

Therefore, $\tilde{G}$ is a $(1,1,0)$-block-encoding of Hermitian matrix
$-\frac{1}{2}(G+G^{\dagger})$. Eigenvalues of $-\frac{1}{2}(G+G^{\dagger})$
are $\\{x_{k}\\}_{k=1}^{N}$. To construct $\tilde{G}$, we need to use
controlled-$U$, controlled-$U^{\dagger}$ four times, and $\mathcal{O}(n)$ one-
and two-qubit gates. Details of gate count are provided in Appendix A.3.

$\tilde{G}^{\prime}$ can be constructed by the same procedure except that we
add an $S$ gate on the ancilla qubit $B$ in $W$ as in Fig. 1. ∎

###  III.2 Nonlinear transformation of complex amplitudes

In this subsection, we provide an algorithm to implement NTCA. The idea is to
apply Lemma 3 to the block-encodings obtained in Theorem 4 to implement
desired functions. We assume the existence of polynomial approximations of
functions $P$ and $Q$ to utilize Theorem 3. Note that in principle, any
continuous real-valued function defined on the interval $[-1,1]$ can be
approximated by a polynomial function with arbitrary precision by the
Weierstrass approximation theorem [15].

Our quantum algorithm for NTCA is the following.

######  Theorem 5 (Nonlinear transformation of complex amplitudes).

If functions $P$ and $Q$ in Definition 1 can be approximated by $d_{p}$\- and
$d_{q}$-degree polynomials $P^{\prime}$ and $Q^{\prime}$ such that
$|P^{\prime}(x)-P(x)|,|Q^{\prime}(x)-Q(x)|\leq\varepsilon/(4N)$ for all
$x\in[-1,1]$, the following holds. Let $d:=\max\\{d_{p},d_{q}\\}$ and
$\gamma:=\underset{x\in[-1,1]}{\max}\\{|P(x)|,|Q(x)|\\}$, then NTCA in
Definition 1 can be achieved by using controlled-$U$, controlled-$U^{\dagger}$

$\mathcal{O}\left(d\gamma\sqrt{N/\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}\right)$

times, and

$\mathcal{O}\left(nd\gamma\sqrt{N/\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}\right)$

one- and two-qubit gates in expectation.

Proof overview. We implement $P^{\prime}(x)$ and $Q^{\prime}(y)$ separately by
applying Lemma 3 to the block-encodings obtained in Theorem 4. This process
provides us two unitaries $\mathcal{P}$ and $\mathcal{Q}$ which block-encodes
matrices whose eigenvalues are $P^{\prime}(x_{k})/(4\gamma)$ and
$Q^{\prime}(y_{k})/(4\gamma)$, respectively. The coefficient of $4\gamma$ is
necessary to make the functions implementable with Lemma 3. Noting that the
eigenstates of the above two unitaries can be prepared by applying $W$
operation in Fig. 2 to a computational basis, we then apply $\mathcal{P}$ and
$\mathcal{Q}$ to uniform superpositions of $N$ eigenstates corresponding to
eigenvalues $P^{\prime}(x_{k})/(4\gamma)$ and $Q^{\prime}(y_{k})/(4\gamma)$.
The concrete algorithm is provided below.

###### Proof.

First, note that $P^{\prime}(x)/(4\gamma)$ satisfies
$|P^{\prime}(x)/(4\gamma)|\leq 1/4$ therefore compatible with Lemma 3. By
using $\tilde{G}$ in Theorem 4 as an input to Lemma 3 and setting
$\delta=\varepsilon/(16\gamma N)$ in Lemma 3, we can construct the unitary
$\mathcal{P}$ as a $(1,4,\varepsilon/(16\gamma))$-block-encoding of matrix
$P^{\prime}\left(-\frac{1}{2}(G+G^{\dagger})\right)/(4\gamma)$ where $G$ is
the unitary defined by Eq. (9). Details of error analysis are provided in
Appendix B. With a similar procedure, we can construct $\mathcal{Q}$ as a
$(1,4,\varepsilon/(16\gamma))$-block-encoding of matrix
$Q^{\prime}(-\frac{1}{2}(G^{\prime}+G^{{}^{\prime}\dagger}))/(4\gamma)$.

We can extract $P^{\prime}(x_{k})$ and $Q^{\prime}(y_{k})$ to the amplitudes
by injecting eigenstates of
$P^{\prime}\left(-\frac{1}{2}(G+G^{\dagger})\right)$ and
$Q^{\prime}(-\frac{1}{2}(G^{\prime}+G^{{}^{\prime}\dagger}))$ to $\mathcal{P}$
and $\mathcal{Q}$ respectively. We claim that
$W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}$ and
$W^{\prime}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}$ is an eigenstate of
$\mathcal{P}$ and $\mathcal{Q}$, respectively. This is because the two states
$\ket{k}_{\mathrm{ad}}\ket{\Psi_{k\pm}}_{\mathrm{da,B}}$ in Eq. (12) are the
eigenstates of $-\frac{1}{2}(G+G^{\dagger})$ with the (degenerate) eigenvalue
$x_{k}$. Therefore, any linear combinations of
$\ket{\Psi_{k\pm}}_{\mathrm{da,B}}$, or equivalently those of
$\ket{\Psi_{k0}}_{\mathrm{da,B}}$ and $\ket{\Psi_{k1}}_{\mathrm{da,B}}$, are
eigenvectors with eigenvalues $x_{k}$. From Eq. (8), we see that
$W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}$ is a linear combination of
$\ket{\Psi_{k0}}_{\mathrm{da,B}}$ and $\ket{\Psi_{k1}}_{\mathrm{da,B}}$ and
hence an eigenvector with the eigenvalue $x_{k}$. Therefore, we have,

$\displaystyle\begin{split}&\mathcal{P}\left[\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right]\\\
\quad&=\frac{P^{\prime}(x_{k})}{4\gamma}\left[\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right]+\cdots,\end{split}$
(14) $\displaystyle\begin{split}&\mathcal{Q}\left[\ket{0}^{\otimes
4}\left(W^{\prime}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right]\\\
\quad&=\frac{Q^{\prime}(y_{k})}{4\gamma}\left[\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right]+\cdots.\end{split}$
(15)

By injecting the uniform superposition of the eigenstates, i.e.,
$\frac{1}{\sqrt{N}}\sum_{k=1}^{N}\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)$ to
$\mathcal{P}$, we can get

$\displaystyle\frac{1}{4\gamma\sqrt{N}}\sum_{k=1}^{N}P^{\prime}(x_{k})\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right),$ (16)

which has transformed amplitudes. We can do likewise to extract
$Q^{\prime}(y_{k})$.

To achieve NTCA of Definition 1, we have to take a linear combination of
$P^{\prime}(x_{k})$ and $Q^{\prime}(y_{k})$. This can be performed by the
circuit in Fig. 4. The state before the application of
controlled-$\mathcal{P}$ gate in Fig. 4 is,

$\displaystyle\begin{split}\frac{1}{\sqrt{2N}}\sum_{k=1}^{N}&\left[\ket{0}\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right.\\\
&\left.+\ket{1}\ket{0}^{\otimes
4}\left(W^{\prime}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right].\end{split}$
(17)

Applying controlled-$\mathcal{P}$ and controlled-$\mathcal{Q}$ to this state
leads to the following state:

$\displaystyle\begin{split}\frac{1}{4\gamma\sqrt{2N}}\sum_{k=1}^{N}&\left[P^{\prime}(x_{k})\ket{0}\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right.\\\
&\left.+Q^{\prime}(y_{k})\ket{1}\ket{0}^{\otimes
4}\left(W^{\prime}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right]+\cdots.\end{split}$
(18)

Then, we apply controlled-$W^{\dagger}$, controlled-$W^{\prime\dagger}$ to
uncompute the data and B qubits. Finally, applying Hadamard gate to the first
qubit as in Fig. 4 provides us the desired state,

$\displaystyle\frac{1}{8\gamma\sqrt{N}}\sum_{k=1}^{N}\left(P^{\prime}(x_{k})+Q^{\prime}(y_{k})\right)\ket{0}^{\otimes
5}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}+\cdots,$ (19)

which contains the target state neglecting the data and $B$ qubits. It is
obvious that we can implement NTCA if we measure the first five qubits and the
outcome is $\ket{0}^{\otimes 5}$. The probability of this event is
$\frac{1}{64\gamma^{2}N}\sum_{k}|P^{\prime}(x_{k})^{2}+Q^{\prime}(y_{k})^{2}|$.

Figure 4: Quantum circuit for the nonlinear transformation of part of complex
amplitudes

We can use amplitude amplification [16] to boost this probability
quadratically. It allows us to achieve the NTCA with

$\mathcal{O}\left(\gamma\sqrt{\frac{N}{\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}}\right)$

use of the circuit in Fig. 4 in expectation. Each of controlled-$\mathcal{P}$
and controlled-$Q$ operations is constructed with $\mathcal{O}(d)$
controlled-$U$ and controlled-$U^{\dagger}$ operations and $\mathcal{O}(nd)$
elementary gates. Therefore, in total, we use controlled-$U$ and
controlled-$U^{\dagger}$

$\mathcal{O}\left(d\gamma\sqrt{\frac{N}{\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}}\right)$

times, and

$\mathcal{O}\left(nd\gamma\sqrt{\frac{N}{\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}}\right)$

one- and two-qubit gates in expectation to achieve NTCA.

∎

Notice that there is a natural generalization of Theorem 5. For $N_{1}\leq N$,
we can output the state

$\displaystyle\frac{1}{8\gamma\sqrt{N_{1}}}\sum_{k=1}^{N_{1}}(P^{\prime}(x_{k})+Q^{\prime}(y_{k}))\ket{0}^{\otimes
5}\ket{k}+\cdots,$ (20)

by slightly modifying the circuit in Fig. 4 so that the state just before the
controlled-$\mathcal{P}$ operation is the following state,

$\displaystyle\begin{split}\frac{1}{\sqrt{2N_{1}}}\sum_{k=1}^{N_{1}}&\left[\ket{0}\ket{0}^{\otimes
4}\left(W\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right.\\\
&\left.+\ket{1}\ket{0}^{\otimes
4}\left(W^{\prime}\ket{k}_{\mathrm{ad}}\ket{0}_{\mathrm{da,B}}\right)\right],\end{split}$
(21)

instead of the uniform superposition of $N$ eigenstates prepared in Eq. (17).
If we are only interested in performing nonlinear transformations to a part of
the amplitudes, we can benefit from this generalization.

Another remark is that, if we consider the case with real function
$P:\mathbb{R}\to\mathbb{R}$ acting on the real part of amplitudes, we can
reduce the total number of ancilla qubits from five to three. This is because
we can construct $\mathcal{P}$ with only two ancilla qubits in this case as
mentioned earlier in Sec. II, and the sum between functions $P$ and $Q$
becomes unnecessary. Therefore, with a continuous real-valued function $P$ and
its polynomial approximation $P^{\prime}$, for $N_{1}\leq N$ we can prepare
the following state,

$\displaystyle\frac{1}{2\gamma\sqrt{N_{1}}}\sum_{k=1}^{N_{1}}P^{\prime}(x_{k})\ket{0}^{\otimes
3}\ket{k}_{\mathrm{ad}}\ket{0}^{\otimes n+1}_{\mathrm{da,B}}+\cdots,$ (22)

only requiring three ancilla qubits.

###  III.3 Comparison with previous work

Our work is inspired by the previous work [14], based on which we focus on how
to apply nonlinear functions on amplitudes of a quantum state on the quantum
computer. Ref. [14] also considered performing nonlinear transformation of
amplitudes. Let us compare the present work with Ref. [14] in the case where
we wish to implement only $P:\mathbb{R}\to\mathbb{R}$ acting on real parts of
amplitudes. Their algorithm works by first performing quantum phase estimation
[17] of the unitary $G$ defined in Eq. (9) to encode $x_{k}$ (and $y_{k}$)
into bitstrings as $\sum_{k=1}^{N}\ket{k}\ket{\bar{x}_{k}}$, where
$\bar{x}_{k}$ is a binary representation of $x_{k}$. Then, using an ancilla
qubit and arithmetical operations, it prepares a state in the form of

$\sum_{k=1}^{N}\ket{k}\ket{\bar{x}_{k}}\left(P(x_{k})\ket{0}+\sqrt{1-P(x_{k})^{2}}\ket{1}\right),$

from which we can obtain the desired state if we measure the ancilla qubit in
$\ket{0}$ state. If this algorithm is applied to the same setting as
Definition 1, it would require $\mathcal{O}(N/\varepsilon)$ uses of the
controlled-$G$ and hence the same amount of controlled-$U$ in the phase
estimation step. In total, it would require

$\tilde{\mathcal{O}}\left(N/\varepsilon\sqrt{N/\sum_{k=1}^{N}|P(x_{k})|^{2}}\right)$

uses of controlled-$U$. In contrast, the algorithm presented in Theorem 5 uses

$\mathcal{O}\left(d\gamma\sqrt{N/\sum_{k=1}^{N}|P^{\prime}(x_{k})+Q^{\prime}(y_{k})|^{2}}\right)$

of controlled-$U$, where $d$ implicitly depends on the precision requirement
$N/\varepsilon$. In many cases, $d$ can be taken as
$d=\mathcal{O}(\log(N/\varepsilon))$ [4], and thus we achieve exponential
speedup in terms of $N$ and $\varepsilon$. This improvement is important when
we consider the running time of possible applications like a quantum neural
network, as described in the next section. We also need fewer ancilla qubits
for NTCA. While our quantum algorithm needs $\mathcal{O}(n)$ ancilla qubits,
Ref. [14] needs $\mathcal{O}(n+\log(N/\varepsilon))$.

##  IV Application to quantum machine learning

Let us finally discuss possible applications of NTCA for machine learning
tasks. A straightforward application of the NTCA is to implement the neural
network by using the complex amplitudes as its nodes as follows. For a
(classical) data vector
$\vec{x}=\\{x_{1},x_{2},\cdots,x_{N}\\}\in\mathbb{R}^{N}$, let us assume that
we have a data-encoding unitary $U_{\vec{x}}$ such that,

$\displaystyle U_{\vec{x}}:\ket{0}\rightarrow\sum_{k=1}^{N}x_{k}\ket{k}.$ (23)

This is the so-called amplitude encoding of a classical data [18].
$U_{\vec{x}}$ can be constructed via the use of quantum random access memory
(QRAM) [19] with the data structure mentioned in Ref. [20]. Using
$U_{\vec{x}}$ and an orthogonal matrix $O=\sum_{j,k}o_{jk}\ket{j}\bra{k}$, we
can prepare,

$\displaystyle\sum_{k=1}^{N}P\left(\sum_{j=1}^{N}o_{kj}x_{j}\right)\ket{k},$
(24)

whose amplitudes correspond to the outputs of a single-layer neural network
with an activation function $P$ and an orthogonal weight matrix, by using
$OU_{\mathrm{data}}$ as $U$ in Theorem 5. Note that the normalization factor
is omitted to simplify the notation. We will do so henceforth if the
normalization factor is not needed explicitly for discussions. We also analyze
concrete implementation of a famous activation function $P(x)=\tanh(x)$ in
Appendix C.

We can straightforwardly generalize them for a complex input vector
$\ket{\psi}=\sum_{k=1}^{N}\psi_{k}\ket{k}$. Let $U_{\psi}\ket{0}:=\ket{\psi}$.
Our NTCA algorithm can prepare a state in the form of,

$\displaystyle\sum_{k=1}^{N}F\left(\sum_{j=1}^{N}v_{kj}\psi_{j}\right)\ket{k}$
(25)

$F:\mathbb{C}\to\mathbb{C}$ is an activation function in the form of
$F(\psi)=P(\mathrm{Re}(\psi))+Q(\mathrm{Im}(\psi))$, and $v_{kj}$ are elements
of a (tranable) unitary $V=\sum_{kj}v_{kj}\ket{k}\bra{j}$, by using
$VU_{\psi}$ as $U$ in Theorem 5. The amplitudes of this state can be regarded
as the outputs of a single-layer neural network with input datum
$\\{\psi_{k}\\}$.

While $U_{\psi}$ naturally includes the amplitude encoding untiary defined in
Eq. (23), it is notable that $U_{\psi}$ can be any encoding of a classical
data $\vec{x}$ to quantum state $\ket{\psi(\vec{x})}$ such as the ones
proposed in quantum machine learning literatures [21, 22, 23, 24, 25, 26].
Moreover, we believe that a more important situation for NTCA is when the
input state $\ket{\psi}$ has intrinsic quantumness. For example, we might be
able to learn properties of a certain family of Hamiltonians $H$ by directly
feeding a time-evolved state $e^{iHt}\ket{0}$ or an approximate ground state
generated via e.g. variational quantum eigensolver [27] to a neural network.

The generated state has a variety of possible applications. A straightforward
application would be the classification. To classify the data into $N_{c}$
classes, we measure certain $\lceil\log_{2}N_{c}\rceil$ qubits of the output
state (25). Note that in this case, we do not need to output a full vector
like Eq. (25) and can exploit the fact that we can output a state like
$\sum_{k=1}^{N_{c}}F(\sum_{j=1}^{N}v_{kj}\psi_{j})\ket{k}$. Another possible
application is to use the output state in Eq. (25) for a generative model
[28]. The purpose of generative models is to create a machine that can sample
from a probability distribution that is close to the distribution of data.
Since it has been shown that the sampling from a certain family of quantum
states is classically hard [29], it is a promising direction to explore the
usefulness of quantum computers for this task. In contrast to the previous
works [30, 31, 32], our algorithm can provide nonlinearity and it may have
better performance compared with them. Finally, we mention that the
transformation can be considered as a quantum feature map [22, 23] that takes
a quantum data $\ket{\psi}$ as an input and maps the state nonlinearly to
create a quantum feature vector
$\ket{\Psi(\psi)}=\sum_{k=1}^{N}F\left(\sum_{j=1}^{N}v_{kj}\psi_{j}\right)\ket{k}$.
The inner product of the feature vectors,
$\braket{\Psi(\psi_{1})}{\Psi(\psi_{2})}$, can be exploited for quantum kernel
methods [22, 23], which constructs a machine learning model based on the inner
products of data in a feature space. We can also perform quantum circuit
learning [21] by applying a trainable unitary to $\ket{\Psi(\psi)}$.

It is also possible to obtain the values of the $N_{1}(\leq N)$ dimensional
nodes, i.e.,
$\left\\{F\left(\sum_{j}v_{kj}\psi_{j}\right)\right\\}_{k=1}^{N_{1}}$, by
using amplitude estimation [16]. The amplitude estimation essentially allows
us to estimate the absolute value $|a|$ of an amplitude $a$ in a quantum state
$\ket{\phi}=a\ket{0}+\cdots$ with an additive error $\beta$ by
$\mathcal{O}(1/\beta)$ uses of a quantum circuit that creates $\ket{\phi}$.
Note that $a$ itself can also be estimated if we can construct quantum
circuits that creates a state in the form of $\frac{1+a}{2}\ket{0}+\cdots$ and
$\frac{1+ia}{2}\ket{0}+\cdots$. In this case, we can separately estimate
$|1+a|$, $|1+ia|$ and $|a|$ from which $\mathrm{Re}(a)$ and $\mathrm{Im}(a)$
can be reconstructed. Since we can easily construct a quantum circuit that
implements the functions $\frac{1+F}{2}$ and $\frac{1+iF}{2}$ instead of $F$
by QSVT, we can estimate each of
$\left\\{F\left(\sum_{j}v_{kj}\psi_{j}\right)\right\\}_{k=1}^{N_{1}}$ with an
additive error $\beta$ with $\mathcal{O}\left(\sqrt{N_{1}}/\beta\right)$ uses
of the circuit in Fig. 4. To estimate all of them, we need to repeat it for
$N_{1}$ times and thus require $\mathcal{O}\left(N_{1}^{3/2}/\beta\right)$
uses of the circuit.

Finally, as a natural extension, we consider how to implement a multi-layer
neural network. We first consider how to achieve the two-layer neural network.
More concretely, we wish to prepare a state in the form of,

$\displaystyle\sum_{l=1}^{N_{2}}F\left[\sum_{k=1}^{N_{1}}v_{lk}^{(2)}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\right]\ket{l},$
(26)

$V^{(\ell)}=\sum_{k,j}v_{kj}^{(\ell)}\ket{k}\bra{j}$ are tranable unitaries
connecting the $(\ell-1)$-th and $\ell$-th layers, that is, we take input
vector $\\{\psi_{j}\\}$ as zeroth layer. We assumed the $\ell$-th layer has
$N_{\ell}$ nodes. Let $\mathcal{A}_{1}$ be the quantum circuit for a single-
layer neural network, i.e., the circuit in Fig. 4 with $U=V^{(1)}U_{\psi}$. It
is easy to see that the state of Eq. (26) can essentially be constructed by
using $\left(\mathcal{I}_{5}\otimes
V^{(2)}\otimes\mathcal{I}_{n+1}\right)\mathcal{A}_{1}$ as the state
preparation oracle in Theorem 5. Detailed analysis of this process is
presented in Appendix D. $\ell$-layer neural network can be achieved by
repeating the above steps $\ell-1$ times. As shown in Appendix D, a quantum
state which corresponds to an $\ell$-layer neural network can be generated by
$\mathcal{\tilde{O}}\left(d^{\ell}\sqrt{N_{1}N_{2}\cdots N_{\ell-1}}\right).$

##  V Conclusion

We have deﬁned a task called NTCA considering how to apply nonlinear functions
onto the amplitudes of a quantum state. To this end, we introduced block-
encoding of amplitudes, which encodes amplitudes of a quantum state on a block
element of a unitary operator by using the state preparation oracle. This
allows us to treat complex amplitudes of a quantum state as singular values of
a matrix encoded into a unitary operator and hence to apply QSVT for NTCA.
Since the proposed mapping from a state preparation oracle to a block-encoding
unitary is very general, we expect that it can be applied widely when we want
to process a quantum state in such a way that cannot be achieved by a simple
unitary transformation. As a concrete example of such an application, we
proposed to use our algorithm to implement neural networks on quantum
computers, where complex amplitudes are used as nodes for the neural networks
and nonlinear transformations, which cannot be realized by a unitary
operation, are performed by the proposed NTCA. From scaling analysis, our
result implies that there could be a complexity-theoretic benefit to use a
quantum computer to process and perform a nonlinear transformation on a high
dimensional input data, while it still relies on several assumptions such as
the state preparation oracle. It is an interesting open question whether the
proposed nonlinear transformation or quantum neural network can provide an
advantage in classical machine learning tasks. We think that it is, at least,
inevitable to apply quantum machine learning for quantum data since a
systematic nonlinear transformation is essentially missing in quantum systems
without the proposed method.

###### Acknowledgements.

NG is supported by Hirose Foundation. KM is supported by JST PRESTO Grant No.
JPMJPR2019 and JSPS KAKENHI Grant No. 20K22330. KF is supported by JSPS
KAKENHI Grant No. 16H02211, JST ERATO JPMJER1601, and JST CREST JPMJCR1673.
This work is supported by MEXT Quantum Leap Flagship Program (MEXT QLEAP)
Grant Number JPMXS0118067394 and JPMXS0120319794. We also acknowledge support
from JST COI-NEXT program.

##  Appendix A Details for Theorem 4

###  A.1 Derivation of Eq. (8)

  1. 1.

Apply oracle $U$ on data qubits, the state will be

$\displaystyle\ket{k}_{\mathrm{ad}}\left(\sum_{j=1}^{N}c_{j}\ket{0}^{\otimes
a}\ket{j}\right)_{\mathrm{da}}\ket{0}_{B}.$ (27)

  2. 2.

Perform Hadamard gate on the $B$ ancilla qubit and controlled-$U$ gate with
$B$ as controlled qubits, we prepare the state

$\displaystyle\ket{k}_{\mathrm{ad}}\biggl{(}$
$\displaystyle\bigl{(}\sum_{j=1}^{N}c_{j}\ket{j}\bigl{)}_{\mathrm{da}}\ket{0}_{B}+\ket{0}^{\otimes
n}_{\mathrm{da}}\ket{1}_{B}\biggl{)}.$ (28)

  3. 3.

Apply Toffoli gates with address qubits and $B$ ancilla qubit as controlled
gates and Hadamard gate on the $B$ ancilla qubits, we have

$\displaystyle\ket{k}_{\mathrm{ad}}\ket{\Psi_{k}}_{\mathrm{da,B}}:=$
$\displaystyle\frac{\ket{k}}{2}_{\mathrm{ad}}\biggl{(}\bigl{(}\sum_{j=1}^{N}c_{j}\ket{j}+\ket{k}\bigl{)}_{\mathrm{da}}\ket{0}_{\mathrm{B}}$
$\displaystyle+\bigl{(}\sum_{j=1}^{N}c_{j}\ket{j}-\ket{k}\bigl{)}_{\mathrm{da}}\ket{1}_{\mathrm{B}}\biggl{)}.$
(29)

###  A.2 Eigenvalues and eigenvectors of $G$

Here, we derive the eigenvalues and eigenvectors of $G$ defined in Eq. 9. It
can be seen that $G$ has invariant two-dimensional subspaces spanned by
$\\{\ket{k}\ket{\Psi_{k0}},\ket{k}\ket{\Psi_{k1}}\\}_{k=1}^{N}$ for each
$k\in\\{1,...,N\\}$. Let
$\overline{Z_{B}},\overline{WS_{0}W^{\dagger}},\overline{G}$ be the operations
$Z_{B},WS_{0}W^{\dagger}$ and $G$ acting only on these subspaces.

The matrix representation of $\overline{Z_{B}},\overline{WS_{0}W^{\dagger}}$
can be written as,

$\displaystyle\overline{Z_{B}}=$
$\displaystyle|k\rangle|\Psi_{k0}\rangle\langle\Psi_{k0}|\langle
k|-|k\rangle|\Psi_{k1}\rangle\langle\Psi_{k1}|\langle k|$ (30)
$\displaystyle\overline{WS_{0}W^{\dagger}}=$
$\displaystyle(1-2\alpha^{2}_{k})|k\rangle|\Psi_{k0}\rangle\langle\Psi_{k0}|\langle
k|$
$\displaystyle+(1-2\beta^{2}_{k})|k\rangle|\Psi_{k1}\rangle\langle\Psi_{k1}|\langle
k|$
$\displaystyle-2\alpha_{k}\beta_{k}\left(|k\rangle|\Psi_{k1}\rangle\langle\Psi_{k0}|\langle
k|+|k\rangle|\Psi_{k0}\rangle\langle\Psi_{k1}|\langle k|\right).$ (31)

Thus, we have,

$\displaystyle\overline{G}=$
$\displaystyle\overline{WS_{0}W^{\dagger}}\overline{Z_{B}}$ (32)
$\displaystyle=$
$\displaystyle(1-2\alpha^{2}_{k})|k\rangle|\Psi_{k0}\rangle\langle\Psi_{k0}|\langle
k|$
$\displaystyle-(1-2\beta^{2}_{k})|k\rangle|\Psi_{k1}\rangle\langle\Psi_{k1}|\langle
k|$
$\displaystyle-2\alpha_{k}\beta_{k}(|k\rangle|\Psi_{k1}\rangle\langle\Psi_{k0}|\langle
k|-|k\rangle|\Psi_{k0}\rangle\langle\Psi_{k1}|\langle k|).$ (33)

Therefore, eigenvectors of $\overline{G}$ can be written as

$\displaystyle\ket{k}_{\mathrm{ad}}\ket{\Psi_{k\pm}}_{\mathrm{da,B}}=\frac{1}{\sqrt{2}}\ket{k}_{\mathrm{ad}}(\ket{\Psi_{k0}}\pm
i\ket{\Psi_{k1}})_{\mathrm{da,B}},$ (34)

with the corresponding eigenvalue $-x_{k}\pm i\sqrt{1-x_{k}^{2}}$. $G$ has the
same eigenvalues and eigenvectors.

###  A.3 One- and two-qubit gate counts

To construct $\tilde{U}$ as in Theorem 4, we use controlled-$G$ and
controlled-$G^{\dagger}$ one time, which consists of controlled-$H$,
controlled-$Z$, Toffoli gates on four qubits, and controlled-$S_{0}$ gates.
Decomposition of Toffoli gates is described in [33]. Notice that here we use
Toffoli gates $\mathcal{O}(n)$ times. The (controlled) conditional phase shift
gate $S_{0}=\mathcal{I}_{n+2}-2|0\rangle\langle 0|$ on $n$ qubits can be
performed with a Toffoli gate on $(n+2)$ qubits and two Hadamard gates. As
described in [34], Toffoli gate on $(n+2)$ qubits can be performed with
$\mathcal{O}(n)$ gates with an additional ancilla qubit. Therefore, in total,
we use controlled-$U$ and controlled-$U^{\dagger}$ four times and
$\mathcal{O}(n)$ one- and two-qubit gates for Theorem 4.

##  Appendix B Detailed error analysis for Theorem 5

Note that $\mathcal{P}$ is a $(1,4,\epsilon/(16\gamma))$-block-encoding of a
matrix whose eigenvalues are $P^{\prime}(x_{k})/(4\gamma)$. For all
$x_{k}\in[-1,1]$, we have

$\displaystyle\left|P^{\prime}(x_{k})/(4\gamma)-P^{\prime\prime}(x_{k})\right|\leq\varepsilon/(16\gamma
N),$ (35)

where $P^{\prime\prime}(x_{k})$ denotes the exact value achieved by Lemma 3.
By assumption, we have $|P(x_{k})-P^{\prime}(x_{k})|\leq\varepsilon/(4N)$.
Therefore,

$\displaystyle|P(x_{k})-4\gamma P^{\prime\prime}(x_{k})|$ $\displaystyle\leq$
$\displaystyle|P(x_{k})-P^{\prime}(x_{k})|+|P^{\prime}(x_{k})-4\gamma
P^{\prime\prime}(x_{k})|$ $\displaystyle\leq$
$\displaystyle|P(x_{k})-P^{\prime}(x_{k})|+4\gamma|P^{\prime}(x_{k})/(4\gamma)-P^{\prime\prime}(x_{k})|\leq\frac{\varepsilon}{2N},$
(36)

where the inequalities comes from triangle inequality. The same discussion
applies for the imaginary part, i.e., $|Q(y_{k})-4\gamma
Q^{\prime\prime}(y_{k})|\leq\varepsilon/(2N)$ for all $y_{k}\in[-1,1]$.
Finally, for all $x_{k},y_{k}\in[-1,1]$ we have

$\displaystyle|4\gamma P^{\prime\prime}(x_{k})+4\gamma
Q^{\prime\prime}(y_{k})-P(x_{k})-Q(y_{k})|\leq\frac{\varepsilon}{N},$ (37)

satisfying the error bound condition for NTCA.

##  Appendix C Polynomial approximation of tanh

Here, we show that $P(x)=\tanh(x)$ can be approximated to an precision
$\varepsilon$ with a degree $d=\mathcal{O}(\log(1/\varepsilon))$ polynomial
$P^{\prime}_{d}(x)$ in the sense that
$|P^{\prime}_{d}(x)-\tanh(x)|\leq\varepsilon$. It suffices to use the simple
Taylor series. By Taylor expansion,

$\displaystyle\tanh(x)=\sum_{n=1}^{\infty}(-1)^{n-1}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1},$
(38)

where $B_{2n}$ is the Bernoulli number. We take,

$\displaystyle
P^{\prime}_{d}(x)=\sum_{n=1}^{d}(-1)^{n-1}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1}.$
(39)

Then, the error can be written as,

$\displaystyle|P^{\prime}_{d}(x)-\tanh(x)|=\sum_{n=d+1}^{\infty}(-1)^{n-1}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1}.$
(40)

As mentioned in Ref. [35], we have

$\displaystyle|B_{2n}|<5\sqrt{\pi n}\left(\frac{n}{\pi e}\right)^{2n}.$ (41)

Also, since $\left(n/e\right)^{n}\leq n!$, we have

$\displaystyle\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}$ $\displaystyle<5\sqrt{\pi
n}\left(\frac{4\frac{n}{\pi e}}{\frac{2n}{e}}\right)^{2n}$
$\displaystyle=5\sqrt{\pi n}\left(\frac{2}{\pi}\right)^{2n}.$ (42)

Further, since $\sqrt{d+1}\leq(\pi/2)^{d+1}$ for $d\geq 0$, we have

$\displaystyle 5\sqrt{\pi(d+1)}\left(\frac{2}{\pi}\right)^{2d+2}\leq
5\sqrt{\pi}\left(\frac{2}{\pi}\right)^{d+1}.$ (43)

Therefore, the error in Eq. (40) can be bounded by

$\displaystyle\sum_{n=d+1}^{\infty}(-1)^{n-1}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1}$
$\displaystyle<$
$\displaystyle\sum_{n=d+1}^{\infty}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1}$
$\displaystyle\leq$
$\displaystyle\sum_{n=d+1}^{\infty}5\sqrt{\pi}\left(\frac{2}{\pi}\right)^{d+1}$
$\displaystyle=$
$\displaystyle\frac{5\sqrt{\pi}}{1-(2/\pi)}\left(\frac{2}{\pi}\right)^{d+1}.$
(44)

It follows that the error bound of $\varepsilon$ can be achieved by setting
$d=\mathcal{O}\left(\log\left(1/\varepsilon\right)\right)$.

##  Appendix D Generalization to multi-layer neural network

We first consider how to perform a two-layer quantum neural network. For
simplicity, we assume $|P(x)|,|Q(x)|\leq 1$ for all $x\in[-1,1]$ so that
$\gamma=1$. We also assume $P(x)$ and $Q(x)$ can exactly be expressed by a
$d$-degree polynomial to avoid a complicated discussion about errors. Let
$\mathcal{A}_{1}$ be the quantum circuit that outputs the state

$\displaystyle\frac{1}{8\sqrt{N_{1}}}\sum_{k=1}^{N_{1}}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\ket{0}^{\otimes
5}\ket{k}_{\mathrm{ad}}\ket{0}^{\otimes n+1}_{\mathrm{da,B}}+\cdots.$ (45)

Also, let $\tilde{\mathcal{A}}_{1}:=\left(\mathcal{I}_{5}\otimes
V^{(2)}\otimes\mathcal{I}_{n+1}\right)\mathcal{A}_{1}$. Then,

$\displaystyle\begin{split}&\tilde{\mathcal{A}}_{1}\ket{0}^{\otimes 2n+6}=\\\
&\frac{1}{8\sqrt{N_{1}}}\sum_{l=1}^{N_{2}}\left[\sum_{k=1}^{N_{1}}v_{lk}^{(2)}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\right]\ket{0}^{\otimes
5}\ket{l}_{\mathrm{ad}}\ket{0}^{\otimes
n+1}_{\mathrm{da,B}}+\cdots.\end{split}$ (46)

$\tilde{\mathcal{A}}_{1}$ can be considered as the state preparation oracle
for Theorem 5 to achieve the two-layer neural network. However, before doing
so, we remove the coefficient $1/(8\sqrt{N_{1}})$ by uniform singular value
amplification [4, 12]. To do so, first note that, by Theorem 4, we can
construct a block-encoding $\tilde{G}^{(2)}$ of a matrix
$-\frac{1}{2}\left(G^{(2)}+(G^{(2)})^{\dagger}\right)$ whose eigenvalues are

$\displaystyle\left\\{\frac{1}{8\sqrt{N_{1}}}\sum_{k=1}^{N_{1}}v_{lk}^{(2)}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\right\\}_{k=1}^{N_{1}}.$
(47)

The coefficient $1/(8\sqrt{N_{1}})$ from these eigenvalues can be removed by
using uniform singular value amplification which uses $\tilde{A}_{1}$ and
$\tilde{A}^{\dagger}_{1}$ $\tilde{\mathcal{O}}\left(\sqrt{N_{1}}\right)$
times. Let $\tilde{\mathcal{A}}_{1}^{\prime}$ be the circuit constructed by
the above procedure, i.e.,

$\displaystyle\begin{split}&\tilde{\mathcal{A}}_{1}^{\prime}\ket{0}^{\otimes
2n+6}\\\
&=\sum_{l=1}^{N_{2}}\left[\sum_{k=1}^{N_{1}}v_{lk}^{(2)}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\right]\ket{0}^{\otimes
5}\ket{l}_{\mathrm{ad}}\ket{0}^{\otimes
n+1}_{\mathrm{da,B}}+\cdots.\end{split}$ (48)

After this step, we use Theorem 5 on $\tilde{\mathcal{A}}_{1}^{\prime}$ to
achieve the state

$\displaystyle\frac{1}{8\sqrt{N_{2}}}\sum_{l=1}^{N_{2}}F\left[\sum_{k=1}^{N_{1}}v_{lk}^{(2)}F\left(\sum_{j=1}^{N}v_{kj}^{(1)}\psi_{j}\right)\right]\ket{0}^{\otimes
5}\ket{l}_{\mathrm{ad}}\ket{0}^{\otimes n+1}_{\mathrm{da,B}}+\cdots.$ (49)

Counting the $U_{\psi}$ operations used in this whole procedure, this state
can be prepared with $\mathcal{\tilde{O}}\left(d^{2}\sqrt{N_{1}}\right)$ uses
of $U_{\psi}$.

An $\ell$-layer neural network can be achieved by repeating the above
procedure $\ell-1$ times, and it uses
$\mathcal{\tilde{O}}\left(d^{\ell}\sqrt{N_{1}N_{2}\cdots N_{\ell-1}}\right)$
times of $U_{\psi}$. If we want to further obtain the values of each amplitude
with an additive error $\beta$, we perform the amplitude estimation on the
resulting state. This would require repeating the whole circuit for
$\mathcal{O}\left(N_{\ell}^{3/2}/\beta\right)$ times, and the total number of
$U_{\psi}$ is calculated to be
$\mathcal{\tilde{O}}\left(d^{\ell}N_{\ell}\sqrt{N_{1}N_{2}\cdots
N_{\ell}}/\beta\right)$.

## References

  * Abrams and Lloyd [1998] D. S. Abrams and S. Lloyd, Physical Review Letters 81, 3992–3995 (1998).
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103, 150502 (2009).
  * Low and Chuang [2017a] G. H. Low and I. L. Chuang, Phys. Rev. Lett. 118, 010501 (2017a).
  * Gilyén  _et al._ [2019] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, in  _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) p. 193–204.
  * Martyn  _et al._ [2021] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, A grand unification of quantum algorithms (2021), arXiv:2105.02859 [quant-ph] .
  * Childs and Wiebe [2012] A. M. Childs and N. Wiebe, Quantum Info. Comput. 12, 901–924 (2012).
  * Berry  _et al._ [2015a] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett. 114, 090502 (2015a).
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Quantum 3, 163 (2019).
  * Childs  _et al._ [2017] A. M. Childs, R. Kothari, and R. D. Somma, SIAM Journal on Computing 46, 1920–1950 (2017).
  * Berry  _et al._ [2015b] D. W. Berry, A. M. Childs, and R. Kothari, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science 10.1109/focs.2015.54 (2015b).
  * Yoder  _et al._ [2014] T. J. Yoder, G. H. Low, and I. L. Chuang, Phys. Rev. Lett. 113, 210501 (2014).
  * Low and Chuang [2017b] G. H. Low and I. L. Chuang, Hamiltonian simulation by uniform spectral amplification (2017b), arXiv:1707.05391 [quant-ph] .
  * Chakraborty  _et al._ [2019] S. Chakraborty, A. Gilyén, and S. Jeffery, in  _46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 132, edited by C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019) pp. 33:1–33:14.
  * Mitarai  _et al._ [2019] K. Mitarai, M. Kitagawa, and K. Fujii, Phys. Rev. A 99, 012301 (2019).
  * Pinkus [2000] A. Pinkus, Journal of Approximation Theory 107, 1 (2000).
  * Brassard  _et al._ [2000] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, arXiv e-prints , quant-ph/0005055 (2000), arXiv:quant-ph/0005055 [quant-ph] .
  * Cleve  _et al._ [1998] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 339–354 (1998).
  * Schuld and Petruccione [2018] M. Schuld and F. Petruccione,  _Supervised Learning with Quantum Computers_ (Springer International Publishing, 2018).
  * Giovannetti  _et al._ [2008] V. Giovannetti, S. Lloyd, and L. Maccone, Phys. Rev. Lett. 100, 160501 (2008).
  * Kerenidis and Prakash [2016] I. Kerenidis and A. Prakash, Quantum recommendation systems (2016), arXiv:1603.08675 [quant-ph] .
  * Mitarai  _et al._ [2018] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Phys. Rev. A 98, 032309 (2018).
  * Schuld and Killoran [2019] M. Schuld and N. Killoran, Phys. Rev. Lett. 122, 040504 (2019).
  * Havlíček  _et al._ [2019] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567, 209–212 (2019).
  * Farhi and Neven [2018] E. Farhi and H. Neven, Classification with quantum neural networks on near term processors (2018), arXiv:1802.06002 [quant-ph] .
  * Glick  _et al._ [2021] J. R. Glick, T. P. Gujarati, A. D. Corcoles, Y. Kim, A. Kandala, J. M. Gambetta, and K. Temme, Covariant quantum kernels for data with group structure (2021), arXiv:2105.03406 [quant-ph] .
  * Kusumoto  _et al._ [2021] T. Kusumoto, K. Mitarai, K. Fujii, M. Kitagawa, and M. Negoro, npj Quantum Information 7, 94 (2021).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, Nature communications 5, 4213 (2014).
  * Ng and Jordan [2002] A. Ng and M. Jordan, in  _Advances in Neural Information Processing Systems_, Vol. 14, edited by T. Dietterich, S. Becker, and Z. Ghahramani (MIT Press, 2002).
  * Lund  _et al._ [2017] A. P. Lund, M. J. Bremner, and T. C. Ralph, npj Quantum Information 3, 15 (2017).
  * Dallaire-Demers and Killoran [2018] P.-L. Dallaire-Demers and N. Killoran, Phys. Rev. A 98, 012324 (2018).
  * Romero and Aspuru-Guzik [2019] J. Romero and A. Aspuru-Guzik, Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions (2019), arXiv:1901.00848 [quant-ph] .
  * Zoufal  _et al._ [2019] C. Zoufal, A. Lucchi, and S. Woerner, npj Quantum Information 5, 103 (2019).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010).
  * He  _et al._ [2017] Y. He, M.-X. Luo, E. Zhang, H.-K. Wang, and X.-F. Wang, International Journal of Theoretical Physics 56, 2350 (2017).
  * Leeming [1989] D. J. Leeming, Journal of Approximation Theory 58, 124 (1989).