Quantum QR decomposition in the computational basis
2020
In this paper, we propose a quantum algorithm for approximating the QR decomposition of any $$N\times N$$
matrix with a running time $$O(\frac{1}{\epsilon ^2}$$
$$N^{2.5}\text {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)$$
. 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))$$
times the running time of the quantum algorithm originally designed with the amplitude encoding method, where N is the size of the problem.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
2
Citations
NaN
KQI