Algorithm guide · arithmetic
Quantum comparator
Set a flag when unsigned a is less than b, while preserving both input registers.
Circuit size: 4–8 qubits (n = 1..3)
Unsigned binary numbers · Carry arithmetic · Uncomputation
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
Compute the flag [a<b] without changing the two input registers. This is a reversible predicate that can be used coherently before measurement.
2. How it works
Subtraction can be implemented by adding a to the bitwise complement of b plus one. Its carry tells whether subtraction underflowed. Copy the opposite of that carry into a clean flag, then undo the arithmetic.
Complement and initialize
Use the carry-chain representation of a+(~b)+1.
Propagate carry
Compute whether a≥b.
Write flag
Toggle the clean flag when the final carry is absent.
Uncompute
Reverse temporary arithmetic, restore b and clear scratch before measuring only the flag.
3. The mathematics, one idea at a time
For n-bit unsigned a,b, a final carry is present exactly when a≥b.
The result is one Boolean answer, not the difference a−b.
Work this through by hand
4. Compare one-bit 0 and 1
Four qubits at n=1: two operands, one scratch and one flag.
Choose a=0 and b=1.
| Stage | Calculation or state | What it means |
|---|---|---|
| Arithmetic test | 0+(~1)+1=0+0+1=1 | A one-bit result with no overflow carry. |
| Flag | 1−0=1 | The predicate a<b is true. |
| Cleanup | a=0, b=1, scratch=0 | Input information is preserved. |
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 |
|---|---|---|
| 1 | 100% ideal | a is less than b. |
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.
- Bits per input register (n)
- 1
- Input a
- 0
- Input b
- 1
- 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
Classical c0 is only the comparison flag: 1 means true and 0 means false.
When a=b, the flag is 0. If inputs are superposed, measuring the flag can correlate/project the operands; the reversible operation before measurement remains coherent.
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
- Flag 0 means a≥b; it does not distinguish equality from greater-than.
- Do not reverse the operands when reading the test. This card computes a<b.
8. Check your understanding
What is the flag for a=1,b=1?
Reveal the reasoning
0. The comparison is strict, so equality is false.
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 a and b, then follow the carry, flag and uncomputation stages 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.
- Bits per input register (n)
- Default: 2 · Whole number from 1 to 3.
- Input a
- Default: 01 · 2 bits (0 or 1); leftmost character is the highest-numbered qubit.
- Input b
- Default: 10 · 2 bits (0 or 1); leftmost character is the highest-numbered qubit.
Implementation notes
The circuit finds the carry of a + (~b) + 1: it is 1 when a ≥ b. It copies the inverse to a flag qubit, reverses the carry chain, restores b, and clears its one scratch qubit. Only the flag is measured. Superpositions of a and b remain coherent before that measurement. In Composer, choose Classical bits to see the 0/1 comparison histogram. At n=3 the full eight-qubit probability chart is unavailable, but the flag histogram still works. The carry construction follows Cuccaro et al., arXiv:quant-ph/0410184, §4.3.
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.
- Comparison
- 1 < 2
- a < b flag
- 1 (true)
- Histogram c0
- 1
- Inputs after
- a=01, b=10
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.