Can PCE solve the factorisation problem via optimisation?

Technische Samenvatting: Kan PCE het factorisatieprobleem oplossen via optimalisatie?

Probleemstelling
Integer factorisatie, met name van semiprime getallen ($N = p \cdot q$), is een fundamenteel probleem in de computationele getaltheorie en vormt de basis voor de veiligheid van RSA-cryptografie. Hoewel het Shor-algoritme een polynomiaal-tijd quantumoplossing biedt, ontbreekt het huidige Noisy Intermediate-Scale Quantum (NISQ) hardware aan het aantal qubits en de coherentie die nodig zijn voor praktische implementatie. Alternatieve benaderingen, zoals Variational Quantum Algorithms (VQA's) die factorisatie omzetten in binaire optimalisatieproblemen, kampen met schaalbaarheidsproblemen, waarbij doorgaans een aantal qubits vereist is dat lineair schaalt met het aantal binaire variabelen. Deze lineaire schaling maakt ze onhaalbaar voor grootschalige instanties op de huidige hardware. Het onderzoek onderzoekt of Pauli Correlation Encoding (PCE), een raamwerk dat in staat is om $m$ binaire variabelen te coderen met een polynomiaal aantal qubits ($n \ll m$), kan worden aangepast om het factorisatieprobleem op te lossen via optimalisatie met beperkte middelen.

Methodologie
De studie herformuleert het factorisatieprobleem als een binaire optimalisatietaak en past PCE toe om de qubit-vereisten te verminderen. De methodologie omvat:

1. Coderingstrategieën: Twee verschillende benaderingen werden ontwikkeld om de factorisatiebeperkingen in een kostenfunctie te mappen:
   • Basisbenadering: Codeert direct de binaire representaties van de onbekende factoren $p$ en $q$. De kostenfunctie minimaliseert de gekwadrateerde Hamming-afstand tussen het doelgetal $N$ en het kandidaatproduct $x_p \cdot x_q$, met straffen om triviale oplossingen (bijv. $N \cdot 1$) te vermijden.
   • Difference of Two Squares (DoTS) Benadering: Herformuleert het probleem als het vinden van gehele getallen $a$ en $b$ waarvoor geldt dat $a^2 \equiv b^2 \pmod N$ (met $a \not\equiv \pm b$). De factoren worden teruggewonnen via $\gcd(a-b, N)$ en $\gcd(a+b, N)$. De kostenfunctie combineert een term die de modulaire congruentie afdwingt met een term die de resulterende factorisatie verifieert.
2. Quantumcircuit: Er werd een hardware-efficiënte "brickwork" ansatz toegepast, bestaande uit afwisselende lagen van single-qubit rotaties ($R_X, R_Y, R_Z$) en verstrengelingspoorten ($R_{XX}, R_{YY}, R_{ZZ}$). De PCE-compressieorde $k$ bepaalt de circuitdiepte en het aantal vereiste qubits ($n \approx m/k$).
3. Optimalisatie: De geparametriseerde quantumcircuits werden klassiek gesimuleerd met Qiskit Aer. De optimalisatie werd uitgevoerd met drie gradiëntvrije algoritmen: Differential Evolution (DE), Particle Swarm Optimisation (PSO) en Quantum Delta Particle Swarm Optimisation (QDPSO). De signfunctie werd gebruikt om binaire variabelen te benaderen, waarbij de hyperbolische tangens-relaxatie werd vermeden om oneindige reële waarden te voorkomen.

Belangrijkste bijdragen en resultaten

• Resource-reductie: De studie toont aan dat PCE het aantal vereiste qubits voor factorisatie drastisch kan verminderen. Voor typische RSA-sleutellengtes blijft het vereiste aantal qubits binnen een "betaalbaar" bereik voor huidige of nabije hardware, en voor compressieordes $k > 2$ kan het probleem volledig op klassieke computers worden opgelost via quantumcircuit-emulatie.
• Prestatievergelijking:
  • DoTS vs. Basis: De DoTS-benadering presteerde consequent beter dan de Basis-benadering. De DoTS-kostenfunctie, die de rekenkundige structuur van de verschil-van-kwadraten-relatie vastlegt, leverde hogere succespercentages en een gunstiger optimalisatielandschap op.
  • Optimiser-gevoeligheid: Differential Evolution (DE) bleek de meest robuuste optimizer, waarbij succesvolle factorisaties werden bereikt over verschillende bit-lengtes. Swarm-gebaseerde methoden (PSO, QDPSO) vertoonden aanzienlijk lagere succespercentages, wat suggereert dat het optimalisatielandschap uitdagend is voor deze specifieke algoritmen.
  • Schaalbaarheidslimieten: De methode slaagde erin om semiprimes tot 36 bits te factoriseren met de DoTS-benadering en DE. De succespercentages daalden voor gehele getallen groter dan 25–36 bits, wat wijst op intrinsieke beperkingen in de huidige formuleringen van de kostenfuncties voor grotere instanties.
• Zoakefficiëntie: Analyse van het aantal evaluaties van de objectieve functie toonde aan dat het algoritme niet vertrouwt op brute-force exploratie. Het aantal evaluaties bleef enkele ordes van grootte lager dan de omvang van de combinatorische zoekruimte ($2^n$), wat duidt op een geleid zoekproces.

Betekenis en Claims
Het artikel positioneert dit werk als een voorlopige, verkennende bijdrage in plaats van een definitieve oplossing of een claim van computationeel voordeel ten opzichte van bestaande algoritmen.

• Haalbaarheid: De belangrijkste bevinding is dat PCE-gebaseerde algoritmen een plausibel raamwerk vormen voor het bestuderen van factorisatie als een optimalisatieprobleem met beperkte quantummiddelen. Het biedt een alternatief perspectief op gevestigde methoden zoals VQF en QAOA door het aantal variabelen los te koppelen van het aantal qubits.
• Beperkingen: De auteurs stellen expliciet dat de huidige formuleringen niet succesvol schalen naar cryptografisch relevante getallen (bijv. 2048-bit RSA). Het succes van de methode is sterk afhankelijk van het ontwerp van de klassieke kostenfunctie en de keuze van de optimizer.
• Toekomstige richtingen: De studie suggereert dat toekomstig onderzoek zich moet richten op:
  • Het ontwerpen van meer informatieve kostenfuncties die de rekenkundige structuur van factorisatie beter vastleggen (mogelijk door de integratie van carry-variabelen).
  • Het verkennen van aannames over gebalanceerde factoren (veelvoorkomend in RSA) om het aantal variabelen te verminderen.
  • Het onderzoeken van warm-start strategieën en alternatieve ansatz-architecturen.
  • Het evalueren van prestaties onder realistische ruismodellen.

Concluderend, hoewel de methode de RSA-beveiliging momenteel niet bedreigt, vestigt het een levensvatbaar, efficiënt raamwerk voor het onderzoeken van factorisatie via quantum-geïnspireerde optimalisatie, wat verder onderzoek naar kostenfunctie-ontwerp en algoritmische verfijning rechtvaardigt.