Klassen QMA (k), som introduceras av Kobayashi et al., består av alla språk som kan verifieras med k unentangled quantum proofs. Många av de enklaste frågorna om denna klass har förblivit pinsamt öppna: till exempel, kan vi ge några bevis på att k quantum proofs är mer kraftfulla än en? Kan vi visa någon övre gräns på QMA (k), förutom den triviala NEXP? Är QMA (k) = QMA (2) för k ≥ 2? Kan QMA (k) protokoll förstärkas till exponentiellt små fel? I detta dokument gör vi framsteg i alla ovanstående frågor. • Vi ger ett protokoll genom vilket en kontrollör kan vara övertygad om att en 3SAT formel av storlek n är tillfredsställande, med konstant ljud, med tanke på O ( ε n) unentangled kvant vittnen med O (log n) qubits vardera. Vårt protokoll bygger på Dinurs version av PCP Theorem och är i sig inte relativiserande. • Vi visar att förutsatt att den berömda Additivity Conjecture från kvantinformationsteori, något QMA (2) protokoll kan förstärkas till exponentiellt litet fel, och QMA (k) = QMA (2) för alla k ≥ 2. • Vi ger bevis för att QMA (2) PSPACE, genom att visa att detta skulle följa av "stark förstärkning" av QMA (2) protokoll. • Vi bevisar att det inte finns "perfekta disentanglers" för att simulera flera Merlins med en. 23:e årliga IEEE-konferensen om beräkningskomplexitet 1093-0159/08 $25.00
Däremot visade REF att 3-SAT kan lösas genom ett QMA(k) protokoll med konstant ljudstyrka, på bekostnad av att öka k till O ε n polylog(n).
The Power of Unentanglement
{'venue': '2008 23rd Annual IEEE Conference on Computational Complexity', 'journal': '2008 23rd Annual IEEE Conference on Computational Complexity', 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}