*(Postet på [[Tanker jeg hadde når jeg våknet i morges]], 12022-06-29)* ![[Pasted image 20250628181309.png]] Når jeg våknet i morges var tankene mine på qPCP, eller "quantum polynomially checkable proofs". Jeg leste om dem i går kveld, og de fulgte meg inn i drømmene mine—jeg husker svært lite av drømmene (annet enn noen dystre landskap), men på ett eller annet vis lå qPCP som et bakteppe hele veien, som noe jeg ønsket å forstå. "The PCP theorem" har blitt hyllet som et av de viktigste og mest overraskende resultatene i teoretisk datavitenskap de siste tiårene. Så vidt jeg forstår det—og jeg er langt fra noen ekspert—kan man vise at hvis man bare er litt smart med hvordan man gjør det, så kan du gi meg et _bevis_ for en hvilken som helst _påstand_, slik at jeg kan _verifisere_ beviset uten å trenge å lese hele. Tvert imot holder det at jeg _sjekker_ det på noen få, tilfeldig valgte punkter. Dersom det jeg ser er konsekvent, kan jeg konkludere at med høy sannsynlighet er beviset korrekt. Vis versa, dersom beviset ikke er korrekt, er det høy sannsynlighet for at jeg ville oppdaget at du prøvde å lure meg.[^1] Den store overraskelsen er hvor _få_ steder man trenger å sjekke for at dette skal funke: uansett hvor stort beviset du gir meg er, holder det å sjekke det samme lille antallet tilfeldig valgte punkter. Og så hører jeg at muligheten for et "kvante-PCP teorem" er et stort åpent spørsmål. Og det fikk meg da til å begynne å undre: Hvordan ville i det hele tatt noe sånt sett ut? Ok, du gir meg et bevis på en påstand, og beviset i seg selv er en kvantestate, altså en rekke med qubits som kan være i superposisjon, og ha sammenfiltring[^2], og alle mulige andre merkelige kvanteeffekter. Problemet er at ved å _observere_ en kvantetilstand, så vil den _kollapse_[^3], så hvis du sjekker beviset på et tilfeldig valgt punkt, vil dette punktet kollapse, sammen med alle qubitsene som var sammenfiltret med qubitsene du leste. Vil dette ødelegge beviset? Eller kan man være smartere med hvordan man sjekker?  En første tanke kan være, hvorfor ikke bare kopiere beviset opp nok ganger? Slik kunne du sjekket hver kopi én gang, og være garantert at når du sjekker neste punkt så er det på et komplett, ukollapset bevis. Så hvorfor funker ikke denne strategien? Riktig: "Ingen-kloning teoremet". Man kan nemlig bevise at det finnes ingen metode for å kopiere, eller "klone", en kvantetilstand. Man kan _flytte_ kvantetilstander, fra én qubit til en annen, og med bruk av sammenfletting til og med _teleportere_ dem, men dette innebærer alltid en ødeleggelse av den opprinnelige tilstanden.  Ok, så det funker ikke. Andre smarte måter vi kan sjekke beviset på? For eksempel finnes det noe som heter "gentle measurement", hvor man kan lese veldig _forsiktig_, og være garantert at tilstanden blir forstyrret bare _litt—_med ulempen at du lærer veldig lite informasjon. Vil dette være nok? Eventuelt, kan du selv bruke en kvantedatamaskin til å sjekke disse punktene? Hvordan ville det blitt gjort, uten at en observasjon av tilstanden på ett eller annet tidspunkt var involvert? Dette er tidspunktet hvor jeg må innrømme at jeg har aldri faktisk _lest_ om kvante-PCP teoremet, så jeg aner ikke om disse tankene treffer kjernen i saken, eller om de er helt på viddene. Men jeg tror aner hvordan dette er et vanskelig problem å løse. For to dager siden ble et teknisk resultat vist, som visstnok var én av de sentrale kampesteinene i veien for et bevis[^4]. Så kanskje vi får et bevis på det fulle teoremet vil følge snart? Det blir i hvert fall spennende å følge med! I mellomtiden skal jeg se denne, så forstår jeg kanskje litt mer om disse kvantepolynomtidssjekkbare bevisene, innen jeg først blir bedt om å verifisere et: [https://www.youtube.com/watch?v=nrRPQ2EP3ms](https://www.youtube.com/watch?v=nrRPQ2EP3ms) [^1]: (I tilfelle noen faktiske eksperter leser dette en dag: tilgi meg om jeg ikke fikk detaljene helt rett, om jeg husker "soundness" og "completeness" litt feil, eller om det bare er påstander i NP/PSPACE/NEEXP som kan bevises: én av reglene mine når jeg skriver her er at jeg skal ikke sjekke andre nettsider—fortrinnsvis ikke lese ett eneste ord!—fra jeg står opp til jeg er ferdig å skrive. Dersom noen undres hvorfor, anbefaler jeg å sjekke ut Dorothea Brandes "Becoming A Writer". Dukker sikkert uansett opp en post om alt det der på ett eller annet tidspunkt her.) [^2]: (Entanglement på norsk! Today I learned.) [^3]: (Eller bli sammenfiltret med én av flere mulige subtilstander i den universelle bølgefunksjonen, og dermed splittet fra den alternative deg som ble sammenfiltret med den andre subtilstanden—dersom man tror Hugh Everett's "mange-verdener fortolkning av kvantefysikk". Og det bør man.) [^4]: (Se: [https://twitter.com/boazbaraktcs/status/1541614829823311872)](https://twitter.com/boazbaraktcs/status/1541614829823311872\))