Quantum Communication Complexity of Regularized Linear Regression Protocols

Linear regression is fundamental to statistical analysis and machine learning, but its application to large-scale datasets necessitates distributed computing. The problem also arises in quantum computing, where handling extensive data requires distributed approaches. This article investigates distributed linear regression in the quantum coordinator model. Building upon the distributed quantum least-squares protocol developed by Montanaro and Shao (2024), this article proposes improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least-squares problems. For ordinary least-squares methods, the proposed protocol reduces the quantum communication complexity compared to the previous protocol. In particular, this yields a quadratic improvement in the number of digits of precision required for the generated quantum states. This improvement is achieved by incorporating advanced techniques such as branch marking and branch-marked gapped phase estimation developed by Low and Su (2026). Furthermore, this article establishes a setting for the L2-regularized least-squares problem specifically in the quantum coordinator model and derives its quantum communication complexity. The effect of regularization parameters on the quantum communication complexity is analyzed.

# Atomic physics. Constitution and properties of matter # Materials of engineering and construction. Mechanics of materials # Quantum communication # quantum computing

Sayaki Matsushita (2026). "Quantum Communication Complexity of Regularized Linear Regression Protocols". IEEE Transactions on Quantum Engineering. https://doi.org/10.1109/tqe.2026.3687237