Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
arXiv:2004.06421 · doi:10.1103/PhysRevResearch.3.043095
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 , that is stored in the quantum random access memory. The quantum resources for decoding the state in 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.
arXiv commentFinal version
References in corpus (45)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Supervised learning with quantum enhanced feature spaces
- Quantum support vector machine for big data classification
- Quantum computational chemistry
- Quantum Amplitude Amplification and Estimation
- Quantum principal component analysis
- Scalable multi-particle entanglement of trapped ions
- Quantum fingerprinting
- Continuous-variable optical quantum state tomography
- Quantum state tomography via compressed sensing
- Quantum random access memory
- Efficient quantum state tomography
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum Data Fitting
- Quantum algorithms for supervised and unsupervised machine learning
- Quantum chemistry calculations on a trapped-ion quantum simulator
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Experimental Realization of Quantum Artificial Intelligence
- A quantum linear system algorithm for dense matrices
- Process tomography of ion trap quantum gates
- Sample-optimal tomography of quantum states
- Quantum gradient descent for linear systems and least squares
- Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
- Quantum singular value decomposition of non-sparse low-rank matrices
- A quantum algorithm for high energy physics simulations
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- q-means: A quantum algorithm for unsupervised machine learning
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Quantum Perceptron Models
- 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
- Quantum state tomography via reduced density matrices
- 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
- Universal state orthogonalizer and qubit generator
- 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
- A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
- Orthogonalization of partly unknown quantum states
- Dimensional lifting through generalized Gram-Schmidt process