A duplication-free quantum neural network for universal approximation

Abstract

The universality of a quantum neural network refers to its ability to approximate arbitrary functions and is a theoretical guarantee for its effectiveness. A non-universal neural network could fail in completing the machine learning task. One proposal for universality is to encode the quantum data into identical copies of a tensor product, but this will substantially increase the system size and the circuit complexity. To address this problem, we propose a simple design of a duplication-free quantum neural network whose universality can be rigorously proved. Compared with other established proposals, our model requires significantly fewer qubits and a shallower circuit, substantially lowering the resource overhead for implementation. It is also more robust against noise and easier to implement on a near-term device. Simulations show that our model can solve a broad range of classical and quantum learning problems, demonstrating its broad application potential.

I Introduction

Machine learning (ML) is a powerful data-analyzing tool that has generated a series of impactful results in image recognition [1, 2, 3], natural language processing [4, 5, 6], self-driving [7, 8, 9], etc. Meanwhile, quantum machine learning has become an emerging interdisciplinary subject combining machine learning with quantum computing. It studies two fundamental questions [10], one on applications of classical ML to quantum problems [11, 12, 13, 14, 15, 16], and the other on implementations of ML algorithms on a quantum processor. Recent works point out that implementing ML algorithms on a quantum computer to process quantum data requires exponentially fewer experiments than dealing with the same task on a classical computer [17]. In addition, it has been shown that many ML algorithms can be implemented on a quantum machine with certain levels of advantage, ranging from data fitting [18], support vector machine [19], nearest neighbors [20], principle component analysis [21], and linear regression [22], to PageRank algorithm [23], reinforcement learning [24, 25, 26], anomaly detection [27] and Boltzmann machine [28]. For other ML topics, especially the quantum neural networks (QNNs), the existence of quantum advantage is largely unknown [29], although an interesting result on the prediction advantage for QNNs has been recently achieved [30].

A neural network (NN) is a parameterized composite mapping comprised of activation functions and is very powerful in data fitting. A QNN is an NN implemented on a quantum computer [31] and there are various proposals to design it, such as the variational QNN [32, 33]. Besides quantum advantage, designing an effective and efficient QNN is also important. Not every QNN design effectively solves the given ML problem, and the concept of universal approximation is introduced to explain why some neural networks fail to work [34, 35]. Universal approximation, or the universality of an NN, refers to its ability to approximate arbitrary functions. For classical NNs, universality is easy to achieve; for QNNs, a smart design is required to make them universal and practical. In fact, the universality of NNs is closely related to the nonlinear activation functions, and the key point of designing a universal QNN is to generate the desired nonlinearity for function fitting. One method is to construct the quantum neurons, which are the building blocks of some QNNs [36, 37, 38, 39, 40, 41]; the other method is to construct a variational QNN from a parameterized quantum circuit, and the nonlinearity can be achieved by duplicating the quantum data into a tensor product of multiple copies [42, 43]. Examples of the latter method include the quantum circuit learning (QCL) algorithm [32] and the circuit-centric quantum classifiers (CCQ) algorithm [33]. So far, the universality of the QCL algorithm has been proved using the Weierstrass theorem, while the universality of the CCQ algorithm remains open. For both QCL and CCQ, approximating a highly-nonlinear function would require a tensor product of many data-encoding subsystems, resulting in a large overall system size with a considerable circuit complexity, conflicting with the principle of NISQ computing where a relatively small quantum system with a shallow circuit is preferred.

To address this problem, we propose a duplication-free quantum neural network (DQNN) based on a variational quantum circuit and rigorously prove its universality. Our model utilizes the classical sigmoid function to generate nonlinearity without duplicating the quantum data into a tensor product of multiple copies. Compared with the CCQ or QCL algorithms, our DQNN significantly reduces the system size and gate complexity, and hence the overall noise effect. Therefore, it is more likely to be implemented on near-term devices. Numerical simulations show that our DQNN outperforms the other two variational QNN algorithms with better performance on typical regression and classification problems and is more robust against noise. In addition, through solving a broad range of classical and quantum learning problems, our model has well demonstrated its wide application potential.

II Two types of designs for universal approximation

Before we discuss the DQNN design, let’s briefly review two common types of designs for the universal approximation of a classical NN. It turns out that universality is closely related to different kinds of convergence. Type I approximation relies on pointwise convergence; a typical example is the polynomial approximation, using the Weierstrass theorem and polynomials to approximate arbitrary functions; Type II approximation depends on the convergence in Lebesgue integration, e.g., $L^2$-norm convergence. For polynomial approximation, there are several limitations. First, the Weierstrass theorem is only valid on a compact set, while many NN problems are defined on unbounded set, on which polynomials could fail to approximate a Lebesgue integrable function. For example, the function $f(x)=e^{-x}$ defined on $[0,+\mathrm{\infty })$ can not be well approximated by polynomials since the latter diverges to $\pm \mathrm{\infty }$ while $e^{-x}$ vanishes as $x\to \mathrm{\infty }$. Second, polynomial approximation has a numerical problem called Runge’s phenomenon [44] when the polynomial order becomes very large, which is why using high-order polynomials for function fitting is not favored in practical use. Due to these limitations, polynomials are ineffective in designing universal NNs. It has been proved that the necessary and sufficient condition for a universal feedforward NN is that its activation functions are not polynomial [35]. In comparison, Type II approximation utilizes basis functions such as the hat function in finite-element method [45] or the sigmoid/ReLU function composite with linear function in neural networks [46]. Usually, the optimal approximation is the solution to a minimization problem, and the error is evaluated in a suitable function norm. In particular, universal NNs based on $L^2$-norm approximation are widely applied and found to be very effective. Such examples include the ones with activation functions, such as the sigmoid or the ReLU functions. Hence, this work aims to discuss how to construct a universal and effective QNN based on $L^2$ approximation, using the trick analogous to the sigmoid function instead of the polynomials. We expect that such QNN is effective in a broad range of applications compared to the QNN based on polynomial approximation.

III DQNN and its universality

Mathematically, a variational QNN is a mapping $q_{𝜽}:𝒙\in {ℝ}^d\to q_{𝜽}(𝒙)\in ℝ$ built on a parameterized quantum circuit $U(𝜽)$. It involves a hybrid quantum-classical algorithm that utilizes a quantum processor to generate the output $q_{𝜽}(𝒙)$ for each input $𝒙$, and a classical processor to optimize $𝜽$ to solve learning problems. Specifically, given an unknown function $f:𝒙\to f(𝒙)$, and a data set $D={\{({𝒙}^{(i)},y^{(i)})\}}_{i=1}^m$, where $y^{(i)}=f({𝒙}^{(i)})$ is the label of ${𝒙}^{(i)}$, the aim of QNN is to find an optimal ${𝜽}^{*}$ such that $q_{{𝜽}^{*}}$ best approximates the target function $f$. Our DQNN model consists of three parts, a quantum processor, a classical processor and a classical optimizer, as illustrated in Fig. 1(a). First, each data point $𝒙={[x_1,x_2,\mathrm{\cdots },x_d]}^T\in {ℝ}^d$ is encoded into a state of an $n$-qubit register ($n=\lceil \log d\rceil$):

$$|\overline{𝒙}⟩=\frac{1}{\gamma }{[x_1,x_2,\mathrm{\cdots },x_d,\tilde{x},0,\mathrm{\cdots }0]}^T\in {ℂ}_2^{\otimes n},$$ (1)

