Quantum-inspired algorithms in practice

Abstract

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

arXiv commentA popular summary can be found at https://medium.com/xanaduai/everything-you-always-wanted-to-know-about-quantum-inspired-algorithms-38ee1a0e30ef . Source code is available at https://github.com/XanaduAI/quantum-inspired-algorithms

References in corpus (12)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Defining and detecting quantum speedup
• Sketching as a Tool for Numerical Linear Algebra
• A quantum-inspired classical algorithm for recommendation systems
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum Recommendation Systems
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum computational finance: quantum algorithm for portfolio optimization
• A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices

Cited by in corpus (49)

• Quantum computing for finance
• Information-theoretic bounds on quantum advantage in machine learning
• Quantum-Inspired Support Vector Machine
• Variational Quantum State Eigensolver
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum computing models for artificial neural networks
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum Algorithms for Deep Convolutional Neural Networks
• Genome assembly using quantum and quantum-inspired annealing
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• An improved quantum-inspired algorithm for linear regression
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum Algorithm for Fidelity Estimation
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Quantum Mixed State Compiling
• A brief introduction to quantum algorithms
• Quantum kernels to learn the phases of quantum matter
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Quantum computing through the lens of control: A tutorial introduction
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Low-depth Clifford circuits approximately solve MaxCut
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Quantum algorithms for SVD-based data representation and analysis
• Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
• Quantum Semi-Supervised Kernel Learning
• Qudit Machine Learning
• A didactic approach to quantum machine learning with a single qubit
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
• Quantum State Discrimination for Supervised Classification
• Quantum mean estimation for lattice field theory
• Framework for Learning and Control in the Classical and Quantum Domains
• From quantum-enhanced to quantum-inspired Monte Carlo
• A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time
• Quantum computing for data science
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Quantum-Inspired Classical Algorithm for Principal Component Regression
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
• Fast Extraction of Word Embedding from Q-contexts
• Quantum Machine Learning For Classical Data
• Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation
• Quantum-inspired memory-enhanced stochastic algorithms
• Quantum Implementation of Risk Analysis-relevant Copulas
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Quantum Algorithms for Causal Estimands