Quantum Federated Learning for Distributed
Quantum Networks

Similar to the classical FL, a dataset $\mathbf{X}=\left[\mathbf{x}_{0},\mathbf{x}_{1},\cdots,\mathbf{x}_{M-1}\right]$ is chosen by a client in quantum FL, where $\mathbf{x}_{i}\in\mathbb{R}^{D}$. $\mathbf{y}=\left(y_{0},y_{1},\cdots,y_{M-1}\right)$ is the corresponding label of each sample of $\mathbf{X}$, respectively. For convenience, assuming that $D=2^{L}$ for some $L$; otherwise, some zeros are inserted into the vector. Furthermore, the server initializes an ML model with parameters. The learnable parameters of the model are represented by a vector $\mathbf{W}\in\mathbb{R}^{D}$, which can be optimized using gradient descent. The ability of quantum computers to effectively solve practical problems depends on encoding this information into quantum states as input to a quantum algorithm. Here, we give methods to extract the data and parameters information to quantum states.

Considering the quantum oracles

and

are provided, where $\mathbf{x}_{i}^{j}$ represents the $j$th element of the $i$th vector of the data set $\mathbf{X}$. These two oracles can respectively access the entries of $\mathbf{x}_{i}$, $\mathbf{y}$ in time $O(\text{polylog}(MD))$ and $O(\text{polylog}(M))$ [17, 30], when the data are stored in quantum random access memory (QRAM) [31] with an appropriate data structure [32]. In addition, the operation

is required, which could access the $2$-norm of the vector $\mathbf{x}_{i}$. Inspired by Ref. [33], $U_{nf}$ can be implemented in time $O\left({{\text{polylog}(D)}/\epsilon_{m}}\right)$ employing controlled rotation [34] and quantum phase estimation (QPE) [35]. The details are shown in appendix A. According to these assumptions, the processes of the quantum data preparation are described as follows.

$(A1)$ In this step, the data information is extracted to the state $\left|{\phi\left(\mathbf{x}_{i}\right)}\right\rangle$. Firstly, three quantum registers are prepared in state $|i\rangle_{1}|0^{\otimes{\log{D}}}\rangle_{2}|0^{\otimes{q}}\rangle_{3}$, where the subscript numbers denote different registers. The $q$ is labeled as the qubits that are enough to store the information about the elements of data, i.e., $2^{q}-1>{\max\limits_{i,j}|\mathbf{x}_{i}^{j}|}$. After that, $H^{\otimes{\log{D}}}$ is applied on the second register to generate a state

Secondly, the quantum oracle $O_{X}$ is performed on the three registers. These registers are in a state

Subsequently, a qubit in the state $|0\rangle$ is added and rotated to $\sqrt{1-({c_{1}\mathbf{x}_{i}^{j}})^{2}}\left|0\right\rangle+c_{1}\mathbf{x}_{i}^{j}\left|1\right\rangle$ controlled on $|\mathbf{x}_{i}^{j}\rangle$, where $c_{1}={1/{\max\limits_{i,j}|\mathbf{x}_{i}^{j}|}}$. The system becomes

Finally, the inverse $O_{X}$ operation is applied on the third register. The quantum state

could be obtained via discarding the third register. The process is denoted as $U_{\mathbf{x}_{i}}$, which generates the state $\left|{\phi\left(\mathbf{x}_{i}\right)}\right\rangle$ in time $O(\text{polylog}(D)+q)$.

$(A2)$ In order to train the gradient, the parameter $\mathbf{w}(n)$ should be introduced in the $n$th iteration. Thus, it is necessary to generate a quantum state, which contains the information of $\mathbf{w}(n)$. Depending on the fact that the parameter is different in each iteration, there are two methods to prepare the quantum state.

One way is based on the assumption that QRAM is allowed to read and write frequently. For the information of $\mathbf{w}^{j}(n)$ ($j=0,1,\cdots,D-1$) are written in QRAM timely, the quantum state

