Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test
Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, Patrick Rebentrost · Physical Review A · 2021
The authors propose two hybrid quantum-classical algorithms for finding approximate solutions to heavily skewed systems of linear equations for overdetermined and underdetermined cases. The algorithms, which have polylogarithmic dependence on the larger dimension and polynomial dependence in other natural quantities, could potentially be used on noisy intermediate scaled quantum devices.