Solving Graph Problems Using Gaussian Boson Sampling

• URL: http://arxiv.org/abs/2302.00936v2
• Date: Mon, 24 Apr 2023 23:29:26 GMT
• Title: Solving Graph Problems Using Gaussian Boson Sampling
• Authors: Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Zhi-Jiong Zhang, Hua-Liang Liu, Hao Su, Hao-Yang Tang, Jia-Min Xu, Meng-Hao Jia, Ming-Cheng Chen, Han-Sen Zhong, Hui Wang, Jiarong Yan, Yi Hu, Jia Huang, Wei-Jun Zhang, Hao Li, Xiao Jiang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, Jian-Wei Pan
• Abstract summary: 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.
• Score: 22.516585968074146
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian boson sampling (GBS) is not only a feasible protocol for demonstrating quantum computational advantage, but also mathematically associated with certain graph-related and quantum chemistry problems. In particular, it is proposed that the generated samples from the GBS could be harnessed to enhance the classical stochastic algorithms in searching some graph features. Here, we use Jiuzhang, a noisy intermediate-scale quantum computer, to solve graph problems. The samples are generated from a 144-mode fully-connected photonic processor, with photon-click up to 80 in the quantum computational advantage regime. We investigate the open question of whether the GBS enhancement over the classical stochastic algorithms persists -- and how it scales -- with an increasing system size on noisy quantum devices in the computationally interesting regime. We experimentally observe the presence of GBS enhancement with large photon-click number and a robustness of the enhancement under certain noise. Our work is a step toward testing real-world problems using the existing noisy intermediate-scale quantum computers, and hopes to stimulate the development of more efficient classical and quantum-inspired algorithms.

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 Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
  We show that a quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states.
  arXiv  Detail & Related papers  (2023-10-11T18:00:53Z)
• Hybrid quantum transfer learning for crack image classification on NISQ hardware [62.997667081978825]
  We present an application of quantum transfer learning for detecting cracks in gray value images. We compare the performance and training time of PennyLane's standard qubits with IBM's qasm_simulator and real backends.
  arXiv  Detail & Related papers  (2023-07-31T14:45:29Z)
• Testing of on-cloud Gaussian Boson Sampler "Borealis'' via graph theory [0.0]
  photonic-based sampling machines solving the Gaussian Boson Sampling problem play a central role in the experimental demonstration of a quantum computational advantage. In this work, we test the performances of the recently developed photonic machine Borealis as a sampling machine and its possible use cases in graph theory.
  arXiv  Detail & Related papers  (2023-06-21T09:02:55Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Noisy Quantum Kernel Machines [58.09028887465797]
  An emerging class of quantum learning machines is that based on the paradigm of quantum kernels. We study how dissipation and decoherence affect their performance. We show that decoherence and dissipation can be seen as an implicit regularization for the quantum kernel machines.
  arXiv  Detail & Related papers  (2022-04-26T09:52:02Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light [32.20791352792308]
  We report a new GBS experiment that produces up to 113 detection events out of a 144-mode photonic circuit. We develop a new high-brightness and scalable quantum light source, exploring the idea of stimulated squeezed photons. The photonic quantum computer, Jiuzhang 2.0, yields a Hilbert space dimension up to $1043$, and a sampling rate $1024$ faster than using brute-force simulation.
  arXiv  Detail & Related papers  (2021-06-29T16:11:29Z)
• 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)

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.