can be produced by the processes similar to step $(A1)$ with the help of the oracle $O_{\mathbf{w}}$ ($O_{\mathbf{w}}\left|j\right\rangle\left|0\right\rangle\longrightarrow\left|j\right\rangle|{\mathbf{w}^{j}(n)}\rangle$), where $c_{2}={1/\left\|\mathbf{w}(n)\right\|}$ and $\mathbf{w}^{j}(n)$ is denoted as the $j$th element of the parameter vector in the $n$th iteration. This way can be implemented in time $O(\text{polylog}(D)+q)$.

For another, the parameter is extracted into the quantum state based on the operation $R(\vartheta)=\cos{(\vartheta)}|0\rangle\langle 0|-\sin{(\vartheta)}|0\rangle\langle 1|+\sin{(\vartheta)}|1\rangle\langle 0|+\cos{(\vartheta)}|1\rangle\langle 1|$, which is inspired by Ref. [36]. In this way, the $\mathbf{w}(n)$ is not required to be written in QRAM. The following are described as the processes.

Assuming that is easy to get $2^{L}-1$ ($L=\log(D)$) angle parameters $\bm{\vartheta}_{t}=(\vartheta_{t}^{0},\cdots,\vartheta_{t}^{2^{t-1}-1})$ ($t=1,2,\cdots,L$) from the updated $\mathbf{w}(n)$ after the last iteration. The angle $\vartheta_{t}^{j}$ satisfies

for $t=1,\cdots,L$, where $h^{j}_{t-1}=\sqrt{(h^{2j}_{t})^{2}+(h^{2j+1}_{t})^{2}}$ and $j=0,\cdots,2^{t-1}-1$. In particular, $h^{j}_{L}=\mathbf{w}^{j}(n)$ for $j=0,1,\cdots,D-1$. And there are defined

where $I\{{L-t}\}$ is represented as the gate $I$ applied on $(L-t)$ qubits.

After that, a quantum state

is generated in time $O(D)$ by applying the operation $U(\bm{\vartheta}_{t})$ for $t=1,2,\cdots,L$. Furthermore, a register in state $|1\rangle$ is appended. The overall system is in the state

To further interpret this method, an example is given in the appendix B.

According to Eq. (16), the state in Eq. (12) can be rewritten as

It means that the above two methods both allow us to extract the parameter $\mathbf{w}(n)$ information into the quantum state $\left|{\phi(\mathbf{w}(n))}\right\rangle$. On the basis of the current quantum technology, we choose the second method which is more feasible, and denote the process as $U_{\mathbf{w}}$.

Now, we propose a QGD algorithm. It enables clients to estimate the gradient of the model in parallel based on their respective local data. According to Eq. (2), with the help of the two operations $U_{\mathbf{x}_{i}}$ and $U_{\mathbf{w}}$ of quantum data preparation, the process of the QGD algorithm is described as follows.

$(B1)$ Generate an intermediate quantum state.

The task of computing the gradient involves an inner product computation, which needs $O(MD)$ in classical computers. In the era of big data, this time is costly. Here, we generate an intermediate state that contains the information of $\mathbf{x}_{i}\cdot\mathbf{w}$. This state facilitates subsequent parallel estimation.

$(B1.1)$ A quantum state is initialized as

$(B1.2)$ The Hadamard gate is performed on the fifth register. Then, a controlled operation $\left|i\right\rangle\left\langle i\right|\otimes U_{\mathbf{x}_{i}}\otimes\left|0\right\rangle\left\langle 0\right|+I\otimes U_{\mathbf{w}}\otimes\left|1\right\rangle\left\langle 1\right|$ is applied to produce a state

$(B1.3)$ Subsequently, the Hadamard gate is implemented on the fifth register to get

where

The state $|\Psi_{i,n}\rangle$ can be rewritten as

where $\theta_{i}\in\left[0,\frac{\pi}{2}\right]$. It is easy to verify that

and $c_{2}^{{\prime}}=\sqrt{D}{c_{2}}$. By observing Eq. (22) and Eq. (23), it can be found that the essential information is provided by the system when its fourth and fifth registers are both in state $|1\rangle$. It means that the superposition of $|0\rangle$ also does not affect the extraction of the required information if choosing the state of Eq. (17). Thus, the first method (in step $(A2)$) is also suitable for our algorithm, which $c_{2}^{{\prime}}=c_{2}$.

$(B2)$ Calculate the $F(\mathbf{x}_{i}\cdot\mathbf{w})$ in parallel.

