⚛️ quantum physics

Quantum Pessiland

Dit artikel stelt het bestaan van "Quantum Pessiland" vast, een theoretische wereld waarin de gemiddelde hardheid van $UP \cap coUP$ samenbestaat met het niet-bestaan van bijna alle kwantumcryptografische primitieven en sampling-gebaseerde kwantumvoordelen, waarmee wordt aangetoond dat niet-relativerende technieken noodzakelijk zijn om bepaalde kwantumprimitieven te construeren vanuit specifieke complexiteitsveronderstellingen.

Oorspronkelijke auteurs: Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

Gepubliceerd 2026-09-01

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Boyang Chen, Tomoyuki Morimae, Takashi Yamakawa

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In het landschap van de moderne informatica bestaat er een fundamentele spanning tussen de moeilijkheid van het oplossen van problemen en de mogelijkheid om geheimen te bewaren. Decennialang hebben wetenschappers verschillende "werelden" van computationele realiteit in kaart gebracht om te begrijpen wat mogelijk is. Een dergelijke wereld, bekend als Pessiland, is een plek waar het oplossen van complexe problemen over het algemeen erg moeilijk is, maar waar de instrumenten die nodig zijn om veilige digitale sloten te bouwen simpelweg niet bestaan. In dit sombere scenario, hoewel de natuur moeilijke puzzels presenteert, is er geen manier om een eenrichtingsfunctie te creëren—een wiskundig proces dat gemakkelijk uit te voeren is, maar onmogelijk om te keren zonder een geheime sleutel. Omdat bijna alle klassieke encryptie steunt op deze eenrichtingsfuncties, is Pessiland een wereld waarin veilige communicatie onmogelijk is, ondanks het bestaan van moeilijke problemen.

De opkomst van quantumcomputing heeft echter een nieuwe laag van complexiteit geïntroduceerd. Quantummechanica staat vreemde gedragingen toe, zoals superpositie, waarbij een systeem zich in meerdere toestanden tegelijk kan bevinden. Onderzoekers vragen zich al lang af of deze vreemde fysica de cryptografie uit de somberheid van Pessiland zou kunnen redden. Zouden quantumcomputers veilige systemen kunnen creëren, zelfs wanneer de klassieke fundamenten ontbreken? Deze vraag leidde wetenschappers tot de vraag of er een quantumversie van deze ellendige wereld bestaat—een plek waar problemen moeilijk blijven, maar zelfs de meest geavanceerde quantumcryptografische instrumenten niet kunnen bestaan.

Een team van onderzoekers heeft nu op deze vraag geantwoord met een definitief "ja". Ze hebben wiskundig een theoretische wereld geconstrueerd die ze Quantum Pessiland noemen. In deze wereld hebben ze bewezen dat er problemen zijn die moeilijk op te lossen zijn op gemiddelde basis, zelfs voor een quantumcomputer uitgerust met extra hints die bekend staan als quantum advice. Toch kunnen in dezezelfde wereld de fundamentele bouwstenen van quantumbeveiliging simpelweg niet worden gebouwd. Specifiek hebben ze aangetoond dat het in deze omgeving onmogelijk is om bepaalde paren quantumtoestanden te creëren die er verschillend uitzien voor het oog maar ononderscheidbaar zijn voor elke efficiënte computer, een vereiste voor veel quantumencryptieschema's. Ze hebben ook aangetoond dat een specifiek type quantumpuzzel, die fungeert als een digitaal slot, niet veilig tegen klassieke aanvallers kan worden gecreëerd.

Om tot deze conclusie te komen, hebben de onderzoekers geen fysieke machine gebouwd of een experiment uitgevoerd in een laboratorium. In plaats daarvan hebben ze een wiskundig model geconstrueerd met behulp van een "oracle", wat in essentie een zwarte doos is die specifieke vragen direct beantwoordt. Ze hebben deze zwarte doos ontworpen om een collectie van willekeurige, gehusselde lijsten te bevatten. In hun model hebben ze aangetoond dat, hoewel een quantumcomputer een enorme hoeveelheid vooraf berekende informatie kan krijgen om problemen op te lossen, het nog steeds zou falen om de beveiliging van deze theoretische puzzels te doorbreken. De kern van hun ontdekking ligt in een nieuw wiskundig hulpmiddel dat ze hebben ontwikkeld, dat ze een "patching lemma" noemen. Dit hulpmiddel stelt hen in staat om aan te tonen dat, zelfs als een aanvaller een beetje weet over het geheime schudden binnen de zwarte doos, hij niet genoeg kan leren om het systeem te breken, omdat de resterende onbekende delen zo uitgestrekt en willekeurig zijn dat elke poging om ze te raden vruchteloos is.

