Solving Graph Problems Using Gaussian Boson Sampling

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.

References in corpus (23)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Gaussian Quantum Information
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum circuits with many photons on a programmable nanophotonic chip
• Gaussian Boson Sampling
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Quantum information with Gaussian states
• Boson Sampling for Molecular Vibronic Spectra
• Generation and sampling of quantum states of light in a silicon chip
• A detailed study of Gaussian Boson Sampling
• Molecular Docking with Gaussian Boson Sampling
• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Gaussian Boson Sampling using threshold detectors
• Gaussian Boson Sampling for perfect matchings of arbitrary graphs
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• Regimes of classical simulability for noisy Gaussian boson sampling
• Experimental Gaussian Boson Sampling
• Quantum approximate optimization with Gaussian boson sampling
• Hafnians, perfect matchings and Gaussian matrices

Cited by in corpus (10)

• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Witnessing non-Markovianity with Gaussian quantum steering in collision model
• The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
• Quantum Scar States in Coupled Random Graph Models
• Gaussian boson sampling at finite temperature
• Validation of a noisy Gaussian boson sampler via graph theory
• Krylov Spread Complexity of Quantum-Walks
• Unified boson sampling
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
• Optical Quantum Computing