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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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. 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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
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 →
How it works
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..
Implementation
Unsupported
group-order-and-membership.txt
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 withpolylog(|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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Quantum algorithms for solvable groups2000 · John Watrous
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.