Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Quantum Complexity of Testing Group Commutativity
verfasst von : Frédéric Magniez, Ashwin Nayak
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of testing the commutativity of a black-box group specified by its
k
generators. The complexity (in terms of
k
) of this problem was first considered by Pak, who gave a randomized algorithm involving
O
(
k
) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in Õ(
k
2/3
). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(
k
2/3
), we introduce a new technique of reduction for quantum query complexity. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.