DC Field | Value | Language |
---|---|---|
dc.contributor.author | Oh, Changhun | ko |
dc.contributor.author | Fefferman, Bill | ko |
dc.contributor.author | Jiang, Liang | ko |
dc.contributor.author | Quesada, Nicolás | ko |
dc.date.accessioned | 2024-05-26T23:00:09Z | - |
dc.date.available | 2024-05-26T23:00:09Z | - |
dc.date.created | 2024-05-27 | - |
dc.date.issued | 2024-05 | - |
dc.identifier.citation | PRX Quantum, v.5, no.2 | - |
dc.identifier.issn | 2691-3399 | - |
dc.identifier.uri | http://hdl.handle.net/10203/319506 | - |
dc.description.abstract | <jats:p>We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>k</a:mi></a:math> 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 <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mi>k</d:mi></d:math> 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.</jats:p> <jats:sec> <jats:title/> <jats:supplementary-material> <jats:permissions> <jats:copyright-statement>Published by the American Physical Society</jats:copyright-statement> <jats:copyright-year>2024</jats:copyright-year> </jats:permissions> </jats:supplementary-material> </jats:sec> | - |
dc.language | English | - |
dc.publisher | American Physical Society (APS) | - |
dc.title | Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.citation.volume | 5 | - |
dc.citation.issue | 2 | - |
dc.citation.publicationname | PRX Quantum | - |
dc.identifier.doi | 10.1103/prxquantum.5.020341 | - |
dc.contributor.localauthor | Oh, Changhun | - |
dc.contributor.nonIdAuthor | Fefferman, Bill | - |
dc.contributor.nonIdAuthor | Jiang, Liang | - |
dc.contributor.nonIdAuthor | Quesada, Nicolás | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.