Original paper: [C:Zhandry19a - How to Record Quantum Queries, and Applications to Quantum Indifferentiability](https://eprint.iacr.org/2018/276) (se Lemma 4/Lemma 23). Zhandry, med Qipeng Liu, anvendte samtidig teknikken til å gi et sikkerhetsbevis for [[Fiat-Shamir]] i [C:LuiZha19](https://eprint.iacr.org/2019/262) (sistnevnte er verdt å lese for deres "New Extraction Technique" og "New Programming Technique"). Man kan si at komprimerte orakler spiller samme rolle for [[Quantum Random Oracle Model]] som lazy sampling (lat ... trekking?) gjør for [[Random Oracle Model]]. Har blitt én av standardteknikkene i [[Quantum Random Oracle Model]], til tross for at den er kjent for å være tung å bruke, og kreve dyp kunnskap i [[Quantum Information Theory]] for å anvende, eller i det hele tatt for å lese beviser som anvender den. Sjekk også ut Joseph's nylige eprint, [Nonadaptive One-Way to Hiding Implies Adaptive Quantum Reprogramming](https://eprint.iacr.org/2024/797), Appendix A, hvor han forklarer hvordan han bruker komprimerte orakler for å få resultatene han ønsker. [EC:HamLiuSin24 - The NISQ Complexity of Collision Finding](https://eprint.iacr.org/2024/360.pdf) introduserer også "hybrid compressed oracles"? Sjekk ut. Historisk har det vist seg vanskelig å overføre teknikken til permutasjoner, men dette ser nylig ut til å ha blitt løst av Majenz et al., se [[Quantum Ideal Cipher Model]]. ### Et modularisert rammeverk Et ønske om å tilgjengeliggjøre teknikken for flere motiverte Serge Fehr og medforfattere i [EC:CFHL21 - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work](https://eprint.iacr.org/2020/1305) til å etablere et modulært rammeverk rundt teknikken som tillater å benytte den til å bevise skranker for kvanteorakler med omtrent utelukkende klassisk argumentasjon. Holder på å lese (anno [[12024-06-07]]). De skriver i introduksjonen: > To start off with, we offer a concise yet mathematically rigorous exposition of the compressed oracle technique. We adopt a more abstract view than other descriptions found in the literature, which allows us to keep the focus on the relevant aspects. Our exposition easily extends to the parallel-query QROM, where in each query-round the considered quantum oracle algorithm may make several queries to the QROM in parallel. This variant of the QROM allows for a more fine-grained query-complexity analysis of quantum oracle algorithms. Denne artikkelen introduserer først og fremst et rammeverk som senker barrieren for bruk av teknikken, som beskrevet over, men den bringer også inn en liten generalisering i form av å skille mellom sekvensielle og parallelle orakelkall, som i noen tilfeller kan lede til tettere skranker. Nøkkelelementet i rammeverket er overgangssannsynligheten, som de skriver $[\neg X \rightarrow X]$, for (den klassiske) sannsynligheten for at et lat-trukket orakel går fra å ikke ha en egenskap $X$ til å ha den egenskapen $X$ etter neste trekk (for eksempel, går fra å ikke ha en kollisjon til å ha en kollisjon). Denne oppgraderes så til kvantevarianten, hvor "lat-trukket" erstattes med hva enn det komprimerte orakelet driver med; det oppgraderte elementet skrives $[\![\neg X \rightarrow X]\!]$. Notasjon for lat-trekking (overfør/kopier til [[Random Oracle Model]]?): - $H$, det tilfeldige orakelet, en tilfeldig funksjon trukket fra mengden av alle funksjoner fra $n$ til $m$. Den mest effektive beskrivelsen er dermed i form av en liste av lengde $2^n$, hvor hvert element er en tilfeldig streng av lengde $m$. - $D$, databasen av lat-trukne elementer, hvor alle elementer initialiseres til $\perp$, men som deretter erstattes av de (tilfeldig) trukne verdiene. Teknisk sett fortsatt en liste av størrelse $2^n$, bare hvor at de fleste elementene i listen er $\perp$. - $(?)$, en kompakt beskrivelse av databasen $D$ i form av en liste av tupler $(x, D(x))$, hvor per definisjon $D(x)=\perp$ for alle elementer $x$ som ikke finnes som første element av en tuppel i listen. ### Uperfekt simulering Å finne verdien til $h(x)$ krever en måling i primærdomenet, mens å oppdatere den komprimerte listen (altså sjekke om $x$ allerede er i listen) krever en måling i Fourierdomenet—og, takket være usikkerhetsprinsippet så kommuterer ikke disse målingene. Likevel viser Zhandry at når simulatoren kun trenger å sjekke hvorvidt $h(x)=y$ for en eller annen $y$, så kan feilen som introduseres av denne ikke-kommuteringen være neglisjerbar (han kaller dette "nesten-kommutering"): Lemma 39 i [C:Zhandry19a, App. E "Quantum Tests"](https://eprint.iacr.org/2018/276) gir en konkret (informasjonsteoretisk, så vidt jeg kan forstå) skranke: > **Definition 7.** Let $U_0, U_1$ be unitaries over the same quantum system. We say that $U_0, U_1$ $\varepsilon$-commute if, for any initial state $\rho$, the images of $\rho$ under $U_0 U_1$ and $U_1 U_0$ are at most $\varepsilon$-far in trace distance. > **Lemma 39.** Consider a quantum system over $n$-bit strings $x$, subsets $S \subseteq \{0, 1\}^n$ of size at most $s$, subsets $T \subseteq \{0, 1\}^n$ of size at most $t$, output registers $b,c \in \{0, 1\}$, and auxiliary information $z$ (of arbitrary size). The following two unitaries $8 \sqrt{st/2^n}$-almost commute: > - $\text{CBT}_C$, where $x$ is the test register, $S$ the set register, $b$ the output register, $(c,z)$ the auxiliary register, and conditional function $C$. > - $\text{FBT}_D$, where $x$ is the test register, $T$ the set register, $c$ the output register, $(b,z)$ the auxiliary register, and conditional function $D$.