De implicaties van deze bevinding zijn diepgaand voor de toekomst van quantumbeveiliging. De onderzoekers hebben bewezen dat in hun geconstrueerde wereld niet alleen veilige quantumsloten falen, maar dat zelfs het vermogen van quantumcomputers om klassieke computers te overtreffen bij het genereren van willekeurige patronen verdwijnt. In dit Quantum Pessiland bieden quantumcomputers geen voordeel ten opzichte van klassieke computers wanneer het gaat om het bemonsteren van willekeurige gegevens. Dit suggereert dat het bestaan van veilige quantumcryptografie niet gegarandeerd is door enkel de moeilijkheid van wiskundige problemen. Het impliceert dat als we een toekomst willen met onkraakbare quantumencryptie, we niet uitsluitend kunnen vertrouwen op de aanname dat sommige problemen moeilijk op te lossen zijn; we moeten wellicht een andere, meer specifieke fundering voor beveiliging vinden die niet verdwijnt in dit sombere theoretische landschap.

De studie behandelt ook een langlopende open vraag in het vakgebied met betrekking tot de relatie tussen de moeilijkheid van het oplossen van problemen en het vermogen om quantumvoordelen te creëren. Door aan te tonen dat er een wereld kan bestaan waarin problemen moeilijk zijn maar geen quantumvoordeel mogelijk is, hebben de onderzoekers aangetoond dat het bewijzen van het bestaan van veilige quantumsystemen technieken vereist die verder gaan dan standaard wiskundige modellen. Hun werk dient als een waarschuwing: alleen omdat een probleem moeilijk is, betekent dat niet automatisch dat we een veilig systeem kunnen bouwen om het te beschermen. Het pad naar een veilige quantumtoekomst is complexer dan simpelweg hopen dat de wiskunde moeilijk genoeg is om hackers te stoppen.

Technische Samenvatting: Quantum Pessiland

1. Probleemstelling en Motivatie

Het artikel behandelt het bestaan van een "Quantum Pessiland", een theoretische wereld die analoog is aan het klassieke "Pessiland" gedefinieerd door Impagliazzo [Imp95]. In klassiek Pessiland zijn problemen in NP gemiddeld moeilijk, maar bestaan One-Way Functions (OWFs) niet. Aangezien bijna alle klassieke cryptografische primitieven OWFs impliceren [IL89], vertegenwoordigt Pessiland een wereld waarin essentieel geen klassieke cryptografie mogelijk is, ondanks het bestaan van gemiddelde-geval harde problemen.

In de quantumwereld is het landschap anders. Recente werken [Kre21, MY22, AQY22] hebben aangetoond dat quantumcryptografie (bijv. private-key quantum geld, secret-key encryptie, digitale handtekeningen) kan bestaan zelfs in de afwezigheid van OWFs, door te vertrouwen op zwakkere primitieven zoals Pseudorandom State Generators (PRSGs), One-Way State Generators (OWSGs), One-Way Puzzles (OWPuzzs), en EFI-paren (Extremely Far but Indistinguishable pairs).

De centrale vraag die wordt gesteld is: Bestaat er een wereld waarin NP (of een relevante deelklasse) gemiddeld moeilijk is, maar zelfs deze zwakkere quantumcryptografische primitieven niet bestaan? Als een dergelijke wereld bestaat, zou dit impliceren dat quantumcryptografie niet louter een versoepeling is van klassieke cryptografie, maar fundamenteel andere hardheidsaannames vereist, of dat quantumcryptografie wellicht onmogelijk is in bepaalde gemiddelde-geval harde settings.

2. Methodologie en Technische Overzicht

De auteurs construeren een relatieve wereld (een oracle-separatie) om het bestaan van Quantum Pessiland aan te tonen. Hun benadering past de klassieke constructie van Pessiland aan en breidt deze uit, die gebruik maakte van een random permutatie-oracle en een PSPACE-oracle door Wee [Wee06].

