Algorithms · Quantum query algorithm
Testing commutativity of a black-box group
Given a list of k generators for a group G together with black-box access to group multiplication, decide whether G is commutative using as few queries to that black box as possible.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(k^(2/3)) for a black-box group given by k generators, with a lower bound of Ω(k^(2/3)) obtained by reduction from a special case of Element Distinctness; the Zoo records the resulting quantum query complexity as Θ̃(k^(2/3)). The classical baseline is Pak's randomized algorithm involving O(k) group operations, which the same paper states it proves optimal for the randomized model.
- Papers1
Given a list of k generators for a group G together with black-box access to group multiplication, decide whether G is commutative using as few queries to that black box as possible. The paper considers the commutativity of a black-box group specified by its k generators, a problem whose complexity in terms of k was first considered by Pak, whose randomized algorithm involves O(k) group operations. Magniez and Nayak construct a quantum algorithm for this problem whose complexity is in O(k^(2/3)), and the paper states that the algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(k^(2/3)) the paper gives a reduction from a special case of Element Distinctness to the commutativity problem, and it describes its own construction, in the abstract's own wording, as a quite optimal one. The authors also report that along the way they prove the optimality of Pak's algorithm for the randomized model, while the Zoo describes Pak's O(k) algorithm as the best known classical one.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
The paper considers the commutativity of a black-box group specified by its k generators, a problem whose complexity in terms of k was first considered by Pak, whose randomized algorithm involves O(k) group operations. Magniez and Nayak construct a quantum algorithm for this problem whose complexity is in O(k^(2/3)), and the paper states that the algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(k^(2/3)) the paper gives a reduction from a special case of Element Distinctness to the commutativity problem, and it describes its own construction, in the abstract's own wording, as a quite optimal one. The authors also report that along the way they prove the optimality of Pak's algorithm for the randomized model, while the Zoo describes Pak's O(k) algorithm as the best known classical one. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: O(k^(2/3)) for a black-box group given by k generators, with a lower bound of Ω(k^(2/3)) obtained by reduction from a special case of Element Distinctness; the Zoo records the resulting quantum query complexity as Θ̃(k^(2/3)). The classical baseline is Pak's randomized algorithm involving O(k) group operations, which the same paper states it proves optimal for the randomized model..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- O(k^(2/3)) for a black-box group given by k generators, with a lower bound of Ω(k^(2/3)) obtained by reduction from a special case of Element Distinctness; the Zoo records the resulting quantum query complexity as Θ̃(k^(2/3)). The classical baseline is Pak's randomized algorithm involving O(k) group operations, which the same paper states it proves optimal for the randomized model.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:quant-ph/0506265, quoted as it is written there: "We construct a quite optimal quantum algorithm for this problem whose complexity is in O (k^{2/3})", "For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem", and, for the classical side, "who gave a randomized algorithm involving O(k) group operations" together with "we prove the optimality of the algorithm of Pak for the randomized model"; Quantum Algorithm Zoo entry "Group Commutativity" (LaTeX rendered into Unicode): "Magniez and Nayak have shown that the quantum query complexity of this task is Θ̃(k^(2/3))". The Zoo's tilde absorbs logarithmic factors that the abstract's "O (k^{2/3})" does not display.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Testing commutativity of a black-box group
PROBLEM: Given a list of k generators for a group G together with black-box access to group multiplication, decide whether G is commutative using as few queries to that black box as possible.
IDEA: The paper considers the commutativity of a black-box group specified by its k generators, a problem whose complexity in terms of k was first considered by Pak, whose randomized algorithm involves O(k) group operations. Magniez and Nayak construct a quantum algorithm for this problem whose complexity is in O(k^(2/3)), and the paper states that the algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(k^(2/3)) the paper gives a reduction from a special case of Element Distinctness to the commutativity problem, and it describes its own construction, in the abstract's own wording, as a quite optimal one. The authors also report that along the way they prove the optimality of Pak's algorithm for the randomized model, while the Zoo describes Pak's O(k) algorithm as the best known classical one.
REPORTED COST: O(k^(2/3)) for a black-box group given by k generators, with a lower bound of Ω(k^(2/3)) obtained by reduction from a special case of Element Distinctness; the Zoo records the resulting quantum query complexity as Θ̃(k^(2/3)). The classical baseline is Pak's randomized algorithm involving O(k) group operations, which the same paper states it proves optimal for the randomized model.
BASIS: abstract of arXiv:quant-ph/0506265, quoted as it is written there: "We construct a quite optimal quantum algorithm for this problem whose complexity is in O (k^{2/3})", "For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem", and, for the classical side, "who gave a randomized algorithm involving O(k) group operations" together with "we prove the optimality of the algorithm of Pak for the randomized model"; Quantum Algorithm Zoo entry "Group Commutativity" (LaTeX rendered into Unicode): "Magniez and Nayak have shown that the quantum query complexity of this task is Θ̃(k^(2/3))". The Zoo's tilde absorbs logarithmic factors that the abstract's "O (k^{2/3})" does not display.
PRIMARY SOURCE: Frederic Magniez, Ashwin Nayak (2005), Quantum Complexity of Testing Group Commutativity — https://arxiv.org/abs/quant-ph/0506265
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Element distinctness by quantum walk
Algorithms
- Discrete-time quantum walk on a line
Algorithms
- Quantum simulated annealing
Algorithms
References
- Quantum Complexity of Testing Group Commutativity
Frederic Magniez, Ashwin Nayak · 2005
Primary source: it constructs the quantum algorithm whose complexity is in O(k^(2/3)) for a black-box group given by k generators, credits the construction to the quantization method of Szegedy, derives the Ω(k^(2/3)) lower bound by reduction from a special case of Element Distinctness, and reports a proof that Pak's O(k) randomized algorithm is optimal for the randomized model. Consult it for the black-box group model it assumes and for the special case of Element Distinctness the reduction uses.