Quantum Search with In-Place Queries
Blake Holman | Purdue University
Quantum query complexity is typically characterized in terms of xor queries (|x, 0⟩ → |x, 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 asymptotically 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.
Location
-
QNC 1201
-
-
Meeting ID: 938 7764 4014
Passcode: 999082
-