Quantum-Accelerated Gowers $U_2$ Norm for Bent Boolean Functions

Dit artikel stelt een hybride quantum-klassiek genetisch algoritme voor dat gebruikmaakt van een quantumcircuit om de Gowers $U_2$-norm efficiënt te evalueren als fitnessfunctie voor het construeren van gebogen Boolese functies, waarbij een aanzienlijk complexiteitsvoordeel ten opzichte van klassieke methoden wordt aangetoond door de rekentijd per query te reduceren van exponentieel $\bigO(2^{2n})$ tot polynomiaal $\bigO(n^2)$.

De kern

Stel je voor dat je probeert het meest "chaotische" en onvoorspelbare patroon mogelijk te vinden met een raster van lichtschakelaars (aan/uit). In de wereld van informatica en cryptografie worden deze patronen Booleaanse functies genoemd. Het "perfecte" patroon, bekend als een Bent-functie, is zo chaotisch dat het voor elk eenvoudig raadselspel volledig willekeurig lijkt. Het is het ultieme schild tegen hackers die proberen codes te kraken.

Het vinden van deze perfecte patronen is echter zoals het zoeken naar een specifiek korreltje zand op een strand dat exponentieel groter wordt elke keer dat je een variabele toevoegt. Voor een klein strand kun je het aflopen. Voor een groot strand zou het langer duren dan de leeftijd van het universum.

Dit artikel stelt een nieuwe manier voor om deze patronen te vinden door een klassieke zoekmethode (Genetische Algoritmen) te combineren met een Quantumcomputer. Hieronder volgt de uitleg van hoe ze dit deden, met behulp van eenvoudige analogieën.

1. Het Probleem: De "Fitness"-Bottleneck

In een Genetisch Algoritme (GA) begin je met een willekeurige menigte patronen. Je laat ze "paren" en "muteren" om betere generaties te creëren, waarbij je alleen de besten behoudt. Om te weten welke het "beste" is, heb je een Fitness-score nodig.

Voor Bent-functies is de beste score gebaseerd op iets dat de Gowers U2-norm heet.

• De Klassieke Manier: Om deze score op een normale computer te berekenen, moet je elke mogelijke combinatie van de schakelaars controleren. Naarmate het aantal schakelaars ($n$) groeit, explodeert de benodigde arbeid. Het is alsof je probeert elk korreltje zand op een strand te tellen door ze één voor één op te pakken. Voor een strand met slechts 25 schakelaars wordt de wiskunde onmogelijk, zelfs voor de snelste supercomputers.
• De Claim van het Artikel: De auteurs zeggen dat deze berekening de "bottleneck" is die ons verhindert om deze perfecte patronen te vinden voor grote systemen.

2. De Oplossing: De Quantum "Schijnwerper"

De auteurs bouwden een Quantumschakeling om te fungeren als een supersnelle fitness-checker.

• De Analogie: Stel je voor dat je in een donkere kamer zit met miljoenen schakelaars.
  • De Klassieke Computer is als een persoon met een enkele zaklamp. Ze moeten naar elke schakelaar lopen, deze aan doen, het licht controleren, het opschrijven en naar de volgende gaan. Dit duurt eeuwig.
  • De Quantumcomputer is als een magische zaklamp die, wanneer je hem aanzet, elke schakelaar in de kamer tegelijk verlicht. Het controleert ze niet één voor één; het controleert het hele patroon in één enkele "snapshot" (of "shot").

De Technische Magie:
Het artikel beschrijft een schakeling die 3n qubits (quantumbits) gebruikt. Voor een systeem met 8 schakelaars zijn 24 qubits nodig. Voor een systeem met 30 schakelaars zijn 90 qubits nodig.

