Quantum interactive proofs and the complexity of entanglement detection
Kevin Milner · eScholarship@McGill (McGill) · 2014
Ce mémoire met en évidence un lien formel entre les problèmes physiques de détection d'intrication et les classes de complexité de l'informatique théorique. Plus particulièrement, nous établissons une correspondance entre la plupart des classes de complexité naturelles issues de preuves interactives quantiques (incluant BQP, QMA, QMA(2), QSZK, et QIP), et une intrication ou un problème de détection de corrélation qui est complet pour cette classe. En ce sens, nous pouvons dire que l'intrication, ou le problème de détection de corrélation, capture la puissance expressive de chaque classe de complexité de preuve interactive quantique et que le contraste entre de tels problèmes donne une idée sur les différences entre les classes de preuves interactives quantiques. Il est démontré que la difficulté de la détection d'intrication varie considérablement du fait que la mesure de distance utilisée soit la distance de trace ou LOCC unidirectionnel. Nous fournissons également l'analyse d'un problème similaire, et montrons que celui-ci est décidable par un système de preuve interactive quantique (de deux messages) tout en étant NP-dur ainsi que QSZK-dur, le premier exemple non trivial d'un tel problème.