The quantum query complexity of algebraic properties. (English) Zbl 1135.68438
Csuhaj-Varjú, Erzsébet (ed.) et al., Fundamentals of computation theory. 16th international symposium, FCT 2007, Budapest, Hungary, August 27–30, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74239-5/pbk). Lecture Notes in Computer Science 4639, 250-260 (2007).
Summary: We present quantum query complexity bounds for testing algebraic properties. For a set \(S\) and a binary operation on \(S\), we consider the decision problem whether \(S\) is a semigroup or has an identity element. If \(S\) is a monoid, we want to decide whether \(S\) is a group.
We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by F. Magniez, A. Nayak, J. Roland, and M. Santha [“Search via quantum walk”, in: Proceedings of the 39th ACM symposium on theory of computing, STOC’07, 575–584 (2007)] that improves the previous bounds by Ambainis and by Szegedy. We also present several lower bounds for testing algebraic properties.
For the entire collection see [Zbl 1122.68004].
We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by F. Magniez, A. Nayak, J. Roland, and M. Santha [“Search via quantum walk”, in: Proceedings of the 39th ACM symposium on theory of computing, STOC’07, 575–584 (2007)] that improves the previous bounds by Ambainis and by Szegedy. We also present several lower bounds for testing algebraic properties.
For the entire collection see [Zbl 1122.68004].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 81P68 | Quantum computation |