using the amplitude encoding method [47], where $\tilde{x}\equiv \frac{\Vert 𝒙\Vert }{1+\Vert 𝒙\Vert }$ is a padding term chosen by the user and $\gamma$ is a normalization factor (Appendix A). After initial state preparation, we apply to $|\overline{𝒙}⟩$ a series of variational quantum circuits ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^{n_{\text{cir}}}$ according to $|{\overline{𝒙}}_f^{(j)}⟩=U^{(j)}({𝜽}^{(j)})|\overline{𝒙}⟩$, followed by measurements of a set of observables ${\{B_i\}}_{i=1}^{n_{\text{obs}}}$, to obtain the outcomes ${⟨B_i⟩}_{{𝜽}^{(j)},\overline{}x}=\mathrm{Tr}(|{\overline{𝒙}}_f^{(j)}⟩⟨{\overline{𝒙}}_f^{(j)}|B_i)$. The choices of $\{B_i\}$ are not unique and they can be chosen randomly from the generalized Pauli basis ${\{P_l\}}_{l=1}^{4^n}$ where $P_l=A_1^{(l)}\otimes A_2^{(l)}\otimes \mathrm{\cdots }\otimes A_n^{(l)}$ with $A_k^{(l)}\in \{I,X,Y,Z\}$, and $\{X,Y,Z\}$ are the Pauli matrices. $U^{(j)}({𝜽}^{(j)})$ comprises $L$-layers of quantum circuits. Each layer consists of $n$ parameterized $R$-rotations (with one on each qubit), and $n$ parameterized controlled-$R$ gates, as shown in Fig. 1, with

Notice that the order of the $2n$ gates in each layer is not unique and can be chosen randomly [33]. Next, based on ${⟨B_i⟩}_{{𝜽}^{(j)},\overline{}x}$ and the sigmoid function $\sigma (x)=1/(1+e^{-x})$, the classical processor computes and obtains the output:

$$q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})\equiv \sum _{j=1}^{n_{\text{cir}}}\sum _{i=1}^{n_{\text{obs}}}{\alpha }_i^{(j)}\sigma (a_i^{(j)}({⟨B_i⟩}_{{𝜽}^{(j)},\overline{𝒙}}-c_i^{(j)}))$$ (2)

with $a_i^{(j)}>0$, $c_i^{(j)}\in [0,1]$ where $𝜽$ and $(𝒂,𝒄,𝜶)$ are parameters to be trained. The entire process from $|\overline{𝒙}⟩$ to $q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})$ is summarized in Fig. 1. Finally, one can find the optimal values of $(𝜽,𝒂,𝒄,𝜶)$ to solve the given learning problem, through gradient-based optimization using algorithms such as SGD [48], ADAM [49] or BFGS [50]. The benefit of such construction is that DQNN can be proved to be universal based on $L^2$ approximation, which is summarized in the following theorem:

Theorem 1.

Let $\overline{G}$ be a subset of the complex sphere $𝕊$ in ${ℂ}_{\mathrm{2}}^{\mathrm{\otimes }n}$, and $f\mathit{}\mathrm{(}\overline{𝐱}\mathrm{)}\mathrm{:}\overline{G}\mathrm{\to }ℝ$ be an arbitrary square-integrable function on $\overline{G}$. We define the following parameterized functions:

$q_{{𝒛}_1,\mathrm{\cdots },{𝒛}_{n_s},𝒂,𝒄,𝜶}(\overline{𝒙})\equiv {\displaystyle \sum _{j=1}^{n_s}}{\alpha }_j\sigma (a_j({|⟨\overline{𝒙}|{𝒛}_j⟩|}^2-c_j))$ (3)

and denote $Q\mathit{}\mathrm{(}\overline{G}\mathrm{)}\mathrm{\equiv }\mathrm{\{}{q}_{{𝐳}_{\mathrm{1}}\mathrm{,}\mathrm{\cdots }\mathrm{,}{𝐳}_{n_s}\mathrm{,}𝐚\mathrm{,}𝐜\mathrm{,}𝛂}\mathrm{\}}$ as the set of all such functions, where $n_s\mathrm{\in }\mathbb{N}$, ${\mathrm{\{}{𝐳}_j\mathrm{\}}}_{j\mathrm{=}\mathrm{1}}^{n_s}\mathrm{\subset }𝕊$, $𝐚\mathrm{\in }{ℝ}_{\mathrm{+}}^{n_s}$, $𝐜\mathrm{\in }{\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{]}}^{\mathrm{\otimes }{n}_s}$, and $𝛂\mathrm{\in }{ℝ}^{n_s}$. Then $Q\mathit{}\mathrm{(}\overline{G}\mathrm{)}$ is dense in $L^{\mathrm{2}}\mathit{}\mathrm{(}\overline{G}\mathrm{)}$ in the following sense: for any $ϵ\mathrm{>}\mathrm{0}$,

(4)

The detailed proof of Theorem 1 can be found in Appendix B. It turns out that any $q_{{𝒛}_1,\mathrm{\cdots },{𝒛}_{n_s},𝒂,𝒄,𝜶}\in Q(\overline{G})$ in Eq. (3) can be generated as the output of the DQNN in Eq. (2). Specifically, given the parameters $({𝒛}_1,\mathrm{\cdots },{𝒛}_{n_s},𝒂,𝒄,𝜶)$, we can design a DQNN with a single observable $B\equiv |b⟩⟨b|$, $n_{\text{obs}}=1$, and a series of quantum circuits ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^{n_s}$ such that $U^{(j)}({𝜽}^{(j)})|b⟩=|z_j⟩$. Then the output of the DQNN in Eq. (2) is reduced to:

$q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})$ $={\displaystyle \sum _{j=1}^{n_s}}{\alpha }_j\sigma (a_j({⟨B⟩}_{{𝜽}^{(j)},\overline{𝒙}}-c_j))$

$={\displaystyle \sum _{j=1}^{n_s}}{\alpha }_j\sigma (a_j({|⟨\overline{𝒙}|{𝒛}_j⟩|}^2-c_j))$

$=q_{{𝒛}_1,\mathrm{\cdots },{𝒛}_{n_s},𝒂,𝒄,𝜶}(\overline{𝒙}).$ (5)

(a) large

Figure 1: (a) The framework of the DQNN consists of three parts, a quantum processor, a classical processor and a classical optimizer. Measurement results of a quantum processor are the inputs of a classical processor. The parameters in the quantum and classical processors are updated by a classical optimizer. (b) One layer variational quantum circuit of $U^{(j)}({𝜽}^{(j)})$. (c) The transformation from $|\overline{𝒙}⟩$ to $q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})$. Yellow balls represent the quantum qubits; green circles represent the classical sigmoid function.

Thus we have proved the following corollary:

Corollary 1.

The DQNN designed in Fig. 1 (c) with the output in Eq. (2) is universal.

Notice that choosing multiple ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^{n_{\text{cir}}}$ and a single observable $B$ is only a sufficient condition to prove the universality in Corollary 1. In practice, we often design a DQNN with a single $U(𝜽)$ ($n_{\text{cir}}=1$) and a set of $\{B_i\}$ as the first trial to solve the given problem. If it is not good enough, we then construct a new DQNN with a larger $n_{\text{cir}}$. It turns out a DQNN with $n_{\text{cir}}=1$ is often sufficient for most learning problems we have studied. In addition, in the proof of Corollary 1, we have assumed that the variational circuits $\{U^{(j)}({𝜽}^{(j)})\}$ with $U^{(j)}({𝜽}^{(j)})|b⟩=|z_j⟩$ can be generated by our designed multi-layer variational circuits as shown in Fig. 1 (b). More layers in $U^{(j)}({𝜽}^{(j)})$ will make it more powerful to approximate arbitrary unitary gate, but will also make the optimization process computationally more expensive. Hence, in practice, we often construct a DQNN starting from a single $U(𝜽)$ consisting of one or two layers. In the following, we will study the performance of DQNN with different values of $n_{\text{cir}}$, and for simplicity, we will denote the corresponding network as DQNN${}_{n_{\text{cir}}}$.

IV Performance comparison among QNN models

In Section II, we have mentioned that universality serves as a necessary condition to build an effective QNN, and among the two types of universal design, an NN with $L^2$ convergence using sigmoid basis functions works more effectively in a broader range of applications. As shown above, the nonlinearity and the universality of DQNN originates essentially from the $L^2$ convergence of sigmoids functions, which is distinctive from other polynomial-approximation-based QNN models, including the CCQ [33] and the QCL [32], whose nonlinearity is mainly generated by duplicating the same data-encoding state into a tensor product of multiple subsystems. In this way, DQNN has significantly reduced the number of qubits required to construct a universal QNN. In the following, we will demonstrate the advantages of DQNN by comparing its performance with those of the two well-established QNN models, the CCQ and the QCL.

