Communication-efficient Quantum Algorithm for Distributed Machine Learning

Abstract

The growing demands of remote detection and 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 problem, in the scenario where the data set is distributed across two parties. Our quantum algorithm finds the model parameters with a communication complexity of $O(\frac{{\log }_2(N)}{\epsilon })$, where $N$ is the number of data points and $\epsilon$ is the bound on parameter errors. Compared to classical algorithms and other quantum algorithms that achieve the same output task, our algorithm provides a communication advantage in the scaling with the data volume. The building block of our algorithm, the quantum-accelerated estimation of distributed inner product and Hamming distance, could be further applied to various tasks in distributed machine learning to accelerate communication.

References in corpus (16)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum random access memory
• A Survey on Distributed Machine Learning
• Non-locality and Communication Complexity
• Quantum Data Fitting
• Prediction by linear regression on a quantum computer
• Quantum Algorithm for Linear Regression
• Quantum Inference on Bayesian Networks
• Simulating Quantum Dynamics On A Quantum Computer
• Beyond the swap test: optimal estimation of quantum state overlap
• High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
• Realizing quantum linear regression with auxiliary qumodes

Cited by in corpus (3)

• Privacy-preserving quantum federated learning via gradient hiding
• Blind quantum machine learning with quantum bipartite correlator
• Des-q: a quantum algorithm to provably speedup retraining of decision trees