2026-07-23T03:47:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24050 2025-12-12T14:56:05Z ddc:004 open_access

Quantum Search with In-Place Queries Holman, Blake Ramachandran, Ronak Yirka, Justin Quantum algorithms query complexity quantum complexity theory quantum search Grover’s algorithm permutation inversion Quantum query complexity is typically characterized in terms of xor queries |x,y⟩ ↦ |x,y⊕ f(x)⟩ or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x⟩↦ |f(x)⟩. Some problems are known to require exponentially fewer in-place queries than xor queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with O(√N) xor queries but was conjectured to require Ω(N) in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using O(√N) in-place queries. Our algorithm achieves the same speedup as Grover’s algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer xor queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 xor query and Θ(√N) in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Blake Holman and Ronak Ramachandran and Justin Yirka 2025 Is Part Of LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2025.1 urn:nbn:de:0030-drops-240502 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.1 eng https://creativecommons.org/licenses/by/4.0/legalcode