For an $n_{\text{tot}}$-qubit QNN model, we define its complexity as $C\equiv n_{\text{gate}}{n}_{\text{m}}$, where $n_{\text{gate}}$ denotes the number of quantum gates and $n_{\text{m}}$ denotes the number of quantum measurements. Notice that given a measurement precision, $n_{\text{m}}$ is proportional to the number of measurement observables $n_{\text{obs}}$. Hence, with a further assumption that the QNN variational circuit can be efficiently generated, i.e., $n_{\text{gate}}=O(\text{poly}(n_{\text{tot}})$, the overall complexity of the QNN then becomes $C=O(\text{poly}(n_{\text{tot}})n_{\text{obs}})$. We hope to figure out the numbers of qubits and observables required to approximate an $M$-order polynomial function $f(𝒙)={\sum }_{i=0}^M{c}_i{𝒙}^i$ with $\Vert 𝒙\Vert =1$ using CCQ, QCL and DQNN respectively. We denote by $n_{\text{data}}$ the number of qubits in the data-encoding register, and by $n_{\text{copy}}$ the number of copies of the data-encoding register used in a QNN model. To approximate such $f$, CCQ requires $n_{\text{copy}}=\frac{M}{2}$ duplicates of the data-encoding register $|\overline{𝒙}⟩=\frac{1}{\gamma }{\sum }_{i=1}^{d+1}{x}_i|i⟩$ such that the amplitude of the input state, $|{\psi }_{𝒙}⟩={|\overline{𝒙}⟩}^{\otimes \frac{M}{2}}$, is an $\frac{M}{2}$-order polynomial of $𝒙$. After applying a circuit $U(𝜽)$, we measure the expectation values of a given observable $B$ according to ${⟨B⟩}_{𝜽,𝒙}=⟨{\psi }_{𝒙}|U{(𝜽)}^{†}BU(𝜽)|{\psi }_{𝒙}⟩$. The output of the CCQ is an $M$-order polynomial of $𝒙$. Then the goal of CCQ is to find the best value $𝜽={𝜽}^{*}$ through optimization such that $𝒙\to {⟨B⟩}_{{𝜽}^{*},𝒙}$ is the optimal function to approximate $𝒙\to f(𝒙)$. The number of qubits in the data-encoding register is $n_{\text{data}}=\lceil \log d\rceil$ and the number of observables is $n_{\text{obs}}=1$. Hence the total complexity of CCQ is equal to $C_{\text{CCQ}}=O(\text{poly}(M\lceil \log d\rceil ))$. For QCL, a $d$-dimensional classical data $𝒙$ is encoded into a $d$-qubit data-encoding register as $\rho (𝒙)=\frac{1}{2^d}{\otimes }_{i=1}^d(\text{I}+x_{i}X+\sqrt{1-x_i^2}Z])$ using several single-qubit rotation gates. In order to generate an $M$-order polynomial, $\rho (𝒙)$ is duplicated into $M$ identical copies in a tensor product as ${\rho }_{\text{in}}(𝒙)={\otimes }_{j=1}^M\rho (𝒙)$. Applying a circuit $U(𝜽)$ to ${\rho }_{\text{in}}$, we measure the expectation value of a given observable $B$. The outcome ${⟨B⟩}_{𝜽,𝒙}$ is an $M$-order polynomial of $𝒙$. Through optimization, we can find the best value ${𝜽}^{*}=𝜽$ such that $𝒙\to {⟨B⟩}_{{𝜽}^{*},𝒙}$ will well approximate $𝒙\to f(𝒙)$. The total number of qubits in QCL is $n_{\text{tot}}=Md$ and the number of observables is $n_{\text{obs}}=1$. Hence the total complexity of QCL is $C_{\text{QCL}}=O(\text{poly}(Md))$.

Different from the above two duplication-based QNN models, DQNN only uses $\lceil \log d\rceil$ qubits to encode $𝒙$ as $|\overline{𝒙}⟩=\frac{1}{\Vert 𝒙\Vert }{\sum }_{i=1}^{d+1}{x}_i|i⟩$. We sequentially apply a set of variational quantum circuits ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^{n_{\text{cir}}}$ to $|\overline{𝒙}⟩$ and measure the expectation ${⟨B_i⟩}_{{𝜽}^{(j)},\overline{𝒙}}=⟨\overline{𝒙}|U^{(j)†}({𝜽}^{(j)})B_i{U}^{(j)}({𝜽}^{(j)})|\overline{𝒙}⟩$ for a set of chosen observables ${\{B_i\}}_{i=1}^{n_{\text{obs}}}$. Next we apply the parameterized classical sigmoid function $\sigma$ and derive the final output $q_{𝜽,𝒂,𝒄,𝜶}$. Through the optimization, we can find the optimal values $({𝜽}^{*},{𝒂}^{*},{𝒄}^{*},{𝜶}^{*})$ to approximate the function $f$. The number of measurement observables $n_{\text{obs}}$ is determined by $f$. Hence the total complexity of DQNN is $C_{\text{DQNN}}=O(\text{poly}(\lceil \log d\rceil )n_{\text{obs}})$. The comparison is summarized in Table 1. It can be seen that for large $d$ and large $M$, our DQNN can significantly reduce the total complexity to generate nonlinearity. More details can be found in Appendix C.

Algorithm	$n_{\text{copy}}$	$n_{\text{data}}$	Complexity
QCL	$M$	$d$	$O(\text{poly}(Md))$
CCQ	$\frac{M}{2}$	$\lceil \log d\rceil$	$O(\text{poly}(M\lceil \log d\rceil ))$
DQNN	$1$	$\lceil \log d\rceil$	$O(\text{poly}(\lceil \log d\rceil )n_{\text{obs}})$

Table 1: The number of required qubits and the circuit complexity among three proposals to approximate an $M$-order polynomial function $f$ of $𝒙$.

Figure 2: (a) The regression data set generated by a polynomial function. (b) The classification data set with the ring-shaped boundaries. The points in the yellow part are labeled $0$; the others are labeled $1$. (c) The approximation process of the DQNN${}_1$ with one variational quantum circuit and $4$ observables in solving the regression problem based on the dataset in (a). In the task, one more sigmoid function (the rightmost node) is added into the DQNN${}_1$ to transform the output of DQNN${}_1$ into a range $(0,1)$.

To demonstrate that our DQNN has advantage in solving classical ML problems and in reducing circuit complexity, we apply DQNN, QCL, and CCQ to two typical supervised learning problems, a regression problem and a classification problem, and compare their performance. The first problem is learning from a data set $\{{𝒙}^{(i)},y^{(i)}\}$ to approximate a highly nonlinear polynomial $f(𝒙)=(0.7156-1.0125x_1^2+x_1^4)(0.7156-1.0125x_2^2+x_2^4)$ with $x_1,x_2\in {[-0.8,0.8]}^2$ (Fig. 2). For input ${𝒙}^{(i)}$, the output of the QNN is denoted as $q^{(i)}$. One can define the relative error $ϵ\equiv \frac{1}{N}{\sum }_i|\frac{q^{(i)}-y^{(i)}}{y^{(i)}}|$ to measure the performance of the QNN in solving regression problems. A tiny relative error implies that the QNN approximates the target function $f$ well. First, we run the hybrid optimization process for each model based on the data set. To show the effectiveness of the three QNN models, we choose different values of the number of layers for each model so that their circuit complexity $C$ is similar in size. We use the same definition of $n_{\text{copy}}$ as in the above section. Then, we compare the optimal relative errors achieved for each model. We choose two types of DQNN to solve the regression problem. One has a single-layer variational quantum circuit and multiple observables. We name it DQNN${}_1$. The other has $4$ single-layer variational quantum circuits and one observable. We name it DQNN${}_4$. We find that, with no duplicate, $n_{\text{copy}}=1$, the relative error achieved by DQNN is substantially lower than those achieved by QCL and CCQ, as shown in Table 2(a). If we add one more duplicate to both the QCL and the CCQ models, their optimal relative error will decrease, but their complexity will increase and surpass that of the DQNN. In addition, we implement such comparison for a few other examples, and simulation results suggest that DQNN can prominently reduce the circuit complexity to approximate highly nonlinear functions compared with QCL and CCQ. The approximation process of the DQNN${}_1$ with $4$ observables is shown in Fig. 2, and more details of the comparison can be found in Appendix D.