• Klassiek Geheugen: Om hetzelfde werk klassiek te doen, zou je een lijst van alle mogelijke combinaties moeten opslaan. Voor 30 schakelaars zou deze lijst zo groot zijn dat hij het RAM-geheugen van elke computer op aarde samen zou vullen.
• Quantum Geheugen: De quantumcomputer verwerkt deze enorme complexiteit met een klein, vast aantal qubits, ongeacht hoe groot het strand wordt.

3. Het Experiment: Testen op Kleine Stranden

De auteurs testten dit hybride systeem (Quantum Fitness-checker + Genetisch Algoritme) op twee maten van "stranden":

• 6 Schakelaars (n=6): Zowel de klassieke als de quantummethode vonden patronen die zeer dicht bij de perfecte "Bent"-score lagen. De quantummethode was iets "ruiziger" (zoals een radio met statische storing) omdat het slechts een beperkt aantal snapshots nam, maar het werkte nog steeds.
• 8 Schakelaars (n=8): Dit is een veel grotere uitdaging.
  • De Klassieke methode draaide 1.000 generaties en vond een patroon met een score van 0,250000. Dit is de exacte theoretisch perfecte score. Het vond een echte Bent-functie.
  • De Quantum methode draaide 250 generaties. Het haalde de perfecte 0,25 niet helemaal, maar volgde hetzelfde pad als de klassieke methode, wat bewijst dat de quantumcalculator accuraat is.

4. Waarom Dit Belangrijk Is (Volgens het Artikel)

Het artikel maakt twee belangrijke punten over waarom dit een groot ding is:

1. De "Magische" Maatstaf (Gowers U2): Ze ontdekten dat het gebruik van de Gowers U2-norm als fitness-score beter is dan oudere methoden. Het biedt een soepelere "heuvel" voor het algoritme om op te klimmen, waardoor het zoeken effectiever wordt geleid naar de perfecte oplossing.
2. Het Kippenpunt: De auteurs berekenden dat voor systemen met meer dan 25 schakelaars, de quantummethode exponentieel sneller en goedkoper wordt dan elke klassieke methode.
   • De Analogie: Tot een bepaalde grootte is het aflopen van het strand (Klassiek) prima. Maar zodra het strand te groot wordt (n > 25), wordt lopen onmogelijk. De Quantum "Schijnwerper" is het enige gereedschap dat nog steeds het hele strand in één keer kan zien.

Samenvatting

Het artikel presenteert een nieuw hulpmiddel: een Quantum Fitness-evaluator die Genetische Algoritmen helpt om de meest veilige, chaotische patronen (Bent-functies) te vinden die worden gebruikt in cryptografie.

• Wat ze deden: Ze bouwden een quantumcircuit dat een complexe wiskundige score (Gowers U2-norm) veel sneller berekent dan een normale computer voor grote problemen.
• Wat ze bewezen: Op een systeem met 8 schakelaars vond hun methode succesvol een wiskundig perfect patroon.
• De Toekomst: Ze voorspellen dat zodra quantumcomputers krachtig genoeg zijn om ongeveer 25 schakelaars te verwerken, deze methode de enige manier zal zijn om deze kritieke beveiligingspatronen te ontwerpen, aangezien klassieke computers simpelweg hun geheugen en tijd zullen opraken.

Opmerking: Het artikel richt zich strikt op het wiskundige ontwerp van deze functies en de rekenkundige versnelling. Het claimt niet om specifieke real-world encryptiecodes te hebben gekraakt of dit toe te passen op medische of klinische gebieden.

Technische samenvatting

1. Probleemstelling

Bent Booleaanse functies zijn extremale objecten in cryptografie en coderingstheorie die nonlineariteit maximaliseren, wat betekent dat ze zo ver mogelijk verwijderd zijn van elke affiene functie. Ze zijn cruciaal voor het weerstaan van lineaire cryptanalyse in blok- en stroomcijfers.

