Algorithm guide · transform
Quantum Fourier Transform
Map computational basis states to the frequency domain — the core of QPE and Shor.
Circuit size: n = 1..6 qubits
Complex phases · Binary integers · H and controlled phase gates
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
Transform a basis label into a pattern of relative phases across frequency labels. The QFT is a building block for estimation and arithmetic; measuring its output does not print all the Fourier coefficients.
2. How it works
Think of x as controlling how quickly a phase arrow turns as the output index y increases. QFT writes those phase arrows coherently. Controlled rotations create the pattern; final swaps establish the intended bit order.
Encode x
Use the input basis-state field to prepare an integer.
Build Fourier phases
Apply H and controlled rotations to create phase-dependent superpositions.
Order the bits
The circuit’s swaps align output significance.
Inspect or measure
Use state amplitudes for phase information; enable measurement to sample a frequency label.
3. The mathematics, one idea at a time
N=2ⁿ, x is the input integer and y labels a Fourier component. The exponential has unit magnitude.
All basis inputs give a flat direct measurement histogram. Their relative phases differ.
The inverse transform restores the original state, including its phase relationships.
Work this through by hand
4. One-qubit QFT of |1⟩
n=1 is the supported minimum. QFT is exactly H on one qubit.
Enter input basis state 1. Enable Measure after the QFT to see the sampled classical output.
| Stage | Calculation or state | What it means |
|---|---|---|
| y=0 component | exp(2πi·1·0/2)/√2=+1/√2 | The phase is zero. |
| y=1 component | exp(2πi·1·1/2)/√2=−1/√2 | The phase is π. |
| Output | (|0⟩−|1⟩)/√2=|−⟩ | Both direct measurement probabilities are 1/2, despite the minus sign. |
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 |
|---|---|---|
| 0 | 50% ideal | One Fourier-label sample. |
| 1 | 50% ideal | The other Fourier-label sample. |
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.
- Qubits (n)
- 1
- Input basis state (before the QFT)
- 1
- Measure after the QFT
- On
- 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
To inspect the minus sign, load a version with measurement disabled and inspect the state amplitudes before measurement.
Appending another H before measurement would return 1 with certainty. This reveals interference that a flat histogram alone hides.
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 flat histogram does not mean that QFT discarded the input.
- Do not claim that one measurement returns every frequency amplitude or a classical Fourier spectrum.
8. Check your understanding
How does QFT|0⟩ differ from QFT|1⟩ for one qubit?
Reveal the reasoning
It is |+⟩ rather than |−⟩. Both have the same Z-basis probabilities but different relative phase.
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
These are the gallery defaults. The worked example above may override them. Configure the card to change the inputs before loading its editable circuit.
- Qubits (n)
- Default: 3 · Whole number from 1 to 6.
- Input basis state (before the QFT)
- Default: 000 · 3 bits (0 or 1); leftmost character is the highest-numbered qubit.
- Measure after the QFT
- Default: false · On or off.
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.
- Frequency bins
- 8
- Controlled phases
- 3
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.