Partial oracles quantum algorithm framework -- Part I: Analysis of in-place operations

Dit artikel introduceert een constructie voor de operator van het 'partial oracles'-quantumzoekalgoritme voor in-place operaties, definieert een nieuwe reciproque transformatie met een kettingregel en demonstreert de toepassing ervan op SHA-256-elementen via de QFrame Python-bibliotheek, hoewel de huidige beperking tot in-place operaties nog geen kwantumvoordeel oplevert.

De kern

De Gouden Sleutel voor de Quantum-Schatzoektocht

Stel je voor dat je in een enorme, donkere berg goud moet zoeken. Je hebt een magische lantaarn (een quantumcomputer) die je kunt gebruiken om te zoeken.

Het oude probleem: De trage lantaarn (Grover's algoritme)

Vroeger hadden we alleen Grover's algoritme. Dit is als een slimme zoektocht, maar het heeft een beperking. Stel je hebt een berg met 1 miljoen goudklompjes. Grover's algoritme moet ongeveer 1.000 keer de berg in om het goud te vinden. Dat is al veel sneller dan een mens die één voor één kijkt, maar voor de grootste berg (zoals het kraken van moderne wachtwoorden) is 1.000 keer nog steeds te langzaam. Het is alsof je een naald in een hooiberg zoekt, maar je mag de hooiberg maar een paar duizend keer doorzoeken.

De nieuwe uitvinding: De "Partiële Orakel" methode

De auteur, Fintan Bolton, heeft een nieuwe manier bedacht om te zoeken. Hij noemt dit de Partial Oracles (Gedeeltelijke Orakels) methode.

In plaats van te vragen: "Is dit het juiste goud?" (wat vaak nee is), vraagt deze nieuwe methode stap voor stap: "Is dit goud in de buurt van het juiste goud?"

De Analogie van de Gids:
Stel je voor dat je in een labyrint loopt.

• Grover's methode: Je loopt blindelijn rond en hoopt dat je de uitgang vindt. Als je op de verkeerde plek bent, loop je terug en probeer je het opnieuw.
• De nieuwe methode: Je hebt een gids die je niet direct naar de uitgang brengt, maar die je wel vertelt: "Je bent nu in de juiste kamer, maar de deur is nog niet open." Dan zegt hij: "Oké, nu ben je in de juiste gang." En dan: "Nu ben je bij de juiste deur."
  Elke stap halveert het aantal mogelijke verkeerde routes. In plaats van 1.000 stappen, heb je misschien maar 20 stappen nodig. Dit is een exponentiële versnelling. Het is alsof je de berg goud niet één voor één doorzoekt, maar de berg in tweeën deelt, dan weer in tweeën, totdat je het goud in je hand hebt.

Het grote geheim: De "Reciprocal Transform" (De Omgekeerde Spiegel)

Het paper introduceert een nieuw wiskundig gereedschap: de Reciprocal Transform.

De Analogie van de Spiegelzaal:
Stel je voor dat je in een kamer staat met spiegels aan alle kanten (dit is de "reciprocal space" of omgekeerde ruimte). Als je een beweging maakt, zie je duizenden reflecties.

• Bij de oude methode (Grover) was het lastig om te weten welke reflectie echt was.
• De Reciprocal Transform is als een magische bril die je opzet. Plotseling zie je dat alle reflecties die niet belangrijk zijn, verdwijnen, en dat alle reflecties die wel belangrijk zijn, samenkomen tot één helder beeld.

De auteur bewijst dat je deze "bril" kunt bouwen voor vrijwel elke wiskundige berekening die je gebruikt in cryptografie (zoals bij SHA-256, het algoritme dat beveiliging voor internet en crypto gebruikt).

Wat betekent dit voor de praktijk?

1. Het is nog niet helemaal klaar: De methode werkt nu alleen voor berekeningen die je "terug kunt draaien" (in-place operations). Denk aan het optellen van getallen of het verschuiven van bits. Het werkt nog niet voor alles (zoals het vermenigvuldigen van grote getallen, wat nodig is voor het kraken van RSA-sleutels). Dat komt in een volgend deel van het onderzoek.
2. Het werkt al voor simpele puzzels: De auteur heeft getoond dat je met deze methode een simpele versie van een wachtwoordpuzzel (een "toy hash") in één keer kunt oplossen, terwijl de oude methode duizenden keren zou moeten proberen.
3. De QFrame bibliotheek: Om dit makkelijker te maken, heeft de auteur een software-tool (een Python-bibliotheek genaamd QFrame) gemaakt. Dit is als een bouwset voor quantum-circuits. Je zegt gewoon: "Ik wil dit getal optellen en dan verschuiven", en de computer bouwt automatisch de complexe quantum-machines die nodig zijn om de "omgekeerde spiegel" te maken.

Conclusie in één zin

Dit paper introduceert een nieuwe, veel krachtigere manier om in quantumcomputers te zoeken die de oude methode (Grover) verslaat door stap voor stap het zoekgebied te halveren, gebruikmakend van een nieuw wiskundig trucje (de Reciprocal Transform) dat de chaos van de quantumwereld ordent tot een helder antwoord.

Kortom: Het is alsof we een nieuwe kaart hebben gevonden voor de quantum-schatzoektocht, die ons van "graven met een lepeltje" naar "graven met een bulldozer" brengt, al moeten we die bulldozer nog wel afstemmen voor de zwaarste rotsen.

Technische samenvatting

Titel: Partial Oracles Quantum Algorithm Framework (Deel I)

Auteur: Fintan Bolton (Bradan Quantum)
Datum: 24 april 2026

---

1. Het Probleem

Bestaande quantumzoekalgoritmen, met name het algoritme van Grover, bieden een kwadratische versnelling ($O(\sqrt{N})$) ten opzichte van klassieke zoekmethoden. Echter, recente studies (zoals die van Hoefler et al. en Stoudenmire & Waintal) tonen aan dat deze kwadratische versnelling in de praktijk vaak onvoldoende is om een echt "quantum advantage" te bereiken binnen redelijke rekentijden, vooral gezien de beperkingen van huidige en nabije toekomstige quantumhardware.

Het Partial Oracles-framework is een onderzoekslijn die is ontwikkeld om deze beperkingen te overwinnen en theoretisch een exponentiële versnelling mogelijk te maken. Het fundamentele probleem dat in dit artikel wordt aangepakt, is het ontbreken van een expliciete methode om de operator te construeren die de zoekiteratie uitvoert voor dit framework.

Specifiek richt dit artikel zich op het geval van in-place operaties (waarbij het resultaat van de orakelfunctie direct uit de index-qubits kan worden gelezen). Het artikel erkent dat dit beperking de huidige versie nog geen quantum advantage biedt, omdat in-place operaties klassiek reversibel zijn. De uitbreiding naar out-of-place operaties (zoals vermenigvuldiging) is voorbehouden aan een toekomstig deel II.

2. Methodologie

Het artikel introduceert een nieuw raamwerk dat het klassieke Grover-algoritme uitbreidt door gebruik te maken van een meerbittige orakelfunctie in plaats van een enkel bit.

• Meerbittige Orakels: In plaats van een functie $f(x) \to \{0, 1\}$ die één bit teruggeeft, gebruikt het framework een bijectieve functie $f(x) : \{0, 1\}^n \to \{0, 1\}^n$. Een oplossing wordt gevonden wanneer alle bits van de output nul zijn ($f_j(x) = 0$ voor alle $j$).
• Iteratieve Strategie: Het algoritme werkt in lagen. In elke stap wordt een subset van indexwaarden gefilterd die voldoen aan een specifieke voorwaarde $f_j(x) = 0$. Dit reduceert de zoekruimte met de helft bij elke iteratie.
• Het Nieuwe Operator-ontwerp: Het grootste obstakel bij het toepassen van Grover's tweede operator (reflectie ten opzichte van de beginstaat) in dit context is dat de staat na de eerste iteratie geen uniforme superpositie meer is, maar een "quasi-willekeurige" verdeling. De auteurs lossen dit op door een nieuwe operator te definiëren die werkt in de reciproque ruimte (na toepassing van de Walsh-Hadamard-transformatie).
• Reciproque Transformatie ($R[f]$): De kern van de methode is de definitie van een nieuwe transformatie, de reciproque transformatie van de orakelfunctie. Deze operator herschikt de basisvectoren (Walsh-functies) in de reciproque ruimte zodanig dat de verticale componenten van de index-staten worden geconcentreerd in de $W_0$-toestand. Dit maakt het mogelijk om de zoekiteratie effectief uit te voeren, zelfs wanneer de staat niet meer uniform is.

3. Belangrijkste Bijdragen

1. Constructie van de Zoekoperator: Het artikel levert de ontbrekende constructie voor de iteratie-operator van het Partial Oracles-algoritme. Deze operator wordt gegeven door:
   $$H^{\otimes n} R^\dagger[f(x)] e^{i \frac{\pi}{2} \kappa_\ell} R[f(x)] H^{\otimes n} e^{i \frac{\pi}{2} f_\ell(x)}$$
   Hierbij is $R[f(x)]$ de reciproque transformatie en $\kappa_\ell$ de corresponderende qubit in de reciproque ruimte.

2. De Kettingregel voor Reciproque Transformaties: De auteurs bewijzen een kettingregel (Chain Rule) voor reciproque transformaties:
   $$R[f(g(x))] = R[f(y)] R[g(x)]$$
   Dit stelt onderzoekers in staat om complexe orakelfuncties op te breken in eenvoudigere, beheersbare stappen, wat essentieel is voor de implementatie van complexe algoritmen zoals hash-functies.

3. Parallelisatie: Het artikel toont aan dat de $n$ sequentiële iteraties (die nodig zijn om $n$ bits te filteren) kunnen worden samengevoegd tot één enkele parallelle iteratie. Dit betekent dat de volledige zoekruimte in één stap kan worden gereduceerd tot de oplossing, wat de theoretische snelheid drastisch verhoogt.

4. Toepassing op SHA-256 Elementen: De auteurs hebben de reciproque transformaties en de bijbehorende quantumcircuits afgeleid voor de fundamentele bouwstenen van het SHA-256 hash-algoritme:

   • Optelling modulo $2^n$ (met gebruik van Carry- en Sum-gates).
   • De Maj(a, b, c) functie (meerderheid).
   • De Ch(a, b, c) functie (keuze).
   • Bit-shift functies (ROTR, SHR).
     Voor elk van deze elementen wordt de specifieke reciproque circuit-constructie getoond.

5. QFrame Python Library: Er wordt een nieuwe bibliotheek, QFrame, geïntroduceerd. Deze bibliotheek automatiseert het genereren van quantumcircuits voor orakels en hun reciproque tegenhangers op basis van Python-code die de klassieke logica beschrijft. Dit vermindert de complexiteit van het handmatig ontwerpen van circuits aanzienlijk.

4. Resultaten

• Simulaties: De auteurs hebben het algoritme gesimuleerd op een klassieke computer (via de Qrisp-simulator) voor twee scenario's:
  1. Een eenvoudige keten van optelling en bit-shift.
  2. Een "toy" hash-algoritme (een vereenvoudigde versie van SHA-256 met 4-bit registers en 20 qubits in totaal).
• Prestaties: In het toy-hash-experiment (zoekruimte $2^{20} \approx 1$ miljoen) vond het Partial Oracles-algoritme de unieke oplossing met 100% waarschijnlijkheid na slechts één iteratie.
• Vergelijking: Een equivalent probleem opgelost met het standaard Grover-algoritme zou $\sqrt{2^{20}} = 1024$ iteraties vereisen. Dit illustreert de theoretische exponentiële versnelling binnen dit specifieke raamwerk.
• Correctheid: De simulaties bevestigden dat de afgeleide circuits voor de reciproque transformaties correct werken en de juiste oplossingen teruggeven voor alle geteste seed-waarden.

5. Betekenis en Toekomstperspectief

Dit artikel is een fundamentele stap in de ontwikkeling van quantumzoekalgoritmen die verder gaan dan de kwadratische limiet van Grover.

• Theoretisch: Het bewijst dat het mogelijk is om een zoekalgoritme te construeren dat in $O(1)$ iteraties (of $O(n)$ in sequentiële vorm) een oplossing vindt in een ruimte van grootte $N$, mits de orakelfunctie voldoet aan de eisen van in-place operaties en bijectiviteit.
• Praktisch: Hoewel de huidige versie beperkt is tot in-place operaties (en dus nog geen quantum advantage toont voor problemen zoals factorisatie of volledige hash-inversie), legt het de basis voor Deel II. De volgende stap is het uitbreiden van de methode naar out-of-place operaties (waarbij hulp-qubits nodig zijn die niet deel uitmaken van de index), wat essentieel is voor complexe wiskundige problemen zoals priemgetalfactorisatie.
• Tooling: De introductie van QFrame maakt het voor onderzoekers en ontwikkelaars mogelijk om complexe quantumcircuits voor reciproque transformaties te genereren zonder deze handmatig te hoeven ontwerpen, wat de toegankelijkheid van dit onderzoeksveld vergroot.

Kortom, dit paper biedt de wiskundige en technische onderbouwing voor een nieuw type quantumzoekalgoritme dat potentieel een doorbraak kan betekenen voor het bereiken van een decisief quantum advantage, mits de beperkingen van in-place operaties in de toekomst worden opgeheven.