Quantum verification of NP problems with single photons and linear optics

Aonan Zhang; Hao Zhan; Junjie Liao; Kaimin Zheng; Tao Jiang; Minghao Mi; Penghui Yao; Lijian Zhang

doi:10.1038/s41377-021-00608-4

Go to Nature Website

Your Location：

Home >

Browse articles >

Quantum verification of NP problems with single photons and linear optics

Articles

- Quantum verification of NP problems with single photons and linear optics
- Light: Science & Applications Vol. 10, Issue 9, Pages: 1750-1760(2021)
- Affiliations：
  
  1.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
  2.Collaborative Innovation Center of Advanced Microstructures, Nanjing University, 210093, Nanjing, China
  3.State Key Laboratory for Novel Software Technology, Nanjing University, 210093, Nanjing, China
- Author bio：
  
  Penghui Yao (pyao@nju.edu.cn)
  Lijian Zhang (lijian.zhang@nju.edu.cn)
- Funds：
- DOI：10.1038/s41377-021-00608-4
  CLC：
- Published：30 September 2021，
  
  Published Online：18 August 2021，
  
  Received：19 January 2021，
  
  Revised：22 July 2021，
  
  Accepted：30 July 2021
- Accepted：
Scan QR Code
Zhang, A. et al. Quantum verification of NP problems with single photons and linear optics. Light: Science & Applications, 10, 1750-1760 (2021).
DOI：

Zhang, A. et al. Quantum verification of NP problems with single photons and linear optics. Light: Science & Applications, 10, 1750-1760 (2021). DOI： 10.1038/s41377-021-00608-4.

摘要

Abstract

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

requires generally the complete solution in an

(

)-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

$$\tilde O(\sqrt n)$$

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.

关键词

Keywords

references

Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM J. Comput.26, 1484–1509 (1997)..

Grover, L. K. A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 1996).

Aaronson, S.&Arkhipov, A. The computational complexity of linear optics. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 2011).

Harrow, A. W.&Montanaro, A. Quantum computational supremacy.Nature549, 203–209 (2017)..

Preskill, J. Quantum computing in the NISQ era and beyond.Quantum2, 79 (2018)..

Arute, F. et al. Quantum supremacy using a programmable superconducting processor.Nature574, 505–510 (2019)..

Zhong, H. S. et al. Quantum computational advantage using photons.Science370, 1460–1463 (2020)..

O'Brien, J. L., Furusawa, A.&Vučković, J. Photonic quantum technologies.Nat. Photon.3, 687–695 (2009)..

Aspuru-Guzik, A.&Walther, P. Photonic quantum simulators.Nat. Phys.8, 285–291 (2012)..

Flamini, F., Spagnolo, N.&Sciarrino, F. Photonic quantum information processing: a review.Rep. Prog. Phys.82, 016001 (2019)..

Broome, M. A. et al. Photonic boson sampling in a tunable circuit.Science339, 794–798 (2013)..

Spring, J. B. et al. Boson sampling on a photonic chip.Science339, 798–801 (2013)..

Tillmann, M. et al. Experimental boson sampling.Nat. Photon.7, 540–544 (2013)..

Crespi, A. et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling.Nat. Photon.7, 545–549 (2013)..

Schreiber, A. et al. A 2D quantum walk simulation of two-particle dynamics.Science336, 55–58 (2012)..

Tang, H. et al. Experimental quantum fast hitting on hexagonal graphs.Nat. Photon.12, 754–758 (2018)..

Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor.Nat. Commun.5, 4213 (2014)..

Santagati, R. et al. Witnessing eigenstates for quantum simulation of hamiltonian spectra.Sci. Adv.4, eaap9646 (2018)..

Kagalwala, K. H. et al. Single-photon three-qubit quantum logic usingspatial light modulators.Nat. Commun.8, 739 (2017)..

Wang, X. L. et al. 18-qubit entanglement with six photons' three degrees of freedom.Phys. Rev. Lett.120, 260502 (2018)..

Reck, M. et al. Experimental realization of any discrete unitary operator.Phys. Rev. Lett.73, 58–61 (1994)..

