Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling
PRX Quantum · 23.05.2024 · 5 (2)
DOI: 10.1103/prxquantum.5.020341 ↗Kurz gefasst
Fachartikel in der Zeitschrift PRX Quantum, online erschienen am 23.05.2024. Verfasst von Changhun Oh und 3 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 63 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF, Packard Foundation, Natural Sciences and Engineering Research Council of Canada.
Abstract (Originalsprache)
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. Published by the American Physical Society 2024
Förderung
- NSF
- Packard Foundation
- Natural Sciences and Engineering Research Council of Canada
- ARO MURI
- AFOSR MURI
- DoE Q-NEXT
- NTT Research
- Ministère de l’Économie et de l’Innovation du Quèbec
Zitieren
APA
Oh, C., Fefferman, B., Jiang, L., & Quesada, N. (2024). Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling. PRX Quantum, 5(2). https://doi.org/10.1103/prxquantum.5.020341
Vancouver
Oh C, Fefferman B, Jiang L, Quesada N. Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling. PRX Quantum. 2024;5(2). doi:10.1103/prxquantum.5.020341
BibTeX
@article{Oh2024,
author = {Oh, Changhun and Fefferman, Bill and Jiang, Liang and Quesada, Nicolás},
title = {Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling},
journal = {PRX Quantum},
year = {2024},
volume = {5},
number = {2},
doi = {10.1103/prxquantum.5.020341}
}
EUVIMED