Utrolig spennende resultat fra Robert Huang og gjengen, presentert på Simon's Colloquium [[12024-11-19]]. Kort oppsummert: Der eksisterer unitærer som kan konstrueres i $log(n)$ depth, hvor $n$ er antall qubits, som er indistinguishable fra Haar-random, dvs. unitærer samplet uniformt fra $SU(2^n)$, under LWE antakelsen (og mer generelt antakelsen om at det eksisterer PQ-OWFs?). (Formulert som et orakelproblem hvor man skal skille mellom hvorvidt unitæren er log-depth eller Haar-random, som krever eksponentiell depth å konstruere, litt som å konstruere en tilfeldig funksjon klassisk.) *Men* hvis man har tilgang på den inverse til funksjonen, så blir det lett å adskille igjen! Her er hvordan (Robert refererte til dette som en "butterfly test"): Start med en kjent tilstand, f.eks. all-zeroes, og så bruk $U^\dagger$ til å beregne deg et stykke "bakover i tid". Der bak, flipp én qubit, og så anvend $U$ like mange ganger i "fremover"-retningen igjen. Hvis $U$ er low-depth, så er den bare locally entangling, så effekten av å flippe én bit vil kun ha spredt seg lokalt rundt qubiten som ble flippet; men hvis den var uniform, vil den resulterende tilstanden være nært uniform selv. Resultatet er overraskende, da det er et kjent resultat (og ikke alt for vanskelig å se) at et lower-bound klassisk for pseudotilfeldige funksjoner er $\Omega(n)$ for $n$ bits, og mye av diskusjonen handlet om hvor overraskende resultatet er. Jeongwan Haah kommenterte at man nesten skulle tro det ville gjøre perturbasjonsteori umulig, siden selv små "perturbasjoner" kan fullstendig scramble tilstanden. Heldigvis oppdaget han at med bare noen få restriksjoner (på $U$, eller de sanne tilfeldige funksjonene, eller begge?), som for eksempel at de har en kontinuerlig symmetri (forbi de innebygget i definisjonen av $SU(N)$ antar jeg), så dukker den nedre skranken $\Omega(n)$ opp igjen. Dette er jo stort sett tilfelle i naturen, så vi er good. (Mye av diskusjonen handlet om hvor merkelig det er at nedre skranke er $\Omega(n)$ i $SO(N)$ men $\Omega(log(n))$ i $SU(N)$. De komplekse tallene utgjør hele forskjellen! Spørsmålet ble stilt om hvorvidt det eksisterer noen gruppe som sitter "mellom" disse to på et vis og som kan hjelpe å bygge en bro mellom de to resultatene, og mer generelt hvilke andre gruppestrukturer som ville tillatt en logaritmisk nedre skranke. Spørsmålet ble stilt om hvorvidt dette kunne brukes til å konstruere iO eller andre krypto-primitiver, men problemet er at straks du har tilgang på kretsen, så er det trivielt å konstruere $U^\dagger$, og alt av sikkerhet fordufter. Én av applikasjonene Robert fremhevet var at dette resultatet impliserer at man ikke kan adskille topological order, hvor "trivial order" basically betyr "local entanglement only" (generert av shallow circuits) og "topological order" betyr "long range entanglement" (generert av dypere circuits). Grunnen er nesten selvsagt: Disse unitærene kan "gjemme" en tilstand med trivial order slik at den ser topological ut. Dermed besvarte dette et long-standing og fundamentalt åpent problem! (... Gitt at LWE er vanskelig.) Det var en andre applikasjon også som viste at kvantedatamaskiner kunne lære ... noe, som er (bevisbart! siden dette er orakelproblemer) klassisk vanskelig. Jeg stilte spørsmålet om hvorvidt dette kan brukes til å lage et verifiserbart kvanteoverlegenhetseksperiment. Han fant spørsmålet interessant (etter at én av paneldeltakerne så det i chatten og fremhevet det), tydeligvis noe han ikke hadde tenkt på før. Han sa at dette er mer en "learning task" enn en beregningsoppgave, som er mer det folk pleier å tenke på rundt verifiserbar kvanteoverlegenhet, men at det definitivt er noe som er er verdt å utforske (yay me). Ved nærmere ettertanke forstår jeg skepsisen: For at dette skal funke, må man gi kvantedatamaskinen *kvanteorakeltilgang* til en (pseudo)tilfeldig unitær: Det øyeblikket kvantedatamaskinen har tilgang til kretsen, så har den også tilgang til unitærens invers, og oppgaven blir triviell og ingenting er bevist. I praksis betyr det at man må anvende tilstanden fra én kvantedatamaskin (som man stoler på at er kvantisk) til en annen (som man ønsker å verifisere). Dette er et stykke unna det vi mener med (klassisk!) verifiserbar kvanteoverlegenhet, og er sikkert allerede løst av enklere protokoller. Så den opplagte løsningen fungerer sannsynligvis ikke. Likevel, *kunne* man brukt dette resultatet på et vis til å designe et slikt eksperiment?