Il costo di un vero oracolo di Grover: ricerca del seed di Minecraft dal software all’hardware quantistico

Abstract degli autori

Presentiamo una stima delle risorse necessarie per valutare come l’aritmetica con costanti note modifichi il costo di un oracolo di Grover per il recupero del seed di Minecraft 1.13.1, un’applicazione della ricerca quantistica alla generazione procedurale dei contenuti. L’oracolo sviluppato qui combina un predicato di posizionamento delle strutture con una trasformazione inversa reversibile del generatore congruenziale lineare, per la ricerca residua a 32 bit. Aritmetica a larghezza ridotta, marcatura di fase, uncomputazione e cicli di Grover completi sono verificati rispetto a un’implementazione Java indipendente, mentre i circuiti a larghezza di produzione sono sottoposti a un audit strutturale. L’aritmetica diretta delle costanti nella base di Fourier riduce la larghezza del predicato di posizionamento da 6n+3 a 4n+3 qubit e la crescita strutturale del conteggio dei gate a due qubit da Theta(n^3) a O(n^2). Nel conteggio con base comune {u, CX} di Qiskit a livello 0, indipendente dal backend, la costruzione rappresentativa per la ricerca residua ripiegata con r non nullo usa 275 qubit del circuito, 48.896 gate CX e una profondità di 4.482, contro i 467 qubit, i 2.038.804 gate CX e la profondità di 186.328 della configurazione di riferimento originale, con registri da registro a registro. Le congiunzioni con posizionamenti multipli evidenziano un compromesso nella ricalcolazione della larghezza, e l’enumerazione esatta individua un plateau nella riduzione dei candidati per il benchmark. Abbiamo eseguito circuiti di posizionamento a larghezza ridotta all’interno di cicli di Grover completi su processori IBM e su Quantinuum H2-1, e mostriamo che la costruzione specializzata produce aumenti maggiori, dopo una singola iterazione, della probabilità degli stati marcati rispetto alla configurazione di riferimento. Questi risultati quantificano i vantaggi in termini di risorse della specializzazione aritmetica e mostrano una notevole sensibilità al routing negli esperimenti hardware IBM a larghezza ridotta. Nel complesso, i risultati quantificano l’effetto della specializzazione dell’aritmetica con costanti note all’interno di un oracolo derivato dalla PCG e mostrano che il suo comportamento sull’hardware compilato dipende fortemente dal routing e dal contesto di esecuzione.