Quantum singular value decomposition of non-sparse low-rank matrices
arXiv:1607.05404 · doi:10.1103/PhysRevA.97.012327
Abstract
In this work, we present a method to exponentiate non-sparse indefinite low-rank matrices on a quantum computer. Given an operation for accessing the elements of the matrix, our method allows singular values and associated singular vectors to be found quantum mechanically in a time exponentially faster in the dimension of the matrix than known classical algorithms. The method extends to non-Hermitian and non-square matrices via embedding matrices. In the context of the generic singular value decomposition of a matrix, we discuss the Procrustes problem of finding a closest isometry to a given matrix.
5 pages, comments welcome
References in corpus (6)
Cited by in corpus (52)
- Quantum Machine Learning
- A rigorous and robust quantum speed-up in supervised machine learning
- Variational Quantum State Diagonalization
- Holographic quantum algorithms for simulating correlated spin systems
- Variational Quantum Singular Value Decomposition
- Quantum Singular Value Decomposer
- Bayesian Deep Learning on a Quantum Computer
- Quantum Machine-Learning for Eigenstate Filtration in Two-Dimensional Materials
- Variational Quantum Algorithms for Dimensionality Reduction and Classification
- Machine learning \& artificial intelligence in the quantum domain
- Configurable sublinear circuits for quantum state preparation
- A Grover-search Based Quantum Learning Scheme for Classification
- A quantum k-nearest neighbors algorithm based on the Euclidean distance estimation
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- New Quantum Algorithms for Computing Quantum Entropies and Distances
- Efficient quantum circuit for singular value thresholding
- Quantum Circulant Preconditioner for Linear System of Equations
- Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of non-sparse low rank matrices
- Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
- Quantum algorithm for Neighborhood Preserving Embedding
- Neural Quantum Embedding: Pushing the Limits of Quantum Supervised Learning
- Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions
- Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
- Quantum correlation alignment for unsupervised domain adaptation
- Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory
- Quantum diffusion map for nonlinear dimensionality reduction
- A Derivative-free Method for Quantum Perceptron Training in Multi-layered Neural Networks
- Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
- Quantum algorithms for SVD-based data representation and analysis
- Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
- Quantum subspace alignment for domain adaptation
- From linear combination of quantum states to Grover's searching algorithm
- Quantum Element Method for Simulation of Quantum Eigenvalue Problems
- A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
- Distributed Memory Techniques for Classical Simulation of Quantum Circuits
- Quantum Machine Learning Algorithm for Knowledge Graphs
- Quantum tensor singular value decomposition with applications to recommendation systems
- Random Projection using Random Quantum Circuits
- Hybrid Quantum Singular Spectrum Decomposition for Time Series Analysis
- Quantum Higher Order Singular Value Decomposition
- Quantum transfer component analysis for domain adaptation
- Automated Synthesis of Quantum Algorithms via Classical Numerical Techniques
- Quantum algorithm for finding the negative curvature direction in non-convex optimization
- Information Compression and Performance Evaluation of Tic-Tac-Toe's Evaluation Function Using Singular Value Decomposition
- Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem
- Quantum Singular Value Decomposition of Spin Correlation Matrix in One-Dimensional Heisenberg Model
- Quantum Algorithms in Cybernetics
- Quantum Algorithm to Cubic Spline Interpolation
- Schmidt quantum compressor
- Quantum Algorithms for Prediction Based on Ridge Regression
- On sampling determinantal and Pfaffian point processes on a quantum computer
- Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms