Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms

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 ${\ell }^2$ norm with $\epsilon$ error require $\mathrm{poly}(r,1/\epsilon )$ copies of the output state and $\mathrm{poly}(r,{\kappa }^r,1/\epsilon )$ queries to the input oracles, where $\kappa$ 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.

Figure 1

Quantum circuit for the $\ell \mathrm{th}$ iteration in the QGSP. Oracles $V_A$ (2) and $U_A$ (1) are employed for encoding rows of the matrix $A$. Gates $C\left(R_i\right)$ (4) are used for extracting the orthogonal part of rows from existing basis rows. After unitary operations, we measure the third register and postselect on the result 0, to generate the state $|{\varphi }_2^{\left(\ell \right)}\rangle$ (7) from the state $|{\varphi }_1^{\left(\ell \right)}\rangle$ (5). Finally, the new index is sampled by measuring the first register of the state $|{\varphi }_2^{\left(\ell \right)}\rangle$.

Figure 2

Quantum circuit for estimating $\langle {\mathit{t}}_k|\mathit{v}\rangle \langle \mathit{v}|{\mathit{t}}_i\rangle$, where $|{\psi }_i\rangle =\frac{1}{\sqrt{2}}\left(\right|{\mathit{t}}_k\rangle |0\rangle +|{\mathit{t}}_i\rangle |1\rangle )$.