Algorithms · Quantum query algorithm
Hidden shift problem
Given oracle access to a function f on the integers mod N together with the promise that f(x) = g(x+s) for a known function g and an unknown shift s, recover s.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Hidden shift for a bent function
4 qubits, f(x) = x₀x₁ ⊕ x₂x₃ (a bent, self-dual function), hidden shift s = 0110.
Step 1 of 11 · Hadamard layer(4)
Probability of each outcome after this step
- 00006%
- 00016%
- 00106%
- 00116%
- 01006%
- 01016%
- 01106%
- 01116%
- 8 more outcomes50%
Spreads all four qubits into an equal superposition, so the oracles below are asked about all 16 inputs at once rather than one at a time.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
Flips qubit 1, the first step of shifting the input by s = 0110 before applying f.
Nothing about the state changes here — the same outcomes with the same probabilities and the same phases as the step before.
Flips qubit 2, completing the shift by s.
Nothing about the state changes here — the same outcomes with the same probabilities and the same phases as the step before.
Applies CZ(0,1), the x₀x₁ term of f, now acting on the shifted input.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
Applies CZ(2,3), the x₂x₃ term of f, completing the oracle for g(x) = f(x ⊕ s).
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
Undoes the shift on qubit 1.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
Undoes the shift on qubit 2.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
The second Hadamard layer. Only g has been applied so far, shifted and then unshifted; this transforms that into an intermediate phase pattern. The f oracle and a THIRD Hadamard layer still have to follow before anything is readable — it is the last of the three that puts the shift into the computational basis.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
Applies CZ(0,1) again, this time as the oracle for f itself (unshifted): since f is self-dual, the same two-CZ pattern is its own Fourier dual.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
Applies CZ(2,3) again, completing the f oracle.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability. The entanglement comes apart here: each qubit has a state of its own again.
A third Hadamard layer reads the shift directly into the computational basis.
Probability gathers from 16 outcomes onto 1. 0110 goes from 6.3% to 100.0%.
Readout The register reads 0110, the hidden shift, exactly: a bent function's perfect duality makes the hidden-shift algorithm deterministic.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(1) quantum queries for the special case in which f is a multiplicative character of a finite ring or field; for hidden shift in general, at least √N queries are necessary, by reduction from Grover's problem.
- Papers1
Given oracle access to a function f on the integers mod N together with the promise that f(x) = g(x+s) for a known function g and an unknown shift s, recover s. Nearly all of the successful quantum algorithms use the Fourier transform to recover subgroup structure, above all periodicity; van Dam, Hallgren and Ip point out that the same transform also captures shift structure, which had received far less attention. They give three unknown-shift problems that can be solved efficiently on a quantum computer using the quantum Fourier transform, and they define the hidden coset problem, one framework that contains both the hidden shift problem and the hidden subgroup problem. The Quantum Algorithm Zoo records that their construction covers the case where f is a multiplicative character of a finite ring or field, and that the previously discovered shifted Legendre symbol algorithm is subsumed as a special case, because the Legendre symbol is a multiplicative character of Fₚ.
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 →
Nearly all of the successful quantum algorithms use the Fourier transform to recover subgroup structure, above all periodicity; van Dam, Hallgren and Ip point out that the same transform also captures shift structure, which had received far less attention. They give three unknown-shift problems that can be solved efficiently on a quantum computer using the quantum Fourier transform, and they define the hidden coset problem, one framework that contains both the hidden shift problem and the hidden subgroup problem. The Quantum Algorithm Zoo records that their construction covers the case where f is a multiplicative character of a finite ring or field, and that the previously discovered shifted Legendre symbol algorithm is subsumed as a special case, because the Legendre symbol is a multiplicative character of Fₚ. 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: O(1) quantum queries for the special case in which f is a multiplicative character of a finite ring or field; for hidden shift in general, at least √N queries are necessary, by reduction from Grover's problem..
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
- O(1) quantum queries for the special case in which f is a multiplicative character of a finite ring or field; for hidden shift in general, at least √N queries are necessary, by reduction from Grover's problem.
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Quantum Algorithm Zoo entry "Hidden Shift": "certain special cases of the hidden shift problem are solvable on quantum computers using O(1) queries. In particular, van Dam et al. showed that this can be done if f is a multiplicative character of a finite ring or field", and "By reduction from Grover's problem it is clear that at least √N queries are necessary to solve hidden shift in general." The abstract of arXiv:quant-ph/0211140 states no query count or running time of its own; it says only that three unknown-shift problems "can be solved efficiently on a quantum computer using the quantum Fourier transform".
- 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 shift problem
PROBLEM: Given oracle access to a function f on the integers mod N together with the promise that f(x) = g(x+s) for a known function g and an unknown shift s, recover s.
IDEA: Nearly all of the successful quantum algorithms use the Fourier transform to recover subgroup structure, above all periodicity; van Dam, Hallgren and Ip point out that the same transform also captures shift structure, which had received far less attention. They give three unknown-shift problems that can be solved efficiently on a quantum computer using the quantum Fourier transform, and they define the hidden coset problem, one framework that contains both the hidden shift problem and the hidden subgroup problem. The Quantum Algorithm Zoo records that their construction covers the case where f is a multiplicative character of a finite ring or field, and that the previously discovered shifted Legendre symbol algorithm is subsumed as a special case, because the Legendre symbol is a multiplicative character of Fₚ.
REPORTED COST: O(1) quantum queries for the special case in which f is a multiplicative character of a finite ring or field; for hidden shift in general, at least √N queries are necessary, by reduction from Grover's problem.
BASIS: Quantum Algorithm Zoo entry "Hidden Shift": "certain special cases of the hidden shift problem are solvable on quantum computers using O(1) queries. In particular, van Dam et al. showed that this can be done if f is a multiplicative character of a finite ring or field", and "By reduction from Grover's problem it is clear that at least √N queries are necessary to solve hidden shift in general." The abstract of arXiv:quant-ph/0211140 states no query count or running time of its own; it says only that three unknown-shift problems "can be solved efficiently on a quantum computer using the quantum Fourier transform".
PRIMARY SOURCE: Wim van Dam, Sean Hallgren, Lawrence Ip (2002), Quantum Algorithms for some Hidden Shift Problems — https://arxiv.org/abs/quant-ph/0211140
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
- Quantum Fourier Transform
Algorithms
- Shor period finding
Algorithms
- Grover unstructured search
Algorithms
References
- Quantum Algorithms for some Hidden Shift Problems
Wim van Dam, Sean Hallgren, Lawrence Ip · 2002
Primary source: it presents three unknown-shift problems that can be solved efficiently by the quantum Fourier transform and defines the hidden coset problem, which generalizes both the hidden shift problem and the hidden subgroup problem. Consult it for the promise conditions on f and g, since the abstract states no query bound.