Quantum Property Testing of Group Solvability

Details Quantum Property Testing of Group Solvability Quantum Property Testing of Group Solvability

2007-12-22

arxiv.org/abs/0712.3829v2

Algorithmica 59(1): 35-47 (2011)

Physics

Quantum Physics

11 pages; supersedes arXiv:quant-ph/0610013

Scientific paper

Testing efficiently whether a finite set with a binary operation over it, given as an oracle, is a group is a well-known open problem in the field of property testing. Recently, Friedl, Ivanyos and Santha have made a significant step in the direction of solving this problem by showing that it it possible to test efficiently whether the input is an Abelian group or is far, with respect to some distance, from any Abelian group. In this paper, we make a step further and construct an efficient quantum algorithm that tests whether the input is a solvable group, or is far from any solvable group. More precisely, the number of queries used by our algorithm is polylogarithmic in the size of the set.

Affiliated with

Also associated with

No associations

Rating

Quantum Property Testing of Group Solvability 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 Quantum Property Testing of Group Solvability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Property Testing of Group Solvability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-425783