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)/ε), where N is the number of data points and ε 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.