Quantum Query Algorithms for Automorphisms of Galois Groups
Agnis Škuškovniks, Freivalds Rusinš · Advances in intelligent systems research/Advances in Intelligent Systems Research · 2013
In this paper we study quantum query complexity of exactly (with probability 1) deciding the parity of npermutations of numbers (from 0 to n-1).We show that for this non-Boolean problem use of quantum complexity techniques gives quite strong results as it does for other, but Boolean problems.We use Galois Theory to find new problems where quantum query algorithms are more efficient than deterministic ones.