Quantum property testing of group solvability

DOI10.1007/978-3-540-78773-0_66zbMATH Open1206.68126arXiv0712.3829OpenAlexW2159110883MaRDI QIDQ627520FDOQ627520

Authors: Yoshifumi Inui, François Le Gall 

Publication date: 2 March 2011

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0712.3829

Recommendations

• The Quantum Complexity of Group Testing
• Efficient testing of groups

zbMATH Keywords

quantum algorithmsolvable groupproperty testing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Finite solvable groups, theory of formations, Schunck classes, Fitting classes, (pi)-length, ranks (20D10)

Cites Work

• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Fast Monte Carlo algorithms for permutation groups
• Title not available (Why is that?)
• Derandomizing homomorphism testing in general groups
• Efficient testing of groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hidden translation and orbit coset in quantum computing
• Solvable black-box group problems are low for PP
• Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups
• Title not available (Why is that?)
• Quantum algorithms for solvable groups
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Mathematical Foundations of Computer Science 2003
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Automata, Languages and Programming

This page was built for publication: Quantum property testing of group solvability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627520)