Algorithm guide · oracle
Hidden shift (bent function)
Recover the exact bit shift s between a known bent function and its shifted oracle.
Circuit size: 2, 4, or 6 qubits · no ancilla
CZ phase gates · Hadamard transforms · XOR shifts
Review quantum fundamentals →Notation used in this lesson
- |ψ⟩ and ⟨ψ|
- A state vector (ket) and its conjugate transpose (bra). ⟨a|b⟩ is their inner product.
- α, β and i
- α and β are complex amplitudes; i²=−1. A probability is the squared magnitude |α|².
- XOR, · and ⊗
- XOR adds bits modulo two. In s·x, multiply corresponding bits and XOR them. ⊗ combines registers or operations on different wires.
- U†, Σ and Tr
- U† is the adjoint (inverse for a unitary). Σ sums terms. Tr is the matrix trace, the sum of diagonal entries.
- Probability, shots and angles
- Ideal probabilities describe the model; measured shot frequencies fluctuate. Angles inside trigonometric expressions are in radians unless explicitly labeled turns.
1. The problem
A known bent Boolean function f and an oracle g satisfy g(x)=f(x XOR s). Recover the shift s. This gallery uses the special even-width pair-product function f(x)=x0x1 XOR x2x3 XOR … .
2. How it works
A hidden shift becomes a phase pattern after the Boolean Fourier transform. For this self-dual bent function, applying the known dual function removes the remaining pattern. A final Hadamard layer exposes the shift as an ordinary bit string.
Prepare and query g
H prepares uniform inputs, then a shifted phase oracle applies (−1)^g(x).
Fourier transform
H on every input brings the hidden shift into a linear sign pattern.
Remove the known dual
CZ pairs apply f*=f.
Decode
Final H on all inputs yields the shift.
3. The mathematics, one idea at a time
X gates before and after the CZ pairs implement the chosen shift in this teaching circuit.
The overall phase γ is irrelevant to measurement. Self-duality is special to the selected pair-product function.
Work this through by hand
4. Two bits, shift 11
n=2 is the smallest allowed even width and needs no helper.
For f(x0,x1)=x0x1, shift 11 makes g(x)=1 only at x=00.
| Stage | Calculation or state | What it means |
|---|---|---|
| After g, ordered 00,01,10,11 | (−1,+1,+1,+1)/2 | The minus is at 00 rather than f’s unshifted 11. |
| After middle H⊗H | (+1,−1,−1,−1)/2 | The amplitudes rearrange by interference. |
| After known CZ and final H⊗H | (+1,−1,−1,+1)/2 → |11⟩ | CZ removes the unwanted quadratic phase; the remaining linear signs decode to s. |
Expected outcomes for this example
These are ideal predictions for the stated configuration, not a result already measured by your browser. Rows describing alternative modes or combined events are labeled explicitly.
| Outcome or event | Ideal probability | Interpretation |
|---|---|---|
| 11 | 100% ideal | The recovered shift. |
5. Load the worked example in Composer
The worked example can use smaller or simpler inputs than the gallery defaults. The button below loads the exact circuit used in this lesson.
- Input qubits (even)
- 2 qubits
- Hidden shift s
- 11
- Save any current circuit you want to keep, then open the worked example. Loading it does not execute a paid hardware job.
- Trace the preparation, main operations and measurements against the worked table. Check the gate editor for controls, targets and angles.
- Start with an ideal noiseless simulator compatible with the circuit. Mid-circuit measurement, reset and feed-forward require support from the chosen backend.
- Inspect the live preview. For a recorded experiment, open Execute, set the available backend options and shots, and Run. Sign in when prompted to retain it in My Jobs.
- Read the output as described below before changing one setting and repeating. The guide describes the original example; edits can change the answer.
6. Read the output correctly
Read c1c0 as the shift, with the last character corresponding to q0.
The circuit uses g once and the known dual once. Count one use of each phase block; only g is unknown when f is given.
A bit label is a register value; its bar height is a probability or count. For S shots and observed count k, the sampled frequency is k/S. A typical sampling scale for probability p is √[p(1−p)/S]; this is not a strict error bound. Finite samples do not have to match the ideal percentages exactly.
7. Common mistakes & limits
- This fast construction does not solve arbitrary hidden-shift functions.
- The visible X gates reveal the configured shift in the expanded teaching circuit; oracle access is an assumed problem model.
8. Check your understanding
Where does the minus sign sit immediately after g when s=00?
Reveal the reasoning
At 11, because the shifted oracle is then just f itself. The final answer is 00.
9. Further study
The lesson’s register mappings, supported inputs and loadable example follow Quantket’s implemented circuit. A reference may use different wire names, bit order or resource conventions.
Gallery reference: defaults, definitions & implementation notes
Inputs & default settings
Choose an even register width and a shift, then inspect the two separated phase-oracle blocks in Composer.
These are the gallery defaults. The worked example above may override them. Configure the card to change the inputs before loading its editable circuit.
- Input qubits (even)
- Default: 4 · Choices for the current settings: 2 qubits; 4 qubits; 6 qubits.
- Hidden shift s
- Default: 1010 · 4 bits (0 or 1); leftmost character is the highest-numbered qubit.
The leftmost digit is the highest-index qubit. Composer's measured c(n−1)…c0 register reads the same way.
Implementation notes
For f(x) = x₀x₁ ⊕ x₂x₃ ⊕ …, the Walsh dual f* equals f. The circuit uses the shifted phase oracle g once and the known dual phase oracle f* once, with Hadamards between and after them. It reads s with certainty in an ideal simulation. Only g is an unknown-oracle query when f is given; counting both phase blocks gives one use of each, not one use total. Composer expands g as X–CZ–X and f* as CZ pairs, so the chosen shift is visible in the editable circuit. Based on Rötteler, arXiv:0811.3208.
Default example: predictions & circuit facts
These values describe the unedited default setup. They are predictions and circuit properties, not measured results from your saved execution.
- Ideal measured shift
- 1010 (100%)
- Oracle uses
- 1 shifted g + 1 known dual f*
Read your saved result
Check the submitted circuit, measured register and execution settings in Run details. Exact results give computed probabilities; sampled results show frequencies from the recorded shots. Edited circuits and noise can change the expected outcome. The algorithm label records the circuit's origin; it does not certify an edited circuit or a measured result.