We apply the three models to a binary classification problem on a ring-shaped data set in the second task. The boundaries of the two sub-datasets are determined by six curves $x_1^2+x_2^2=0.16$, $x_1^2+x_2^2=0.81$, and $x_1=x_2=\pm 1$ (Fig. 2). One can use classification accuracy to quantify the performance of QNN model in solving classification problems, which is defined as $ϵ\equiv \frac{1}{N}{\sum }_i{1}_{\delta (q^{(i)}-y^{(i)})}$ where $q^{(i)}$ is the output of QNN, $y^{(i)}$ represents the label of ${𝒙}^{(i)}$ and $\delta$ is the Dirac delta function [51]. Analogous to the first task, we choose the DQNN with one variational quantum circuit and multiple observables (DQNN${}_1$) and the DQNN with $4$ variational quantum circuits and one observable (DQNN${}_4$) for the classification task. We choose appropriate values for $n_{\text{copy}}$ and $n_{\text{lay}}$, so that the circuit complexity $C$ of the three models is similar in size. After optimizing the three QNN models, we find that accuracy achieved by the DQNN is substantially higher than those achieved by QCL and CCQ. In addition, increasing the number of duplicates does help QCL and CCQ to improve their optimal accuracy, but even a $5$-copy model (with 12 qubits) for QCL or CCQ cannot perform equally well as a DQNN with only two qubits (Table 2(b)). Next, we implement such a comparison for a few other examples. Simulation results suggest that DQNN can prominently reduce the circuit complexity compared to QCL and CCQ, but maintain a good performance in solving classification problems.

Model	$n_{\text{data}}$	Copy number ($n_{\text{copy}}$)	# Qubits ($n_{\text{tol}}$)	# Layers ($n_{\text{lay}}$)	# Observables ($n_{\text{obs}}$)	$C$	Relative error
DQNN${}_1$	2	1	2	1	4	48	6.79%
DQNN${}_4$	2	1	2	1	1	48	5.46%
QCL	2	1	2	4	1	48	8.21%
CCQ	2	1	2	4	1	51	12.92%
QCL	2	2	4	5	1	120	7.35%
CCQ	2	2	4	4	1	99	4.74%

(a) Regression problem to approximate $f(𝒙)=(0.7156-1.0125x_1^2+x_1^4)(0.7156-1.0125x_2^2+x_2^4)$

Model	$n_{\text{data}}$	Copy number ($n_{\text{copy}}$)	# Qubits ($n_{\text{tol}}$)	# Layers ($n_{\text{lay}}$)	# Observables ($n_{\text{obs}}$)	$C$	Accuracy
DQNN${}_1$	2	1	2	1	20	240	91.40%
DQNN${}_4$	2	1	2	1	1	48	97.63%
QCL	2	2	4	5	2	240	74.18%
CCQ	2	2	4	10	1	243	75.20%
QCL	2	6	12	10	2	1440	76.93%
CCQ	2	6	12	10	1	723	80.63%

(b) A classification problem defined on a ring-shaped dataset

Table 2: A comparison of the performance among DQNN, QCL and CCQ in two classical ML problems. $n_{\text{data}}$ indicates the number of qubits to store the classical data. The total number of qubits in each QNN model is equal to $n_{\text{tot}}=n_{\text{data}}{n}_{\text{copy}}$. We use $C\equiv n_{\text{gate}}{n}_{\text{obs}}$ to represent the circuit complexity where $n_{\text{gate}}$ is the number of quantum gates in the variational quantum circuit and $n_{\text{obs}}$ is the number of observables. For QCL and CCQ, $n_{\text{copy}}$, $n_{\text{lay}}$ are free to choose; for DQNN, $n_{\text{lay}}$ and $n_{\text{obs}}$ are free to choose. We choose two types of DQNN in the simulations: DQNN${}_1$ contains one circuit and multiple observables, while DQNN${}_4$ contains four circuits and one observable. All of the results are obtained by averaging $10$ independent simulations.

Since the DQNN can reduce the circuit complexity, we expect that it can achieve a better performance in the presence of noise, and hence is easier to be implemented on NISQ devices. We will consider two types of noise in this work: one is the coherent noise caused by the imprecision of the classical control on the parameter values in the QNN circuits; the other is the decoherence generated by interactions between the quantum register and its environment. We add a coherent noise ${ϵ}_j$ to the $j$-th parameter, ${\theta }_j$, in the variational circuit according to ${\tilde{\theta }}_j={\theta }_j+{ϵ}_j$ when we train the three QNN models, and test their performance under the noisy environment. The coherent noise ${ϵ}_j$ is generated by sampling from a Gaussian distribution, $N(0,{\mathrm{\Delta }}^2)$ where $\mathrm{\Delta }$ indicates the noise intensity. It can be seen from Fig. 3 and 3 that for the regression task, the DQNN achieves lower relative error than QCL and CCQ when we increase the coherent noise. Meanwhile, for the classification task (as shown in Fig. 3), DQNN is more robust than the other two when the coherent noise increases. In addition to the coherent noise, we further apply the decoherence, $ϵ$, to the two-qubit control gates, $U_{CR}$, contained in the quantum circuits according to $ϵ(U_{CR}\rho U_{CR}^{†})=(1-p)U_{CR}\rho U_{CR}^{†}+p\sum P_i{U}_{CR}\rho U_{CR}^{†}{P}_i^{†}$ where $\{P_i\}$ indicates the complete Pauli basis and $p$ represents the probability of decoherence occurrence. From Fig. 3, we can find that, in the regression task, the DQNN has a significantly lower relative error than QCL and CCQ as the probability of decoherence increases. These numerical results demonstrate that the DQNN can decrease the influence of noise accumulation in the training process and is more likely to be implemented on near-term devices.

Figure 3: Comparison of the robustness for three QNN models in solving the regression and classification problems. In the regression task, we use DQNN${}_1$, $2$-qubit QCL and $2$-qubit CCQ for the comparison. In the classification task, we use DQNN${}_1$, $4$-qubit QCL and $4$-qubit CCQ for the comparison. (a)-(b) Relative errors achieved by QCL, CCQ and DQNN as the coherent noise increases in the regression task. (c) The comparison among three QNNs in the classification task as the coherent noise increases. (d) The comparison among three QNNs in the regression task as the probability of decoherence occurrence increases.

Besides the comparison among three QNN models over two supervised learning problems, we further demonstrate the performance of the different QNNs in solving the typical real-world machine learning problem based on the handwritten digits data set, MNIST [52]. In this task, a QNN is first trained with $60,000$ figures, each of which has a number ranging from $0$ to $9$, and then is tested with $10,000$ new figures to generate the classification accuracy. A figure in the MNIST data set is reshaped to be a $256$-dimensional vector and encoded into an $8$-qubit quantum state by using the amplitude encoding method. Since the QCL needs $256$ qubits to encode the classical data, it is intractable to implement the QCL in solving this task and we only compare the performance of the DQNN and the CCQ. For our DQNN, we use $20$ $2$-layer variational circuits and one observable $B=Z^{(1)}\otimes Z^{(2)}\otimes \mathrm{\cdots }\otimes Z^{(8)}$. The classification accuracy over $10,000$ new figures can achieve $94.36\%$. For the CCQ, we use one variational quantum circuit and a set of POVM operators ${\{B_j\}}_{j=1}^{10}$ to generate the final output. We adopt different layers for the variational quantum circuit, however, the performance of the CCQ is still significantly lower than the DQNN. For instance, the CCQ with a $20$-layer variational quantum circuit only achieves $83.52\%$ accuracy. The result demonstrates that the QNN without a strict universality guarantee will fail in solving machine learning problems.

