• Featured in Physics
  • Editors' Suggestion

Solving Graph Problems Using Gaussian Boson Sampling

Yu-Hao Deng, Si-Qiu Gong, Yi-Chao Gu, Zhi-Jiong Zhang, Hua-Liang Liu, Hao Su, Hao-Yang Tang, Jia-Min Xu, Meng-Hao Jia, Ming-Cheng Chen, Han-Sen Zhong, Hui Wang, Jiarong Yan, Yi Hu, Jia Huang, Wei-Jun Zhang, Hao Li, Xiao Jiang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan
Phys. Rev. Lett. 130, 190601 – Published 9 May 2023
Physics logo See synopsis: Large Photonic Processor Solves Graph Problems
PDFHTMLExport Citation

Abstract

Gaussian boson sampling (GBS) is not only a feasible protocol for demonstrating quantum computational advantage, but also mathematically associated with certain graph-related and quantum chemistry problems. In particular, it is proposed that the generated samples from the GBS could be harnessed to enhance the classical stochastic algorithms in searching some graph features. Here, we use Jiǔzhāng, a noisy intermediate-scale quantum computer, to solve graph problems. The samples are generated from a 144-mode fully connected photonic processor, with photon click up to 80 in the quantum computational advantage regime. We investigate the open question of whether the GBS enhancement over the classical stochastic algorithms persists—and how it scales—with an increasing system size on noisy quantum devices in the computationally interesting regime. We experimentally observe the presence of GBS enhancement with a large photon-click number and a robustness of the enhancement under certain noise. Our work is a step toward testing real-world problems using the existing noisy intermediate-scale quantum computers and hopes to stimulate the development of more efficient classical and quantum-inspired algorithms.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 27 December 2022
  • Revised 15 March 2023
  • Accepted 30 March 2023

DOI:https://doi.org/10.1103/PhysRevLett.130.190601

© 2023 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & TechnologyAtomic, Molecular & Optical

synopsis

Key Image

Large Photonic Processor Solves Graph Problems

Published 9 May 2023

A quantum photonic device can perform some real-world tasks more efficiently than classical computers.

See more in Physics

Authors & Affiliations

Yu-Hao Deng1,2,3,*, Si-Qiu Gong1,2,3,*, Yi-Chao Gu1,2,3,*, Zhi-Jiong Zhang1,2,3, Hua-Liang Liu1,2,3, Hao Su1,2,3, Hao-Yang Tang1,2,3, Jia-Min Xu1,2,3, Meng-Hao Jia1,2,3, Ming-Cheng Chen1,2,3, Han-Sen Zhong1,2,3, Hui Wang1,2,3, Jiarong Yan1,2,3, Yi Hu1,2,3, Jia Huang4, Wei-Jun Zhang4, Hao Li4, Xiao Jiang1,2,3, Lixing You4, Zhen Wang4, Li Li1,2,3, Nai-Le Liu1,2,3, Chao-Yang Lu1,2,3,5, and Jian-Wei Pan1,2,3

  • 1Hefei National Research Center for Physical Sciences at the Microscale and School of Physical Sciences, University of Science and Technology of China, Hefei 230026, China
  • 2CAS Centre for Excellence and Synergetic Innovation Centre in Quantum Information and Quantum Physics, University of Science and Technology of China, Shanghai 201315, China
  • 3Hefei National Laboratory, University of Science and Technology of China, Hefei 230088, China
  • 4State Key Laboratory of Functional Materials for Informatics, Shanghai Institute of Micro system and Information Technology (SIMIT), Chinese Academy of Sciences, 865 Changning Road, Shanghai 200050, China
  • 5New Cornerstone Science Laboratory, Shenzhen 518054, China

  • *These authors contributed equally to this work.

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 130, Iss. 19 — 12 May 2023

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×