Quantum Query Algorithms for Automorphisms of Galois Groups

DOI

10.2991/3ca-13.2013.10How to use a DOI?

Keywords

quantum computin; quantum query algorithms; galois groups; permutations.

Abstract

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.

Copyright

© 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/).

Download article (PDF)

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  -