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.
Related
- Magic in Grover's Algorithm and the Role of Oracle Synthesis
- An Open-Source Hardware and Software Toolkit to Enable Agentic RHEED-Guided Thin-Film Synthesis
- Harmonic Reduction of Spin-Coupled Grover Walks on Hypercubes via Quantum Bernoulli Noises
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Ancilla-mediated fixed-point quantum search using Grover iterations
BibTeX
@misc{reeves2026cost,
title = {{The Cost of a Real Grover Oracle: Minecraft Seed Search from Software to Quantum Hardware}},
author = {Evan M. Reeves and Elias Sopkin and Thomas A. Searles},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33139},
eprint = {2610.33139},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33139},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Cost of a Real Grover Oracle: Minecraft Seed Search from Software to Quantum Hardware
AU - Evan M. Reeves
AU - Elias Sopkin
AU - Thomas A. Searles
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33139
UR - https://arxiv.org/abs/2610.33139
AB - 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.
ER -