V Comparison with classical neural networks

To demonstrate that our DQNN can perform at least as effectively as the classical NN, we apply the DQNN to solve three typical real-world classification problems and further compare its performance with the classical NN in the minimum parameters required the number of iterations to achieve a similar classification accuracy. Since our DQNN is essentially with a single hidden layer, we will choose a single-hidden-layer classical neural network for the comparison. On the handwritten digits data set, MNIST [52], we implement a binary classification (MNIST${}_2$) to distinguish the digits $0$ and $1$, and a $3$-target classification (MNIST${}_3$) to recognize the digits $0$, $1$, $2$. Each sample is reshaped into a $256$-dimensional vector and taken as the input of DQNN and classical NN. Meanwhile, we implement two more classification tasks based on the Wine data set [53] and the Breast Cancer data set [53]. We use a $4$-qubit state to store the $13$-dimensional classical data for the Wine problem, and a $4$-qubit state to store the $10-$dimensional data for the Breast Cancer problem. As shown in Table 3, the DQNN performs as well as the classic neural networks in discovering complex patterns hidden in real-world data sets. Notice that DQNN uses fewer parameters to achieve similar accuracy than the classical counterpart but is at the extra cost of required iterations in some cases.

Model	Task	$N_{\text{Train}}$	$N_{\text{Test}}$	# Parameters	# Iterations	${\text{Acc}}_{\text{Train}}$	${\text{Acc}}_{\text{Test}}$
DQNN	MNIST${}_2$	$12665$	$2115$	$54$	$150$	$98.66\%$	$99.05\%$
Classical NN	MNIST${}_2$	$12665$	$2115$	$259$	$26$	$98.54\%$	$99.07\%$
DQNN	MNIST${}_3$	$18623$	$3147$	$495$	$254$	$98.61\%$	$99.03\%$
Classical NN	MNIST${}_3$	$18623$	$3147$	$523$	$367$	$98.48\%$	$99.02\%$
DQNN	Wine	$143$	$35$	$27$	$172$	$96.29\%$	$100\%$
Classical NN	Wine	$143$	$35$	$83$	$230$	$97.04\%$	$100\%$
DQNN	Breast Cancer	$560$	$39$	$34$	$282$	$94.46\%$	$95.74\%$
Classical NN	Breast Cancer	$560$	$39$	$55$	$105$	$93.57\%$	$95.89\%$

Table 3: A comparison of the minimum parameters required and the number of iterations to achieve a similar classification accuracy between DQNN and classical neural network on three typical real-world data sets. We use the ADAM algorithm to optimize the parameters. $N_{\text{Train}}$ and $N_{\text{Test}}$ respectively denote the number of the training set and the test set. ${\text{Acc}}_{\text{Train}}$ and ${\text{Acc}}_{\text{Test}}$ represent the classification accuracy on each data set.

VI Quantum phase recognition

Besides the classical ML problems, our DQNN model can solve ML problems on quantum data sets. In the following, we concentrate on a class of quantum phase recognition problems, the discrimination of the ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$ symmetry-protected topological (SPT) phase on a $S=1$ Haldane chain [54]. The ground state of the Hamiltonian,

$H=$ $-J{\displaystyle \sum _{i=1}^{N-2}}{Z}^{(i)}{X}^{(i+1)}{Z}^{(i+2)}-h_1{\displaystyle \sum _{i=1}^N}{X}^{(i)}$

$-h_2{\displaystyle \sum _{i=1}^{N-1}}{X}^{(i)}{X}^{(i+1)},$

has three topological phases, the SPT phase, the paramagnetic phase and the antiferromagnetic phase, where $h_1$ and $h_2$ are parameters. Our goal is to identify whether a given state sampled from the phase diagram in Fig. 4 belongs to the SPT phase. To complete such a task, we take $20\times 20$ equally spaced points from $h_1\in [0,1.6]$ and $h_2\in [-1.6,1.6]$ as the training set and $64\times 64$ equally spaced points as the test set. If the ground state belongs to the SPT phase, it is labeled ${[1,0]}^T$; otherwise, it is labeled ${[0,1]}^T$. We numerically implement the DQNN with a single $15$-qubit variational quantum circuit with $420$ parameters and $10$ observables. After training, the accuracy of the DQNN on the test data achieves $99.10\%$. It indicates that our DQNN model has solved the quantum phase recognition problem with good performance. However, the training set to train the DQNN is larger than the training set to train the quantum convolutional neural network [55] for phase recognition task. The reason for the difference is that the DQNN used in the comparison is only a prototype, while the quantum convolutional neural network in [55] has been optimized for this task, with a stronger ability to analyze the local information of quantum states. Hence, as a future work, we hope to improve the DQNN design to optimize its performance for the given ML problem.

Figure 4: The phase diagram of the $S=1$ Haldane chain. The phase boundary is generated by the 2-degree polynomial regression based on some boundary points.

VII Conclusion

There have been many successes in achieving larger scale and higher fidelity of the NISQ devices. These improvements provide the quantum neural network with the opportunity to deal with larger data sets and even outperform the classical counterpart. This paper presents a duplication-free quantum neural network model, DQNN, to solve machine learning problems. Meanwhile, we provide it with the universal guarantee to approximate any arbitrary continuous function using several variational quantum circuits, multiple measurement observables and the classical parameterized sigmoid function. We can enhance the expressibility of DQNN by increasing the number of quantum circuits and the number of observables without requiring auxiliary qubits. This property for the number of qubits makes DQNN more likely to be implemented on intermediate-scale quantum computers.

Unlike other variational QNN proposals, DQNN utilizes the classical computer in the hybrid system to generate nonlinearity. Without duplicates, DQNN significantly reduces the number of required qubits and decreases circuit complexity compared with two well-known QNN models. Our simulation results demonstrate that, compared with QCL and CCQ, DQNN uses fewer qubits and fewer quantum gates to outperform the other two QNN models and hence weaken the influence of the circuit noise. Furthermore, DQNN requires fewer parameters than the classical counterpart but is at an extra cost of the iterations in some cases. DQNN can also be used to solve quantum problems. These results indicate that the DQNN is an efficient QNN model which can find the patterns hidden in the classical and quantum data sets.

Like the classical naive neural network, DQNN can be considered a subroutine to construct more complex quantum deep learning models. In addition, DQNN can also be improved by optimizing its structure for the given ML problem. For example, DQNN can be combined with the concept of recurrent neural network to efficiently solve the natural language processing tasks, or integrated into a quantum reinforcement learning framework. Moreover, due to its simple design, DQNN is relatively easy to be implemented on NISQ devices for QNN demonstration.

Appendix A Amplitude encoding method

Suppose $\{{𝒙}^{(i)}\}$ of the data set $D=\{{𝒙}^{(i)},y^{(i)}\}$ is contained in a subset $G$ of ${ℝ}^d$. Without loss of generality, we can choose an appropriate coordinate frame through translation such that $\mathrm{𝟎}\notin G$ and every $𝒙\in G$ satisfies with constants ${\kappa }_1$ and ${\kappa }_2$. In order to apply variational QNN, we encode the classical data into the states of a quantum register. In this work, we define the encoding mapping $F:G\to \overline{G}$ such that $|\overline{𝒙}⟩=F(𝒙)$ is an $n$-qubit state in the Hilbert space ${ℂ}_2^{\otimes n}$ with $d\le 2^n$:

$$F:𝒙={(x_1,\mathrm{\dots },x_d)}^T\mapsto |\overline{𝒙}⟩\equiv {\gamma }^{-1}{(x_1,\mathrm{\dots },x_d,\tilde{x},0,\mathrm{\dots },0)}^T$$ (6)

where $\tilde{x}=\frac{\Vert 𝒙\Vert }{1+\Vert 𝒙\Vert }$, $\gamma ={({\Vert 𝒙\Vert }^2+{\tilde{x}}^2)}^{\frac{1}{2}}$. It is easy to validate that $\frac{{\kappa }_1}{1+{\kappa }_1}\le \tilde{x}\le \frac{{\kappa }_2}{1+{\kappa }_2}$ and

