دورية أكاديمية
أعرض في EDS

Quantum verification of NP problems with single photons and linear optics.

التفاصيل البيبلوغرافية
العنوان: Quantum verification of NP problems with single photons and linear optics.
المؤلفون: Zhang A; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Zhan H; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Liao J; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Zheng K; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Jiang T; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Mi M; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China., Yao P; State Key Laboratory for Novel Software Technology, Nanjing University, 210093, Nanjing, China. pyao@nju.edu.cn., Zhang L; National Laboratory of Solid State Microstructures, Key Laboratory of Intelligent Optical Sensing and Manipulation (Ministry of Education) and College of Engineering and Applied Sciences, Nanjing University, 210093, Nanjing, China. lijian.zhang@nju.edu.cn.; Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China. lijian.zhang@nju.edu.cn.
المصدر: Light, science & applications [Light Sci Appl] 2021 Aug 18; Vol. 10 (1), pp. 169. Date of Electronic Publication: 2021 Aug 18.
نوع المنشور: Journal Article
اللغة: English
بيانات الدورية: Publisher: Springer Nature Country of Publication: England NLM ID: 101610753 Publication Model: Electronic Cited Medium: Internet ISSN: 2047-7538 (Electronic) Linking ISSN: 20477538 NLM ISO Abbreviation: Light Sci Appl Subsets: PubMed not MEDLINE
أسماء مطبوعة: Original Publication: [London] : Springer Nature, [2012]-
مستخلص: Quantum computing is seeking to realize hardware-optimized algorithms for application-related computational tasks. NP (nondeterministic-polynomial-time) is a complexity class containing many important but intractable problems like the satisfiability of potentially conflict constraints (SAT). According to the well-founded exponential time hypothesis, verifying an SAT instance of size n requires generally the complete solution in an O(n)-bit proof. In contrast, quantum verification algorithms, which encode the solution into quantum bits rather than classical bit strings, can perform the verification task with quadratically reduced information about the solution in [Formula: see text] qubits. Here we realize the quantum verification machine of SAT with single photons and linear optics. By using tunable optical setups, we efficiently verify satisfiable and unsatisfiable SAT instances and achieve a clear completeness-soundness gap even in the presence of experimental imperfections. The protocol requires only unentangled photons, linear operations on multiple modes and at most two-photon joint measurements. These features make the protocol suitable for photonic realization and scalable to large problem sizes with the advances in high-dimensional quantum information manipulation and large scale linear-optical systems. Our results open an essentially new route toward quantum advantages and extend the computational capability of optical quantum computing.
(© 2021. The Author(s).)
References: Phys Rev Lett. 2018 Jun 29;120(26):260502. (PMID: 30004724)
Nature. 2019 Oct;574(7779):505-510. (PMID: 31645734)
Science. 2013 Feb 15;339(6121):794-8. (PMID: 23258411)
Nat Commun. 2021 Feb 8;12(1):850. (PMID: 33558480)
Science. 2013 Feb 15;339(6121):798-801. (PMID: 23258407)
Sci Adv. 2018 Jan 26;4(1):eaap9646. (PMID: 29387796)
Science. 2012 Jan 20;335(6066):303-8. (PMID: 22267806)
Phys Rev Lett. 1994 Jul 4;73(1):58-61. (PMID: 10056719)
Nature. 2017 Sep 13;549(7671):203-209. (PMID: 28905912)
Phys Rev Lett. 1987 Nov 2;59(18):2044-2046. (PMID: 10035403)
Phys Rev Lett. 2007 Mar 16;98(11):110503. (PMID: 17501036)
Rep Prog Phys. 2019 Jan;82(1):016001. (PMID: 30421725)
Science. 2015 Aug 14;349(6249):711-6. (PMID: 26160375)
Nat Commun. 2014;5:3074. (PMID: 24445949)
Phys Rev Lett. 2020 Jan 10;124(1):010501. (PMID: 31976709)
Nat Commun. 2017 Sep 29;8(1):739. (PMID: 28963536)
Science. 2012 Apr 6;336(6077):55-8. (PMID: 22403179)
Science. 2020 Dec 18;370(6523):1460-1463. (PMID: 33273064)
Nat Commun. 2014 Jul 23;5:4213. (PMID: 25055053)
Nature. 2013 Apr 25;496(7446):456-60. (PMID: 23619692)
معلومات مُعتمدة: 61972191, 11690032, 61975077 and 91836303 National Natural Science Foundation of China (National Science Foundation of China); 61972191, 11690032, 61975077 and 91836303 National Natural Science Foundation of China (National Science Foundation of China)
تواريخ الأحداث: Date Created: 20210819 Latest Revision: 20210903
رمز التحديث: 20240829
مُعرف محوري في PubMed: PMC8373877
DOI: 10.1038/s41377-021-00608-4
PMID: 34408129
قاعدة البيانات: MEDLINE
الوصف
تدمد:2047-7538
DOI:10.1038/s41377-021-00608-4