Communication-Efficient Quantum Algorithm for Distributed Machine Learning

The growing demands of remote detection and an increasing amount of training data make distributed machine learning under communication constraints a critical issue. This work provides a communication-efficient quantum algorithm that tackles two traditional machine learning problems, the least-square fitting and softmax regression problems, in the scenario where the dataset is distributed across two parties. Our quantum algorithm finds the model parameters with a communication complexity of $O({\log }_2(N)/\epsilon )$, where $N$ is the number of data points and $\epsilon$ is the bound on parameter errors. Compared to classical and other quantum methods that achieve the same goal, our methods provide a communication advantage in the scaling with data volume. The core of our methods, the quantum bipartite correlator algorithm that estimates the correlation or the Hamming distance of two bit strings distributed across two parties, may be further applied to other information processing tasks.

Figure 1

Quantum circuits for the distributed quantum counting or QBC scheme. $H$, $G$, and ${\mathrm{QFT}}^{†}$ represent the Hadamard gate, the Grover operator, and the inverse QFT, respectively. The $t$-qubit register is measured after the inverse QFT. The inset shows the biparty distributed scheme of the Grover operation, where $U_{x_l}$ and $V_{y_k}$ are defined in Eqs. (7) and (8).

Figure 2

Communication complexity phase diagram of the QBC algorithm, deterministic, and stochastic classical algorithms in parameter space of $N$, $\epsilon$, and $M$. Without loss of generality, we assume that both $\overrightarrow{x}$ and $y$ are normalized and different components of $\overrightarrow{x}$ are iid. The color map represents the minimal communication complexity of the three algorithms in the logarithmic scale. Black lines divide the space into three regions denoted as Classical (D), Classical (S), and Quantum, representing the region where the deterministic classical, stochastic classical, and QBC algorithm have the smallest communication complexity. The black dashed line in each layer indicates the statistical variance $\epsilon =1/\sqrt{N}$.