(7)

with ${\overline{x}}_{d+1}={\gamma }^{-1}\tilde{x}$. Such encoding method is called amplitude encoding, since the classical information $𝒙$ is encoded into the amplitudes of $|\overline{𝒙}⟩$, as illustrated in Fig. 5. Therefore, approximating $f(𝒙):G\to ℝ$ is equivalent to the approximation of $f(F^{-1}|\overline{𝒙}⟩):\overline{G}\to ℝ$.

Appendix B Proof of Theorem 1

It suffices to show $Q(\overline{G})=\{q_{{𝒛}_1,\mathrm{\cdots },{𝒛}_{n_s},𝒂,𝒄,𝜶}\}$ is dense in $L^2(\overline{G})$. We will prove it by contradiction. Assume that the closure $\overline{Q(\overline{G})}\ne L^2(\overline{G})$. By the Hahn-Banach theorem [56], there exists a bounded linear functional $l$ on $L^2(\overline{G})$ such that $l(Q(\overline{G}))=0$ and $l\ne 0$. By the Riesz representation theorem [57], there exists a function $g(\overline{𝒙})\in L^2(\overline{G})$ such that the linear functional $l$ can be represented as

$$l(f)={\int }_{\overline{G}}f(\overline{𝒙})g(\overline{𝒙})𝑑\mu \text{for all}f\in L^2(\overline{G}).$$ (8)

Note that $l\ne 0$ implies $g\ne 0$ on $\overline{G}$. Therefore, the following two sets $S_1=\{\overline{𝒙}\in \overline{G}:g(\overline{𝒙})>0\}$ and are measurable and at least one of them has a positive measure. Without loss of generality, we assume that $g(\overline{𝒙})>0$ almost everywhere in an open subset $E\subset \overline{G}$ with $\mu (E)>0$. Substituting $f(𝒙)=\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))\in Q(\overline{G})$ into above equation, and in view of $l(Q(\overline{G}))=0$, we have:

$${\int }_{\overline{G}}\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))g(\overline{𝒙})𝑑\mu =0.$$ (9)

As the open set $E$ contains a small ball , we will show that, by choosing large enough $a>0$ and , the function $\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))$ tends to $1$ in a smaller ball $B({𝒛}^{*},{\delta }_1)\subset B({𝒛}^{*},\delta )$ and vanishes quickly outside of $B({𝒛}^{*},{\delta }_1)$, which leads to a contradiction to Eq. (9).

Since $\overline{G}$ is a real subset of the unit sphere,

$${|\overline{𝒙}-{𝒛}^{*}|}^2=2-2⟨\overline{𝒙}|{𝒛}^{*}⟩\text{for all}\overline{𝒙}\in \overline{G},$$ (10)

which implies that ${|⟨\overline{𝒙}|{𝒛}^{*}⟩|}^2>c$ is equivalent to one of the following two cases:

(11)

For $c\to 1$, case (i) means $\overline{𝒙}$ is sufficiently close to ${𝒛}^{*}$, and (ii) means $\overline{𝒙}$ is sufficiently close to $-{𝒛}^{*}$, but the latter case is impossible. Specifically, for $c$ sufficiently close to $1$, and a given value ${\kappa }_2>0$, we can choose $c$ such that $c\ge {(1-2{(1+{(1+{\kappa }_2)}^2)}^{-1})}^2$, and together with Eq. (7), we have:

$${|\overline{𝒙}+{𝒛}^{*}|}^2\ge {(z_{d+1}^{*}+{\overline{x}}_{d+1})}^2\ge 4{(1+{(1+{\kappa }_2)}^2)}^{-1}\ge 2(1-\sqrt{c})$$ (12)

If (ii) were true, then by ${|\overline{𝒙}-{𝒛}^{*}|}^2+{|\overline{𝒙}+{𝒛}^{*}|}^2=4$, we would find , contradictory to Eq. (12). Hence case (ii) is impossible. Therefore, when $c\to 1$, ${|⟨\overline{𝒙}|{𝒛}^{*}⟩|}^2>c$ is only equivalent to case (i). Passing to the limit $a\to +\mathrm{\infty }$, we get

(13)

with ${\delta }_1={(2(1-\sqrt{c}))}^{\frac{1}{2}}$. Taking $c$ sufficiently close to $1$, we have ${\delta }_1\le \delta$, and from Eq. (9) we obtain

$0$ $={\displaystyle {\int }_{\overline{G}}}\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))g(\overline{𝒙})𝑑\mu$ (14)

$\to {\displaystyle {\int }_{B({𝒛}^{*},{\delta }_1)}}1g(\overline{𝒙})𝑑\mu >0(\text{as}a\to +\mathrm{\infty }),$ (15)

which is a contradiction. Hence, we conclude that $Q(\overline{G})$ is dense in $L^2(\overline{G})$. Thus for any $f\in L^2(\overline{G})$ and $ϵ>0$, there exists a $q(\overline{𝒙})\in Q(\overline{G})$ such that

$${\Vert f-q\Vert }_{L^2(\overline{G})}^2={\int }_{\overline{G}}{|f(\overline{𝒙})-q(\overline{𝒙})|}^2𝑑\mu \le ϵ,$$ (16)

which proves Theorem 1.

Remark 1.

If $\sigma$ is a ReLU-type function, then the conclusion still holds. In fact, instead of Eq.(13), we have $\sigma \mathit{}\mathrm{(}a\mathit{}\mathrm{(}{\mathrm{|}\mathrm{⟨}\overline{𝐱}\mathrm{|}𝐳\mathrm{⟩}\mathrm{|}}^{\mathrm{2}}\mathrm{-}c\mathrm{)}\mathrm{)}\mathrm{>}\mathrm{0}$ for all $\overline{𝐱}\mathrm{\in }B\mathit{}\mathrm{(}{𝐳}^{\mathrm{*}}\mathrm{,}{\delta }_{\mathrm{1}}\mathrm{)}$ and $\sigma \mathit{}\mathrm{(}a\mathit{}\mathrm{(}{\mathrm{|}\mathrm{⟨}\overline{𝐱}\mathrm{|}𝐳\mathrm{⟩}\mathrm{|}}^{\mathrm{2}}\mathrm{-}c\mathrm{)}\mathrm{)}\mathrm{=}\mathrm{0}$ otherwise, which leads to the contradiction:

$0$ $={\displaystyle {\int }_{\overline{G}}}\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))g(\overline{𝒙})𝑑\mu$

$={\displaystyle {\int }_{B({𝒛}^{*},{\delta }_1)}}\sigma (a({|⟨\overline{𝒙}|𝒛⟩|}^2-c))g(\overline{𝒙})𝑑\mu >0.$

Appendix C Introduction to other variational QNN models

In order to compare the performance of DQNN with other models, in this section, we will present a brief introduction to two established variational QNN models, circuit-centric quantum classifier (CCQ) [33] and quantum circuit learning (QCL) [32], and will apply these models to solve the following quantum learning problem: constructing a QNN to approximate an $M$-order polynomial $f$: $𝒙\to f(𝒙)$, where $M$ is an even number.

First, we consider the CCQ model, where the classical data $𝒙={[x_1,x_2,\mathrm{\cdots },x_d]}^T\in {ℝ}^d$ with $\Vert 𝒙\Vert =1$ is mapped into a $n_{\text{data}}$-qubit register with $n_{\text{data}}\equiv \lceil \log d\rceil$, using the following encoding scheme:

$$|\overline{𝒙}⟩=\frac{1}{\gamma }{[x_1,x_2,\mathrm{\cdots },x_d,\tilde{x},0,\mathrm{\cdots }0]}^T\in {ℂ}_2^{\otimes n_{\text{data}}},$$ (17)

where $\tilde{x}$ is a padding term chosen by the user, and $\gamma$ is the normalization factor. Notice that $|\overline{𝒙}⟩$ alone is not sufficient as an input to generate the desired nonlinearity, and an input state as a tensor product of copies of $|\overline{𝒙}⟩$ is required to generate the high-order terms in $f(𝒙)$. Specifically, to approximate the polynomial $f$, the input state $|{\psi }_{𝒙}⟩$ of CCQ is chosen as:

