This article presents an argument for why quantum computers could unlock new methods for machine learning. We argue that spectral methods, in particular those that learn, regularise, or otherwise manipulate the Fourier spectrum of a machine learning model, are often natural for quantum computers. For example, if a generative machine learning model is represented by a quantum state, the Quantum Fourier Transform allows us to manipulate the Fourier spectrum of the state using the entire toolbox of quantum routines, an operation that is usually prohibitive for classical models. At the same time, spectral methods are surprisingly fundamental to machine learning: A spectral bias has recently been hypothesised to be the core principle behind the success of deep learning; support vector machines have been known for decades to regularise in Fourier space, and convolutional neural nets build filters in the Fourier space of images. Could, then, quantum computing open fundamentally different, much more direct and resource-efficient ways to design the spectral properties of a model? We discuss this potential in detail here, hoping to stimulate a direction in quantum machine learning research that puts the question of ``why quantum?'' first.
Figures & tables
Figure 1: A common simplicity bias of machine learning models is their smoothness, which is linked to a decay of the model function’s Fourier spectrum. But designing such a decay in Fourier space is usually computationally expensive. Can quantum computers help here?
Figure 2: A sketch of the idea of smoothing an empirical distribution of training samples in Fourier space. The empirical distribution is sparse, with support only on the training data. Therefore, its Fourier spectrum is dense and has support on high-order frequencies which can be seen as a consequence of finite data effects. By applying a low-pass filter in Fourier space we impose smoothness on the resulting distribution.
Figure 3: An example of smoothing an empirical distribution in Fourier space to solve the generative learning problem. Starting from an empirical distribution pX of four binary data samples (top left), we compute the (Walsh) Fourier spectrum (bottom left). We then apply a filter of the form p^θ(k)=(1−2θ)∣k∣p^X(k) , where θ∈[0,1] controls the spectral decay rate. Moving back into direct space, we get a model that generalised from the training data by making the empirical distribution smoother.
Figure 4: An example of smoothing empirical distributions with quantum computers, using the same filter as in Figure 3 . Fourier filtering is performed on the amplitudes of the quantum state. We encode the empirical distribution (top left) into a superposition ∣ψX⟩ (mid left), to which we apply the (Walsh) Fourier transform (bottom left). We then apply a non-unitary transformation (with the help of ancillas) to implement the filter ψ^θ(k)∝(1−2θ)∣k∣ψ^X(k) (bottom right). Moving back into direct space (mid right), we get a quantum model with a new distribution of amplitudes, whose measurement distribution constitutes the generative model. Comparing to Figure 3 , it is clear that manipulating the Fourier coefficients of the amplitudes of a quantum model leads to a different generative model, but with a similar structure: high probabilities are amplified and low ones suppressed.
Figure 5: Illustration of the relation between a group and a homogeneous space, which are spaces where every point can be reached by acting with a group element. Group elements that map to the same point live in cosets of the stabiliser subgroup (whose elements map x0 to itself). We can associate the homogeneous space with the quotient space G/H .
Figure 6: Fourier basis functions χk(x) for the cyclic group Zd with imaginary part in blue and real part in red.
Figure 7: Fourier basis functions χk(x) for the boolean group Z2n with imaginary part in blue and real part in red.
Figure 8: Examples for basis functions m^(λ)i,j of the “marginal” subspaces, which are indicator functions that are 1 for certain permutation patterns. Shown are basis functions from the three marginal subspaces corresponding to frequencies indexed by the integer partitions (3,1) , (2,2) and (2,1,1) . It is visible that the highest order (bottom) has support over fewer permutations, than the lowest order (top). The marginal subspaces lend interpretation to Fourier coefficients, which define different subspaces that are “pure” versions of those spanned by the marginal basis.