LAUSR

In this paper, we propose a quantum algorithm for approximating the QR decomposition of any $$N\times N$$ N × N matrix with a running time $$O(\frac{1}{\epsilon ^2}$$ O ( 1 ϵ 2 $$N^{2.5}\text {polylog}(N))$$ N 2.5 polylog ( N ) ) , where $$\epsilon $$ ϵ is the desired precision. This quantum algorithm provides a polynomial speedup over the best classical algorithm, which has a running time $$O(N^3)$$ O ( N 3 ) . Our quantum algorithm utilizes the quantum computation in the computational basis (QCCB) and a setting of updatable quantum memory. We further present a systematic approach to applying the QCCB to simulate any quantum algorithm. By this approach, the simulation time does not exceed $$O(N^2\text {polylog}(N))$$ O ( N 2 polylog ( N ) ) times the running time of the quantum algorithm originally designed with the amplitude encoding method, where N is the size of the problem.