$|{\psi }_{𝒙}⟩$ $={|\overline{𝒙}⟩}^{\otimes n_{\text{copy}}}={|\overline{𝒙}⟩}^{\otimes \frac{M}{2}}$ (18)

$={\displaystyle \frac{1}{{\gamma }^{\frac{M}{2}}}}{[x_1^{\frac{M}{2}},x_1^{\frac{M}{2}-1}{x}_2,\mathrm{\cdots },{\tilde{x}}^{\frac{M}{2}},0,\mathrm{\cdots },0]}^T\in {ℂ}_2^{\otimes n_{\text{tot}}},$ (19)

where $n_{\text{tot}}\equiv n_{\text{copy}}{n}_{\text{data}}=\frac{1}{2}M\lceil \log d\rceil$. Here we have chosen the number of copies of $|\overline{𝒙}⟩$ in $|{\psi }_{𝒙}⟩$ to be $n_{\text{copy}}=\frac{M}{2}$.

Denoting the variational quantum circuit in CCQ by $U(𝜽)$, the output state $|{\psi }_{𝜽,𝒙}⟩$ becomes:

(20)

where each amplitude $p_i(𝜽,𝒙)$ of $|{\psi }_{𝜽,𝒙}⟩$ is an $\frac{M}{2}$-order polynomial of $𝒙$. Hence, for a chosen observable $B$, the measurement outcome ${⟨B⟩}_{𝜽,𝒙}\equiv ⟨{\psi }_{𝜽,𝒙}|B|{\psi }_{𝜽,𝒙}⟩$ is an $M$-order polynomial of $𝒙$. Then the goal of CCQ is to choose an appropriate $B$ and to find the best value $𝜽={𝜽}^{*}$ through quantum-classical hybrid optimization such that $𝒙\to {⟨B⟩}_{{𝜽}^{*},𝒙}$ is the optimal function to approximate $𝒙\to f(𝒙)$. The quantum circuit for CCQ is presented in Fig. 6.

Figure 6: The quantum circuit for CCQ to approximate the $M$-order polynomial function $𝒙\to f(𝒙)$.

Next, we consider the QCL model, where the data point $𝒙={[x_1,x_2,\mathrm{\cdots },x_d]}^T$ is encoded into a $d$-qubit data-encoding pure-state density operator:

$\rho (𝒙)$ $=|{\psi }_{𝒙}⟩⟨{\psi }_{𝒙}|$

$={\otimes }_{i=1}^d{(R_i^Y(\arcsin x_i)|0⟩}_i⟨0{|}_i{R}_i^{Y†}(\arcsin x_i))$

$={\displaystyle \frac{1}{2^d}}{\otimes }_{i=1}^d\left(I+x_{i}X+\sqrt{1-x_i^2}Z\right)$ (21)

where $R_i^Y(𝜽)$ represents a Pauli-$Y$ rotation on the $i$-th qubit. Analogous to the CCQ case, $\rho (𝒙)$ along is not sufficient as an input to generate the desired nonlinearity. In order to generate an $M$-order polynomial, $\rho (𝒙)$ is duplicated into $M$ identical copies in a tensor product. Specifically, the input state of QCL is chosen as:

${\rho }_{\text{in}}(𝒙)$ $={\otimes }_{j=1}^M\rho (𝒙)$

$={\displaystyle \frac{1}{2^{Md}}}{\otimes }_{j=1}^M({\otimes }_{i=1}^d[I+x_{i}X+\sqrt{1-x_i^2}Z).$ (22)

Applying a parameterized quantum circuit $U(𝜽)$ to ${\rho }_{\text{in}}(𝒙)$, followed by a measurement of a chosen observable $B$, we obtain the measurement outcome as the output of QCL:

$${⟨B⟩}_{𝜽,𝒙}\equiv \mathrm{Tr}\left(U(𝜽){\rho }_{\text{in}}(𝒙)U^{†}(𝜽)B\right)$$ (23)

Define $\{A_l\}\equiv {\{I,X,Z\}}^{\otimes Md}$ as a set of generalized Pauli operators. Due to Eq. (22), ${\rho }_{\text{in}}(𝒙)$ can be expanded in terms of $\{A_l\}$:

$${\rho }_{\text{in}}(𝒙)=\frac{1}{2^{Md}}\sum _{l=1}^{3^{Md}}{p}_l(x_1,\mathrm{\cdots },x_d,\sqrt{1-x_1^2},\mathrm{\cdots },\sqrt{1-x_d^2})A_l,$$ (24)

where $(x_1,\mathrm{\cdots },x_d,x_1^{\prime },x_2^{\prime },\mathrm{\cdots },x_d^{\prime })\in {ℝ}^{2d}\to p_l(x_1,x_2,\mathrm{\cdots },x_d,x_1^{\prime },x_2^{\prime },\mathrm{\cdots },x_d^{\prime })$, $l=1,2,\mathrm{\cdots },3^{Md}$, are polynomials with respect to all $2d$ variables. Assuming $B$ is unitarily diagonalized as

(25)

we substitute Eq. (24) and Eq. (25) into Eq. (23) and obtain:

${⟨B⟩}_{𝜽,𝒙}$ $={\displaystyle \frac{1}{2^{Md}}}{\displaystyle \sum _{l=1}^{3^{Md}}}{b}_l(𝜽,\lambda )p_l$

$b_l(𝜽,\lambda )$ $\equiv {\displaystyle \sum _{j=1}^{2^{Md}}}{\lambda }_j\text{Tr}\left(A_l{(WU(𝜽))}^{†}|e_j⟩⟨e_j|WU(𝜽)\right),$

where $\{|e_j⟩\}$ is the set of computational basis. Thus, the task of QCL is to choose an appropriate observable $B$ and to find the best value $𝜽={𝜽}^{*}$ through quantum-classical hybrid optimization such that $𝒙\to {⟨B⟩}_{{𝜽}^{*},𝒙}$ will well approximate $𝒙\to f(𝒙)$. The quantum circuit for QCL is given in Fig. 7.

Figure 7: The quantum circuit for QCL to approximate the $M$-order polynomial function $𝒙\to f(𝒙)$.

In summary, to prepare the desired initial state to solve the same polynomial approximation problem, it requires $\frac{1}{2}M\lceil \log d\rceil$ qubits for CCQ, and $Md$ qubits for QCL. In comparison, it only requires $\lceil \log d\rceil$ qubits for DQNN to prepare the input state as $|\overline{𝒙}⟩$ in Eq. (17). This is a significant reduction for large $M$ and large $d$. Specifically, for DQNN, after we prepare the input state $|\overline{𝒙}⟩$, we sequentially apply a series of variational quantum circuits, ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^{n_{\text{cir}}}$, and quantum measurement to derive the measurement outcome ${⟨B_i⟩}_{{𝜽}^{(j)},𝒙}=⟨\overline{𝒙}|U^{(j)†}({𝜽}^{(j)})B_i{U}^{(j)}({𝜽}^{(j)})|\overline{𝒙}⟩$ for a set of chosen observables ${\{B_i\}}_{i=1}^{n_{\text{obs}}}$. Next, we apply a parameterized classical sigmoid function $\sigma$ to each ${⟨B_i⟩}_{{𝜽}^{(j)},\overline{𝒙}}$ to construct the final output $q_{𝜽,𝜶,𝒂,𝒄}(\overline{𝒙})$. Finally, we implement the hybrid optimization to find the optimal values of $(𝜽,𝜶,𝒂,𝒄)$ to approximate the target polynomial, where $𝜶$, $𝒂$, $𝒄$ are parameters used to construct the final output $q_{𝜽,𝜶,𝒂,𝒄}$, with details in the following.

Appendix D Solving regression problems using DQNN, CCQ and QCL

In the following, we aim to solve a regression task of approximating a highly nonlinear function:

$f:(x_1,x_2)\in {[-0.8,0.8]}^2\to$ $(0.716-1.0125x_1^2+x_1^4)$

$\times (0.716-1.0125x_2^2+x_2^4)\in ℝ$ (26)

using DQNN, QCL and CCQ. The data set $D\equiv \{{𝒙}^{(i)},y^{(i)}\}={\{(x_1^{(i)},x_2^{(i)},y^{(i)})\}}_{i=1}^{400}$ is of size $400$, with $(x_1^{(i)},x_2^{(i)})$ randomly chosen from the square ${[-0.8,0.8]}^2$, and each label $y^{(i)}$ is calculated according to $y^{(i)}=f(x_1^{(i)},x_2^{(i)})$. The goal of a QNN is to generate a nonlinear function $𝒙\to q_{𝜽}(𝒙)$ to approximate $f$ by optimizing over the parameters $𝜽$ of the QNN.

(a) DQNN${}_1$ based on one single-layer quantum circuit and $4$ observables.

(b) DQNN${}_4$ based on $4$ single-layer quantum circuits and one observable.

Figure 8: The implementation of DQNN in the regression task of Eq. (26).

First, we use the DQNN model to solve this problem. We choose two cases for DQNN in the task. Case $1$ (DQNN${}_1$) is based on a $2$-qubit single-layer variational quantum circuit, $U^{(1)}({𝜽}^{(1)})$, and four measurement observables, ${\{B_i\}}_{i=1}^4$, randomly chosen the generalized Pauli basis on two qubits, as shown in Fig. 8(a). Case $2$ (DQNN${}_4$) is based on four $2$-qubit single-layer variational quantum circuits, ${\{U^{(j)}({𝜽}^{(j)})\}}_{j=1}^4$, and one measurement observable $B_1=Z^{(1)}\otimes Z^{(2)}$, as shown in Fig. 8(b). Through state reparation, each data point $𝒙$ is encoded into the input state:

$$|\overline{𝒙}⟩=\frac{1}{\gamma }{[x_1,x_2,\tilde{x},0]}^T$$ (27)

where $\tilde{x}=\frac{|𝒙|}{1+|𝒙|}$ and $\gamma ={({|𝒙|}^2+{\tilde{x}}^2)}^{\frac{1}{2}}$. Then we sequentially apply the variational circuit $U^{(j)}({𝜽}^{(j)})$ and quantum measurement to obtain the measurement outcome ${⟨B_i⟩}_{{𝜽}^{(j)},\overline{𝒙}}$:

${⟨B_i⟩}_{{𝜽}^{(j)},\overline{𝒙}}\equiv \mathrm{Tr}(U^{(j)}({𝜽}^{(j)})|\overline{𝒙}⟩⟨\overline{𝒙}|U^{(j)}{({𝜽}^{(j)})}^{†}{B}_i).$ (28)

Denoting the sigmoid function as $\sigma (x)$, with

$$\sigma (x)\equiv \frac{1}{1+e^{-x}},$$ (29)

for DQNN${}_1$, we obtain

$u(\overline{𝒙})\equiv {\displaystyle \sum _{i=1}^4}{\alpha }_i^{(1)}\sigma (a_i^{(1)}({⟨B_i⟩}_{{𝜽}^{(1)},\overline{𝒙}}-c_i^{(1)})),i=1,2,3,4.$ (30)

and finally derive

$$q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})\equiv \sigma (a_5(u(\overline{𝒙})-c_5))$$ (31)