The approximation of $F(\mathbf{x}_{i}\cdot\mathbf{w})$ should be estimated and stored in a quantum state. To achieve this goal, the $\theta_{i}$ is needed to estimate via quantum phase estimation which the unitary operation is defined as

where $\mathcal{A}_{i}\left|{0}^{\otimes{[\log{(D)}+2]}}\right\rangle=\left|\Psi_{i,n}\right\rangle$, $S_{00}=I^{\otimes{[\log{(D)}+2]}}-2{\left|0^{\otimes{[\log{(D)}+2]}}\right\rangle\left\langle 0^{\otimes{[\log{(D)}+2]}}\right|}$ and $S_{11}=I^{\otimes{\log{(D)}}}\otimes\left(I^{\otimes{2}}-2|1^{\otimes{2}}\rangle\langle 1^{\otimes{2}}|\right)$. Mathematically, the eigenvalues of $Q_{i}$ are $e^{\pm 2\mathbf{i}\theta_{i}}$ $(\mathbf{i}=\sqrt{-1})$ and the corresponding eigenvectors are $\left|\Psi_{i,n}^{\pm}\right\rangle=\frac{1}{\sqrt{2}}\left({\left|\psi_{i}^{0}\right\rangle\pm\mathbf{i}\left|\psi_{i}^{1}\right\rangle}\right)$), respectively. Based on the set of its eigenvectors, $\left|\Psi_{i,n}\right\rangle$ can be rewritten as $\left|\Psi_{i,n}\right\rangle=-\frac{\mathbf{i}}{\sqrt{2}}\left({e^{\mathbf{i}\theta_{i}}\left|\Psi_{i,n}^{+}\right\rangle-e^{-\mathbf{i}\theta_{i}}\left|\Psi_{i,n}^{-}\right\rangle}\right)$. The procedure of estimating the $F(\mathbf{x}_{i}\cdot\mathbf{w})$ is displayed as follows.

$(B2.1)$ Performing the QPE on $Q_{i}$ with the state $\left|\psi_{1}\right\rangle\left|0^{\otimes l}\right\rangle$ for some $l=O\left(\text{log}{\epsilon_{\theta}^{-1}}\right)$, an approximate state

is obtained, where ${\widetilde{\theta}}_{i}\in\mathbb{Z}_{2^{l}}$ satisfies $\left|{\theta_{i}-{\widetilde{\theta}}_{i}\pi/2^{l}}\right|\leq\epsilon_{\theta}$. Then, the quantum state

is generated by using the sine gate. It holds for the fact that ${{\sin}^{2}({\widetilde{\theta}}_{i})}={{\sin}^{2}(-{\widetilde{\theta}}_{i})}$.

$(B2.2)$ According to Eq. (23), it is needed to access $\left\|\mathbf{x}_{i}\right\|$ to compute $\mathbf{x}_{i}\cdot\mathbf{w}$. Combining with the operation $U_{nf}$ and the quantum arithmetic operations [37], we can get

$(B2.3)$ An oracle $O_{F}$ is supposed to achieve any function which has a convergent Taylor series [34]. Combining with $O_{y}$, the function $F(*)$ could be implemented (a simple example is described in Sec. V ). The state becomes

$(B2.4)$ Next, a register in the state $|0\rangle$ is appended as the last register and rotated it to $\left|\phi_{i}\right\rangle=c_{3}F\left({\mathbf{x}_{i}\cdot\mathbf{w}}\right)\left|0\right\rangle+\sqrt{1-\left(c_{3}F\left({\mathbf{x}_{i}\cdot\mathbf{w}}\right)\right)^{2}}\left|1\right\rangle$ in a controlled manner, where $c_{3}={1/{\max\limits_{i}\left|{F\left({\mathbf{x}_{i}\cdot\mathbf{w}}\right)}\right|}}$. This results in the overall state

$(B2.5)$ The inverse operations of steps $(B1.2)-(B2.3)$ are performed on $\left|\psi_{6}\right\rangle$. Afterwards, a register in the state $|1\rangle$ is added to obtain

For convenience, the $\mathcal{A}_{\psi}$ is marked as the operations which achieve $\mathcal{A}_{\psi}|00\cdots 0\rangle=|\psi\rangle$. Its schematic quantum circuit is given in Fig. 3.

