Quantum kernel methods are a proposal for achieving quantum computational advantage in machine learning. They are based on a hybrid classical-quantum computation where a function called the quantum kernel is estimated by a quantum device while the rest of computation is performed classically. Quantum advantages may be achieved through this method only if the quantum kernel function cannot be estimated efficiently on a classical computer. In this paper, we provide sufficient conditions for the efficient classical estimation of quantum kernel functions for bosonic systems. These conditions are based on phase-space properties of data-encoding quantum states associated with the quantum kernels: negative volume, non-classical depth, and excess range, which are shown to be three signatures of phase-space negativity. We consider quantum optical examples involving linear-optical networks with and without adaptive non-Gaussian measurements, and investigate the effects of loss on the efficiency of the classical simulation. Our results underpin the role of the negativity in phase-space quasi-probability distributions as an essential resource in quantum machine learning based on kernel methods.
Quantum kernel methods are a proposal for achieving quantum computational advantage in machine learning. They are based on a hybrid classical-quantum computation where a function called the quantum kernel is estimated by a quantum device while the rest of computation is performed classically. Quantum advantages may be achieved through this method only if the quantum kernel function cannot be estimated efficiently on a classical computer. In this paper, we provide sufficient conditions for the efficient classical estimation of quantum kernel functions for bosonic systems. These conditions are based on phase-space properties of data-encoding quantum states associated with the quantum kernels: negative volume, non-classical depth, and excess range, which are shown to be three signatures of phase-space negativity. We consider quantum optical examples involving linear-optical networks with and without adaptive non-Gaussian measurements, and investigate the effects of loss on the efficiency of the classical simulation. Our results underpin the role of the negativity in phase-space quasi-probability distributions as an essential resource in quantum machine learning based on kernel methods.
Phase-space representations can be used to reveal resources for quantum computational advantage. In odd-dimensional qudit systems, states and operations admitting non-negative quasi-probability representations are efficiently classically simulable, and analogous conclusions hold for bosonic systems, usually represented in quadrature phase space. However, when quantum information is encoded in bosonic systems, the link between physical phase-space representations and computational resources becomes nontrivial: large negativities may arise in the physical space even when the encoded model remains efficiently simulable. We establish a general framework connecting physical phase spaces of bosonic systems to the effective computational phase spaces associated with arbitrary encodings. We show that bosonic Hilbert spaces with finitely many modes can always be exactly encoded on a quantum computer, without truncation or approximations, and that for any encoding there exists an adapted physical phase-space representation in which all provably classically simulable states and protocols are non-negative. Conversely, negativity can always persist in physical representations for arbitrary encodings. Our results formalize the operational meaning of phase-space negativity in bosonic quantum information and its relation with computational resources.
Kernel methods are ubiquitous in classical machine learning, and recently their formal similarity with quantum mechanics has been established. To grasp the potential advantage of quantum machine learning, it is necessary to understand the distinction between nonclassical kernel functions and classical kernels. This paper builds on a recently proposed phase-space nonclassicality witness [Bohmann and Agudelo, Phys. Rev. Lett. 124, 133601 (2020)] to derive a witness for the kernel's quantumness in continuous-variable systems. We discuss the role of the kernel's nonclassicality in data distribution in the feature space and the effect of imperfect state preparation. Furthermore, we show that the nonclassical kernels lead to the quantum advantage in parameter estimation. Our work highlights the role of the phase-space correlation functions in understanding the distinction of classical machine learning from quantum machine learning.
A classical simulation scheme of quantum computation given a restricted set of states and measurements may be---occasionally, but only occasionally---interpreted naturally as a statistical simulation of positive quasi-probability distributions on a phase space. In this dissertation, we explore phase space representations for finite-dimensional quantum systems and their negativities beyond the usual analogues of the Wigner function. The first line of study focuses on a characterization tool for valid quasi-probability distributions of (possibly mixed) quantum states. A quantum generalization of Bochner's theorem from classical probability theory simultaneously characterizes both the set of valid Wigner functions and the subset of positive ones. We extend this theorem to discrete phase spaces based on projective representations of abelian groups, including the discrete Wigner functions of Gross (J. Math. Phys. 47, 122107 (2006)) and Gibbons et al. (Phys. Rev. A 70, 062101 (2004)). The rest of the dissertation is then dedicated to phase space representations covariant with respect to a general Lie group. This means, in particular, that operators that lie in the same orbit of the group have the same amount of negativity in their quasi-probabilities---a natural requirement if one would like to interpret negativity as non-classicality, and the group action as a classical dynamics. We show that the construction due to Brif and Mann (Phys. Rev. A 59, 971 (1999)) of group covariant phase space representations satisfying the so-called Stratonovich-Weyl correspondence is essentially unique, given the group and an input state in the relevant representation. As an application, we construct quasi-probability representations on a compact phase space of fermionic Gaussian states tailored to a classically simulatable problem of fermionic linear optics and find that, in the first non-trivial case of four fermionic modes, the quasi-probabilities of the Gaussian states exhibit a considerable amount of negativity.
It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS). We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements. In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.
Quantum computers have the opportunity to be transformative for a variety of computational tasks. Recently, there have been proposals to use the unsimulatably of large quantum devices to perform regression, classification, and other machine learning tasks with quantum advantage by using kernel methods. While unsimulatably is a necessary condition for quantum advantage in machine learning, it is not sufficient, as not all kernels are equally effective. Here, we study the use of quantum computers to perform the machine learning tasks of one- and multi-dimensional regression, as well as reinforcement learning, using Gaussian Processes. By using approximations of performant classical kernels enhanced with extra quantum resources, we demonstrate that quantum devices, both in simulation and on hardware, can perform machine learning tasks at least as well as, and many times better than, the classical inspiration. Our informed kernel design demonstrates a path towards effectively utilizing quantum devices for machine learning tasks.
Kernel methods in Quantum Machine Learning (QML) have recently gained significant attention as a potential candidate for achieving a quantum advantage in data analysis. Among other attractive properties, when training a kernel-based model one is guaranteed to find the optimal model's parameters due to the convexity of the training landscape. However, this is based on the assumption that the quantum kernel can be efficiently obtained from quantum hardware. In this work we study the performance of quantum kernel models from the perspective of the resources needed to accurately estimate kernel values. We show that, under certain conditions, values of quantum kernels over different input data can be exponentially concentrated (in the number of qubits) towards some fixed value. Thus on training with a polynomial number of measurements, one ends up with a trivial model where the predictions on unseen inputs are independent of the input data. We identify four sources that can lead to concentration including expressivity of data embedding, global measurements, entanglement and noise. For each source, an associated concentration bound of quantum kernels is analytically derived. Lastly, we show that when dealing with classical data, training a parametrized data embedding with a kernel alignment method is also susceptible to exponential concentration. Our results are verified through numerical simulations for several QML tasks. Altogether, we provide guidelines indicating that certain features should be avoided to ensure the efficient evaluation of quantum kernels and so the performance of quantum kernel methods.