Database Reordering for Compact Grover Oracles with ESOP Minimization

Quantum Physics [Submitted on 8 Apr 2026] Database Reordering for Compact Grover Oracles with ESOP Minimization Yusuke Kimura, Yutaka Takita Grover's algorithm searches for data satisfying a desired condition in an unstructured database. This algorithm can search a space of size N in \sqrt{N} queries, thereby achieving a quadratic speedup. However, within the Grover oracle circuit that is repeatedly applied, the quantum state preparation circuit -- which embeds database information into quantum states -- suffers from a large gate count and circuit depth. To address this problem, we propose reducing the quantum state preparation circuit by reordering the database. Specifically, we consider a Quantum Read-Only Memory (QROM), where data are assigned to addresses, and assume that the address assignment of data can be freely permuted. By applying Exclusive Sum-of-Products (ESOP) minimization to the resulting truth table, we reduce the quantum circuit. Although the resulting circuit logic differs from the original, the state preparation remains correct in the sense that every desired datum is encoded at some address. Furthermore, we propose a proxy metric that estimates circuit size without compilation, and combine it with simulated annealing to efficiently find a near-optimal data ordering. In our experiments, an exhaustive search over all orderings for databases of size N=8 reveals that circuit size varies by up to approximately a factor of two depending on the ordering, demonstrating the utility of reordering. Compared with applying ESOP minimization without reordering, simulated annealing reduces the circuit size by approximately 30\% and yields circuits close to optimal. For N=64 and 128, simulated annealing is shown to discover smaller circuits compared with random search. Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2604.06578 [quant-ph]   (or arXiv:2604.06578v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.06578 Focus to learn more Submission history From: Yusuke Kimura [view email] [v1] Wed, 8 Apr 2026 02:02:22 UTC (999 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)