where the parameter $𝜽$ comes from the quantum circuit $U(𝜽)$, while the parameters $(𝒂,𝒄,𝜶)$ come from the classical processing after $U(𝜽)$. For DQNN${}_4$, we obtain

$u(\overline{𝒙})\equiv {\displaystyle \sum _{j=1}^4}{\alpha }_1^{(j)}\sigma (a_1^{(j)}({⟨B_1⟩}_{{𝜽}^{(j)},\overline{𝒙}}-c_1^{(j)})),j=1,2,3,4$ (32)

and derive

$$q_{𝜽,𝒂,𝒄,𝜶}(\overline{𝒙})\equiv \sigma (a_5(u(\overline{𝒙})-c_5)).$$ (33)

Finally, through optimization, we can find the optimal values of parameters $(𝜽,𝒂,𝒄,𝜶)$ that correspond to the optimal approximation to the target function $f$.

Second, we consider the CCQ model. For any data point $(𝒙,y)\in D$, $𝒙$ can be encoded into a 2-qubit state $|\overline{𝒙}⟩=\frac{1}{\gamma }{[x_1,x_2,\tilde{x},0]}^T$ as in Eq. (17). For the input state $|{\psi }_{𝒙}⟩$ in Eq. (19), the number of copies $n_{\text{copy}}$ can be chosen to be $n_{\text{copy}}\ge 1$. Here we consider two cases, $n_{\text{copy}}=1$ and $n_{\text{copy}}=2$. For $n_{\text{copy}}=1$, we design $U(𝜽)$ in CCQ to be a $2$-qubit $4$-layer variational quantum circuit; for $n_{\text{copy}}=2$, $U(𝜽)$ in CCQ is chosen to be a $4$-qubit $4$-layer circuit. The circuit depth of $U(𝜽)$ is $13$ in the former case, and $21$ in the latter case. Correspondingly, the input state $|{\psi }_{𝒙}⟩$ is either a 2-qubit state or a 4-qubits state, as shown in Fig. 9. After input state preparation in each case, we apply $U(𝜽)$ and a measurement to $|{\psi }_{𝒙}⟩$, and derive the measurement outcome

$${⟨B⟩}_{𝜽,𝒙}\equiv \mathrm{Tr}(U(𝜽)|{\psi }_{𝒙}⟩⟨{\psi }_{𝒙}|U{(𝜽)}^{†}B)$$ (34)

where the observable is chosen as $B\equiv Z^{(1)}$, the local Pauli-Z gate on the first qubit. Then we derive the following output

$$q_{𝜽}(𝒙)=\frac{{⟨B⟩}_{𝜽,𝒙}+1}{2}.$$ (35)

Through optimization, we can find the optimal value $𝜽$ that correspond to the best approximated $q_{𝜽}$ to the target function $f$.

Figure 9: The circuit of CCQ in the regression task of Eq. (26), with $U(𝜽)$ chosen as a $2$-qubit $4$-layer circuit (case a), and as a $4$-qubit $4$-layer circuit (case b)

Figure 10: The circuit of QCL in the regression task of Eq. (26), with $U(𝜽)$ chosen as a $2$-qubit $4$-layer circuit (case a), and as a $4$-qubit $5$-layer circuit (case b).

Finally, we apply QCL to solve the same problem. We also consider two cases where the classical data point $𝒙$ is encoded into a 2-qubit state ($n_{\text{copy}}=1$) and a 4-qubit state ($n_{\text{copy}}=2$) respectively, as in Eq. (21):

$$\rho (𝒙)=\frac{1}{4}{\otimes }_{j=1}^{n_{\text{copy}}}{\otimes }_{i=1}^2(\text{I}+x_{i}X+\sqrt{1-x_i^2}Z).$$ (36)

The entire process from the input state to the final output of QCL is illustrated in Fig. 10. Notice that the variational quantum circuit $U(𝜽)$ is slightly different from the original suggestion in [32], as we find that our modified circuit has a better performance. After input state preparation in each case, we apply $U(𝜽)$ and a measurement to $\rho (𝒙)$, and derive the measurement outcome

$${⟨B⟩}_{𝜽,𝒙}\equiv \mathrm{Tr}(U(𝜽)\rho (𝒙)U{(𝜽)}^{†}B).$$ (37)

where the observable is chosen as $B\equiv Z^{(1)}$. Then we obtain the final output of QCL:

$$q_{𝜽,a}(𝒙)=a{⟨B⟩}_{𝜽,𝒙}$$ (38)

where $a$ is a trainable parameter. Then, through optimization, we find the optimal values of the parameters $(𝜽,a)$ that correspond to the best approximated $q_{𝜽,a}$ to the target function $f$.