Quantum advantage for machine learning using subspace states

My posts on quantum computing are usually pessimistic, in an attempt to counter the excessive amount of hype present in the literature and media. Recently I stumbled upon a refreshingly humble and exciting paper which presents a few quantum algorithms with the potential for a near-term quantum advantage:

Quantum machine learning with subspace states

I will attempt to summarise the main ideas of this paper and why they are important. For a video summary, one of the authors of the preprint (Anupam Prakash) also recently presented this work at a workshop (video here).

Introduction

Behind all the hype on quantum machine learning and optimization, practical algorithms remain scarce. Variational algorithms such as QAOA are extremely challenging to implement on problems of useful size. Moreover, the need for iterative optimization of the circuit parameters means that convergence issues may prevent these algorithms from out-performing existing highly sophisticated classical optimisation algorithms.

On the other hand, most non-variational algorithms are designed for fault-tolerant quantum computers and either only offer modest speedups (quadratic in the case of quantum amplitude amplification / quantum search), which may not be suitable for achieving a quantum advantage, or the claimed exponential speedups (quantum linear algebra subroutines) evaporate using "dequantization" techniques to obtain quantum-inspired classical algorithms with similar performance. The key point underlying dequantization is that certain quantum algorithms assume access to input data stored in quantum RAM (QRAM); their apparent speed-up comes from the additional overhead required to load the classical data into the QRAM.

Quantum algorithms for topological data analysis (QTDA) are one promising exception that promise an exponential quantum speedup that persists even when the classical data encoding step is taken into account. The reason for this is that QTDA algorithms take a set of N classical vectors as their input, and then consider different subsets of k vectors. Combinatorial explosion means that the runtime of classical algorithms for TDA grows exponentially with k, while quantum circuits can process and efficiently sample from different combinations in parallel, enabling an exponential speedup.

It turns out that performing efficient weighted sampling of subsets appears as a subroutine in other machine learning algorithms. One example is performing linear regression on large datasets by sampling a small number of the data points; the ability to use weighted sampling to construct an unbiased estimator of the optimal regression model allows the calculation to be performed using distributed computing.

Quantum subspace states are a generalization of amplitude encoded quantum states. Amplitude encoding is a way to map an n-dimensional data vector into a quantum state. Amplitude encoding starts with the |100...0> state, and then performs a sequence of n-1 data-dependent reconfigurable beam-splitter gates to produce a superposition of n unary (i.e. only one of the qubits is in the state |1>) quantum states using a circuit of depth log(n), called a data loader circuit. This scaling is very good for near-term quantum processors lacking quantum error correction; hardware providers are adding more and more qubits, but their devices can still only run very shallow circuits.

Subspace states generalise amplitude encoded states to, as the name implies, d-dimensional subspaces of the n-dimensional vector space. One way they can be viewed is as a suitable rotation of the product state (|1>)^d (|0>)^(n-d), i.e. with the first d qubits in the |1> state. They can be efficiently generated using a sequence of d "Clifford Loader" circuits applied to the initial state (|0>)^n, which has depth O(d log n) and O(nd) gates. Thus, subspace states are also NISQ-friendly.

Applications of quantum subspace states

(1) Simply measuring quantum subspace states in the computational basis, one samples bitstrings with probability weight given by the determinant of d-dimensional submatrices of the input data. The best classical algorithm scales as O(d^3), while the quantum sampling requires only O(nd) gates and depth O(log n). This kind of weighted sampling can have applications in distributed machine learning and randomised linear algebra algorithms. 

(2) Singular value estimation of compound matrices. Here, the quantum subspace state is used as an input to the quantum phase estimation algorithm, allowing k-order correlations to be decomposed into a linear combination of subspaces of singular vectors of some input matrix A. This has applications in joint recommendation algorithms.

(3) Quantum topological data analysis. The Clifford loader circuit provides an exponentially shallower [O(log n) vs O(n)] way to encode the Dirac operator of a simplicial complex.

Take home message

To achieve a quantum advantage for machine learning it is not necessary to encode classical data into a highly entangled quantum state that makes full use of the exponentially-large Hilbert space. Machine learning algorithms based on sampling from subsets of classical large datasets use shallow circuits and do not need variational optimisation, but still exhibit quantum speedups. This makes them highly promising for near-term applications of quantum processors; full quantum error correction is not required!