Sample efficient graph classification using binary Gaussian boson sampling

• URL: http://arxiv.org/abs/2301.01232v3
• Date: Thu, 21 Sep 2023 20:59:32 GMT
• Title: Sample efficient graph classification using binary Gaussian boson sampling
• Authors: Amanuel Anteneh and Olivier Pfister
• Abstract summary: We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. Our setup only requires binary (light/no light) detectors, as opposed to photon number resolving detectors.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS) a near term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup only requires binary (light/no light) detectors, as opposed to photon number resolving detectors. These detectors are technologically simpler and can operate at room temperature, making our algorithm less complex and less costly to implement on the physical hardware. We also investigate the connection between graph theory and the matrix function called the Torontonian which characterizes the probabilities of binary GBS detection events.

Related papers

• Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification [0.9935277311162707]
  We propose a hybrid quantum-classical algorithm for the NP-complete problem of determining if two graphs are minor of one another. We find a graph embedding that allows trading between the one-shot classification accuracy and the amount of input squeezing. We introduce a new classical algorithm based on graph spectra, which we show outperforms various well-known graph-similarity algorithms.
  arXiv  Detail & Related papers  (2024-02-05T21:24:11Z)
• Quantum Architecture Search with Unsupervised Representation Learning [24.698519892763283]
  Unsupervised representation learning presents new opportunities for advancing Quantum Architecture Search (QAS) QAS is designed to optimize quantum circuits for Variational Quantum Algorithms (VQAs)
  arXiv  Detail & Related papers  (2024-01-21T19:53:17Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  We use a noisy intermediate-scale quantum computer to solve graph problems. We experimentally observe the presence of GBS enhancement with large photon-click number and an enhancement under certain noise. Our work is a step toward testing real-world problems using the existing intermediate-scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-02T08:25:47Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• On the Cryptographic Hardness of Learning Single Periodic Neurons [42.86685497609574]
  We show a simple reduction which demonstrates the cryptographic hardness of learning a single neuron over isotropic Gaussian distributions in the presence of noise. Our proposed algorithm is not a gradient-based or an adversarial SQ-time algorithm, but is rather based on the celebrated Lenstra-LenstraLov'asz (LLL) lattice basis reduction algorithm.
  arXiv  Detail & Related papers  (2021-06-20T20:03:52Z)
• Gaussian boson sampling with partial distinguishability [0.0]
  We investigate GBS with partial distinguishability using an approach based on virtual modes and indistinguishability efficiency. We show how the boundary of quantum supremacy in GBS can be pushed further by partial distinguishability.
  arXiv  Detail & Related papers  (2021-05-20T08:17:51Z)
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers [0.0]
  Photonic Quantum Computers provides several benefits over the discrete qubit-based paradigm of quantum computing. We build an anomaly detection model to use on searches for New Physics. We present a novel method of anomaly detection, combining the use of Gaussian Boson Sampling and a quantum extension to K-means known as Q-means.
  arXiv  Detail & Related papers  (2021-03-05T19:02:31Z)
• Learning Graph Neural Networks with Approximate Gradient Descent [24.49427608361397]
  Two types of graph neural networks (GNNs) are investigated, depending on whether labels are attached to nodes or graphs. A comprehensive framework for designing and analyzing convergence of GNN training algorithms is developed. The proposed algorithm guarantees a linear convergence rate to the underlying true parameters of GNNs.
  arXiv  Detail & Related papers  (2020-12-07T02:54:48Z)
• Quantum Sampling Algorithms for Near-Term Devices [0.0]
  We introduce a family of quantum algorithms that provide unbiased samples by encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm. It opens the door to exploring potentially useful sampling algorithms on near-term quantum devices.
  arXiv  Detail & Related papers  (2020-05-28T14:46:20Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound bound, which selects one pair of nodes from the two input graphs to expand at a time. Our GLSearch can be potentially extended to solve many other problems with constraints on graphs.
  arXiv  Detail & Related papers  (2020-02-08T10:03:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.