Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms

Abstract

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/ε)$ copies of the output state and $\poly(r, κ^r,1/ε)$ 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.

Final version

References in corpus (19)

• Quantum algorithm for solving linear systems of equations
• Scalable multi-particle entanglement of trapped ions
• Quantum random access memory
• Efficient quantum state tomography
• Quantum Data Fitting
• Experimental Realization of Quantum Artificial Intelligence
• Process tomography of ion trap quantum gates
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
• Quantum State Orthogonalization and a Toolset for Quantum Optomechanical Phonon Control
• Quantum Algorithms for Deep Convolutional Neural Networks
• Resilience of quantum random access memory to generic noise
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Maximal entropy approach for quantum state tomography
• Complexity of quantum state verification in the quantum linear systems problem
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Orthogonalization of partly unknown quantum states

Cited by in corpus (2)

• Quantum Blockchain Based on Dimensional Lifting Generalized Gram-Schmidt Procedure
• Unleashed from Constrained Optimization: Quantum Computing for Quantum Chemistry Employing Generator Coordinate Inspired Method