Algorithm guide · arithmetic
Modular adder mod 15 (Beauregard)
Add a chosen classical value to a four-bit quantum register, wrapping at 15 rather than 16.
Circuit size: 6 qubits · 4-bit result
Modular arithmetic · Fourier addition · Conditional correction and 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
Add a chosen classical constant a to a four-bit input x modulo 15. Valid inputs are 0 through 14. Keep overflow/comparison workspace clean.
2. How it works
First add a, then test whether subtracting 15 went too far. If so, add 15 back. A reversible cleanup removes the temporary underflow record. Unlike ordinary four-bit addition, wrapping happens at 15 rather than 16.
Prepare x
Encode x into four data wires and keep the extra Fourier wire and flag clean.
Add and subtract
Use Fourier-phase additions to form x+a−15.
Correct underflow
A flag controls adding 15 back when x+a<15.
Clean and read
Undo comparison work and measure only the four-bit result.
3. The mathematics, one idea at a time
Since x,a≤14, the sum is at most 28; subtracting 15 once is sufficient.
Workspace cleanup is part of the intended arithmetic map. The classical constant a is not a second quantum operand register.
Work this through by hand
4. Start with 1+1; then test the wrap
This card is fixed at six physical qubits: four result bits plus two work wires. Smaller numbers do not reduce its register size.
Choose x=1 and addend=1 for the first run.
| Stage | Calculation or state | What it means |
|---|---|---|
| Raw sum | 1+1=2 | No wrap is needed. |
| Tentative subtraction | 2−15<0 | The reversible underflow test selects adding 15 back. |
| Final result | r=2=0010₂ | Both work wires return to zero. |
| Boundary extension | Change to x=14,a=2: 16 mod 15=1 | This gives 0001, unlike modulo-16 arithmetic, which would give 0000. |
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 |
|---|---|---|
| 0010 | 100% ideal for x=1,a=1 | The four-bit result is two. |
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 x (0–14)
- 1
- Classical addend a (0–14)
- 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
Read c3c2c1c0 directly as the result integer. Work bits are excluded.
The |15⟩ data input is outside the promised valid domain. The circuit’s behavior there is not an example of its advertised modulo-15 function.
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 is an arithmetic building block, not an entire Shor factoring algorithm.
- Modulo 15 and keeping four low bits are different operations.
8. Check your understanding
What does x=14,a=1 produce?
Reveal the reasoning
15 mod 15=0, so output 0000.
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 x and a, then inspect Fourier addition, subtract-15, conditional correction and cleanup 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 x (0–14)
- Default: 14 · Whole number from 0 to 14.
- Classical addend a (0–14)
- Default: 2 · Whole number from 0 to 14.
Implementation notes
Beauregard's constant adder maps |x⟩ to |(x+a) mod 15⟩ for 0 ≤ x,a < 15. A fifth register wire detects underflow after subtracting 15; a flag controls adding 15 back when needed. The circuit reverses its comparison work and returns both extra qubits to |0⟩. The addend is a chosen classical constant, not a second quantum input register. Only the four result bits are measured. This is one arithmetic block from the Shor construction, not full order-finding. See arXiv:quant-ph/0205095, §2.2.
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.
- Result
- 0001 (1)
- Subtract 15?
- Yes
- Histogram c3c2c1c0
- 0001
- Work qubits
- overflow = 0, flag = 0
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.