Magic in Grover's Algorithm and the Role of Oracle Synthesis
Abstract
Grover's algorithm is a textbook example of quantum advantage, providing a quadratic query speedup over classical methods for unstructured search. In this Letter, we characterize the non-stabilizerness, or magic, developed throughout Grover's protocol, quantifying quantum complexity with respect to the efficiently simulable stabilizer states. First, we compute the compilation-independent magic at the end of each Grover iteration, deriving an analytic prediction for the stabilizer Rényi entropy and proving that it remains intensive as the system size grows. We then investigate the magic overhead due to decomposing the circuit into elementary gates. When the solution to the search problem is known, we show that an efficient decomposition exists that keeps magic bounded despite using an extensive number of Toffoli gates. In contrast, agnostic implementations are expected to generate volume-law non-stabilizerness, as we confirm for the 3-SAT problem, which rules out efficient simulation by stabilizer-based methods in practically relevant cases. Our findings clarify the growth of magic in Grover's algorithm and the role of solution-awareness in its circuit compilation.
Related
- The Cost of a Real Grover Oracle: Minecraft Seed Search from Software to Quantum Hardware
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Efficient preparation of spin-squeezed states with Grover's algorithm
- Implementation of Grover’s Search Algorithm for Tectonic Activity Detection in an Unsorted Seismic Database
- Experimental quantum-computing-enhanced sensing using Grover's algorithm
BibTeX
@misc{paviglianiti2026magic,
title = {{Magic in Grover's Algorithm and the Role of Oracle Synthesis}},
author = {Alessio Paviglianiti and Vincenzo Savona},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37772},
eprint = {2610.37772},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37772},
}
RIS
TY - UNPB
TI - Magic in Grover's Algorithm and the Role of Oracle Synthesis
AU - Alessio Paviglianiti
AU - Vincenzo Savona
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37772
UR - https://arxiv.org/abs/2610.37772
AB - Grover's algorithm is a textbook example of quantum advantage, providing a quadratic query speedup over classical methods for unstructured search. In this Letter, we characterize the non-stabilizerness, or magic, developed throughout Grover's protocol, quantifying quantum complexity with respect to the efficiently simulable stabilizer states. First, we compute the compilation-independent magic at the end of each Grover iteration, deriving an analytic prediction for the stabilizer Rényi entropy and proving that it remains intensive as the system size grows. We then investigate the magic overhead due to decomposing the circuit into elementary gates. When the solution to the search problem is known, we show that an efficient decomposition exists that keeps magic bounded despite using an extensive number of Toffoli gates. In contrast, agnostic implementations are expected to generate volume-law non-stabilizerness, as we confirm for the 3-SAT problem, which rules out efficient simulation by stabilizer-based methods in practically relevant cases. Our findings clarify the growth of magic in Grover's algorithm and the role of solution-awareness in its circuit compilation.
ER -