• De Uitdaging: Het construeren van bent-functies voor een groot aantal variabelen ($n$) is computationeel onuitvoerbaar. Bekende constructieve families dekken slechts een tiny fractie van alle mogelijke bent-functies.
• De Bottleneck: Metaheuristische benaderingen (zoals Genetische Algoritmen) worden gebruikt om nieuwe bent-functies te zoeken, maar vereisen dat een "fitnessfunctie" honderdduizenden keren wordt geëvalueerd.
  • De standaard fitness-proxy is gebaseerd op de Walsh-Hadamard-transformatie (WHT).
  • Het klassiek berekenen van de exacte WHT en de bijbehorende metrieken (zoals de Gowers $U_2$-norm) vereist $O(n \cdot 2^n)$ operaties en $O(n \cdot 2^n)$ geheugen.
  • Voor $n \gtrsim 25$ worden de geheugen- en tijdseisen prohibitief (exponentiële overhead), waardoor klassieke exhaustieve of metaheuristische zoekopdrachten onuitvoerbaar worden.

2. Methodologie

De auteurs stellen een Hybride Quantum-Klassiek Genetisch Algoritme (GA)-kader voor. De kerninnovatie is het vervangen van de klassieke fitness-evaluator door een quantumcircuit dat de Gowers $U_2$-norm schat.

A. De Fitness-metriek: Gowers $U_2$-norm

In plaats van de maximale Walsh-coëfficiënt (WH-fitness) te gebruiken, maken de auteurs gebruik van de Gowers $U_2$-norm ($\|f\|_{U_2}^4$).

• Definitie: $\|f\|_{U_2}^4 = 2^{-4n} \sum_{u} W_f(u)^4$.
• Betekenis: Een functie is bent dan en slechts dan als $\|f\|_{U_2}^4 = 2^{-n}$.
• Voordeel: De Gowers-norm aggregeert informatie van alle Walsh-coëfficiënten via een vierde-machtsgewichting, waardoor een gladdere, informatiever fitness-landschap ontstaat met sterkere gradiëntsignalen dan de max-norm (WH-fitness).

B. De Quantum-evaluator (Algoritme 1)

De auteurs ontwerpen een quantumcircuit om $\|f\|_{U_2}^4$ te schatten zonder de WHT expliciet te berekenen.

• Architectuur: Gebruikt $3n$ qubits (drie registers van grootte $n$: $X, A, B$).
• Mechanisme:
  1. Initialiseer registers in uniforme superpositie via Hadamard-poorten.
  2. Pas fase-oracls $U_f$ en CNOT fan-out-operaties toe om het tweede-orde verschil te coderen: $\Delta_{a,b}f(x) = f(x) \oplus f(x \oplus a) \oplus f(x \oplus b) \oplus f(x \oplus a \oplus b)$.
  3. Pas definitieve Hadamard-poorten toe en meet de waarschijnlijkheid om de $|0\rangle^{\otimes 3n}$-toestand waar te nemen.
  4. Deze waarschijnlijkheid komt direct overeen met $\|f\|_{U_2}^4$.
• Complexiteit: Het circuit gebruikt $O(n^2)$ twee-qubit-poorten per query.

C. Het Hybride GA-kader

• Representatie: Waarheidstabellen van grootte $2^n$.
• Proces: Standaard GA-stappen (Selectie, Crossover, Mutatie, Elitisme).
• Fitness-evaluatie:
  • Klassiek: Gebruikt exacte WHT (haalbaar voor kleine $n$).
  • Quantum: Gebruikt het quantumcircuit (gesimuleerd) om de norm te schatten met shot-ruis.

3. Belangrijkste Bijdragen

