Improved constructions of mixed state quantum automata. (English) Zbl 1163.68022

Freivalds, Rūsiņš; Ozols, Māris; Mančinska, Laura

Theor. Comput. Sci. 410, No. 20, 1923-1931 (2009).

Summary: Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished “folk theorem” proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable.
We prove that there is an infinite sequence of distinct integers \(n\), languages \(L_n \), and quantum finite automata with mixed states with \(5n\) states recognizing language \(L_n\) with probability \(\frac 3 4\), while any deterministic finite automaton recognizing \(L_n\) needs at least e\(^{O(n\ln n)}\) states.
Unfortunately, the alphabet for these languages grows with \(n\). In order to prove a similar result for languages in a fixed alphabet we consider a counterpart of Hamming codes for permutations of finite sets, i.e. sets of permutations such that any two distinct permutations in the set have Hamming distance at least \(d\). The difficulty arises from the fact that in the traditional Hamming codes for binary strings, positions in the string are independent while positions in a permutation are not independent. For instance, any two permutations of the same set either coincide or their Hamming distance is at least 2. The main combinatorial problem still remains open.

MSC:

68Q45	Formal languages and automata
68P10	Searching and sorting
81P68	Quantum computation

Keywords:

finite automata; quantum algorithms; permutation groups

References:

[1]	Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum circuits with mixed states, in: Proc. STOC 1998, 1998, pp. 20-30; Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum circuits with mixed states, in: Proc. STOC 1998, 1998, pp. 20-30 · Zbl 1028.68054
[2]	Ambainis, Andris, The complexity of probabilistic versus deterministic finite automata, (Lecture Notes in Computer Science, vol. 1178 (1996), Springer), 233-237 · Zbl 1036.68510
[3]	Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Ķikusts, Arnolds; Mercer, Mark; Thérien, Denis, Algebraic results on quantum automata, Theory Comput. Syst., 39, 1, 165-188 (2006) · Zbl 1101.68029
[4]	Andris Ambainis, Rūsiņš Freivalds, 1-way quantum finite automata: Strengths, weaknesses and generalizations, in: Proc. IEEE FOCS’98, 1998, pp. 332-341; Andris Ambainis, Rūsiņš Freivalds, 1-way quantum finite automata: Strengths, weaknesses and generalizations, in: Proc. IEEE FOCS’98, 1998, pp. 332-341
[5]	Artin, Emil, Beweis des allgemeinen Reziprozitätsgesetzes, Math. Sem. Univ. Hamburg, B.5, 353-363 (1927) · JFM 53.0144.04
[6]	Cameron, Peter, (Permutation Groups. Permutation Groups, London Mathematical Society Student Texts Series (1999), Cambridge University Press) · Zbl 0922.20003
[7]	Peter Cameron, Permutation codes, in: Talk at the International Combinatorics, Geometry and Computer Science Conference, Luminy, 2007; Peter Cameron, Permutation codes, in: Talk at the International Combinatorics, Geometry and Computer Science Conference, Luminy, 2007
[8]	Freivalds, Rūsiņš, Non-constructive methods for finite probabilistic automata, (Lecture Notes in Computer Science, vol. 4588 (2007), Springer), 169-180 · Zbl 1202.68224
[9]	Kempe, Julia; Pyber, Laszlo; Shalev, Aner, Permutation groups, minimal degrees and quantum computing, Groups Geom. Dynam., 1, 4, 553-584 (2007), (See also arXiv:quant-ph/0607204v1) · Zbl 1143.20002
[10]	Attila Kondacs, John Watrous, On the power of quantum finite state automata, in: Proc. IEEE FOCS’97, 1997, pp. 66-75; Attila Kondacs, John Watrous, On the power of quantum finite state automata, in: Proc. IEEE FOCS’97, 1997, pp. 66-75