Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909218756362240 |
|---|---|
| author | Oh, Changhun Fefferman, Bill Jiang, Liang Quesada, Nicolás |
| author_facet | Oh, Changhun Fefferman, Bill Jiang, Liang Quesada, Nicolás |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_00536 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling Oh, Changhun Fefferman, Bill Jiang, Liang Quesada, Nicolás Quantum Physics 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. |
| title | Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2302.00536 |