caa a22 4500 445804734 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-009-9338-8 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9338-8 Quantum Property Testing of Group Solvability [Elektronische Daten] [Yoshifumi Inui, François Le Gall] 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 is 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 (Γ,⋅) 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Γ. Springer Science+Business Media, LLC, 2009 Property testing nationallicence Quantum algorithms nationallicence Solvable groups nationallicence Inui Yoshifumi Department of Computer Science, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-0033, Tokyo, Japan aut Le Gall François ERATO-SORST Quantum Computation and Information Project, Japan Science and Technology Agency, 5-28-3 Hongo, Bunkyo-ku, 113-0033, Tokyo, Japan aut Algorithmica Springer-Verlag 59/1(2011-01-01), 35-47 0178-4617 59:1<35 2011 59 453 https://doi.org/10.1007/s00453-009-9338-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9338-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Inui Yoshifumi Department of Computer Science, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113-0033, Tokyo, Japan aut NATIONALLICENCE 700 1- Le Gall François ERATO-SORST Quantum Computation and Information Project, Japan Science and Technology Agency, 5-28-3 Hongo, Bunkyo-ku, 113-0033, Tokyo, Japan aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 35-47 0178-4617 59:1<35 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer