Quantum Query Algorithms for Automorphisms of Galois Groups
- 10.2991/3ca-13.2013.10How to use a DOI?
- quantum computin; quantum query algorithms; galois groups; permutations.
In this paper we study quantum query complexity of exactly (with probability 1) deciding the parity of n-permutations 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.
- © 2013, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Agnis Škuškovniks AU - Freivalds Rusinš PY - 2013/04 DA - 2013/04 TI - Quantum Query Algorithms for Automorphisms of Galois Groups BT - Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation PB - Atlantis Press SP - 38 EP - 39 SN - 1951-6851 UR - https://doi.org/10.2991/3ca-13.2013.10 DO - 10.2991/3ca-13.2013.10 ID - Škuškovniks2013/04 ER -