Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling

Abstract

We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest $k$-subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph's adjacency matrix to be encoded in a Gaussian boson sampler is nonnegative, which does not necessitate quantum interference. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest $k$-subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed sampler.

arXiv comment11 pages, 5 figures

References in corpus (30)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Gaussian Quantum Information
• Quantum computational advantage using photons
• Characterizing Quantum Supremacy in Near-Term Devices
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum circuits with many photons on a programmable nanophotonic chip
• Gaussian Boson Sampling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Boson Sampling for Molecular Vibronic Spectra
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Dynamic Local Search for the Maximum Clique Problem
• Molecular Docking with Gaussian Boson Sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Applications of Near-Term Photonic Quantum Computers: Software and Algorithms
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Gaussian Boson Sampling for perfect matchings of arbitrary graphs
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Quantum approximate optimization with Gaussian boson sampling
• Solving Graph Problems Using Gaussian Boson Sampling
• Graph isomorphism and Gaussian boson sampling
• A universal programmable Gaussian Boson Sampler for drug discovery
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum Algorithm for Simulating Molecular Vibrational Excitations
• Hafnians, perfect matchings and Gaussian matrices
• Spoofing cross entropy measure in boson sampling
• Quantum-inspired classical algorithm for molecular vibronic spectra

Cited by in corpus (4)

• Simulating Chemistry on Bosonic Quantum Devices
• Holographic Gaussian Boson Sampling with Matrix Product States on 3D cQED Processors
• Validation of a noisy Gaussian boson sampler via graph theory
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs