.png){kind=icon}
.png){kind=icon}
Return
Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling
.png){kind=icon}
OA
AI
DOI：10.1103/PRXQuantum.5.020341.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 non-negative and that computing the output probability of Gaussian boson sampling restricted to a non-negative adjacency matrix is thought to be strictly easier than general cases. 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 quantum-inspired classical sampler.
Keywords:
COMPUTATIONAL ADVANTAGE
LOCAL SEARCH
SUPREMACY
Journal
P
IF:
11
Papers:
919
Citations:
9.0K