EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling

Changhun Oh, Bill Fefferman, Liang Jiang, Nicolás Quesada

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →