# Quantum-inspired algorithms in practice

@article{Arrazola2020QuantuminspiredAI, title={Quantum-inspired algorithms in practice}, author={Juan Miguel Arrazola and Alain Delgado and Bhaskar Roy Bardhan and Seth Lloyd}, journal={Quantum}, year={2020}, volume={4}, pages={307} }

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… Expand

#### Figures, Tables, and Topics from this paper

#### 48 Citations

Quantum-Inspired Classical Algorithm for Slow Feature Analysis

- Mathematics, Computer Science
- ArXiv
- 2020

This work proposed an algorithm for slow feature analysis, a machine learning algorithm that extracts the slow-varying features, with a run time O(polylog(n)poly(d)). Expand

Quantum Algorithms for Data Representation and Analysis

- Computer Science, Physics
- ArXiv
- 2021

We narrow the gap between previous literature on quantum linear algebra and useful data analysis on a quantum computer, providing quantum procedures that speed-up the solution of eigenproblems for… Expand

Quantum Algorithms for Feedforward Neural Networks

- Physics, Computer Science
- ArXiv
- 2018

This work presents quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms that rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. Expand

Quantum-inspired memory-enhanced stochastic algorithms

- Computer Science, Physics
- 2019

It is shown that it is possible to develop quantum-inspired classical algorithms that require much less memory than the best classical algorithms known to date. Expand

Quantum-Inspired Classical Algorithm for Principal Component Regression

- Computer Science, Physics
- ArXiv
- 2020

An algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. Expand

Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions.

- Computer Science, Physics
- Physical review letters
- 2021

With this model, classical analogues to Lloyd, Mohseni, and Rebentrost’s quantum algorithms for principal component analysis and nearest-centroid clustering are described and it is suggested that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions. Expand

Quantum-inspired canonical correlation analysis for exponentially large dimensional data

- Computer Science, Medicine
- Neural Networks
- 2021

The conducted experiments demonstrate that, as a result of mapping raw input data into the high-dimensional spaces with the use of second-order monomials, qiCCA extracts more correlations compared with the linear CCA and achieves comparable performance with state-of-the-art nonlinear variants of CCA on several datasets. Expand

Quantum classification of the MNIST dataset via Slow Feature Analysis

- Computer Science, Physics
- ArXiv
- 2018

This work proposes a quantum version of Slow Feature Analysis (QSFA), a dimensionality reduction technique that maps the dataset in a lower dimensional space where it can apply a novel quantum classification procedure, the Quantum Frobenius Distance (QFD). Expand

Optimal quantum eigenstate filtering with application to solving quantum linear systems

- Mathematics
- 2019

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given… Expand

A survey on HHL algorithm: From theory to application in quantum machine learning

- Physics
- 2020

Abstract The Harrow-Hassidim-Lloyd (HHL) algorithm is a method to solve the quantum linear system of equations that may be found at the core of various scientific applications and quantum machine… Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

A quantum-inspired classical algorithm for recommendation systems

- Computer Science, Physics
- Electron. Colloquium Comput. Complex.
- 2018

A classical analogue to Kerenidis and Prakash’s quantum recommendation system is given, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning, which produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n. Expand

Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches

- Computer Science, Mathematics
- ArXiv
- 2019

This paper presents a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms and applies it to a quantum state learning task as an application. Expand

Quantum-inspired sublinear classical algorithms for solving low-rank linear systems

- Mathematics, Computer Science
- ArXiv
- 2018

Two classical sublinear-time algorithms for solving low-rank linear systems of equations with query and time complexity are presented, inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithms for recommendation systems. Expand

An Empirical Evaluation of Sketching for Numerical Linear Algebra

- Mathematics, Computer Science
- KDD
- 2018

This work investigates least squares regression, iteratively reweighted least squares, logistic regression, robust regression with Huber and Bisquare loss functions, leverage score computation, Frobenius norm low rank approximation, and entrywise $\ell_1$-low rank approximation. Expand

Quantum Recommendation Systems

- Mathematics, Computer Science
- ITCS
- 2017

This work presents the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application. Expand

Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

- Mathematics, Computer Science
- SIAM Rev.
- 2011

This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation, and presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. Expand

Quantum computational finance: quantum algorithm for portfolio optimization

- Mathematics, Physics
- 2018

We present a quantum algorithm for portfolio optimization. We discuss the market data input, the processing of such data via quantum operations, and the output of financially relevant results. Given… Expand

Defining and detecting quantum speedup

- Computer Science, Medicine
- Science
- 2014

Here, it is shown how to define and measure quantum speedup and how to avoid pitfalls that might mask or fake such a speedup, and the subtle nature of the quantum speed up question is illustrated. Expand

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

- Mathematics, Computer Science
- IEEE Trans. Evol. Comput.
- 2002

The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm, and a Q-gate is introduced as a variation operator to drive the individuals toward better solutions. Expand

A fast randomized algorithm for the approximation of matrices ✩

- 2007

We introduce a randomized procedure that, given an m×n matrix A and a positive integer k, approximates A with a matrix Z of rank k. The algorithm relies on applying a structured l ×m random matrix R… Expand