Algorithms · Quantum query algorithm
Group order and membership for black-box groups
Given a finite group G presented only through an oracle that takes an ordered pair of element labels and returns the label of their product, compute the order of G from the labels of a set of generators, and decide whether a given bitstring is the label of a group element — in the constructive form of the membership question, exhibiting that element as a product of the generators.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costpolylog(|G|) queries to compute the order and to decide membership when G is solvable, and likewise when G is Abelian, against a classical query cost that the Zoo says cannot be brought down to polylog(|G|) even for Abelian G. Watrous states the solvable case as a polynomial-time quantum algorithm for computing orders of solvable groups, and the abstract names no query count and no parameter that its polynomial time is measured in.
- Papers1
A part this method uses, worked through
This page says quantum algorithms for discrete log
— here is a concrete, runnable instance of it.
Order-finding for 7 mod 15
3 counting qubits, 4 work qubits, finding the order of 7 modulo 15 (the order is 4: 7⁴ mod 15 = 1).
Where it ends up
- 00010006%
- 00010106%
- 00011006%
- 00011106%
- 12 more outcomes75%
The counting register reads 000, 010, 100 or 110, each equally likely, corresponding to the four powers k = 0, 1, 2, 3 of the order r = 4; the work register ends entangled with the counting outcome, holding one of 1, 7, 4 or 13. Repeating this and applying the continued-fractions step of the full algorithm to a nonzero outcome recovers the order r = 4 exactly.
Open this part in StudioGiven a finite group G presented only through an oracle that takes an ordered pair of element labels and returns the label of their product, compute the order of G from the labels of a set of generators, and decide whether a given bitstring is the label of a group element — in the constructive form of the membership question, exhibiting that element as a product of the generators. The Zoo records that for Abelian groups these tasks reduce to the Abelian hidden subgroup problem, which is how Mosca solves them with polylog(|G|) queries. Watrous extends the reach to solvable groups: the paper gives a polynomial-time quantum algorithm for computing orders of solvable groups, and its abstract states that testing membership in a solvable group, testing equality of two subgroups of a given solvable group and testing normality of a subgroup all reduce to that order computation, so each admits a polynomial-time quantum algorithm as well. The abstract describes an important byproduct: the algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which it says yields a natural way to apply existing quantum algorithms to factor groups of solvable groups. The setting throughout is black-box groups, in which, the abstract states, none of these problems can be computed classically in polynomial time.
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 Zoo records that for Abelian groups these tasks reduce to the Abelian hidden subgroup problem, which is how Mosca solves them with polylog(|G|) queries. Watrous extends the reach to solvable groups: the paper gives a polynomial-time quantum algorithm for computing orders of solvable groups, and its abstract states that testing membership in a solvable group, testing equality of two subgroups of a given solvable group and testing normality of a subgroup all reduce to that order computation, so each admits a polynomial-time quantum algorithm as well. The abstract describes an important byproduct: the algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which it says yields a natural way to apply existing quantum algorithms to factor groups of solvable groups. The setting throughout is black-box groups, in which, the abstract states, none of these problems can be computed classically in polynomial time. This record's speedup class, "Superpolynomial", 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: polylog(|G|) queries to compute the order and to decide membership when G is solvable, and likewise when G is Abelian, against a classical query cost that the Zoo says cannot be brought down to polylog(|G|) even for Abelian G. Watrous states the solvable case as a polynomial-time quantum algorithm for computing orders of solvable groups, and the abstract names no query count and no parameter that its polynomial time is measured in..
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)
- Superpolynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- polylog(|G|) queries to compute the order and to decide membership when G is solvable, and likewise when G is Abelian, against a classical query cost that the Zoo says cannot be brought down to polylog(|G|) even for Abelian G. Watrous states the solvable case as a polynomial-time quantum algorithm for computing orders of solvable groups, and the abstract names no query count and no parameter that its polynomial time is measured in.
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Quantum Algorithm Zoo entry "Group Order and Membership", quoted with the entry reference numerals omitted and the spacing inside | G | left as the Zoo prints it: "Classically, these problems cannot be solved using polylog(| G |) queries even if G is Abelian. For Abelian groups, quantum computers can solve these problems using polylog(| G |) queries by reduction to the Abelian hidden subgroup problem, as shown by Mosca", and "quantum computers can solve these problems using polylog(| G |) queries for any solvable group"; abstract of arXiv:quant-ph/0011023: "In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups" together with "Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time." The polylog(|G|) figures are the Zoo entry's; the abstract states neither a query count nor the quantity its polynomial is in.
- 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: Group order and membership for black-box groups
PROBLEM: Given a finite group G presented only through an oracle that takes an ordered pair of element labels and returns the label of their product, compute the order of G from the labels of a set of generators, and decide whether a given bitstring is the label of a group element — in the constructive form of the membership question, exhibiting that element as a product of the generators.
IDEA: The Zoo records that for Abelian groups these tasks reduce to the Abelian hidden subgroup problem, which is how Mosca solves them with polylog(|G|) queries. Watrous extends the reach to solvable groups: the paper gives a polynomial-time quantum algorithm for computing orders of solvable groups, and its abstract states that testing membership in a solvable group, testing equality of two subgroups of a given solvable group and testing normality of a subgroup all reduce to that order computation, so each admits a polynomial-time quantum algorithm as well. The abstract describes an important byproduct: the algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which it says yields a natural way to apply existing quantum algorithms to factor groups of solvable groups. The setting throughout is black-box groups, in which, the abstract states, none of these problems can be computed classically in polynomial time.
REPORTED COST: polylog(|G|) queries to compute the order and to decide membership when G is solvable, and likewise when G is Abelian, against a classical query cost that the Zoo says cannot be brought down to polylog(|G|) even for Abelian G. Watrous states the solvable case as a polynomial-time quantum algorithm for computing orders of solvable groups, and the abstract names no query count and no parameter that its polynomial time is measured in.
BASIS: Quantum Algorithm Zoo entry "Group Order and Membership", quoted with the entry reference numerals omitted and the spacing inside | G | left as the Zoo prints it: "Classically, these problems cannot be solved using polylog(| G |) queries even if G is Abelian. For Abelian groups, quantum computers can solve these problems using polylog(| G |) queries by reduction to the Abelian hidden subgroup problem, as shown by Mosca", and "quantum computers can solve these problems using polylog(| G |) queries for any solvable group"; abstract of arXiv:quant-ph/0011023: "In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups" together with "Our algorithm works in the setting of black-box groups, wherein none of these problems can be computed classically in polynomial time." The polylog(|G|) figures are the Zoo entry's; the abstract states neither a query count nor the quantity its polynomial is in.
PRIMARY SOURCE: John Watrous (2000), Quantum algorithms for solvable groups — https://arxiv.org/abs/quant-ph/0011023
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
- Testing commutativity of a black-box group
Algorithms
- Discrete logarithm on a quantum computer
Algorithms
- Shor period finding
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Quantum algorithms for solvable groups
John Watrous · 2000
Primary source: it gives the polynomial-time quantum algorithm for computing orders of solvable groups that this record rests on, states that membership testing, equality of subgroups and normality of a subgroup reduce to that order computation, works throughout in the black-box group setting where the abstract says none of these problems is classically polynomial-time, and reports the byproduct that the algorithm can produce a pure quantum state uniform over the elements of any chosen subgroup. Consult it for the black-box group model it assumes and for the quantity its polynomial time is measured in, which the abstract does not name.