2.1 De Oracle Constructie

De auteurs definiëren oracles waaraan hun resultaten standhouden:

Klassiek Oracle ( $O$ ): Bestaat uit een verificatie-oracle $V^\pi$ $V^{π}$ voor een familie van uniform willekeurige permutaties $\pi = (\pi_1, \pi_2, \dots)$ $π = (π_{1}, π_{2}, \dots)$ en een vaste PSPACE-complete oracle ( $QBF$ $QB F$ ).
- $V^\pi(\ell, u, v) = 1$ als $|u|=|v|=\ell$ en $\pi_\ell(u)=v$ , anders $0$.
Quantum Oracle ( $U$ ): Voor het EFI-paar resultaat introduceren ze een Helstrom oracle (een unitaire oracle) die optimale metingen uitvoert om onderscheid te maken tussen quantumtoestanden gegenereerd door circuits, naast de klassieke oracle $V$ .

2.2 De Kernuitdaging: Auxiliary Inputs

Een aanzienlijke technische hindernis is het uitsluiten van auxiliary-input primitieven. In de klassieke setting sloot Wee [Wee06] auxiliary-input OWFs uit door te laten zien dat elke polynoom-grootte circuit benaderd kon worden door een oracle-vrije circuit als de oracle-waarden op een kleine set "zware" queries hardcoded waren. Echter, deze techniek faalt in de quantumsetting om twee redenen:

Superpositie Queries: Quantumalgoritmen bevragen oracles in superpositie, waardoor het klassieke begrip van "zware queries" (gebaseerd op het fractie van klassieke inputs) niet goed gedefinieerd is.
Uniformiteit vs. Niet-uniformiteit: Auxiliary-input quantumprimitieven worden gedefinieerd tegen uniforme tegenstanders die een oneindige set harde auxiliary inputs ontvangen. Een niet-uniforme "hardwiring" strategie (advice) is onvoldoende; de tegenstander moet verslagen worden door een uniform algoritme dat de noodzakelijke informatie leert.

2.3 De Patching Lemma (Belangrijke Technische Innovatie)

Om deze obstakels te overwinnen, introduceren de auteurs de Patching Lemma (Theorem 5.2). Deze lemma biedt een uniforme Quantum Polynomial-Time (QPT) extractor $E$ die, gegeven een auxiliary input $x$ , een "patch" $\Gamma$ leert (een eindige set triples $(\ell, u, v)$ waar $V^\pi(\ell, u, v)=1$ ).

Mechanisme: De extractor draait het algoritme van de tegenstander $A$ tot een willekeurige query, meet de query-register, en controleert klassiek de oracle $V^\pi$ . Als de query een "positieve" is (d.w.z. $V^\pi=1$ ), wordt deze toegevoegd aan de patch.
Exponentiële Momenten-grens: Het cruciale inzicht is dat hoewel een eenvoudige union bound over alle $2^n$ auxiliary inputs zou falen, het aantal "ontdekkingen" (het toevoegen van elementen aan de patch) een distributie volgt waarbij de waarschijnlijkheid om veel ontdekkingen te doen exponentieel klein is. Door de exponentiële momenten van het aantal ontdekkingen te begrenzen, tonen de auteurs aan dat het verwachte aantal ontdekkingen lineair is in de inputlengte ( $O(n)$ ), zelfs voor de worst-case input. Dit maakt de patch van polynomiale grootte terwijl de ononderscheidbaarheid voor alle inputs simultaan behouden blijft met waarschijnlijkheid één over de keuze van de random permutatie $\pi$ .

2.4 Hardheidsproeven

Gemiddelde-geval Hardheid: Ze maken gebruik van recente strakke grenzen op quantum permutatie inversie met quantum advice [ABC+26], gecombineerd met de Goldreich-Levin stelling [KT24, AC02], om te laten zien dat het inverteren van de permutatie (of het oplossen van de bijbehorend zoekprobleem) hard blijft, zelfs voor QPT algoritmen met quantum advice.
Niet-bestaan van Primitieven: Met behulp van de Patching Lemma tonen ze aan dat elke kandidaat auxiliary-input OWPuzz of EFI paar "gepatched" kan worden naar een oracle-vrije versie (of een versie die enkel de PSPACE/Helstrom oracle gebruikt). Aangezien de PSPACE/Helstrom oracles efficiënte inversie of onderscheid mogelijk maken, worden de oorspronkelijke primitieven gebroken.

