Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2508.16141 · IEEE Transactions on Quantum Engineering

Quantum Communication Complexity of Regularized Linear Regression Protocols

Sayaki Matsushita

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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 paper investigates distributed linear regression in the quantum coordinator model. Building upon the distributed quantum least squares protocol developed by Montanaro and Shao, I propose improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least squares problems. For ordinary least squares methods, my 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. Furthermore, I establish a setting for the$\ell _{2}$-regularized least squares problem specifically in the quantum coordinator model and derive its quantum communication complexity. I analyze the effect of regularization parameters on the quantum communication complexity.

DOI
10.1109/tqe.2026.3687237

Related papers

Communication-Efficient Quantum Algorithm for Distributed Machine Learning

Hao Tang, Boning Li, Guoqing Wang +5 more

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.

arXiv:2209.04888•Physical Review Letters•Apr 12, 2023•12 citations

Quantum Algorithms for Solving Linear Regression Equation

Kai Li, Hong‐Yi Dai, Jing Feng +4 more

Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.

Journal of Physics Conference Series•Jan 1, 2021•6 citations

Quantum Regularized Least Squares

Shantanav Chakraborty, Aditya Morolia, Anurudh Peduri

Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.

arXiv:2206.13143•Quantum•Apr 27, 2023•22 citations

Quantum algorithm for linear regression

Guoming Wang

We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where $N$ is the size of the data set, $d$ is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on $d$ and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

arXiv:1402.0660•Physical Review A•Jul 31, 2017•144 citations

Linear regression by quantum amplitude estimation and its extension to convex optimization

Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda +1 more

Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ${N}_{D}$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ${N}_{D}$, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.

arXiv:2105.13511•Physical Review A•Aug 25, 2021•7 citations

Quantum Tomography by Regularized Linear Regression

Biqiang Mu, Hongsheng Qi, Ian R. Petersen +1 more

In this paper, we study extended linear regression approaches for quantum state tomography based on regularization techniques. For unknown quantum states represented by density matrices, performing measurements under certain basis yields random outcomes, from which a classical linear regression model can be established. First of all, for complete or over-complete measurement bases, we show that the empirical data can be utilized for the construction of a weighted least squares estimate (LSE) for quantum tomography. Taking into consideration the trace-one condition, a constrained weighted LSE can be explicitly computed, being the optimal unbiased estimation among all linear estimators. Next, for general measurement bases, we show that $\ell_2$-regularization with proper regularization gain provides even lower mean-square error under a cost in bias. The regularization parameter is tuned by two estimators in terms of a risk characterization. Finally, a concise and unified formula is established for the regularization parameter with complete measurement basis under an equivalent regression model, which proves that the proposed tuning estimators are asymptotically optimal as the number of samples grows to infinity under the risk metric. Additionally, numerical examples are provided to validate the established results.

arXiv:1904.11839•Apr 26, 2019•0 citations
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 paper investigates distributed linear regression in the quantum coordinator model. Building upon the distributed quantum least squares protocol developed by Montanaro and Shao, I propose improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least squares problems. For ordinary least squares methods, my 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. Furthermore, I establish a setting for theℓ2\ell _{2}ℓ2​-regularized least squares problem specifically in the quantum coordinator model and derive its quantum communication complexity. I analyze the effect of regularization parameters on the quantum communication complexity.
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.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.
Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where NNN is the size of the data set, ddd is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on ddd and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.
Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ND{N}_{D}ND​. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND{N}_{D}ND​, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
In this paper, we study extended linear regression approaches for quantum state tomography based on regularization techniques. For unknown quantum states represented by density matrices, performing measurements under certain basis yields random outcomes, from which a classical linear regression model can be established. First of all, for complete or over-complete measurement bases, we show that the empirical data can be utilized for the construction of a weighted least squares estimate (LSE) for quantum tomography. Taking into consideration the trace-one condition, a constrained weighted LSE can be explicitly computed, being the optimal unbiased estimation among all linear estimators. Next, for general measurement bases, we show that ℓ2\ell_2ℓ2​-regularization with proper regularization gain provides even lower mean-square error under a cost in bias. The regularization parameter is tuned by two estimators in terms of a risk characterization. Finally, a concise and unified formula is established for the regularization parameter with complete measurement basis under an equivalent regression model, which proves that the proposed tuning estimators are asymptotically optimal as the number of samples grows to infinity under the risk metric. Additionally, numerical examples are provided to validate the established results.