Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms
- Publisher:
- American Physical Society (APS)
- Publication Type:
- Journal Article
- Citation:
- Physical Review Research, 2021, 3, (4), pp. 043095
- Issue Date:
- 2021-12-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Many quantum algorithms that claim speedup over their classical counterparts only generates quantum states as solutions instead of their final classical description. The additional step to decode quantum states into classical vectors normally will destroy the quantum advantage in most scenarios because all existing tomographic methods require runtime that is polynomial with respect to the state dimension. In this work, we present an efficient readout protocol that yields the classical vector form of the generated state, so it will achieve the end-to-end advantage for those quantum algorithms. Our protocol suits the case in which the output state lies in the row space of the input matrix, of rank r, that is stored in the quantum random access memory. The quantum resources for decoding the state in 2 norm with ϵ error require poly(r,1/ϵ) copies of the output state and poly(r,κr,1/ϵ) queries to the input oracles, where κ is the condition number of the input matrix. With our readout protocol, we completely characterize the end-to-end resources for quantum linear equation solvers and quantum singular value decomposition. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure, which we believe will be of independent interest.
Please use this identifier to cite or link to this item: