Anzeige
Erschienen in:
01.08.2020
Quantum QR decomposition in the computational basis
Erschienen in: Quantum Information Processing | Ausgabe 8/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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.