Source-linked AI summary
Prediction by linear regression on a quantum computer
Maria Schuld, Ilya Sinayskiy, Francesco Petruccione
TL;DR
The paper addresses quantum linear regression’s focus on prediction from labeled examples rather than reading out optimal fit parameters. It uses amplitude encoding, SVD-based processing, and low-rank-compatible quantum routines to produce the prediction through an ancilla measurement. The approach is logarithmic in input dimension under quantum-data access, but its efficiency depends on low-rank spectral structure and excludes state-preparation costs.
Problem
Quantum linear-regression methods need to support the machine-learning task of predicting outputs for new inputs from examples, while avoiding full parameter readout and expensive state tomography.
Method
The algorithm combines least-squares linear regression, amplitude-encoded quantum states, SVD-based singular-value inversion, and low-rank approximations of X†X for non-sparse data matrices.
Results
The prediction can be accessed through a single-qubit measurement, with runtime roughly O(log Nκ2ǫ−3) when the required quantum data and low-rank condition are available.
Takeaways & Limitations
The routine reproduces the unregularised classical least-squares prediction and runs logarithmically in feature dimension, independent of training-set size under quantum-information input.
Takeaways & Limitations
Efficiency requires the data-derived density matrix to be close to a low-rank approximation dominated by a few large eigenvalues, and the runtime excludes quantum state-preparation costs.
Abstract
from arXiv · showhide
We give an algorithm for prediction on a quantum computer which is based on a linear regression model with least squares optimisation. Opposed to related previous contributions suffering from the problem of reading out the optimal parameters of the fit, our scheme focuses on the machine learning task of guessing the output corresponding to a new input given examples of data points. Furthermore, we adapt the algorithm to process non-sparse data matrices that can be represented by low-rank approximations, and significantly improve the dependency on its condition number. The prediction result can be accessed through a single qubit measurement or used for further quantum information processing routines. The algorithm's runtime is logarithmic in the dimension of the input space provided the data is given as quantum information as an input to the routine.
I. INTRODUCTION
The paper reframes quantum linear regression around predicting outputs for new inputs rather than reading out fitted parameters. It targets non-sparse data represented by low-rank structure and gives a prediction routine with logarithmic input-dimension dependence when data is quantum-encoded.
- Linear regression is presented as a machine-learning method for mapping training inputs to outputs, including continuous-label regression and nonlinear feature mappings.
- The paper focuses quantum linear regression on predicting a new input's output from training data.
- The proposed routine runs in roughly O(log Nκ^2ε^-3) when the information is encoded into a quantum state.
- The method does not require the data matrix X to be sparse, but requires X^T X to admit a low-rank approximation dominated by a few large eigenvalues.
II. PREDICTION WITH LINEAR REGRESSION
This section formulates supervised prediction as linear regression and derives the least-squares solution using the Moore-Penrose pseudoinverse and singular-value decomposition. The resulting scalar prediction for a new input avoids expensive state tomography and targets quantum efficiency under specified data assumptions.
- Problem formulation: Supervised pattern recognition predicts a scalar output for a new input from labeled training pairs.The inputs and outputs are represented as vectors and real-valued targets, respectively.
- Feature mapping: A nonlinear feature map can transform the inputs before linear regression, enabling the model to fit nonlinear functions.The paper gives polynomial curve fitting as an example of this feature-map approach.
- Least-squares model: Linear regression fits parameters by minimizing the unregularised least-squares error |Xw − y|^2.The paper identifies regularisation as an open question in quantum machine learning.
- Pseudoinverse solution: The least-squares parameters are expressed with the Moore-Penrose pseudoinverse X+, including the SVD-based form X+ = VΣ−1U†.The reduced SVD supports non-square matrices and non-sparse data matrices.
- Singular-value structure: Singular values of X are the square roots of the nonzero eigenvalues of X†X and XX†, linking the SVD to the matrices used later in the algorithm.The corresponding singular vectors are eigenvectors of these products.
- Prediction objective: The quantum objective is to reproduce the classical prediction more efficiently, with classical solution time stated as O(N^d) for 2 ≤ d ≤ 3.The desired quantum output is a single scalar rather than the full fitted parameter state.
III. THE QUANTUM LINEAR REGRESSION ALGORITHM
The algorithm uses amplitude-encoded quantum states and singular-value inversion to compute a prediction without explicitly reading out the fitted parameters. The desired prediction is placed in an ancilla qubit’s offdiagonal elements for direct measurement or subsequent quantum processing.
- State encoding: Classical vectors are stored in quantum amplitudes through amplitude encoding on n qubits.A 2^n-dimensional vector is represented across the computational-basis amplitudes.
- Singular-value inversion: The routine uses quantum techniques to invert the unknown singular values associated with the data matrix.This inversion forms part of the algorithm’s intermediate processing after state encoding.
- Prediction readout: The prediction is written into the offdiagonal elements of an ancilla qubit and read out with σx or σy measurement.The same encoded result can be used in further quantum information-processing routines.
A. State preparation
The algorithm assumes quantum states encoding X, y, and the new input x̃, with normalized data and nontrivial state-preparation requirements for classical datasets.
- The routine takes amplitude-encoded quantum states representing X, y, and the new input x̃.
- The data are normalized, so prediction results must be rescaled to recover the corresponding values for unnormalized data.
- The encoded X state can represent a matrix through singular vectors and singular values, using ⌈log N⌉ + ⌈log M⌉ qubits.
- Preparing arbitrary quantum states from a classical dataset remains nontrivial and controversial, although specialized preparation methods have been proposed.
B. Extracting the singular values
The algorithm extracts the eigenvalues of X†X from an encoded matrix state by tracing out one register and applying quantum principal component analysis with phase estimation.
- Tracing out the row register of the encoded X state produces a mixed state representing the positive Hermitian matrix X†X.
- Quantum principal component analysis is used to apply the reduced matrix state to the encoded X state.
- Quantum phase estimation approximately encodes the eigenvalues λr = (σr)2 in an additional register.
C. Inverting the singular values
The inversion stage conditionally applies inverse eigenvalues to encode the inverse singular-value factors needed for the linear-regression prediction.
- An ancilla qubit is rotated conditionally on the eigenvalue register to implement the singular-value inversion step.
- The scaling constant c must be smaller than the smallest nonzero eigenvalue λmin of X†X so that inverse eigenvalues do not exceed 1.
- The algorithm continues only when the inversion ancilla is measured in state |1⟩, while amplitude amplification can quadratically increase acceptance probability.
D. Executing the inner products
The final routine encodes the regression prediction in an ancilla qubit’s offdiagonal density-matrix elements, allowing its signed value to be accessed by measurement.
- The final step targets the weighted inner-product expression involving inverse singular values and overlaps with x̃ and y.
- A direct SWAP test is insufficient because its squared overlap loses the sign of the prediction.
- Conditional state preparation entangles the relevant states with an ancilla, whose offdiagonal elements contain the prediction up to a known normalization factor.
- Conditional execution of the full routine may be difficult, motivating a construction that leaves the all-zero basis amplitude fixed while renormalizing the remaining amplitudes.
- A common SWAP test can then reveal the shifted inner product, from which the sign of the coefficient sum can be extracted.
IV. RUNTIME ANALYSIS
The runtime is efficient when the data-derived density matrix is well approximated by low rank, but uniform eigenvalues can eliminate the exponential speedup. With amplitude amplification, the runtime is roughly O(log Nκ^2ε^-3), improving condition-number dependence over WBL while worsening accuracy dependence.
- Runtime bound: O(log N) temporal resources and O(ε^-3) copies of ρX†X are required to exponentiate the density matrix in Step 2.Here, ε is the error and N is the input dimension.
- Low-rank condition: The method remains efficient only when ρX†X is dominated by a few large eigenvalues; nearly uniform eigenvalues of order 1/N make the simulation time grow quadratically with N.The low-rank condition is therefore required to maintain the exponential speedup.
- Runtime bound: O(log Nκ^2ε^-3) is the approximate runtime when sufficient copies of ρX†X are available and it is close to low rank.The bound excludes quantum state-preparation costs for classical inputs.
- Condition-number dependence: Amplitude amplification reduces the conditional-measurement cost from fewer than κ^4 average tries to an O(κ^2) runtime factor.This can be significant for matrices close to singular.
- Comparison with prior work: Compared with WBL, the algorithm improves condition-number dependence by κ^-4 but worsens accuracy dependence by ε^-2.The comparison concerns the runtime scaling of the two algorithms.
V. CONCLUSION
The paper presents a quantum linear-regression algorithm for supervised pattern recognition that reproduces unregularised least-squares predictions. It is logarithmic in feature dimension under quantum-information input, supports low-rank approximations of non-sparse data matrices, and leaves kernel choice, regularisation, accuracy sensitivity, and state preparation as open or unresolved issues.
- Conclusion: The algorithm implements linear regression for supervised pattern recognition on a universal quantum computer.It reproduces the prediction result of classical linear regression with unregularised least-squares optimisation.
- Conclusion: The runtime is logarithmic in feature-vector dimension N and independent of training-set size when inputs are given as quantum information.This scaling applies to the algorithmic runtime under quantum-information input.
- Conclusion: The method requires X†X to be representable by a low-rank approximation rather than requiring the training-input matrix X to be sparse.This broadens the stated data-matrix representation beyond sparse matrices.
- Conclusion: A nonlinear feature map, the kernel trick, can transform inputs to increase the method’s potential power.The paper discusses polynomial kernels and identifies different kernels as an open research question.
- Conclusion: Accuracy sensitivity and unresolved quantum state preparation for classical information remain limitations, while including regularisation terms is open research.The conclusion also leaves the application of different kernels for further research.