Quantum-classical algorithms for skewed linear systems with optimized Hadamard test

Understand

The solving of linear systems provides a rich area to investigate the use of nearer-term, noisy, intermediate-scale quantum computers.

• In this work, we discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases.
• Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth and the number of circuits is much smaller than their Hilbert space dimension.
• Our algorithms have poly-logarithmic dependence on the dimension and polynomial dependence in other natural quantities.