Quantum Interactive Oracle Proofs

Das Kapitel vertieft sich in das Quanten-Analogon des PCP-Theorems, das als Quanten-PCP-Vermutung (qPCP) bekannt ist, und seine bedeutenden Implikationen für die Grundlagen der Quantenmechanik. Es stellt quanteninteraktive Orakelnachweise (qIOP) als Lockerung der qPCP-Vermutung vor und präsentiert zwei unterschiedliche Konstruktionen, die auf unterschiedlichen technischen Ansätzen beruhen. Die erste Konstruktion basiert auf Teleportation und der Verwendung eines PCP der Nähe, während das zweite Protokoll einen Multi-Qubit-Test verwendet, um Messungen an den Prüfer und klassische PCP-Techniken zu delegieren. Das Kapitel untersucht auch das Potenzial von QIOPs zur Entwicklung quantenprägnanter Argumente für QMA-Sprachen und diskutiert offene Fragen hinsichtlich der Verbindung zwischen QIOPs und Quanten-PCPs. Darüber hinaus bietet es einen technischen Überblick über verwandte Arbeiten und die Herausforderungen bei der Analyse der Robustheit der Protokolle. Das Kapitel schließt mit einer Diskussion über die möglichen kryptographischen Anwendungen des QIOP-Modells und die Möglichkeit, eine Fiat-Shamir-Transformation anzuwenden, um ein nicht interaktives, prägnantes Quantenargument für QMA zu erhalten.