  State-of-the-art noisy intermediate-scale quantum devices (NISQ), although
imperfect, enable computational tasks that are manifestly beyond the
capabilities of modern classical supercomputers. However, present quantum
computations are restricted to exploring specific simplified protocols, whereas
the implementation of full-scale quantum algorithms aimed at solving concrete
large scale problems arising in data analysis and numerical modelling remains a
challenge. Here we introduce and implement a hybrid quantum algorithm for
solving linear systems of equations with exponential speedup, utilizing quantum
phase estimation, one of the exemplary core protocols for quantum computing. We
introduce theoretically classes of linear systems that are suitable for current
generation quantum machines and solve experimentally a $2^{17}$-dimensional
problem on superconducting IBMQ devices, a record for linear system solution on
quantum computers. The considered large-scale algorithm shows superiority over
conventional solutions, demonstrates advantages of quantum data processing via
phase estimation and holds high promise for meeting practically relevant
challenges.