3. Belangrijkste Resultaten

Het artikel stelt twee hoofdtheorema's vast met betrekking tot het bestaan van Quantum Pessiland:

Theorem 1.1 (Klassiek Oracle)

Er bestaat een klassiek oracle $O$ waartoe:

Hardheid: Er is een taal $L_O \in UP^O \cap coUP^O$ die sterk hard is op gemiddelde tegen QPT algoritmen met polynomiale-grootte oracle-afhankelijke quantum advice. (Consequentelijk is $NP \cap coNP$ ook hard).
Zoek-hardheid: Er is een totale unieke zoekrelatie $R_O \in TFUP^O$ die hard is op gemiddelde tegen dezelfde klasse van algoritmen.
Geen Quantum Voordeel: $SampBQP^O = SampBPP^O$ . Er is dus geen sampling-gebaseerd quantum voordeel.
Geen Cryptografie: Klassiek beveiligde auxiliary-input One-Way Puzzles (OWPuzzs) bestaan niet.

Theorem 1.2 (Quantum Oracle)

Er bestaat een quantum unitaire oracle $U$ en een klassiek oracle $V$ waartoe:

Hardheid: $L_V \in UP^V \cap coUP^V$ en een relatie $R_V \in TFUP^V$ zijn hard op gemiddelde tegen QPT algoritmen met quantum advice.
Geen Cryptografie: Auxiliary-input EFI paren bestaan niet.

Corollaria

Corollary 1.3: Relatief aan de klassieke oracle is $PP$ sterk hard op gemiddelde tegen QPT met quantum advice, terwijl OWPuzzs niet bestaan. Dit impliceert dat $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ .
Corollary 1.4: Relatief aan de klassieke oracle bestaan Inefficient-Verifier Proofs of Quantumness (IV-PoQ) niet, ondanks de gemiddelde-geval hardheid van $UP \cap coUP$ .

4. Betekenis en Implicaties

Het artikel claimt de volgende betekenis:

Bestaan van Quantum Pessiland: Het bewijst dat er een wereld is waar gemiddelde-geval hardheid bestaat (specifiek voor $UP \cap coNP$ ) maar geen quantumcryptografie (noch klassiek beveiligde, noch quantum-beveiligde varianten van OWPuzzs en EFI pairs) mogelijk is. Dit contrasteert met de klassieke situatie waar het niet-bestaan van OWFs de niet-existentie van alle klassieke cryptografie impliceert, maar hier wordt getoond dat de niet-existentie van quantumprimitieven zelfs geldt wanneer $UP \cap coUP$ hard is.
Limieten van Quantum Voordeel: Het resultaat $SampBQP = SampBPP$ in deze wereld geeft aan dat de gemiddelde-geval hardheid van $UP \cap coUP$ alleen onvoldoende is om een sampling-gebaseerd quantum voordeel te garanderen.
Scheiding van Technieken: Het artikel adresseert een open probleem over de constructie van OWPuzzs vanuit $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ . Aangezien OWPuzzs niet bestaan in hun oracle wereld ondanks dat deze scheiding standhoudt, concluderen de auteurs dat niet-relativerende bewijstechnieken noodzakelijk zijn om OWPuzzs uitsluitend vanuit deze complexiteitstheoretische aanname te construeren. Dit geeft een gedeeltelijk negatief antwoord op het openstaande probleem van Khurana en Tomer [KT25].
Technische Vooruitgang: De Patching Lemma wordt gepresenteerd als een uniforme, quantum analogue van de approximation lemma van Wee, specifiek ontworpen om uniforme tegenstanders met auxiliary inputs te behandelen in aanwezigheid van superpositie queries.

De auteurs nemen een bescheiden houding aan door te merken dat hun resultaten relatief aan oracles zijn en niet de vraag oplossen of een dergelijke wereld bestaat in de niet-relatieve (echte) wereld. Ze benadrukken dat hun werk de scheiding verheldert tussen gemiddelde-geval hardheid en het bestaan van quantum cryptografische primitieven in de relatieve setting.