Algorithms · Quantum query algorithm
Search with wildcards
Identify a hidden n-bit string x using an oracle that, for a chosen subset S of the n positions and a string y of length |S|, returns one when the substring of x specified by S equals y and zero otherwise.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(√n log n) quantum queries to recover the hidden n-bit string, against the classical lower bound of Ω(n) queries. The Zoo states the problem's quantum query complexity as Θ(√n) and its classical query complexity as Θ(n); the paper's abstract claims only the upper bound and calls its algorithm nearly optimal, so the Zoo's Θ(√n) is the stronger of the two statements and both are recorded rather than reconciled. For combinatorial group testing, the second problem in the same paper, O(k log k) queries against the classical lower bound of Ω(k log(n/k)) queries, where n counts the items in the set and k bounds the special items among them rather than the bits of the hidden string above.
- Papers1
Identify a hidden n-bit string x using an oracle that, for a chosen subset S of the n positions and a string y of length |S|, returns one when the substring of x specified by S equals y and zero otherwise. Each query tests a partial guess: the chosen positions S carry the guessed bits y, the positions left out of S are left unconstrained, and the query is answered yes only when the guess is right on every position it commits to. Ambainis and Montanaro describe an algorithm for recovering x that rests neither on amplitude amplification nor on a quantum walk, but ultimately on the solution to a state discrimination problem; the Zoo names the measurement it uses as the Pretty Good Measurement. The same paper gives a separate and, in its own description, simple quantum algorithm for combinatorial group testing, the task of identifying at most k special items among n when each query asks whether a chosen subset contains any special item.
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 →
Each query tests a partial guess: the chosen positions S carry the guessed bits y, the positions left out of S are left unconstrained, and the query is answered yes only when the guess is right on every position it commits to. Ambainis and Montanaro describe an algorithm for recovering x that rests neither on amplitude amplification nor on a quantum walk, but ultimately on the solution to a state discrimination problem; the Zoo names the measurement it uses as the Pretty Good Measurement. The same paper gives a separate and, in its own description, simple quantum algorithm for combinatorial group testing, the task of identifying at most k special items among n when each query asks whether a chosen subset contains any special item. 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(√n log n) quantum queries to recover the hidden n-bit string, against the classical lower bound of Ω(n) queries. The Zoo states the problem's quantum query complexity as Θ(√n) and its classical query complexity as Θ(n); the paper's abstract claims only the upper bound and calls its algorithm nearly optimal, so the Zoo's Θ(√n) is the stronger of the two statements and both are recorded rather than reconciled. For combinatorial group testing, the second problem in the same paper, O(k log k) queries against the classical lower bound of Ω(k log(n/k)) queries, where n counts the items in the set and k bounds the special items among them rather than the bits of the hidden string above..
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(√n log n) quantum queries to recover the hidden n-bit string, against the classical lower bound of Ω(n) queries. The Zoo states the problem's quantum query complexity as Θ(√n) and its classical query complexity as Θ(n); the paper's abstract claims only the upper bound and calls its algorithm nearly optimal, so the Zoo's Θ(√n) is the stronger of the two statements and both are recorded rather than reconciled. For combinatorial group testing, the second problem in the same paper, O(k log k) queries against the classical lower bound of Ω(k log(n/k)) queries, where n counts the items in the set and k bounds the special items among them rather than the bits of the hidden string above.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:1210.1148: "We give a nearly optimal O(sqrt(n) log n) quantum query algorithm for search with wildcards, beating the classical lower bound of Omega(n) queries", and, for the second problem, "We give a simple quantum algorithm which uses O(k log k) queries to solve this problem, as compared with the classical lower bound of Omega(k log(n/k)) queries". The tight figures are from the Quantum Algorithm Zoo entry "Search with Wildcards" (LaTeX rendered into Unicode, spacing inside the reference bracket normalized): "Classically, this problem has query complexity Θ(n). As shown in [167], the quantum query complexity of this problem is Θ(√n)." The Zoo asserts a tight Θ(√n) where the abstract quoted above states only the upper bound O(sqrt(n) log n); this record carries both and settles neither.
- 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: Search with wildcards
PROBLEM: Identify a hidden n-bit string x using an oracle that, for a chosen subset S of the n positions and a string y of length |S|, returns one when the substring of x specified by S equals y and zero otherwise.
IDEA: Each query tests a partial guess: the chosen positions S carry the guessed bits y, the positions left out of S are left unconstrained, and the query is answered yes only when the guess is right on every position it commits to. Ambainis and Montanaro describe an algorithm for recovering x that rests neither on amplitude amplification nor on a quantum walk, but ultimately on the solution to a state discrimination problem; the Zoo names the measurement it uses as the Pretty Good Measurement. The same paper gives a separate and, in its own description, simple quantum algorithm for combinatorial group testing, the task of identifying at most k special items among n when each query asks whether a chosen subset contains any special item.
REPORTED COST: O(√n log n) quantum queries to recover the hidden n-bit string, against the classical lower bound of Ω(n) queries. The Zoo states the problem's quantum query complexity as Θ(√n) and its classical query complexity as Θ(n); the paper's abstract claims only the upper bound and calls its algorithm nearly optimal, so the Zoo's Θ(√n) is the stronger of the two statements and both are recorded rather than reconciled. For combinatorial group testing, the second problem in the same paper, O(k log k) queries against the classical lower bound of Ω(k log(n/k)) queries, where n counts the items in the set and k bounds the special items among them rather than the bits of the hidden string above.
BASIS: abstract of arXiv:1210.1148: "We give a nearly optimal O(sqrt(n) log n) quantum query algorithm for search with wildcards, beating the classical lower bound of Omega(n) queries", and, for the second problem, "We give a simple quantum algorithm which uses O(k log k) queries to solve this problem, as compared with the classical lower bound of Omega(k log(n/k)) queries". The tight figures are from the Quantum Algorithm Zoo entry "Search with Wildcards" (LaTeX rendered into Unicode, spacing inside the reference bracket normalized): "Classically, this problem has query complexity Θ(n). As shown in [167], the quantum query complexity of this problem is Θ(√n)." The Zoo asserts a tight Θ(√n) where the abstract quoted above states only the upper bound O(sqrt(n) log n); this record carries both and settles neither.
PRIMARY SOURCE: Andris Ambainis, Ashley Montanaro (2012), Quantum algorithms for search with wildcards and combinatorial group testing — https://arxiv.org/abs/1210.1148
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.
Where this sits
This record is named by the layer graph at:
- Search by state discrimination Method
Takes An oracle that accepts a subset of the positions together with a guess for those positions, and answers whether the hidden string agrees with on every position in — as the unitary . No promise on the hidden string is required. Returns The hidden -bit string in full — every stage ends on an oracle answer confirming it, so what is uncertain here is the bill and not the answer — together with the expected number of queries spent on the worst-case input.
Related entries
References
- Quantum algorithms for search with wildcards and combinatorial group testing
Andris Ambainis, Ashley Montanaro · 2012
Primary source and the origin of the upper bounds in the cost claim: the O(√n log n) query algorithm for search with wildcards, described as nearly optimal and as beating the classical lower bound of Ω(n) queries, and the O(k log k) query algorithm for combinatorial group testing against the classical lower bound of Ω(k log(n/k)) queries. The abstract also records what the algorithm is not built from, stating that rather than using amplitude amplification or a quantum walk it is ultimately based on the solution to a state discrimination problem.