Source-linked AI summary
Quantum Data Fitting
Nathan Wiebe, Daniel Braun, Seth Lloyd
TL;DR
Fitting very large data sets can be costly, and fit quality may be difficult to assess without learning fit parameters. The paper adapts quantum linear-systems techniques to estimate least-squares fit quality efficiently and bound approximation error, including for quantum-generated data.
Problem
Fitting very large experimental data sets can be costly, while obtaining fit quality without learning fit parameters has remained unclear.
Method
The algorithm adapts HHL-style quantum linear-systems methods to prepare the fitted state and estimate its overlap with the data state.
Results
The algorithm efficiently assesses fit quality and provides an upper bound whose error scales as O(δ).
Takeaways & Limitations
The approach can assess whether quantum-device outputs admit concise approximations without first learning the fit parameters.
Takeaways & Limitations
The method may not be efficient for non-sparse fitting matrices and may require efficient preparation of the input state |y⟩.
Abstract
from arXiv · showhide
We provide a new quantum algorithm that efficiently determines the quality of a least-squares fit over an exponentially large data set by building upon an algorithm for solving systems of linear equations efficiently (Harrow et al., Phys. Rev. Lett. {\bf 103}, 150502 (2009)). In many cases, our algorithm can also efficiently find a concise function that approximates the data to be fitted and bound the approximation error. In cases where the input data is a pure quantum state, the algorithm can be used to provide an efficient parametric estimation of the quantum state and therefore can be applied as an alternative to full quantum state tomography given a fault tolerant quantum computer.
Appendix A: Moore–Penrose Pseudoinverse
The appendix proves that applying the Moore–Penrose pseudoinverse to y produces least-squares-optimal fit parameters. The proof establishes pseudoinverse properties and uses an error decomposition whose equality condition identifies the minimizing parameters.
- Proof setup: The appendix reviews an elementary proof that the Moore–Penrose pseudoinverse applied to y yields parameters minimizing the least-squares fit.The proof begins by establishing properties of the pseudoinverse.
- Error decomposition: The error norm decomposes into the fit error, a parameter-dependent term, and two cross terms: ∥Fλ −y∥2 = ∥Fz −y∥2 + ∥F(λ −z)∥2 + (Fz −y)†F(λ −z) + (λ −z)†F†(Fz −y).This identity is labeled (A8).
- Minimizer: Equality holds when λ = z = F+y, so applying the Moore–Penrose pseudoinverse to y provides parameters that minimize the least-square error.The conclusion follows from the established pseudoinverse properties and the error decomposition.