Carolan, J. et al. Universal linear optics.Science349, 711–716 (2015)..

Clements, W. R. et al. Optimal design for universal multiport interferometers.Optica3, 1460–1465 (2016)..

Saygin, M. Y. et al. Robust architecture for programmableuniversal unitaries.Phys. Rev. Lett.124, 010501 (2020)..

Cook, S. A. The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. (Association for Computing Machinery, 1971).

Malik, S.&Zhang, L. T. Boolean satisfiability from theoretical hardness to practical success.Commun. ACM52, 76–82 (2009)..

Impagliazzo, R.&Paturi, R. On the complexity ofk-SAT.J. Comput. Syst. Sci.62, 367–375 (2001)..

Aaronson, S. et al. The power of unentanglement.Theory Comput.5, 1–42 (2009)..

Blier, H.&Tapp, A. All languages in NP have very short quantum proofs. Proceedings of 2009 Third International Conference on Quantum, Nano and Micro Technologies. (IEEE, 2009).

Chen, J.&Drucker, A. Short multi-prover quantum proofs for SAT without entangled measurements. Preprint athttps://arxiv.org/abs/1011.0716https://arxiv.org/abs/1011.0716(2010).

Chiesa, A.&Forbes, M. A. Improved soundness for QMA with multiple provers.Chic. J. Theor. Computer Sci.19, 1–23 (2013)..

Harrow, A. W.&Montanaro, A. Testing product states, quantum Merlin-Arthur games and tensor optimization.J. ACM60, 3 (2013)..

Brandão, F. G. S. L.&Harrow, A. W. Quantum de finetti theorems under local measurements with applications.Commun. Math. Phys.353, 469–506 (2017)..

Arrazola, J. M., Diamanti, E.&Kerenidis, I. Quantum superiority for verifying NP-complete problems with linear optics.npj Quantum Inf.4, 56 (2018)..

Centrone, F. et al. Experimental demonstration of quantum advantage for NP verification with limited information.Nat. Commun.12, 850 (2021)..

Kitaev, A. Y., Shen, A. H.&Vyalyi, M. N. Classical and Quantum Computation. (American Mathematical Society, 2002).

Watrous, J. Succinct quantum proofs for properties of finite groups. Proceedings 41st Annual Symposium on Foundations of Computer Science. (IEEE, 2000).

Kobayashi, H., Matsumoto, K.&Yamakami, T. Quantum merlin-arthur proof systems: are multiple merlins more helpful to arthur? Proceedings of the 14th International Symposium on Algorithms and Computation. (Springer, 2003).

Garcia-Escartin, J. C.&Chamorro-Posada, P. Swap test and Hong-Ou-Mandel effect are equivalent.Phys. Rev. A87, 052330 (2013)..

Hong, C. K., Ou, Z. Y.&Mandel, L. Measurement of subpicosecond time intervals between two photons by interference.Phys. Rev. Lett.59, 2044–2046 (1987)..

Maslov, D. et al. Quantum advantage for computations with limited space.Nat. Phys.(2021).https://doi.org/10.1038/s41567-021-01271-7https://doi.org/10.1038/s41567-021-01271-7.

Wang, J. W. et al. Integrated photonic quantum technologies.Nat. Photon.14, 273–284 (2020)..

Jain, R. et al. QIP = PSPACE.J. ACM58, 30 (2011)..

Ji, Z. F. et al. MIP*=RE. Preprint athttps://arxiv.org/abs/2001.04383https://arxiv.org/abs/2001.04383(2020).

Barz, S. et al. Demonstration of blind quantum computing.Science335, 303–308 (2012)..

Reichardt, B. W., Unger, F.&Vazirani, U. Classical command of quantum systems.Nature496, 456–460 (2013)..

Barz, S. et al. Experimental verification of quantum computation.Nat. Phys.9, 727–731 (2013)..

Fisher,K. A. G. et al. Quantum computing on encrypted data.Nat. Commun.5, 3074 (2014)..

Liu, Y. K., Christandl, M.&Verstraete, F. Quantum computational complexity of theN-representability problem: QMA complete.Phys. Rev. Lett.98, 110503 (2007)..

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