A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
arXiv:1905.12646 · doi:10.1103/PhysRevA.101.032314
Abstract
A device called a 'Gaussian Boson Sampler' has initially been proposed as a near-term demonstration of classically intractable quantum computation. As recently shown, it can also be used to decide whether two graphs are isomorphic. Based on these results we construct a feature map and graph similarity measure or 'graph kernel' using samples from the device. We show that the kernel performs well compared to standard graph kernels on typical benchmark datasets, and provide a theoretical motivation for this success, linking the distribution of a Gaussian Boson Sampler to the number of matchings in subgraphs. Our results contribute to a new way of thinking about kernels as a (quantum) hardware-efficient feature mapping, and lead to an interesting application for near-term quantum computing.
7 pages, 6 figures, 2 tables
References in corpus (17)
- Gaussian Quantum Information
- Supervised learning with quantum enhanced feature spaces
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Quantum machine learning in feature Hilbert spaces
- Boson Sampling on a Photonic Chip
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Gaussian Boson Sampling
- Boson Sampling from Gaussian States
- A detailed study of Gaussian Boson Sampling
- Subgraph Matching Kernels for Attributed Graphs
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- Graph isomorphism and Gaussian boson sampling
- Franck-Condon factors by counting perfect matchings of graphs with loops
- Hafnians, perfect matchings and Gaussian matrices
- GraKeL: A Graph Kernel Library in Python
Cited by in corpus (44)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum circuits with many photons on a programmable nanophotonic chip
- Non-Gaussian Quantum States and Where to Find Them
- Broadband quadrature-squeezed vacuum and nonclassical photon number correlations from a nanophotonic device
- Computational advantage of quantum random sampling
- Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
- Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing
- Solving Graph Problems Using Gaussian Boson Sampling
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
- The Complexity of Bipartite Gaussian Boson Sampling
- Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
- Quantum Algorithm for Simulating Molecular Vibrational Excitations
- Quantum Feature Maps for Graph Machine Learning on a Neutral Atom Quantum Processor
- Training Gaussian Boson Sampling Distributions
- Quantum machine learning with Adaptive Boson Sampling via post-selection
- Quantum machine learning with adaptive linear optics
- Degenerate Squeezing in Waveguides: A Unified Theoretical Approach
- Experimental demonstration of Gaussian boson sampling with displacement
- Threshold detection statistics of bosonic states
- What do QAOA energies reveal about graphs?
- Error mitigation on a near-term quantum photonic device
- Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
- Certification of Gaussian Boson Sampling via graph theory
- Noise thresholds for classical simulability of non-linear Boson sampling
- Phase-space negativity as a computational resource for quantum kernel methods
- Graph kernels encoding features of all subgraphs by quantum superposition
- Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers
- A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits
- Sample efficient graph classification using binary Gaussian boson sampling
- Gaussian boson sampling at finite temperature
- Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spaces
- Nodal statistics-based equivalence relation for graph collections
- Validation of a noisy Gaussian boson sampler via graph theory
- Supervised binary classification of small-scale digit images and weighted graphs with a trapped-ion quantum processor
- Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
- Harnessing a 256-qubit Neutral Atom Simulator for Graph Classification
- Quantum interference with time-frequency modes and multiple-photons generated by a silicon nitride microresonator
- Classical modelling of a bosonic sampler with photon collisions
- Towards graph classification with Gaussian Boson Sampling by embedding graphs on the X8 photonic chip
- Realistic photon-number resolution in Gaussian boson sampling
- Optical Quantum Computing
- Quantum Advantage with Timestamp Membosonsampling
- Computational indistinguishability and boson sampling