1. Quantumcircuit-ontwerp: Een nieuw $3n$-qubit-circuit dat de Gowers $U_2$-norm schat met behulp van $O(n^2)$ poorten, waardoor de expliciete constructie van het $2^n$-grote WHT-Array wordt vermeden.
2. Complexiteitstheoretische Scheiding:
   • Klassieke Kosten: $O(n \cdot 2^n)$ tijd en $O(n \cdot 2^n)$ geheugen per evaluatie.
   • Quantum Kosten: $O(n^2 \cdot 2^{4n} / \epsilon^2)$ tijd (door sampling shots) maar slechts $3n$ qubits en $O(n^2)$ poortdiepte.
   • Crossover-punt: De auteurs bewijzen dat voor $n > 25$ de quantumbenadering computationeel goedkoper en geheugenefficiënter wordt dan het klassieke alternatief, met een superpolynoom voordeel in resourceschaling.
3. Superioriteit van het Fitness-landschap: Demonstratie dat de Gowers $U_2$-norm een superieure fitness-criteria is ten opzichte van de Walsh-Hadamard max-norm, wat leidt tot snellere en betrouwbaardere convergentie naar bent-functies.
4. Experimentele Validatie: Succesvolle validatie op $n=6$ en $n=8$ systemen, waarbij de correctheid van de quantum-evaluator tegen klassieke baselines wordt bevestigd.

4. Experimentele Resultaten

Het kader werd getest op een klassieke simulator (PennyLane) met $M=1000$ shots per fitness-evaluatie.

• Geval $n=6$:

  • Theoretische bent-drempel: $\approx 0.3536$.
  • Klassiek GA: Convergeerde naar $0.3536$ (exacte grens) in 250 generaties.
  • Quantum GA: Convergeerde naar $\approx 0.3426$ met hogere variantie door shot-ruis, maar volgde dezelfde traject.

• Geval $n=8$ (Kritiek Resultaat):

  • Theoretische bent-drempel: Exact **$0.25$** ($2^{-8/4}$).
  • Klassiek GA (1000 generaties): Bereikte een beste fitness van exact $0.250000$. Dit bevestigt dat het algoritme een echte 8-variabele bent-functie heeft ontdekt.
  • Quantum GA (250 generaties): Bereikte $\approx 0.2829$. Hoewel nog niet bij de exacte grens door minder generaties en shot-ruis, volgde het het klassieke traject nauwkeurig.
  • Betekenis: Het $n=8$-resultaat bewijst dat de Gowers $U_2$-norm een evolutionaire zoekopdracht kan leiden naar exacte bent-functies, niet alleen naar bijna-bent benaderingen.

5. Betekenis en Toekomstperspectief

• Schalbaarheid: Het artikel stelt vast dat terwijl klassieke methoden tegen een muur lopen bij $n \approx 25$ door geheugenbeperkingen (waarbij gigabytes RAM per individu nodig zijn), de quantumbenadering lineair schaalt in qubit-aantal ($3n$). Voor $n=30$ vereist de quantummethode slechts 90 qubits, ruim binnen de projecteerde capaciteiten van toekomstige fouttolerante quantumcomputers op korte termijn.
• Cryptografische Impact: Dit biedt een haalbare weg om nieuwe, hoogwaardige bent-functies voor grotere $n$ te ontdekken, die essentieel zijn voor het ontwerpen van veiligere cryptografische primitieven.
• Algoritmisch Inzicht: Het werk benadrukt dat "quantumversnelling" in deze context niet alleen gaat over snelheid, maar over haalbaarheid – het mogelijk maken van de evaluatie van fitnessfuncties die fysiek onmogelijk zijn om klassiek te berekenen voor grote $n$.
• Toekomstig Werk: De auteurs plannen om dit uit te breiden naar $n=10\text{--}12$ op fouttolerante backends en hogere-orde Gowers-normen ($U_k$ voor $k>2$) te verkennen voor het zoeken naar "hyper-bent" functies.

Kortom, het artikel presenteert een rigoureuze proof-of-concept dat quantumcomputing de exponentiële geheugenbottleneck kan overwinnen bij het zoeken naar bent Booleaanse functies, met gebruikmaking van de Gowers $U_2$-norm als een superieure fitness-metriek om een hybride genetisch algoritme te sturen.