Quantum-Inspired Algorithms Could Revolutionize Machine Learning, Say Scientists

Quantum-inspired classical algorithms, which mimic the computational power of quantum computers, could offer significant advantages in machine learning and distributed computation, according to researchers from the University of Liverpool and the Chinese Academy of Sciences. The study found that these algorithms can achieve large quantum speedups for certain matrix-related problems, particularly those that are sparse, high-rank, and well-conditioned. The research also suggests that the quantum-classical separation is quadratic for row-sparse matrices and quartic for dense matrices, indicating potential areas for further exploration and development of more efficient algorithms.

What are Quantum-Inspired Classical Algorithms and Why are They Important?

Quantum-inspired classical algorithms are a new way to understand the computational power of quantum computers, particularly for practically relevant problems in machine learning. These algorithms differ from standard classical algorithms, which typically output vector solutions. Instead, they are more comparable to quantum algorithms and can be used as a tool to study quantum advantage.

In a quantum-inspired classical algorithm for a matrix-relevant problem, such as a linear regression problem, we are given access to a matrix and vector via some data structures similar to Quantum Random Access Memory (QRAM) access. The goal is to output a data structure to the solution. The requirements of this data structure are that we must be able to query entries of the solution and sample from the distribution defined by the solution under the ℓ2-norm. This data structure can thus be viewed as a classical analog of the quantum state of the solution.

The importance of quantum-inspired classical algorithms lies in the finding that quantum computers only achieve polynomial speedups rather than exponential speedups as we originally expected for some matrix problems when the input matrices have low rank. A typical example is the linear regression problem. Assuming the QRAM data structure, the best quantum algorithm known so far has complexity linear in AF, which is believed to be optimal. Here, AF is the Frobenius norm of A, which is defined as the square root of the sum of the absolute squares of all entries.

How Do Quantum-Inspired Classical Algorithms Compare to Quantum Algorithms?

Using a similar data structure to QRAM, some efficient quantum-inspired classical algorithms were also proposed. The best algorithms known so far have complexity quartic in AF^2. This implies that the quantum speedup is at most quartic in terms of the Frobenius norm. We remark that the efficiency of quantum-quantum inspired algorithms is also influenced by other parameters, however, the Frobenius norm is usually the dominating one.

To better understand quantum-classical separations and also to see how far these quantum-inspired classical algorithms are far from optimal, we provide the first approach for proving lower bounds of quantum-inspired classical algorithms. We show that this quartic dependence on the Frobenius norm cannot be improved further for some tasks like linear regression and supervised clustering. For some other tasks like principal component analysis, recommendation systems, and Hamiltonian simulation, we obtain a lower bound that is quadratic in the Frobenius norm.

What are the Findings from the Study of Lower Bounds?

Through the study of these lower bounds, we have two positive findings. First, large quantum speedup can exist for row and column sparse, high-rank, and well-conditioned matrix-relevant problems. Here, by large, we mean the quantum speedup can be exponential. This provides a direction for looking for problems that can demonstrate large quantum speedups.

Second, quantum-inspired classical algorithms can play an important role in classical distributed computation. As a result, efficient classical protocols for many problems with low communication complexity can be found by quantum-inspired classical algorithms. We feel it is interesting to use this idea to find some useful applications such as for machine learning problems.

What is the Conjecture Regarding Quantum-Classical Separation?

We also have a conjecture. If the matrix is row-sparse, then the quantum-classical separation is quadratic for the above tasks and/or for some other tasks that are not covered in this work in terms of the Frobenius norm. If the matrix is dense, then the quantum-classical separation is quartic.

To address this, more efficient quantum-inspired classical algorithms utilizing the property of sparsity are waiting to be discovered in the sparse case and some new ideas are required to prove better lower bounds in the dense case.

What are the Implications of this Research?

This research, conducted by Nikhil S Mande from the Department of Computer Science at the University of Liverpool and Changpeng Shao from the Academy of Mathematics and Systems Science at the Chinese Academy of Sciences, provides a new method to study lower bounds for tasks solved by quantum-inspired classical algorithms.

The findings suggest that large quantum speedup can exist for sparse, high-rank, well-conditioned matrix-related problems. This could provide a direction for identifying problems that can demonstrate large quantum speedups. Furthermore, quantum-inspired classical algorithms could play a significant role in classical distributed computation, potentially leading to efficient classical protocols for many problems with low communication complexity.

The researchers also conjecture that if the matrix is row-sparse, the quantum-classical separation is quadratic for certain tasks, and if the matrix is dense, the separation is quartic. This suggests that more efficient quantum-inspired classical algorithms could be discovered in the sparse case, and new ideas are needed to prove better lower bounds in the dense case.