Physical Review Research 3, 04395 (2021). [arXiv]
Abstract
Many quantum machine learning (QML) algorithms that claim speed-up over their classical counterparts only generate 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 Letter, 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 that 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 read-out protocol, we completely characterise 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.