$(B3)$ Estimate the gradient $\bm{g}^{j}\left({\mathbf{w}(n)}\right)$ with swap test.

$(B3.1)$ Three registers in state $\frac{1}{\sqrt{M}}{\sum_{i=0}^{M-1}{\left|i\right\rangle_{1}\left|j\right\rangle_{2}}}\left|0\right\rangle_{3}$ are prepared. Performing $O_{X}$ on it to generate the state

$(B3.2)$ The controlled rotation operation ($|0\rangle\rightarrow\sqrt{1-({c_{1}\mathbf{x}_{i}^{j}})^{2}}\left|0\right\rangle+c_{1}\mathbf{x}_{i}^{j}\left|1\right\rangle$) is implemented to get

$(B3.3)$ The inverse operation of $O_{X}$ is performed. After that, we can obtain the state

via undoing the register $|j\rangle$.

$(B3.4)$ In order to obtain the gradient, the technology of swap test [38] is utilized. Combining the processes of generating the states $\left|\psi\right\rangle$ and $\left|\chi^{j}\right\rangle$, a quantum state $\frac{1}{\sqrt{2}}\left(\left|0\right\rangle\left|\psi\right\rangle+\left|1\right\rangle\left|\chi^{j}\right\rangle\right)$ can be constructed. Then, measuring the first register to see whether it is in the state $\left|+\right\rangle=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right\rangle\right)$. The measurement has the success probability

According to Eq. (2), the $\bm{g}^{j}\left({\mathbf{w}(n)}\right)={(2P-1)}/{({c_{1}c_{3}})}$ can be calculated. Hence, it is possible for ${\rm Bob}_{k}$ to obtain the local gradient $\bm{g}_{k}\left(\mathbf{w}\right)=\left({\bm{g}_{k}^{0}\left({\mathbf{w}(n)}\right),\bm{g}_{k}^{1}\left({\mathbf{w}(n)}\right),\cdots,\bm{g}_{k}^{D-1}\left({\mathbf{w}(n)}\right)}\right)^{T}$ by repeating the steps of the above algorithm with his data.

We will design a protocol to safely compute the federated gradients $\bm{G}\left(\mathbf{w}\right)={\sum_{k=1}^{K}{\beta_{k}}{\bm{g}_{k}\left(\mathbf{w}\right)}}$ in this section. That is, calculating $\bm{G}\left(\mathbf{w}\right)$ without revealing the local gradient ${\bm{g}_{k}\left(\mathbf{w}\right)}$. To do it, the server Alice is assumed to be semi-honest who may misbehave on her own but cannot conspire with others. Moreover, the federated gradients are needed to be accurate to ${\gamma}^{-1}$. This means that $\gamma{\beta_{k}}{\bm{g}_{k}^{j}(\mathbf{w})}\geq 0$. Simply, the $\gamma{\beta_{k}}{\bm{g}_{k}^{j}(\mathbf{w})}$ is marked as $\mu_{k}^{j}$. And supposing that ${\sum_{k=1}^{K}\mu_{k}^{j}}<S$. The further details are described as follows.

$(C1)$ Preparation for multi-party quantum communication.

Alice announces ${\gamma}$ and the global dataset scale $(\sum_{k=1}^{K}{M_{k}})$. At same time, the participants (server and clients) choose $m$ numbers $d_{i}$ ($i=1,2,\cdots,m$) which are mutually prime and satisfy $d_{1}\times d_{2}\times\cdots\times d_{m}=S$. Subsequently, ${\rm Bob}_{k}$ $(k=1,2,\cdots,K)$ calculates his secret

Alice produces a $d_{i}$-level $(K+1)$-particle GHZ state

and marks the $(K+1)$ particles by $Q_{0},Q_{1},\cdots,Q_{K}$.

$(C2)$ Distribution of quantum pairs.

For the sake of checking the presence of eavesdroppers, Alice prepares $K$ sets of $\delta$ decoy states, where each decoy photon randomly is in one of the states from the set $V_{1}=\left\{\left|p\right\rangle\right\}_{p=0}^{d_{i}-1}$ and $V_{2}=\left\{QFT\left|p\right\rangle\right\}_{p=0}^{d_{i}-1}$, where $QFT$ is represented as the quantum Fourier transform [39]. These sets are denoted as $E_{1},E_{2},\cdots,E_{K}$, respectively. Then Alice inserts $Q_{k}$ into $E_{k}$ at a random position, and sends them to ${\rm Bob}_{k}$ for $k=1,2,\cdots,K$.

$(C3)$ Security checking of quantum channel.

After receiving $\delta+1$ particles, ${\rm Bob}_{k}$ sends acknowledgements to Alice. Subsequently, the positions and the bases of the decoy photons are announced to ${\rm Bob}_{k}$ by Alice. ${\rm Bob}_{k}$ measures the decoy photons and returns the measurement results to Alice who then calculates the error rate by comparing the measurement results with initial states. If the error rate is higher than the threshold determined by the channel noise, Alice cancels this protocol and restarts it. Otherwise, the protocol is continued.

$(C4)$ Measurement of particles and encoding of transmission information.

${\rm Bob}_{k}$ extracts all the decoy photons and discards them. Then, server and clients perform a measurement $\left\{QFT\left|p\right\rangle\right\}_{p=0}^{d_{i}-1}$ on the remaining particles, respectively. The measurement results record as $o_{s,i},o_{1,i},\cdots,o_{K,i}$ and these satisfy $o_{s,i}+o_{1,i}+\cdots+o_{K,i}=0~{}\text{mod}~{}d_{i}$. Subsequently, ${\rm Bob}_{k}$ encodes his data $s_{k,i}^{\prime j}=s_{k,i}^{j}+o_{k,i}$ and sends it to Alice.

$(C5)$ Computation of federated gradient by server.

At this stage, Alice accumulates all the results $s_{k,i}^{\prime j}$ to compute

For $i=1,2,\cdots,m$, Alice can obtain $m$ equations such as Eq. (37). According to the Chinese remainder theorem, Alice compute the summation

And it is easy to get the federated gradient

After the similar processes, the federated gradient $(\bm{G}^{0}(\mathbf{w}),\bm{G}^{1}(\mathbf{w}),\cdots,\bm{G}^{D-1}(\mathbf{w}))$ could be obtained by Alice. And she updates the global model parameters $\mathbf{w}({n+1})=\mathbf{w}(n)-\alpha\times\bm{G}\left({\mathbf{w}(n)}\right)$. In order to exhibit the process of model aggregation more clearly, a concrete example is presented in the appendix C.

The server (Alice) needs to evaluate whether the model should be further optimized after one round of training in QFLGD. Similar to classical FL, Alice utilizes the smoothness of the gradient to evaluate the model performance. Specifically, the server sends a termination training signal and announces the global parameters when ${\sum\limits_{j=0}^{D-1}\left[{\bm{G}^{j}\left(\mathbf{w}(n)\right)}\right]^{2}}\leq\varepsilon$. Otherwise, she distributes the updated model parameters to clients for new training.

In the QFLGD framework, assuming that $M_{1}\leq M_{2}\leq\cdots\leq M_{K}\leq M$. Namely, the dataset scale is at most $M$. And all clients need to accomplish the gradient training before calculating the federated gradient. Thus the waiting time for the distributed training gradient is the time consumed to train the dataset which scale is $M$. In the following, the time complexity of the QGD algorithm is analyzed with the $M$-scale dataset.

In the data preparation period (the Sec. III-A), the time consumption is caused by the processes of $U_{\mathbf{x}_{i}}$ and $U_{\mathbf{w}}$, which generate the states $\left|{\phi(\mathbf{x}_{i})}\right\rangle$ and $\left|{\phi(\mathbf{w}(n))}\right\rangle$ about data information. It could be implemented in time $O(\text{polylog}(MD)+D+q)$ with the help of the $O_{X}$, $U(\bm{\vartheta}_{t})$ and the controlled rotation operation [14, 30]. The $q$ is represented as the number of qubits which store the data information. Afterwards, $U_{\mathbf{x}_{i}}$ and $U_{\mathbf{w}}$ are applied to produce the state $\left|\psi_{1}\right\rangle$ in step $(B1)$ of local training (the Sec. III-B). Hence, step $(B1)$ can be implemented in time $O(\text{polylog}(MD)+D+q)$.

