Algorithms · Quantum query algorithm
Hidden nonlinear structures over finite fields
Given oracle access to a hidden subset over a finite field that is not a lattice, that is, a hidden nonlinear structure, identify that subset.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costNot stated by the sources read
- Papers1
A part this method uses, worked through
This page says Fourier transform
— here is a concrete, runnable instance of it.
QFT then its inverse, on |0101⟩
4 qubits, starting at |0101⟩, applying the QFT then immediately undoing it.
Where it ends up
- 0101100%
The register reads 0101 again, exactly: the QFT and its inverse cancel, the way any unitary and its adjoint do.
Open this part in StudioGiven oracle access to a hidden subset over a finite field that is not a lattice, that is, a hidden nonlinear structure, identify that subset. The Zoo pictures an Abelian group as a lattice, a subgroup as a sublattice and the cosets of that subgroup as the shifts of the sublattice, and records that the Abelian hidden subgroup problem is then normally solved by obtaining a superposition over a random coset of the hidden subgroup and taking the Fourier transform, so as to sample from the dual lattice. Rather than generalizing that picture to non-Abelian groups, Childs, Schulman and Vazirani suggest an alternative generalization, to hidden subsets that are not lattices at all, which the paper calls hidden nonlinear structures over finite fields. The paper gives examples of two such problems that it states can be solved efficiently by a quantum computer but not by a classical computer, and it also gives some positive results on the quantum query complexity of finding hidden nonlinear structures. The Zoo records that, as shown by Childs et al., this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres, and that Decker et al. showed how to efficiently solve some related problems.
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 pictures an Abelian group as a lattice, a subgroup as a sublattice and the cosets of that subgroup as the shifts of the sublattice, and records that the Abelian hidden subgroup problem is then normally solved by obtaining a superposition over a random coset of the hidden subgroup and taking the Fourier transform, so as to sample from the dual lattice. Rather than generalizing that picture to non-Abelian groups, Childs, Schulman and Vazirani suggest an alternative generalization, to hidden subsets that are not lattices at all, which the paper calls hidden nonlinear structures over finite fields. The paper gives examples of two such problems that it states can be solved efficiently by a quantum computer but not by a classical computer, and it also gives some positive results on the quantum query complexity of finding hidden nonlinear structures. The Zoo records that, as shown by Childs et al., this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres, and that Decker et al. showed how to efficiently solve some related problems. 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. The sources read state no complexity bound for this record (Two sources were read and neither states a bound. The Quantum Algorithm Zoo entry "Hidden Nonlinear Structures" says only that "this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres", with no query count and no running time. The abstract of arXiv:0705.2784 likewise quotes no figure: "We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures." Since neither source states an exponent, a constant, a query count or a gate count, the complexity field is left empty rather than filled from elsewhere.).
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
- Not stated by the sources read
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Two sources were read and neither states a bound. The Quantum Algorithm Zoo entry "Hidden Nonlinear Structures" says only that "this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres", with no query count and no running time. The abstract of arXiv:0705.2784 likewise quotes no figure: "We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures." Since neither source states an exponent, a constant, a query count or a gate count, the complexity field is left empty rather than filled from elsewhere.
- 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: Hidden nonlinear structures over finite fields
PROBLEM: Given oracle access to a hidden subset over a finite field that is not a lattice, that is, a hidden nonlinear structure, identify that subset.
IDEA: The Zoo pictures an Abelian group as a lattice, a subgroup as a sublattice and the cosets of that subgroup as the shifts of the sublattice, and records that the Abelian hidden subgroup problem is then normally solved by obtaining a superposition over a random coset of the hidden subgroup and taking the Fourier transform, so as to sample from the dual lattice. Rather than generalizing that picture to non-Abelian groups, Childs, Schulman and Vazirani suggest an alternative generalization, to hidden subsets that are not lattices at all, which the paper calls hidden nonlinear structures over finite fields. The paper gives examples of two such problems that it states can be solved efficiently by a quantum computer but not by a classical computer, and it also gives some positive results on the quantum query complexity of finding hidden nonlinear structures. The Zoo records that, as shown by Childs et al., this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres, and that Decker et al. showed how to efficiently solve some related problems.
REPORTED COST: Not stated by the sources read
BASIS: Two sources were read and neither states a bound. The Quantum Algorithm Zoo entry "Hidden Nonlinear Structures" says only that "this problem is efficiently solvable on quantum computers for certain subsets defined by polynomials, such as spheres", with no query count and no running time. The abstract of arXiv:0705.2784 likewise quotes no figure: "We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures." Since neither source states an exponent, a constant, a query count or a gate count, the complexity field is left empty rather than filled from elsewhere.
PRIMARY SOURCE: Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani (2007), Quantum algorithms for hidden nonlinear structures — https://arxiv.org/abs/0705.2784
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
- Hidden shift problem
Algorithms
- Quantum Fourier Transform
Algorithms
- Discrete logarithm on a quantum computer
Algorithms
- Shor period finding
Algorithms
References
- Quantum algorithms for hidden nonlinear structures
Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani · 2007
Primary source: it proposes finding hidden nonlinear structures over finite fields as an alternative to the nonabelian hidden subgroup problem, gives two such problems it states are solvable efficiently by a quantum computer but not classically, and reports positive results on the quantum query complexity of the task. Consult it for the two example problems and for the query complexity results themselves, since the abstract names neither.