Algorithm guide · oracle
Probabilistic Bernstein–Vazirani
Two secret strings share one oracle. A run returns one complete string; repeat to discover both.
Circuit size: n = 2..5 input qubits + 2 ancillas
Standard BV · An unmeasured selector · Joint versus independent probabilities
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 selector chooses between two parity secrets s0 and s1. Recover a complete secret from each execution, then repeat to discover both. This differs from asking each output bit to be an independent random choice.
2. How it works
Keep the selector coherent while it controls the two parity oracles. The final inputs are correlated with that selector. Looking only at the input register therefore produces one whole secret or the other, rather than arbitrary mixtures of their bits.
Prepare
Inputs and selector begin in equal superpositions; the output helper is |−⟩.
Conditional parity
The selector controls which secret’s parity phase is written.
Decode and repeat
Apply H to the inputs and measure them, leaving the selector unmeasured. Repeated runs reveal the two possible strings.
3. The mathematics, one idea at a time
This is the decoded selector/input state. The two strings are entire branches.
Ignoring the selector gives 50% per distinct secret. If the secrets are equal, the two contributions combine into one certain outcome.
Work this through by hand
4. Two-bit secrets 00 and 11
n=2 is the supported minimum; two extra qubits hold selector and helper.
Set First secret to 00 and Second secret to 11.
| Stage | Calculation or state | What it means |
|---|---|---|
| Selector 0 branch | Input decodes to 00 | Its branch weight is 1/2. |
| Selector 1 branch | Input decodes to 11 | Its branch weight is also 1/2. |
| Discard selector | P(00)=P(11)=1/2; P(01)=P(10)=0 | Secret bits are correlated, not independent coin tosses. |
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 | First secret. |
| 11 | 50% ideal | Second secret. |
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
- First secret s₀
- 00
- Second secret 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 two measured input bits together. With 100 shots you expect roughly 50 of each, not an exact quota.
One shot never reveals both secrets. Several repeats can still miss one by chance.
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
- A histogram with only one observed secret after a few shots does not prove the other secret is absent.
- This card uses equal selector weights; it does not model every possible probabilistic oracle distribution.
8. Check your understanding
What if both secret fields are 11?
Reveal the reasoning
Every ideal input outcome is 11. Distinct selector branches do not create distinct answers when their strings agree.
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
Set two n-bit secrets. The selector chooses their parity oracles equally; Composer measures one complete secret per run.
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 5.
- First secret s₀
- Default: 011 · 3 bits (0 or 1); leftmost character is the highest-numbered qubit.
- Second secret s₁
- Default: 101 · 3 bits (0 or 1); leftmost character is the highest-numbered qubit.
The secrets may match. When they do, the circuit reduces to ordinary deterministic Bernstein–Vazirani.
Implementation notes
The selector starts in |+⟩ and controls two parity oracles. The output ancilla starts in |−⟩, so controlled Toffoli gates kick back the selected parity. The selector stays unmeasured: the input histogram shows both whole strings, not independent bits. Distinct secrets occur 50% each; identical secrets give one certain result. One oracle call returns one string, while seeing both requires repeated runs.
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.
- Oracle queries
- 1 per run
- Outcome probabilities
- 50% each
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.