Quantum-classical algorithms for skewed linear systems with an optimized Hadamard test
Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun, Patrick Rebentrost
Abstract
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.
Topics & Concepts
Overdetermined systemUnderdetermined systemHadamard transformAlgorithmQuantumDimension (graph theory)MathematicsQuantum algorithmPolynomialQuantum algorithm for linear systems of equationsComputer scienceApplied mathematicsPure mathematicsQuantum mechanicsMathematical analysisPhysicsQuantum processQuantum dynamicsQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyNeural Networks and Reservoir Computing