We study supervised learning algorithms in which a quantum device is used to perform a computational subroutine – either for prediction via probability estimation, or to compute a kernel via estimation of quantum states overlap. We design implementations of these quantum subroutines using Boson Sampling architectures in linear optics, supplemented by adaptive measurements. We then challenge these quantum algorithms by deriving classical simulation algorithms for the tasks of output probability estimation and overlap estimation. We obtain different classical simulability regimes for these two computational tasks in terms of the number of adaptive measurements and input photons. In both cases, our results set explicit limits to the range of parameters for which a quantum advantage can be envisaged with adaptive linear optics compared to classical machine learning algorithms: we show that the number of input photons and the number of adaptive measurements cannot be simultaneously small compared to the number of modes. Interestingly, our analysis leaves open the possibility of a near-term quantum advantage with a single adaptive measurement.
We study supervised learning algorithms in which a quantum device is used to perform a computational subroutine – either for prediction via probability estimation, or to compute a kernel via estimation of quantum states overlap. We design implementations of these quantum subroutines using Boson Sampling architectures in linear optics, supplemented by adaptive measurements. We then challenge these quantum algorithms by deriving classical simulation algorithms for the tasks of output probability estimation and overlap estimation. We obtain different classical simulability regimes for these two computational tasks in terms of the number of adaptive measurements and input photons. In both cases, our results set explicit limits to the range of parameters for which a quantum advantage can be envisaged with adaptive linear optics compared to classical machine learning algorithms: we show that the number of input photons and the number of adaptive measurements cannot be simultaneously small compared to the number of modes. Interestingly, our analysis leaves open the possibility of a near-term quantum advantage with a single adaptive measurement.
The implementation of large-scale universal quantum computation represents a challenging and ambitious task on the road to quantum processing of information. In recent years, an intermediate approach has been pursued to demonstrate quantum computational advantage via non-universal computational models. A relevant example for photonic platforms has been provided by the Boson Sampling paradigm and its variants, which are known to be computationally hard while requiring at the same time only the manipulation of the generated photonic resources via linear optics and detection. Beside quantum computational advantage demonstrations, a promising direction towards possibly useful applications can be found in the field of quantum machine learning, considering the currently almost unexplored intermediate scenario between non-adaptive linear optics and universal photonic quantum computation. Here, we report the experimental implementation of quantum machine learning protocols by adding adaptivity via post-selection to a Boson Sampling platform based on universal programmable photonic circuits fabricated via femtosecond laser writing. Our experimental results demonstrate that Adaptive Boson Sampling is a viable route towards dimension-enhanced quantum machine learning with linear optical devices. Extending quantum photonics’ capabilities from simple linear-optics-based schemes to universal quantum computing presents several challenges, but intermediate regimes with some degree of adaptivity might already bring practical advantages. Here, the authors experimentally emulate an adaptive Boson Sampling scheme using post-selection, and apply it to a data classification task.
Recent photonic quantum machine learning proposals combined linear optics with adaptivity to enhance expressivity and improve algorithm performance and scalability. The particle-number-preserving property of linear optical platforms was recently employed to design a quantum convolutional neural network architecture with advantages in terms of resource complexity and the number of parameters needed. Here, we design and experimentally implement a photonic quantum convolutional neural network (PQCNN) based on linear optics equipped with adaptive state injection, a tool that increases the linear optical circuits controllability. We validate the PQCNN for a binary image classification on a photonic platform utilizing a semiconductor quantum dot-based single-photon source and programmable integrated photonic interferometers comprising 8 and 12 modes. To investigate the scalability of the PQCNN design, we performed numerical simulations on datasets of different sizes. These findings demonstrate potential utilities of a simple adaptive technique for a nonlinear boson sampling task, compatible with near-term quantum devices.
In this dissertation, we study the intersection of quantum computing and supervised machine learning algorithms, which means that we investigate quantum algorithms for supervised machine learning that operate on classical data. This area of research falls under the umbrella of quantum machine learning, a research area of computer science which has recently received wide attention. In particular, we investigate to what extent quantum computers can be used to accelerate supervised machine learning algorithms. The aim of this is to develop a clear understanding of the promises and limitations of the current state of the art of quantum algorithms for supervised machine learning, but also to define directions for future research in this exciting field. We start by looking at supervised quantum machine learning (QML) algorithms through the lens of statistical learning theory. In this framework, we derive novel bounds on the computational complexities of a large set of supervised QML algorithms under the requirement of optimal learning rates. Next, we give a new bound for Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known supervised QML algorithms, and then derive a classical algorithm with nearly the same complexity. We then draw the parallels to recent "quantum-inspired" results, and will explain the implications of these results for quantum machine learning applications. Looking for areas which might bear larger advantages for QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann machines, and argue that quantum algorithms for quantum data are one of the most promising applications for QML with potentially exponential advantage over classical approaches.
Universal photon-based quantum computing requires optical nonlinearities, which can be induced by intermediate measurements and by adaptivity, to be supplied to linear-optical elements. In a near-term perspective, it is essential to probe whether dynamics going beyond linear optics can be accessed with a limited amount of resources. Although recent results show how linear-optical dynamics implies bounds on the set of photonic states that can be generated, quantitative methods for studying the emergence of nonlinear dynamics are largely missing. Here we analyse a regime in which such bounds can be surpassed. We do this by leveraging an adaptive boson sampling architecture in which the optical evolution implemented in a photonic device is progressively adapted via measurement-based feedback. We introduce practical methods to quantify the emergence of a gap with respect to linear optics and derive nonlinearity witnesses from the properties of linear-optical evolution. Then, we validate the toolbox developed within adaptive boson sampling architectures of increasing complexity implemented on a state-of-the-art photonic platform, both by realizing real-time adaptivity and by emulating adaptive protocols via post-selection for more complex configurations. In particular, we probe experimentally a regime in which nonlinear dynamics, unobtainable within a linear-optical paradigm, can arise, thus showing how optical architectures with limited adaptivity are a powerful testbed for exploring new regimes.
Abstract Demonstration of quantum advantage for classical machine learning tasks remains a central goal for quantum technologies and artificial intelligence. Two major bottlenecks to this goal are the high dimensionality of practical datasets and the limited performance of near-term quantum computers. Boson sampling is among the few models for which experiments have claimed quantum advantage, yet it has limited practical applications. Here, we propose a hybrid framework that combines the computational power of boson sampling with the adaptability of neural networks to construct quantum kernels that enhance support vector machine classification. The neural network adapts the data features onto a programmable boson sampling circuit, producing quantum states that span a high-dimensional Hilbert space and enable improved classification performance. Using four datasets with various classes, we demonstrate that our model outperforms classical linear and sigmoid kernels. These results highlight the potential of boson sampling-based quantum kernels for practical quantum-enhanced machine learning.
We propose a new scheme for near-term photonic quantum devices that allows us to increase the expressive power of the quantum models beyond what linear optics can do. This scheme relies upon state injection, a measurement-based technique that can produce states that are more controllable, and solve learning tasks that are believed to be intractable classically. We explain how circuits made of linear optical architectures separated by state injections are well-suited for experimental implementation. In addition, we give theoretical results regarding the evolution of the purity of the resulting states, and we discuss how it impacts the distinguishability of the circuit outputs. Finally, we study a computational subroutine of learning algorithms named probability estimation, and we show that the state injection scheme we propose may offer a potential quantum advantage in a regime that can be more easily achieved than state-of-the-art adaptive techniques. Our analysis offers new possibilities for near-term advantage that rely on overcoming fewer experimental difficulties.