Quantum complexity of testing group commutativity

DOI10.1007/S00453-007-0057-8MaRDI QIDQ2642314zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Frédéric Magniez, Ashwin Nayak

Publication date 20 August 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0506265

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Quantum computation (81P68)

Abstract: 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 O (k^{2/3}). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.

Recommendations

• Automata, Languages and Programming
• The Quantum Complexity of Group Testing
• Testing commutativity of a group and the power of randomization.
• Quantum query complexity of multilinear identity testing
• The Quantum Query Complexity of Algebraic Properties

Cited in

(24)

• A note on the search for k elements via quantum walk
• Quantum algorithm design: techniques and applications
• Quantum walks: a comprehensive review
• Quantum search with variable times
• Efficient quantum circuits for Szegedy quantum walks
• On the hitting times of quantum versus random walks
• Quantum walks can find a marked element on any graph
• Szegedy quantum walks with memory on regular graphs
• Models in quantum computing: a systematic review
• Quantum algorithms for algebraic problems
• Quantum Walk Based Search Algorithms
• Quantum Testers for Hidden Group Properties
• Testing commutativity of a group and the power of randomization.
• Quantum algorithms for a set of group theoretic problems
• Quantum query complexity of multilinear identity testing
• The Quantum Query Complexity of Algebraic Properties
• Quantum Random Walks – New Method for Designing Quantum Algorithms
• The Quantum Complexity of Group Testing
• Automata, Languages and Programming
• Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond
• On the relationship between continuous- and discrete-time quantum walk
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs

This page was built for publication: Quantum complexity of testing group commutativity

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