The Cost of a Real Grover Oracle: Minecraft Seed Search from Software to Quantum Hardware

Abstract

We present the resource estimation of how known-constant arithmetic changes the cost of a Grover oracle for Minecraft 1.13.1 seed recovery, an application of quantum search to procedural content generation. The oracle developed here combines a structure-placement predicate with a reversible inverse transform of the linear congruential generator for the 32-bit residual search. Reduced-width arithmetic, phase marking, uncomputation, and complete Grover loops are verified against an independent Java reference, while production-width circuits are structurally audited. Direct Fourier-basis constant arithmetic reduces the placement-predicate width from 6n+3 to 4n+3 qubits and the structural scaling of the two-qubit gate counts from Theta(n^3) to O(n^2). Under backend-agnostic common-basis Qiskit level-0 {u, CX} accounting, the representative nonzero-r folded residual-search construction uses 275 circuit qubits, 48,896 CX gates, and depth 4,482, versus 467 qubits, 2,038,804 CX gates, and depth 186,328 for the original register-to-register baseline. Multi-placement conjunctions expose a width-recomputation tradeoff, and exact enumeration identifies a plateau in candidate reduction for the benchmark. We executed reduced-width placement circuits within complete Grover loops on IBM processors and Quantinuum H2-1 and show larger one-iteration increases in marked-state probability for the specialized construction than for the baseline. These results quantify the resource benefits of arithmetic specialization and show substantial routing sensitivity in the reduced-width IBM hardware experiments. Together, the results quantify the effect of specializing known-constant arithmetic within a PCG-derived oracle and show that its compiled hardware behavior strongly depends on routing and execution context.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.