Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
- Publication Type:
- Journal Article
- Citation:
- Physical Review Research, 2020, 3, pp. 04395
- Issue Date:
- 2020-04-14
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Many quantum 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 work, we present an efficient read-out
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 $\ell^2$ norm with $\epsilon$
error require $\poly(r,1/\epsilon)$ copies of the output state and $\poly(r,
\kappa^r,1/\epsilon)$ queries to the input oracles, where $\kappa$ 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.
Please use this identifier to cite or link to this item: