The Quantum Query Complexity of Algebraic Properties

Details The Quantum Query Complexity of Algebraic Properties The Quantum Query Complexity of Algebraic Properties

2007-05-10

arxiv.org/abs/0705.1446v1

Physics

Quantum Physics

13 pages, 0 figures

Scientific paper

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 Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.

Affiliated with

Also associated with

No associations

Rating

The Quantum Query Complexity of Algebraic Properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Quantum Query Complexity of Algebraic Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Quantum Query Complexity of Algebraic Properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-600716