Algorithm guide · oracle
Simon's algorithm
A hidden 2-to-1 function has f(x) = f(x ⊕ s) for a secret s ≠ 0ⁿ. Find s.
Circuit size: n = 2..4 input + n output qubits
XOR of bit strings · Hadamard interference · Linear equations modulo two
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
An oracle obeys f(x)=f(x XOR s) for one nonzero secret s, with exactly those two inputs sharing each output. Find s. A measured string is a constraint on s, not normally s itself.
2. How it works
The oracle entangles inputs that share an output. Interference of each pair removes all final strings y whose parity dot product with s is one. The surviving random y values provide linear equations that a classical solver combines.
Query in superposition
Prepare uniform inputs and compute f into a separate output register.
Pair branches
Conditioning on an output would leave (|x⟩+|x XOR s⟩)/√2; ignoring that output produces the same input statistics.
Collect constraints
Apply H to inputs and measure y. Repeat until there are enough independent equations, then solve y·s=0 over bits.
3. The mathematics, one idea at a time
If s·y=1, the bracket is zero. If s·y=0, its two terms reinforce.
Each shot is one homogeneous binary equation. The nonzero-promise excludes the trivial all-zero candidate when the independent equations leave only one nonzero solution.
Work this through by hand
4. Two-bit period s=11
n=2 is the supported minimum: two input and two output wires.
Define secret 11. The paired inputs are {00,11} and {01,10}.
| Stage | Calculation or state | What it means |
|---|---|---|
| Pair interference | Allowed y satisfy y0 XOR y1=0 | Both secret bits are 1. |
| Possible constraints | y=00 or y=11, each with probability 1/2 | 00 adds no information; 11 says the secret bits agree. |
| Classical solve | s0=s1 and s≠00 ⇒ s=11 | The promise selects the unique nonzero solution. |
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 |
|---|---|---|
| 00 | 50% ideal | Valid sample but no new equation. |
| 11 | 50% ideal | One useful parity equation. |
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 (n)
- 2
- Secret setup
- Define secret
- Secret string 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 the input-register histogram. Do not decode y as an ordinary integer estimate of the secret.
For larger n, many independent rows may be needed. Repeated copies of the same y do not increase matrix rank.
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
- Seeing y=s in this small example is a coincidence; many valid Simon samples do not equal s.
- The promise is stronger than merely having some repeated function values.
8. Check your understanding
For secret 10, which two-bit y values satisfy the constraint?
Reveal the reasoning
Using a matching MSB-first convention, y’s first bit must be 0, so y=00 or 01.
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
- s
- secret, never 0ⁿ
- 2-to-1
- x and x ⊕ s share one output
Inputs & default settings
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 (n)
- Default: 3 · Whole number from 2 to 4.
- Secret setup
- Default: define · Choices for the current settings: Define secret; Hidden secret.
- Secret string s
- Default: 101 · 3 bits (0 or 1), not all zero; leftmost character is the highest-numbered qubit. Shown only for the relevant configuration.
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.