In step $(B2)$, we first consider the complexity of the unitary operation $\mathcal{A}_{i}$. It contains $H$, $U_{\mathbf{x}_{i}}$, and $U_{\mathbf{w}}$ which take time $O(\text{polylog}(MD)+D+q)$. Then, the QPE block needs $O\left({1/\epsilon_{\theta}}\right)$ applications of $Q_{i}$ to estimate the $\theta_{i}$ within error $\epsilon_{\theta}$ [35]. Therefore, the time complexity of step $(B2.1)$ is $O[(\text{polylog}(MD)+D+q)/{\epsilon_{\theta}}]$. The runtime $O(\text{log}({1/\epsilon_{\theta}}))$ [37] of implementing the sine gate can be ignored, which is much smaller than the QPE.

Next, the time complexity of step $(B2.2)$ and step $(B2.3)$ are discussed. The main operation of the two steps includes $U_{nf}$, $O_{y}$, and the quantum arithmetic operation, which are performed to calculate $|F({\mathbf{x}}\cdot{\mathbf{w}})\rangle$ in time $O[{(\text{polylog}(D))/{\epsilon_{m}}}+\text{polylog}(M)+q]$. In step $(B2.4)$, the time complexity of the controlled rotation is $O(q)$. Step $(B2.5)$ takes time $O[{(\text{polylog}(D))/{\epsilon_{m}}}+{(\text{polylog}(MD)+D+q)/{\epsilon_{\theta}}}]$ to implement the inverse operations of steps $(B1.2)$-$(B2.3)$. Putting all the steps together to get the time complexity of step $(B2)$ as $O[{(\text{polylog}(D))/{\epsilon_{m}}}+{(\text{polylog}(MD)+D+q)/{\epsilon_{\theta}}}]$.

In step $(B3)$, the processes of generating the $|\chi^{j}\rangle$ (described in steps $(B3.1)$-$(B3.3)$) are accomplished in time $O(\text{polylog}(MD)+q)$. According to step $(B2)$, a copy of the quantum state $|\psi\rangle$ is produced in time $O[{(\text{polylog}(D))/{\epsilon_{m}}}+{(\text{polylog}(MD)+D+q)/{\epsilon_{\theta}}}]$. The swap test is applied $O\left({{P\left({1-P}\right)}/\epsilon_{P}^{2}}\right)=O\left({1/\epsilon_{P}^{2}}\right)$ times to get the result $P$ within error $\epsilon_{P}$ in step $(B3.4)$ [40]. And each swap test should prepare a copy of $|\chi^{j}\rangle$ and $|\psi\rangle$. Therefore, the runtime is $\left\{[{(\text{polylog}(D))/{\epsilon_{m}}}+{(\text{polylog}(MD)+D+q)/{\epsilon_{\theta}}}]\epsilon_{P}^{-2}\right\}$ in step $(B3)$, that is the complexity of obtaining the desired result.

For convenience, we assume that $\mathbf{w}^{j}$, $\mathbf{x}_{i}^{j}=O(1)$, then $\|\mathbf{w}\|$, ${\max\limits_{i}\left\|\mathbf{x}_{i}\right\|}=O(\sqrt{D})$. Therefore, $q={\text{polylog}(D)}$ could fulfill the number of qubit required to store data information. In addition, taking $\epsilon_{m}$, $\epsilon_{\theta}$, and $\epsilon_{P}$ equaling to $\epsilon$. After that, the complexity of the entire quantum algorithm to get $\bm{g}^{j}\left(\mathbf{w}\right)$ $(j=0,1,\cdots,D-1)$ in each iteration can further simplify into

This means that the time complexity of training gradient is $O(D^{2}\text{polylog}(MD))$ when $\epsilon^{-1}=\text{log}(MD)$, achieving exponential acceleration on the number of data samples. Furthermore, the elements of $\mathbf{w}$ can also be accessed in time $O(\text{polylog}(D))$ if they are timely writing in QRAM. In this case, the proposed algorithm has exponential acceleration on the number $M$ and the quadratic speedup in the dimensionality $D$, compared with the classical algorithm whose runtime is $O(MD^{2})$.