In this section
@article{Zhang:2021:10.1038/s41377-021-00608-4,
author = {Zhang, A and Zhan, H and Liao, J and Zheng, K and Jiang, T and Mi, M and Yao, P and Zhang, L},
doi = {10.1038/s41377-021-00608-4},
journal = {Light: Science & Applications},
title = {Quantum verification of NP problems with single photons and linear optics},
url = {http://dx.doi.org/10.1038/s41377-021-00608-4},
volume = {10},
year = {2021}
}
TY - JOUR
AB - <jats:title>Abstract</jats:title><jats:p>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 <jats:italic>n</jats:italic> requires generally the complete solution in an <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic>)-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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\tilde O(\sqrt n )$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mrow> <mml:mo></mml:mo> </mml:mrow> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msqrt> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math></jats:alternatives></jats:inline-f
AU - Zhang,A
AU - Zhan,H
AU - Liao,J
AU - Zheng,K
AU - Jiang,T
AU - Mi,M
AU - Yao,P
AU - Zhang,L
DO - 10.1038/s41377-021-00608-4
PY - 2021///
TI - Quantum verification of NP problems with single photons and linear optics
T2 - Light: Science & Applications
UR - http://dx.doi.org/10.1038/s41377-021-00608-4
VL - 10
ER -