45 min read

> *"It computes a Fourier transform exponentially faster than any classical algorithm, and you cannot

Prerequisites

  • 3
  • 4
  • 5
  • 15
  • 19
  • 20
  • 21

Learning Objectives

  • Build the QFT circuit and verify it against the classical DFT matrix.
  • Explain why an exponentially faster transform does not give an exponential speedup.
  • Implement quantum phase estimation and predict its accuracy.
  • Choose the number of counting qubits for a required precision.
  • Apply the approximate QFT and quantify the fidelity it costs.
  • Price a QFT in the fault-tolerant regime, where rotations dominate.

In This Chapter

Exercises Quiz Case Study 01 Case Study 02 Key Takeaways Further Reading

Chapter 22: The Quantum Fourier Transform

"It computes a Fourier transform exponentially faster than any classical algorithm, and you cannot look at the answer."

Overview

The QFT is the engine of the most important quantum algorithms. Shor's factoring (Chapter 23) is period-finding by phase estimation, and phase estimation is the QFT. Chapter 21's quantum counting is the same machinery. So is most of quantum chemistry's energy estimation.

It is also the subject of the field's most persistent overstatement, and this chapter deals with that first.

The QFT is exactly the discrete Fourier transform — verified against the DFT matrix to $10^{-10}$ — and it uses exponentially fewer operations:

     n        N = 2ⁿ    QFT gates ~ n(n+1)/2    classical FFT ~ N log₂N
     8           256                      36                     2,048
    16        65,536                     136                 1,048,576
    32   4.3 × 10⁹                       528             1.4 × 10¹¹

136 gates against a million operations at $n = 16$. That looks like an exponential speedup for signal processing, and it is not one — because you cannot read the output.

   QFT output amplitudes:  [0, 0, 0, 0, 0, 1, 0, 0]
   one measurement gives:  outcome 5, and nothing else

The transform is computed, in superposition, correctly. Extracting the $2^n$ amplitudes requires tomography — exponentially many shots — which gives back everything the transform saved. §22.3 makes this precise, because it is the single most important thing to understand about the QFT.

What the QFT is genuinely for is phase estimation, where you do not want the amplitudes. You want one number, and the QFT concentrates it into a single measurable outcome.

In this chapter, you will learn to:

  • Build the QFT and verify it against the DFT.
  • Explain the readout problem precisely.
  • Implement phase estimation and predict its accuracy.
  • Choose the counting qubits for a target precision.
  • Apply the approximate QFT and measure what it costs.
  • Price a QFT where rotations, not T gates, dominate.

Learning Paths

How to read this chapter by track. - 🔰 Beginner — §22.2 and §22.3. The readout problem is the idea to leave with. - 🔬 Researcher — §22.4 and §22.6; precision-versus-qubits is the design decision. - 🤖 Quantum ML — §22.3 directly; many QML speedup claims founder on exactly this. - 🏗️ Quantum Engineer — §22.5 and §22.6. The AQFT is how Shor becomes feasible. - 🔐 Security — all of it, then Chapter 23.

22.1 The Transform

The QFT is the discrete Fourier transform, as a unitary:

$$\text{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,|k\rangle$$

Verified against the DFT matrix built directly in NumPy:

   n=2: matches DFT matrix?  True
   n=3: matches DFT matrix?  True
   n=4: matches DFT matrix?  True

Not "approximately" — the unitary Qiskit's QFTGate produces is the DFT matrix, to $10^{-10}$.

The circuit is Hadamards interleaved with controlled phase rotations, followed by a swap layer:

                                         ┌───┐
  q_0: ────────────────────■────────■────┤ H ├─X─
                    ┌───┐  │        │P(π/2)     │
  q_1: ──────■──────┤ H ├──┼────────■───────────┼─
       ┌───┐ │P(π/2)└───┘  │P(π/4)              │
  q_2: ┤ H ├─■──────────────■──────────────────X─
       └───┘

   3-qubit QFT: {'h': 3, 'cp': 3, 'swap': 1}

The structure is $n$ Hadamards and $n(n-1)/2$ controlled phases, with rotation angles halving at each step: $\pi/2$, $\pi/4$, $\pi/8$, … That decay is what §22.5 exploits.

⚠️ Common Pitfall — the qubit ordering convention will bite you.

Reconstructing the QFT by hand, there are four plausible conventions — Hadamards applied in ascending or descending qubit order, with or without the final swaps. Only one matches Qiskit's QFTGate:

text ascending + swaps fidelity vs QFTGate = 0.265 DESCENDING + SWAPS fidelity vs QFTGate = 1.000 <- this one descending, no swaps fidelity = 0.250 ascending, no swaps fidelity = 0.250

Three of four give you a wrong answer with no error message, and the wrongness is not obvious — 0.25 and 0.265 both look like something went subtly wrong rather than completely wrong.

This is Chapter 14 §14.5's endianness problem in a new place, and the fix is the same: verify against a reference implementation before building anything on top.

Deriving the Circuit from the Definition

The circuit above looks like something someone discovered. It is not — it falls out of the definition in about six lines, and the derivation explains every feature of it, including the swap layer that §22.1's pitfall turns on.

Write $j$ in binary as $j = j_1 j_2 \dots j_n$, so that $j = \sum_{l=1}^{n} j_l 2^{n-l}$, and do the same for $k$. Then

$$\text{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,|k\rangle$$

The exponent $2\pi i jk/2^n$ is a sum over $k$'s bits, because $k = \sum_l k_l 2^{n-l}$:

$$\frac{jk}{2^n} = \sum_{l=1}^{n} \frac{j\,k_l\,2^{n-l}}{2^n} = \sum_{l=1}^{n} j\,k_l\,2^{-l}$$

A sum in the exponent is a product outside it, and a sum over all $k$ is a product of independent sums over each bit $k_l \in \{0,1\}$. So the whole thing factorises:

$$\text{QFT}\,|j\rangle = \bigotimes_{l=1}^{n} \frac{|0\rangle + e^{2\pi i j / 2^{l}}\,|1\rangle}{\sqrt 2}$$

This is the product form, and it is the entire algorithm. The transform of a basis state is a product state — no entanglement at all — with one qubit per output bit and a single phase on each. That is why the QFT is cheap: a state with $2^n$ amplitudes, described by $n$ independent numbers.

Now read off the circuit. Look at the $l$-th factor's phase, $e^{2\pi i j/2^l}$. Since $e^{2\pi i m} = 1$ for integer $m$, only $j \bmod 2^l$ survives — that is, only the lowest $l$ bits of $j$ matter. Writing the binary fraction $0.j_{n-l+1}\dots j_n$ for that residue:

$$\frac{j}{2^l} \equiv 0.j_{n-l+1}j_{n-l+2}\dots j_n \pmod 1$$

The $l = 1$ factor depends on one bit — that is a Hadamard. The $l = 2$ factor depends on two bits — a Hadamard plus one controlled rotation by $\pi/2$. The $l = 3$ factor needs a further rotation by $\pi/4$. Each additional bit of the residue contributes one controlled phase, halved. Summing over $l$ gives $n$ Hadamards and $1 + 2 + \dots + (n-1) = n(n-1)/2$ controlled phases, which is exactly the gate count §22.1 measured.

And the swaps are not an afterthought. In the product form, the factor that depends on $j$'s lowest bit is $l = 1$, the first output qubit. The circuit builds output bit $l$ from input bits $n-l+1 \dots n$, so the natural construction writes the answer in reverse order. The final swap layer un-reverses it. This is precisely why "descending, no swaps" scores 0.250 in the pitfall table rather than something obviously catastrophic: the circuit computes the right transform and then hands it to you with the qubits backwards.

⚛️ The Physics Underneath — the QFT is a change of basis, not a computation.

Nothing in the product form is "calculating" anything. Each output qubit ends in an equal superposition of $|0\rangle$ and $|1\rangle$ with a relative phase set by some bits of the input, and the entire transform is $n$ single-qubit states sitting side by side.

Physically this is the same move as going from position to momentum. A state sharply localised in the computational basis — one basis state $|j\rangle$ — becomes maximally delocalised after the QFT: all $2^n$ output amplitudes have magnitude $1/\sqrt N$, and every bit of information about $j$ lives in the phases. Run it the other way and a state with a uniform periodic phase pattern collapses onto the few basis states matching that period.

That is the whole mechanism behind period finding, and it is why the QFT is the natural tool for it. Chapter 23's modular-exponentiation register carries a periodic phase; the QFT converts periodic phase into a localised amplitude, which is the only kind of thing a measurement can see.

It is also why §22.3's readout problem is unavoidable rather than an engineering shortfall. The information is in the phases, and measurement in any single basis destroys phase. Getting it back is tomography by definition, not by bad luck.

22.2 Exponentially Fewer Operations

$n$ Hadamards plus $n(n-1)/2$ controlled phases is $\mathcal{O}(n^2)$ gates for a transform over $N = 2^n$ amplitudes. The best classical algorithm, the FFT, takes $\mathcal{O}(N \log N)$:

     n        N = 2ⁿ     QFT gates    classical FFT ops
     4            16            10                   64
     8           256            36                2,048
    16        65,536           136            1,048,576
    32   4.3 × 10⁹             528        1.4 × 10¹¹
    64   1.8 × 10¹⁹          2,080        1.2 × 10²¹

$$\mathcal{O}(n^2) = \mathcal{O}\big((\log N)^2\big) \quad\text{versus}\quad \mathcal{O}(N\log N)$$

Exponentially fewer operations, and the comparison is real. The QFT genuinely applies the Fourier transform to $2^n$ amplitudes in $n^2$ gates.

Counting the Gates Honestly

The table's "QFT gates" column is $n(n+1)/2$, and §22.1's structure was $n$ Hadamards plus $n(n-1)/2$ controlled phases. Those agree:

$$n + \frac{n(n-1)}{2} = \frac{2n + n^2 - n}{2} = \frac{n(n+1)}{2}$$

The swap layer is not in that count. It adds $\lfloor n/2 \rfloor$ swaps — 8 at $n = 16$, 32 at $n = 64$ — which is $\mathcal{O}(n)$ and disappears into the $\mathcal{O}(n^2)$. In practice it often disappears entirely: if the next stage of your algorithm can absorb a qubit relabelling, the swaps become free bookkeeping rather than gates. Cirq exposes this directly as a without_reverse flag.

What is in neither count is the decomposition. A cp is not a hardware instruction, and neither is a swap. §22.2's numbers are counts of logical operations at the level the algorithm is written, and the next two subsections measure what happens when you cash them in — once on real connectivity (below) and once under error correction (§22.6). Both multiply.

This is worth saying plainly because the $\mathcal{O}(n^2)$-versus-$\mathcal{O}(N\log N)$ comparison is usually made at exactly this level and nowhere else. The exponent is right. The constant is not 1, and §22.6 finds it is nearer 300.

⚙️ Under the Transpiler — 28 controlled phases become 56 two-qubit gates, or 95, or 137.

A single cp translated into a hardware basis:

text cp(pi/8) -> cz, rz, sx, x {'rz': 6, 'sx': 4, 'cz': 2, 'x': 2}

Two cz and twelve single-qubit gates for one logical cp — and that is the free case, with perfect connectivity. The QFT's controlled phases are all-to-all: every qubit talks to every other one. Real chips are not.

Transpiling QFTGate(8) to cz, rz, sx, x at optimization_level=3:

text coupling map depth cz total gates all-to-all 96 56 271 linear chain 169 95 471 ring 198 108 474

56 is exactly $28 \times 2$ — the transpiler pays the per-cp price and nothing more when it can place gates freely. Restricting to a line costs +70% two-qubit gates and +76% depth, entirely in routing.

And Chapter 39 §39.2 scheduled the same circuit on a real backend's coupling map: 137 two-qubit gates, depth 252, 10.55 μs, 43.20 ms for 4,096 shots. So the honest progression for an 8-qubit QFT is 28 cp → 56 cz (ideal) → 95 (line) → 137 (real device), a 2.4× spread caused by connectivity alone, before any discussion of algorithms.

The AQFT (§22.5) shrinks the same circuit to 36 cz on all-to-all and 69 on a line — and it shrinks the routing penalty too, because the rotations it drops are precisely the long-range ones.

22.3 Why That Is Not an Exponential Speedup

The most important section in the chapter.

Prepare a pure frequency-3 signal on 3 qubits, apply the QFT, and look at what comes out:

   QFT output amplitudes:      [0, 0, 0, 0, 0, 1, 0, 0]
   measurement probabilities:  [0, 0, 0, 0, 0, 1, 0, 0]
   measuring gives outcome 5 with P = 1.0000

The transform is correct. The amplitudes are exactly what the DFT says they should be.

And one measurement gives one integer. Not eight amplitudes — one outcome.

To learn the $2^n$ output amplitudes you would need state tomography: exponentially many measurements in exponentially many bases. That cost is $\mathcal{O}(4^n)$, which annihilates the $\mathcal{O}(n^2)$ you saved and then some.

$$\underbrace{\mathcal{O}(n^2)}_{\text{compute the transform}} \;+\; \underbrace{\mathcal{O}(4^n)}_{\text{read the result}} \;=\; \text{worse than classical}$$

How Many Shots Buy One Spectrum

$\mathcal{O}(4^n)$ is the cost of full tomography, phases included. It is worth working the weaker case too — magnitudes only, no phases — because that is what people actually try first, and it loses anyway.

Repeated measurement gives you a multinomial sample over the $2^n$ outcomes. With $N$ shots, the standard error on an estimated probability $\hat p_k$ is

$$\sigma_k = \sqrt{\frac{p_k(1-p_k)}{N}} \;\approx\; \sqrt{\frac{p_k}{N}} \quad (p_k \ll 1)$$

A spectrum spread over $2^n$ bins has typical $p_k \sim 2^{-n}$. To pin each bin to 1% relative precision you need $\sigma_k \le 0.01\,p_k$, which rearranges to

$$N \;\ge\; \frac{10^4}{p_k} \;=\; 10^4 \cdot 2^{\,n}$$

The shot count is exponential in $n$ before you have asked for a single phase. Case Study 1's group wanted $n = 20$:

   shots for 1% per bin, n = 20      1.0486 × 10¹⁰
   classical FFT operations          2.0972 × 10⁷
   ratio                                     500×

500 times more shots than the FFT does operations, and the ratio is $10^4/n$ — it improves with $n$ only because 1% of a smaller number is a smaller absolute target, which is not a comfort.

Put a clock on it with Chapter 39 §39.2's measured throughput — a QFT-8 job of 4,096 shots occupying a real device for 43.20 ms:

   1.0486 × 10¹⁰ shots  ÷  4,096 per job  ×  43.20 ms  =  30.7 hours

Thirty hours of pure QPU time, to recover magnitudes the FFT produces in 21 million operations — and that timing is borrowed from an 8-qubit circuit, so it flatters the 20-qubit case substantially. The phases, which a Fourier transform exists to produce, are not in that number at all.

📊 What the Numbers Say — "136 gates against a million" compares two different things.

The headline in §22.2 is real and it is also a category error waiting to happen. Read the two columns carefully:

text QFT: 136 GATES -> produces a quantum state FFT: 1,048,576 OPERATIONS -> produces 65,536 usable numbers

The left column is an input cost. The right column is an input cost and a deliverable. They are not the same kind of quantity, and writing them adjacent in a table is what makes the comparison feel settled.

The book's recurring form of this is "the number that is easy to get is not the number that answers the question." Gate count is easy — count_ops() returns it in a millisecond. Shots-to-deliverable is hard, requires deciding what precision you need, and is the number that decides the project.

The corrected comparison, both sides carrying their I/O:

text n = 20 load transform read out total classical 0 2.10 × 10⁷ ops 0 2.10 × 10⁷ quantum ~10⁶ gates 210 gates ≥1.05 × 10¹⁰ ≥1.05 × 10¹⁰

The middle column is the only one the speedup claim ever looked at, and it is the only column that does not matter.

The Readout Problem and the Input Problem Are the Same Theorem

§22.3's argument runs on the output side. The input side has been measured, in Chapter 32.

Chapter 32 §32.2 is titled The input problem, and it counts the cost of amplitude encoding — loading $N$ arbitrary classical values into $\log_2 N$ qubits — arriving at an exact two-qubit gate count that its measured counts follow with no error term at all:

$$\text{two-qubit gates} \;=\; N - \log_2 N - 1$$

At Case Study 1's $n = 20$ that is 1,048,555 two-qubit gates to load, against 210 gates to transform:

   load  (Ch.32's measured formula)    1,048,555 two-qubit gates
   QFT   (n(n+1)/2)                          210 gates
   ratio                                   4,993×

The load alone is five thousand times the transform, and it is a measured count from a different chapter about a different subject, arrived at without reference to the QFT at all.

That is the point worth holding onto. The readout problem and the input problem are not two objections; they are one theorem seen from two ends. A quantum register holds $2^n$ amplitudes in $n$ qubits, and the compression is real — but it is a compression of storage, not of access. Writing $2^n$ independent numbers in costs $\Omega(2^n)$; reading $2^n$ independent numbers out costs $\Omega(2^n)$. The only thing that is cheap is what happens in between.

So a quantum speedup survives exactly when the problem's input and output are both small. Not small-ish — polynomial in $n$. Shor's input is an integer and its output is a factor; both are $\mathcal{O}(n)$ bits, which is why Chapter 23 works and this section's spectral analysis does not.

Chapter 32 will reach the same wall from the machine-learning side, where a feature matrix is exactly the kind of $\mathcal{O}(2^n)$-sized arbitrary input that has no efficient preparation. The two chapters are 10 apart and are describing the same constraint.

Where the Objection Does Not Bite

Being precise about a limitation means being precise about its edges. There are three ways out, and they are the three places quantum algorithms actually live.

1. You want $\mathcal{O}(\text{poly}(n))$ bits of answer. Phase estimation, period finding, counting, energy estimation. The register is asked for one number and it can produce one number. This is §22.4 onward and it is the honest case.

2. The input has structure that makes preparation cheap. The $\mathcal{O}(2^n)$ load is for arbitrary data. A state with a closed-form amplitude pattern — a Gaussian, a uniform superposition, a coherent state, the output of a previous quantum computation — may be preparable in $\mathcal{O}(\text{poly}(n))$ gates. Exercise 22.15 asks you to build one and check whether the advantage returns. It does, and this is not a loophole: it is the actual condition.

3. The QFT is not at the boundary at all. This is the most important one and it is easy to miss. Inside Shor's algorithm the QFT's output is never read as a spectrum. It is measured once, yielding a single integer, which classical post-processing turns into a period (§22.4's continued fractions). The transform sits in the middle of a quantum circuit with quantum data on both sides, so neither the load nor the readout cost is ever paid.

   QFT at the boundary   load 2ⁿ  ->  QFT  ->  read 4ⁿ      dead
   QFT in the interior   quantum  ->  QFT  ->  quantum      fine

The readout problem is a property of the interface, not of the transform. That reframing is what lets you evaluate a proposal in a minute: find where the quantum-classical boundary is, and count what crosses it.

🔬 Honest Assessment — the QFT is not a fast Fourier transform.

You cannot use the QFT to speed up signal processing, image compression, or spectral analysis. Every one of those needs the transformed data as data — all of it, in a form you can compute with — and the QFT does not give you that.

And loading the input has the same problem. Getting a classical signal of $2^n$ samples into a quantum register is $\mathcal{O}(2^n)$ state preparation, unless the signal has structure letting you prepare it efficiently. So the transform is sandwiched between an exponential load and an exponential readout.

This is the same shape as Chapter 21 §21.7's database argument, and it is the single most common way quantum speedup claims go wrong: an exponentially fast subroutine, wrapped in exponential I/O. Chapter 32 will find it again in quantum machine learning, where efficient state preparation from classical data is assumed far more often than it is justified.

What the QFT is actually for is problems where you want ONE number — a period, a phase, an eigenvalue — and the QFT's job is to concentrate that number into a measurable outcome. That is phase estimation, it is genuinely exponentially faster, and it is the rest of this chapter.

22.4 Phase Estimation

Chapter 19 §19.3's phase kickback extracted one bit of phase information. Phase estimation extracts many.

The problem. Given a unitary $U$ and an eigenvector $|\psi\rangle$ with

$$U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle$$

estimate $\varphi$.

The circuit has three stages, and the pattern should look familiar:

   1. SUPERPOSE   H on t counting qubits
   2. KICK BACK   controlled-U^(2^j) from counting qubit j
   3. INTERFERE   INVERSE QFT on the counting register

Stage 2 writes $2^j\varphi$ into the phase of counting qubit $j$ — a binary expansion of $\varphi$ spread across the register. Stage 3's inverse QFT converts that phase pattern into a number you can measure.

This is Chapter 20 §20.1's three-step pattern, with the QFT in place of the final Hadamard layer. The Hadamard layer is the QFT over $(\mathbb{Z}_2)^n$; phase estimation needs the version over $\mathbb{Z}_{2^t}$.

Deriving It, and Why Dyadic Phases Come Back Exact

The whole algorithm is three lines of algebra, and the third line is the reason the measured table below splits into two behaviours.

After stage 1, the counting register is uniform:

$$\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle \otimes |\psi\rangle$$

Stage 2 applies $U^{2^j}$ controlled on counting qubit $j$. Because $|\psi\rangle$ is an eigenvector, $U^{2^j}|\psi\rangle = e^{2\pi i \varphi 2^j}|\psi\rangle$ — the target is untouched and the phase kicks back onto the control. Applying every controlled power in turn, counting qubit $j$ picks up $e^{2\pi i \varphi 2^j}$ exactly when it is $|1\rangle$, so basis state $|x\rangle$ acquires the product of the phases for the bits set in $x$:

$$\frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1} e^{2\pi i \varphi x}\,|x\rangle \otimes |\psi\rangle$$

Now compare that to §22.1's definition of the QFT. Set $N = 2^t$ and $j = 2^t\varphi$:

$$\text{QFT}\,|2^t\varphi\rangle = \frac{1}{\sqrt{2^t}}\sum_{x} e^{2\pi i (2^t\varphi) x/2^t}|x\rangle = \frac{1}{\sqrt{2^t}}\sum_{x} e^{2\pi i \varphi x}|x\rangle$$

They are the same state. Stage 2 does not "encode" $\varphi$ in some indirect way — it produces literally the QFT of the integer $2^t\varphi$. Stage 3's inverse QFT undoes the transform and leaves $|2^t\varphi\rangle$, a basis state, measured with probability 1.

And that is the exactness condition, stated precisely:

$$2^t\varphi \in \mathbb{Z} \;\Longleftrightarrow\; \varphi \text{ is dyadic with } \le t \text{ bits} \;\Longleftrightarrow\; \text{phase estimation is exact}$$

$\varphi = 0.5, 0.25, 0.125$ give $2^3\varphi = 4, 2, 1$ — integers — so the register lands on a single basis state and returns it with certainty. There is no approximation anywhere in the argument, which is why the measured errors are $0.000000$ rather than something small. It is not that the estimate is very good; it is that the circuit is computing an identity.

$\varphi = 1/3$ gives $2^3\varphi = 8/3$, which is not an integer, and the state above is not the QFT of any basis state. The inverse QFT still runs — it is a unitary, it always runs — but it produces a superposition instead of a basis state, and the measurement samples from it.

Measured, estimating known phases with $t$ counting qubits:

     true phase   bits   measured   estimate      error
       0.500000      3        100   0.500000   0.000000
       0.250000      3        010   0.250000   0.000000
       0.125000      3        001   0.125000   0.000000

       0.333333      3        011   0.375000   0.041667
       0.333333      5      01011   0.343750   0.010417
       0.333333      8   01010101   0.332031   0.001302

Two behaviours, and the distinction matters.

Exact when the phase is dyadic. $\varphi = 0.5$, $0.25$, $0.125$ are exactly representable in $t$ bits, and phase estimation returns them with zero error and probability 1.

Approximate otherwise. $\varphi = 1/3$ is not a dyadic rational, so the register holds the best $t$-bit approximation. The error falls as $2^{-t}$:

   t=3:  error 0.041667  ≈  2⁻⁴.6
   t=5:  error 0.010417  ≈  2⁻⁶.6
   t=8:  error 0.001302  ≈  2⁻⁹.6

Each additional counting qubit halves the error. That is the design rule:

$$\text{to resolve } \varphi \text{ to } \pm 2^{-m}, \text{ use } t = m + \mathcal{O}(1) \text{ counting qubits}$$

Where the Rest of the Probability Goes

"Error 0.0417" is the distance from the most likely outcome to the truth. It is not the whole story, because a non-dyadic phase does not give one outcome — it gives a distribution, and knowing its shape is what lets you choose $t$ and the number of repetitions honestly.

Carry the derivation one step further. Applying the inverse QFT to the stage-2 state and reading off the amplitude of outcome $k$:

$$a_k = \frac{1}{2^t}\sum_{x=0}^{2^t-1} e^{2\pi i x\left(\varphi - k/2^t\right)} = \frac{1}{2^t}\cdot\frac{1 - e^{2\pi i 2^t \delta}}{1 - e^{2\pi i \delta}}, \qquad \delta \equiv \varphi - \frac{k}{2^t}$$

a geometric series, whose modulus squared is the Dirichlet kernel:

$$P(k) = \frac{\sin^2\!\left(\pi 2^t \delta\right)}{4^t\,\sin^2\!\left(\pi \delta\right)}$$

Measured against the simulator at $\varphi = 1/3$, $t = 3$ — closed form on the left, statevector on the right:

     k    k/2ᵗ    predicted    simulated         diff
     0  0.0000     0.015625     0.015625     1.4e-17
     1  0.1250     0.031622     0.031622     1.4e-17
     2  0.2500     0.174940     0.174940     1.4e-16
     3  0.3750     0.687838     0.687838     1.0e-15
     4  0.5000     0.046875     0.046875     2.8e-17
     5  0.6250     0.018619     0.018619     1.7e-17
     6  0.7500     0.012560     0.012560     5.2e-18
     7  0.8750     0.011922     0.011922     2.1e-17

Agreement to $10^{-15}$, which is floating-point noise. The formula is the circuit.

Three things to read off it.

The peak is sharp but not certain. $P(k=3) = 0.6878$; the two nearest outcomes together hold $0.8628$. Roughly one shot in seven lands somewhere else entirely.

The tail decays as $1/\delta^2$. For $|\delta| \gg 2^{-t}$ the numerator oscillates between 0 and 1 while the denominator grows, so $P(k) \lesssim 1/(4^t\sin^2\pi\delta)$. Outcomes far from the truth are suppressed quadratically, not exponentially — which is why the far bins in the table are $\sim 0.012$ rather than $\sim 0$.

And there is a floor. The worst case is $\varphi$ sitting exactly halfway between two grid points, $\delta = 2^{-(t+1)}$. Measured:

      t   P(nearest)   two nearest
      3     0.410533      0.821067
      5     0.405610      0.811221
      8     0.405290      0.810580
     16     0.405285      0.810569

     4/π² = 0.405285     8/π² = 0.810569

$P(\text{nearest}) \ge 4/\pi^2 \approx 0.4053$, converging to it from above. That constant is the whole reason the $\mathcal{O}(1)$ in the design rule is a constant: the single-shot success probability never drops below about 40%, no matter how large $t$ gets, so a fixed number of repetitions — or a fixed number of extra qubits — buys any confidence you like.

And notice what does not change with $t$. At $t = 6$ the same phase $1/3$ gives $P = 0.6840$ on the best outcome and $0.1710$ on the second, against $0.6878$ and $0.1749$ at $t = 3$. The shape is essentially fixed; only the grid it sits on gets finer. That is the difference between precision and confidence made visible, and it is exactly what the next callout formalises.

📐 Math Aside — where the extra $\mathcal{O}(1)$ comes from.

With $t$ counting qubits you get the best $t$-bit approximation with high probability, not certainty. The standard result: to obtain $m$ correct bits with success probability at least $1-\epsilon$, use

$$t = m + \left\lceil \log_2\!\left(2 + \frac{1}{2\epsilon}\right) \right\rceil$$

The extra qubits buy confidence, not precision. For $\epsilon = 0.01$ that is about 6 extra qubits regardless of $m$ — a constant, which is why the scaling is clean.

And this is why Chapter 21's quantum counting works. Counting the marked states $M$ is phase estimation applied to the Grover operator, whose eigenvalue phase encodes $\theta$, and $\sin^2\theta = M/N$.

Working the formula gives the overhead directly, and it is worth seeing that it does not move:

   confidence   ε        2 + 1/(2ε)   extra qubits
        90%     0.1             7.0              3
        99%     0.01           52.0              6
      99.9%     0.001         502.0              9

Three qubits per factor-of-ten in confidence, and no dependence on $m$ at all. A 4-bit estimate and a 40-bit estimate both cost 6 extra qubits for 99%. That is the cleanest scaling result in the chapter, and it is what makes phase estimation the routine that survives cost analysis where sampling-based methods do not (§22.6).

Continued Fractions: Getting the Fraction Back

Phase estimation returns $k/2^t$ — a dyadic approximation. But the quantity you want is often a fraction with a small denominator: a period $r$, a count $M$, a rational eigenphase $s/r$. Recovering the exact fraction from the approximation is a classical post-processing step, and it is a solved problem.

The tool is the continued-fraction expansion. If $\varphi = s/r$ and your measured $k/2^t$ satisfies

$$\left|\frac{k}{2^t} - \frac{s}{r}\right| < \frac{1}{2r^2}$$

then $s/r$ is guaranteed to appear among the convergents of $k/2^t$'s continued fraction. That bound is met whenever $2^t > 2r^2$, i.e. $t > 2\log_2 r + 1$ — the standard reason Chapter 23 sizes its counting register at roughly twice the bit-length of the modulus.

Run it on §22.4's own measured bit strings, all for $\varphi = 1/3$:

     t         bits     k       k/2ᵗ            convergents      1/3 found?
     3          011     3        3/8       0, 1/2, 1/3, 3/8            yes
     4         0101     5       5/16           0, 1/3, 5/16            yes
     5        01011    11      11/32     0, 1/2, 1/3, 11/32            yes
     6       010101    21      21/64          0, 1/3, 21/64            yes
     8     01010101    85     85/256         0, 1/3, 85/256            yes
    10   0101010101   341   341/1024       0, 1/3, 341/1024            yes

Every one of them recovers $1/3$ exactly — including $t = 3$, where the raw estimate was $0.375$ and the error a fat $0.0417$. The criterion explains why:

   t=3:  |3/8 - 1/3| = 0.041667  <  1/(2·3²) = 0.055556   ✓ (barely)
   t=8:  |85/256 - 1/3| = 0.001302  <  0.055556           ✓ (comfortably)

★ This changes what "error 0.0417" means. The $t = 3$ estimate is 12% off as a number and perfectly correct as a fraction. If what you want is $r$, three counting qubits sufficed; if what you want is $\varphi$ to four decimals, they did not. The precision you need is set by the question, and the raw error column answers a different question than the one Chapter 23 asks.

This is also the third escape from §22.3's readout problem in action: the QFT's output crosses the quantum–classical boundary as one integer, and everything after that is arithmetic on a laptop.

When the Input Is Not an Eigenvector

The derivation assumed $U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle$. In practice you frequently cannot prepare an eigenvector — if you could prepare the ground state of a molecular Hamiltonian you would not need to estimate its energy — so it is worth knowing what the circuit does when you feed it something else.

The circuit is linear, so it does the obvious thing. Expand the input in the eigenbasis, $|\phi\rangle = \sum_i c_i|\psi_i\rangle$; each component drives its own phase estimation, and the counting register ends up in a superposition of the corresponding peaks. Measuring collapses onto one of them with probability $|c_i|^2$.

Measured. Take $U = P(2\pi \times 0.25)$, whose eigenphases are $0$ on $|0\rangle$ and $0.25$ on $|1\rangle$, and prepare the target in $|+\rangle$ — an equal superposition of both eigenvectors — with $t = 4$:

     k    k/2ᵗ           P
     0  0.0000    0.500000
     4  0.2500    0.500000

Exactly half and half, both peaks perfectly sharp. Not a smeared average of $0$ and $0.25$; two correct answers, each returned half the time.

This is what makes Chapter 23 possible. Shor's algorithm needs an eigenvector of modular multiplication, and those eigenvectors depend on the period $r$ — the thing you are trying to find. The resolution is that $|1\rangle$ is an equal superposition of all $r$ of them, so running phase estimation on $|1\rangle$ returns one randomly chosen $s/r$, uniformly over $s$. You never prepare an eigenvector; you prepare a superposition of all of them and let the measurement pick. The continued fractions above then recover $r$ from whichever $s$ you got.

And it is what makes energy estimation risky. If your trial state has overlap $|c_0|^2 = 0.1$ with the ground state, you get the ground-state energy 10% of the time and excited-state energies the rest — correct answers to questions you did not ask. The overlap, not the circuit, sets the repetition count.

🐛 Debug This — phase estimation returning a plausible wrong number.

The characteristic failure is not garbage. It is a clean, sharp, confident peak in the wrong place — which is far harder to notice than noise, and is exactly Case Study 2's warning applied one layer up.

Four causes, in the order they are worth checking:

```text symptom likely cause

bit string reversed vs expected QFT convention (§22.1) estimate is 1 - φ instead of φ forward QFT, not inverse sharp peak, wrong value, P ≈ 1 wrong controlled power 2^j two or more sharp peaks input is not an eigenvector ```

The check that separates all four costs one run: estimate $\varphi = 0.25$ first.

A dyadic phase must come back with error exactly $0.000000$ and $P = 1.0000$. There is no statistical slack in that — §22.4's derivation shows the circuit is computing an identity. So:

  • Right value, $P = 1$ → the machinery is correct; any problem is with your $U$ or your eigenvector.
  • Wrong value, $P = 1$ → structural. Convention, inversion, or power sequence. Not shots.
  • Right value, $P < 1$ → your inverse QFT is approximate (§22.5) or your $U$ is noisy.
  • Two peaks → your "eigenvector" is a superposition; check $U|\psi\rangle \propto |\psi\rangle$ directly with Statevector.

The instinct to reach for more shots is wrong in three of the four cases, and it is the expensive one. A structural bug produces $P = 1$ on the wrong answer; adding shots makes you more confident of it.

🧪 Run It — watch the distribution, not just the argmax.

Every table in this section reports max(counts). That throws away the informative part. Replace it with the full distribution and the diagnostics above become visible at a glance:

```python from qiskit.quantum_info import Statevector

qc = phase_estimation(1/3, t=6) # without the measure instructions probs = Statevector(qc).probabilities(range(6)) for k in probs.argsort()[::-1][:5]: print(f"{k:>4} {k/2**6:>9.6f} {probs[k]:>9.6f}") ```

text 21 0.328125 0.683979 22 0.343750 0.171041 20 0.312500 0.042806 23 0.359375 0.027418 19 0.296875 0.014019

A statevector run costs no shots and has no sampling error, so the numbers are the true distribution rather than an estimate of it. Two peaks means the wrong input state; a flat spread means the wrong $U$; a sharp single peak in the wrong place means a convention error. All three are one glance apart and none of them is visible in an argmax.

Then compare against the Dirichlet formula above. Agreement to $10^{-15}$ says your circuit is the textbook circuit; disagreement localises the bug before you have spent a single shot.

22.5 The Approximate QFT

The controlled-phase angles halve at every step: $\pi/2$, $\pi/4$, $\pi/8$, …, down to $2\pi/2^n$.

The far ones are almost the identity. At $n = 16$ the smallest rotation is $2\pi/65536$ — an angle smaller than any hardware can reliably apply, and smaller than the noise floor.

So drop them. Keep only rotations between qubits within distance $c$, and the result is the approximate QFT.

Measured at $n = 8$, against the exact QFT:

   cutoff   cp gates   fidelity    gate saving
        1          7   0.458548          75.0%
        2         13   0.852517          53.6%
        3         18   0.970902          35.7%
        4         22   0.995137          21.4%
        5         25   0.999341          10.7%
        7         28   1.000000           0.0%

Cutoff 3 gives 97% fidelity for 36% fewer gates. Cutoff 4 gives 99.5% for 21% fewer.

Why Dropping Them Is Nearly Free

"The far rotations are almost the identity" is the intuition. The standard way to make it rigorous is to bound the error by the sum of the dropped angles: each omitted $P(\theta)$ differs from the identity by $\lVert P(\theta) - I\rVert = 2|\sin(\theta/2)| \le \theta$, and errors add at worst linearly. At distance $d$ there are $n - d$ such gates, each of angle $2\pi/2^{d+1}$, so

$$\varepsilon(c) \;\le\; \sum_{d=c+1}^{n-1} (n-d)\,\frac{2\pi}{2^{\,d+1}}$$

Measured against the actual infidelity at $n = 8$:

   cutoff   fidelity   infidelity   angle bound   bound/measured
        1   0.458548     0.541452      7.878525            14.6×
        2   0.852517     0.147483      3.166136            21.5×
        3   0.970902     0.029098      1.202641            41.3×
        4   0.995137     0.004863      0.417243            85.8×
        5   0.999341     0.000659      0.122718           186.3×
        6   0.999944     0.000056      0.024544           434.6×

★ The bound holds, and it is loose — and it gets looser exactly where you would want to use it. At cutoff 3 it overstates the damage 41-fold; by cutoff 6, 435-fold. The ratio roughly doubles at every step (41.3 → 85.8 → 186.3 → 434.6).

That doubling is not an accident, and the reason is one line. The bound is first order in the dropped angle. Fidelity is second order: for a small unitary perturbation $e^{i\theta A}$, the overlap with the identity goes as $\cos\theta \approx 1 - \theta^2/2$, so the infidelity scales as $\theta^2$. Each increment of the cutoff halves the dropped angles, which halves the bound and quarters the true infidelity — so the ratio between them doubles.

$$\text{bound} \sim \theta \qquad \text{true infidelity} \sim \theta^2 \qquad \Longrightarrow \qquad \frac{\text{bound}}{\text{true}} \sim \frac{1}{\theta} \sim 2^{c}$$

This is the honest answer to "is the standard bound tight?" — no, and predictably not. Exercise 22.28 asks you to reproduce it. Use the bound to prove an asymptotic statement; use the measurement to choose a cutoff. Sizing a real AQFT from the worst-case bound will cost you several unnecessary rotations per qubit, and at $n$ in the thousands that is not a rounding error.

The standard rule is $c = \mathcal{O}(\log n)$, and the saving grows with size:

     n     full cp gates    cutoff = ⌈log₂n⌉    AQFT gates    saved
     8                28                   3            18    35.7%
    16               120                   4            54    55.0%
    32               496                   5           145    70.8%
    64             2,016                   6           363    82.0%

At $n = 64$ the AQFT uses 18% of the gates. For Shor's algorithm on a cryptographic modulus, where $n$ is in the thousands, this is not an optimization — it is what makes the circuit expressible at all.

The AQFT Inside Phase Estimation, Which Is What Actually Matters

The fidelity column above measures the AQFT as a transform, in isolation. Almost nobody uses it that way. It is used as the third stage of phase estimation, and the question that decides whether you can afford it is not "how close is the unitary?" but "does the algorithm still return the right number?"

Those turn out to be very different questions. Driving §22.4's circuit with an AQFT inverse at $t = 8$, exact statevector probabilities, no shot noise:

   φ = 1/3 (non-dyadic)                  φ = 0.25 (dyadic)
   cutoff   estimate     P(best)         cutoff   estimate    P(best)
        1   0.332031    0.239770              1   0.250000   1.000000
        2   0.332031    0.539788              2   0.250000   1.000000
        3   0.332031    0.656108              3   0.250000   1.000000
        4   0.332031    0.677595              4   0.250000   1.000000
        5   0.332031    0.683064              5   0.250000   1.000000
    exact   0.332031    0.683922          exact   0.250000   1.000000

★★ The estimate never changes. At every cutoff, for both phases, the most likely outcome is bit-for-bit identical to the exact QFT's. The approximation does not move the answer — it only moves the confidence.

And for the dyadic phase it does not even do that. An AQFT with cutoff 1 has transform fidelity $0.4585$ — it is barely the QFT at all — and it still estimates $\varphi = 0.25$ with probability exactly $1.000000$.

Sweeping more phases shows the rule, and it is exact:

   φ            binary       bits b   smallest cutoff giving P = 1.000000
   0.5          0.1_2             1                                  ≤ 1
   0.25         0.01_2            2                                    1
   0.125        0.001_2           3                                    2
   0.6875       0.1011_2          4                                    3
   1/256        0.00000001_2      8                            not by 5

$$\textbf{An AQFT with cutoff } c \textbf{ is exact on any phase whose binary expansion terminates within } c+1 \textbf{ bits.}$$

Which follows immediately from §22.4's derivation: a phase needing $b$ bits produces a state whose product form couples qubits at most $b-1$ apart, and rotations beyond that distance were multiplying by 1 anyway. The AQFT is not approximating those cases — it is dropping gates that do nothing.

For the non-dyadic phase the cost is real but small. Retained success probability relative to the exact QFT:

   φ           c=1      c=2      c=3      c=4    exact
   0.25     1.0000   1.0000   1.0000   1.0000   1.0000
   0.6875   0.5901   0.9619   1.0000   1.0000   1.0000
   1/3      0.3506   0.7893   0.9593   0.9907   1.0000

Cutoff 3 keeps 95.9% of the success probability of the exact transform, using 18 rotations instead of 28, and — again — with zero change to the estimate itself.

📊 What the Numbers Say — 0.970902 is not the number you want.

The transform fidelity at cutoff 3 is 0.9709. The retained success probability at cutoff 3 is 1.0000 for $\varphi = 0.25$ and $\varphi = 0.6875$, and 0.9593 for $\varphi = 1/3$.

The fidelity is wrong in both directions, and neither error is small. It is pessimistic by 3% on the dyadic phases, where the AQFT is perfect. It is optimistic by 1.2% on $1/3$, where the AQFT is slightly worse than the fidelity implies.

The reason is that unitary fidelity averages over all input states, and phase estimation does not feed it all input states — it feeds it exactly the states stage 2 produces. A figure of merit that averages over inputs your algorithm never sees is measuring something adjacent to your question.

This is a specific instance of a shape Part V hits six times: a measurement that cannot detect the thing being asked about. Chapter 30 §30.4 found a chip's median gate error predicting circuit fidelity within 12%, while §30.3 found the same chip's quoted two-qubit error ranging over a factor of 9.6 depending on how you aggregate it. The aggregate that is easiest to quote was not the one that predicted anything.

Report the fidelity if you like. Decide on the success probability. They cost the same to compute, and only one of them is denominated in the units of your actual problem.

📉 Noise Report — on hardware, the AQFT can be more accurate than the exact QFT.

§22.5 argues the far rotations are below the noise floor. Make it quantitative. At $n = 16$ the smallest rotation is

$$\frac{2\pi}{65536} = 9.587 \times 10^{-5}\ \text{rad}$$

Chapter 30 §30.1 read a real backend's two-qubit error distribution off its Target:

text two-qubit (ecr), 144 entries min 0.00347 median 0.00750 p95 0.01999 mean 0.01018

A rotation of $10^{-4}$ radians is more than an order of magnitude below even the best gate on the chip, and two below the median. Executing it does not add signal; it adds a gate.

The breakeven is a one-line calculation, to first order in the gate error. Dropping from cutoff 7 to cutoff 3 at $n = 8$ removes 10 cp gates, which §22.2's transpiler measurement puts at 2 cz each — 20 two-qubit gates removed. It costs $0.029$ in transform infidelity. So it is worth doing whenever

$$20 p \;>\; 0.029 \qquad\Longrightarrow\qquad p \;>\; 0.00145$$

Chapter 30's median two-qubit error on a real device is 0.00750 — five times the breakeven, and even its best edge at 0.00347 is more than twice it. On that chip, at that size, the approximate QFT is not a compromise. It is the more accurate circuit.

Where this flips: on a simulator, where $p = 0$ and the AQFT is strictly worse; and under error correction, where $p$ is engineered to $10^{-10}$ or below and the calculus inverts completely — at which point the reason to use an AQFT is §22.6's rotation-synthesis cost instead, which is a different argument reaching the same conclusion.

🔀 In Another Framework — Cirq and PennyLane, and a convention result that cuts against expectation.

Qiskit Cirq PennyLane
exact QFT QFTGate(n) cirq.qft(*qubits) qml.QFT(wires=...)
skip the swaps decompose and edit without_reverse=True not exposed
inverse .inverse() inverse=True keyword qml.adjoint(qml.QFT(...))
approximate build it yourself build it yourself build it yourself
unitary Operator(qc).data circuit.unitary() qml.matrix(op)

None of the three ships an approximate QFT, which is the practical reason §22.5 is a build-it-yourself section and why vqelab/qft.py exists.

Now the measurement. Case Study 2 warns that "matches Qiskit" and "computes the DFT" can come apart, citing Chapter 18 §18.2's finding that Qiskit is the endianness outlier among three frameworks. Checking all three against the DFT matrix directly at $n = 3$:

text qiskit QFTGate(3) fidelity vs DFT = 1.000000 cirq cirq.qft(*q) fidelity vs DFT = 1.000000 pennylane qml.QFT(wires=range(3)) fidelity vs DFT = 1.000000

All three agree, with each other and with the mathematics. For the QFT specifically, the outlier result does not reproduce — the frameworks have converged on the same convention, and porting a QFT between them is safe.

What is not safe is the flag. Cirq exposes the swap-layer choice §22.1 warns about, and turning it on gives you one of the wrong conventions with a keyword argument:

text cirq.qft(*q, without_reverse=True) fidelity vs DFT = 0.500000 cirq.qft(*q), qubit_order reversed fidelity vs DFT = 0.393306

0.500 and 0.393 — two more plausible-looking wrong numbers, reachable without writing a single line of circuit construction. The lesson survives intact and moves target: the danger is not the framework, it is the option.

22.6 What a QFT Costs

The QFT is built from arbitrary-angle controlled rotations, and Chapter 19 §19.5 measured that rotations are the expensive thing under error correction — they are not primitives, and each must be synthesized into Clifford+T at a precision-dependent cost.

Chapter 15's estimator prices them separately from T gates, and the AQFT's saving shows up directly:

   n = 16, rotations sequential

   full QFT   120 rotations  ->  190,970 physical qubits,  10,067 μs
   AQFT c=4    54 rotations  ->  121,690 physical qubits,   4,576 μs

36% fewer qubits and 55% less runtime, for a 99.5%-fidelity approximation.

Where the T Gates Actually Are

"Rotations are expensive" is the summary. The distribution behind it is sharper and more useful than that, and it is measurable directly: translate each of the QFT's controlled phases into a Clifford+T basis and count.

   distance d   cp angle   T + T†   cx   total gates
            1     2π/4          3    2             5
            2     2π/8        381    2           970
            3     2π/16       369    2           917
            4     2π/32       375    2           938
            5     2π/64       378    2           951
            6     2π/128      384    2           998
            7     2π/256      372    2           946

★★ Two findings, and both are counterintuitive.

First: there is a cliff between distance 1 and distance 2 — 3 T gates against 381, a factor of 127. $\text{CP}(\pi/2)$ decomposes into three $P(\pi/4)$ rotations, and $P(\pi/4)$ is the T gate, so the whole thing is exact Clifford+T with three T gates. $\text{CP}(\pi/4)$ decomposes into three $P(\pi/8)$ rotations, and $P(\pi/8)$ is not in Clifford+T at all — it must be approximated. The cliff is the boundary of exact representability, and it lands one distance earlier for a controlled gate than for a bare one, because the control halves the angle.

Second, and this is the one people get wrong: the cost does not depend on the angle. Distance 7's rotation is 64 times smaller than distance 2's and costs 372 T gates against 381 — the same, within the synthesiser's run-to-run variation. Synthesis cost is set by the target precision, not by how small the rotation is. A near-identity rotation is not a cheap rotation.

Which reverses the naive reading of §22.5. You do not drop the far rotations because they are cheap. You drop them because they cost as much as the near ones and contribute almost nothing. That is a much stronger argument, and it is the reason the AQFT's saving lands where it does.

Whole circuits at $n = 8$, transpiled to Clifford+T:

   circuit             cp   T + T†   total gates   T saved
   AQFT cutoff=1        7       21            47     99.7%
   AQFT cutoff=2       13    2,307         5,873     70.9%
   AQFT cutoff=3       18    4,152        10,439     47.6%
   AQFT cutoff=4       22    5,652        14,199     28.7%
   AQFT cutoff=5       25    6,786        17,052     14.4%
   full QFT            28    7,926        19,919      0.0%

An 8-qubit QFT is 7,926 T gates. For scale, Chapter 19 §19.5's 8-bit oracle was 26,978 T gates without ancillas and 55 with — so a QFT of the same width is a third of the bad oracle and 144 times the good one. The transform is not the cheap part of anything.

The per-distance table reconstructs the whole-circuit table exactly. At $n = 8$ there are $n - d$ gates at distance $d$, so cutoff 3 predicts $7(3) + 6(381) + 5(369) = 4{,}152$ — the measured value, to the gate. Nothing is hiding in the transpiler.

And the AQFT's T-gate saving beats its gate saving at every cutoff:

   cutoff   gate saving   T-gate saving
        3         35.7%           47.6%
        4         21.4%           28.7%

Cutoff 3 removes 36% of the gates and 48% of the T gates, because every gate it removes is on the expensive side of the cliff while 7 of the 18 it keeps are on the cheap side. The metric that matters under error correction improves faster than the metric that is easy to count — which is, unusually for this book, a case where the easy number understates the win.

The cutoff-1 row is the extreme case. 21 T gates for the whole circuit: a 377× reduction, because all seven surviving rotations are exact Clifford+T. As a transform it is useless, at fidelity 0.4585. As the inverse QFT inside phase estimation for a 2-bit dyadic phase, §22.5 measured it returning the right answer with probability exactly 1.0000. Same circuit, 377× cheaper, no loss — provided you know what you are asking it.

💰 Cost and Queue — what the AQFT is worth, in the two regimes.

Today, on hardware. §22.2 measured the 8-qubit QFT at 56 cz with free connectivity and 95 on a line; the AQFT at cutoff 3 needs 36 and 69. Chapter 39 §39.2 clocked the real transpiled QFT-8 at 10.55 μs per shot, 43.20 ms for 4,096 shots. Scaling that by the ideal-connectivity two-qubit gate ratio ($36/56$) predicts roughly 28 ms for the same job — about 15 ms saved. That is a projection from two measurements, not a measurement; the real device would route the AQFT differently.

That is nothing, and it is the point. Chapter 39 §39.3 measured device utilization at 2.31 × 10⁻⁵ for a 6.92 ms job behind a five-minute queue — 43,340× more wall clock than execution. Shaving 15 ms off a job that waits five minutes is not an optimization anyone will notice. On today's hardware the AQFT is worth using for accuracy (see the Noise Report above), not for time.

Under error correction the arithmetic inverts. §22.6's estimate at $n = 16$: full QFT 190,970 physical qubits and 10,067 μs; AQFT cutoff 4 121,690 and 4,576 μs. That is 69,280 physical qubits freed — and Chapter 15 §15.8 measured a single T gate driving a small circuit from 450 to 2,882 physical qubits, a 6.4× jump for one gate, with §15.7 finding T factories consuming 93% of a small circuit's physical qubits.

The AQFT's saving is denominated in factories. It is not shaving milliseconds off a queue; it is removing thousands of T gates whose magic-state supply is the dominant hardware cost of the whole machine. This is the book's "every remedy is denominated in the currency of the disease" running the right way for once: the disease is T gates, and the remedy is measured in T gates.

🗝️ Version Note — rotationDepth is not optional, and omitting it produces nonsense.

Sweeping rotationCount with rotationDepth left at 0:

text rotations physical qubits runtime μs 27 1,230,570 189.2 54 1,579,050 308.0 90 4,060,890 466.4 120 1,299,610 1,284.4 <- FEWER qubits than 90

Non-monotonic: 120 rotations reports fewer physical qubits than 90. The estimator has switched to a different space–time tradeoff point — note the runtime nearly tripling as the qubit count drops. It is Chapter 15 §15.8's T-factory saturation in a new guise.

Setting rotationDepth to the actual sequential depth fixes it:

text rotations depth physical qubits runtime μs 0 0 7,290 57.6 27 27 112,010 2,189.2 54 54 121,690 4,576.0 120 120 190,970 10,067.2 monotonic in both columns

A QFT's rotations are largely sequential, so rotationDepth ≈ rotationCount is the honest input. Leaving it at 0 tells the estimator every rotation happens in parallel, which is both false and the reason the numbers stop making sense.

The Route That Survives the Shot Budget

There is one more cost worth pricing here, and it is not the QFT's — it is the reason anyone tolerates the QFT's cost at all.

Chapter 36 §36.7 prices variational chemistry at the scale where it would matter. Estimating a single energy at 50 orbitals by VQE:

   VQE at 50 orbitals        1.91 × 10²⁰ shots     6.06 × 10⁸ QPU-years
   every negotiable factor
   deleted (no 2p+1, no
   200 iterations)           6.10 × 10¹¹ shots            1.94 QPU-years

Two QPU-years for one energy evaluation, after removing everything that could be removed. That is the arithmetic phase estimation exists to escape, and §36.8 names it explicitly: the route that survives the arithmetic is the one that needs fault tolerance.

The structural reason is a change of exponent. An expectation value estimated by sampling converges as $1/\sqrt{N}$, so precision $\epsilon$ costs $\mathcal{O}(1/\epsilon^2)$ shots. Phase estimation does not sample the quantity at all — it writes it into a register — and §22.4's design rule says precision $2^{-m}$ costs $t = m + \mathcal{O}(1)$ qubits, i.e. $\mathcal{O}(\log(1/\epsilon))$ qubits and $\mathcal{O}(1/\epsilon)$ applications of $U$.

$$\text{VQE: } \mathcal{O}(1/\epsilon^2)\ \text{shots} \qquad\text{versus}\qquad \text{QPE: } \mathcal{O}(1/\epsilon)\ \text{depth}$$

Size the register for chemistry, using this chapter's own formula. Chapter 36 §36.4's active-space error of 0.0201 Ha is quoted as 12.6× chemical accuracy, which puts chemical accuracy at 0.0016 Ha. To resolve that over a spectral range normalised to 1 Ha:

   m = ⌈log₂(1/0.0016)⌉                       = 10 precision bits
   t = m + ⌈log₂(2 + 1/(2×0.01))⌉ = 10 + 6    = 16 counting qubits
   controlled-U applications = Σ 2ʲ = 2¹⁶ - 1 = 65,535

Sixteen counting qubits and 65,535 applications of the time-evolution operator — against $6.10\times10^{11}$ shots for the same answer by VQE. Nine orders of magnitude, and the register is smaller than the molecule.

🔬 Honest Assessment — the nine orders of magnitude are a change of currency, not a discount.

Those 65,535 applications are sequential and coherent. Not 65,535 independent shots that can be spread across a queue, retried, or averaged — one unbroken circuit, and every one of them is itself many Trotter steps, so the real depth is larger by another substantial factor.

VQE pays in shots. Phase estimation pays in coherent depth. Shots are a currency NISQ hardware has, in quantities that turn out to be unaffordable. Coherent depth of $10^5$ or more is a currency NISQ hardware does not have at all — Chapter 39 §39.6 measured T1 across a device at 15.2 to 483.0 μs (median 174.9) against §39.2's cz at 68–184 ns, which caps a physical circuit in the thousands of gates, not the millions.

This is "every remedy is denominated in the currency of the disease" in its sharpest form in the book. The remedy for an impossible shot budget is an impossible depth budget, and the only thing that converts one into the other is error correction. Chapter 25 §25.10 prices that, and §22.6's estimate above — 190,970 physical qubits for a 16-qubit QFT alone — is a preview of what the conversion rate looks like.

What this chapter can honestly claim is that phase estimation is the route whose scaling does not disqualify it. Not that it is available. Chapter 40's six head-to-head comparisons found zero quantum wins on present hardware, and nothing in this section contradicts that.

🧱 Project Checkpoint — vqelab/qft.py: transform, estimate, approximate.

qft_circuit(n, cutoff=None) builds the QFT in the convention that matches Qiskit's QFTGate, with a cutoff parameter giving the AQFT. Its docstring records the three conventions that do not match and the fidelities they produce, because §22.1's trap costs an afternoon.

verify_against_dft(n) compares the constructed unitary against a NumPy-built DFT matrix — the reference-value habit from Chapter 7 §7.7, applied to a circuit rather than an expectation value.

phase_estimation(unitary, eigenstate, counting_qubits) returns a PhaseEstimate carrying the measured value, the bit string, whether the phase was dyadic (hence exact), and the expected error bound $2^{-t}$.

counting_qubits_for(precision, confidence) implements $t = m + \lceil\log_2(2 + 1/2\epsilon)\rceil$, so the register size is computed rather than guessed.

aqft_fidelity(n, cutoff) measures §22.5's table for your own $n$, and qft_cost(n, cutoff) prices it with rotationDepth set correctly — the Version Note's trap, encoded.

Its tests assert: the construction matches QFTGate to $10^{-9}$ and matches the DFT matrix; the three wrong conventions are detected as wrong; dyadic phases estimate exactly; non-dyadic error falls as $2^{-t}$; AQFT fidelity increases monotonically with cutoff and reaches 1.0; and qft_cost is monotonic in rotation count when depth is set.

22.7 Summary

The QFT is exactly the discrete Fourier transform — verified against the DFT matrix to $10^{-10}$ at $n = 2, 3, 4$ — built from $n$ Hadamards and $n(n-1)/2$ controlled phase rotations plus a swap layer.

⚠️ Three of the four plausible qubit-ordering conventions give a wrong answer with no error. Only descending order with final swaps matches Qiskit's QFTGate (fidelity 1.000 against 0.265, 0.250, 0.250). Verify against a reference before building on it.

It uses exponentially fewer operations than the classical FFT — $\mathcal{O}(n^2)$ against $\mathcal{O}(N\log N)$, or 136 gates against a million at $n = 16$.

★★ And that is not an exponential speedup, because you cannot read the output. One measurement gives one integer; extracting $2^n$ amplitudes needs tomography at $\mathcal{O}(4^n)$. Loading the input is equally bad: an arbitrary classical signal costs $\mathcal{O}(2^n)$ to prepare. The transform is sandwiched between an exponential load and an exponential readout — the same failure shape as Chapter 21's database argument, and the most common way quantum speedup claims go wrong. You cannot use the QFT to speed up signal processing.

What it is for is phase estimation, where you want one number and the QFT concentrates it into a measurable outcome. The circuit is Chapter 20 §20.1's three-step pattern with the QFT replacing the final Hadamard layer — because the Hadamard layer is the QFT over $(\mathbb{Z}_2)^n$.

★ Phase estimation is exact for dyadic phases — $\varphi = 0.5, 0.25, 0.125$ returned with zero error — and approximates otherwise, with error falling as $2^{-t}$: estimating $1/3$ gave errors of 0.0417, 0.0104, 0.0013 at 3, 5, and 8 counting qubits. Each qubit halves the error. Extra qubits beyond the target precision buy confidence, not precision: $t = m + \lceil\log_2(2 + \frac{1}{2\epsilon})\rceil$, about 6 extra for 99%.

★ The approximate QFT drops the small rotations. At $n = 8$: cutoff 3 gives 97% fidelity for 36% fewer gates; cutoff 4 gives 99.5% for 21% fewer. With the standard $c = \mathcal{O}(\log n)$ rule the saving grows — 82% at $n = 64$ — and for Shor at cryptographic sizes it is what makes the circuit expressible at all.

★★ And the AQFT's approximation does not move the answer — only the confidence. Driving phase estimation with an AQFT inverse at $t = 8$, the estimate is bit-for-bit identical at every cutoff, including cutoff 1 whose transform fidelity is 0.4585. Dyadic phases are returned with probability exactly 1.000000 at every cutoff, because an AQFT with cutoff $c$ is exact on any phase terminating within $c+1$ bits. For $\varphi = 1/3$, cutoff 3 retains 95.9% of the exact transform's success probability. The 0.9709 transform fidelity is wrong in both directions — pessimistic on dyadic phases, optimistic on $1/3$ — because it averages over inputs the algorithm never sees.

⚠️ The standard sum-of-dropped-angles bound is loose, and gets looser where you would use it. At $n = 8$ it overstates the true infidelity 14.6× at cutoff 1 and 434.6× at cutoff 6, doubling each step — because the bound is first order in the dropped angle and infidelity is second order. Prove asymptotics with the bound; choose a cutoff by measurement.

Rotations, not T gates, dominate the QFT's fault-tolerant cost, since each arbitrary rotation must be synthesized into Clifford+T. Measured at $n = 16$: full QFT 190,970 physical qubits / 10,067 μs; AQFT cutoff 4, 121,690 qubits / 4,576 μs — 36% fewer qubits and 55% less runtime.

★★ There is a 127× cliff at qubit distance 1, and beyond it the cost is flat in the angle. $\text{CP}(\pi/2)$ translates to 3 T gates; every longer-range controlled phase costs ~375, whether its angle is $2\pi/16$ or $2\pi/256$. Synthesis cost is set by target precision, not by how small the rotation is — so you drop the far rotations not because they are cheap but because they cost as much as the near ones and contribute nothing. Whole circuits at $n = 8$: full QFT 7,926 T gates; AQFT cutoff 3, 4,152 — a 47.6% T saving for a 35.7% gate saving, and cutoff 1 costs 21 T gates, a 377× reduction, because all seven surviving rotations are exact Clifford+T.

Under the transpiler an 8-qubit QFT's 28 controlled phases become 56 cz with free connectivity, 95 on a line, and — Chapter 39 §39.2 — 137 on a real device. A 2.4× spread from routing alone. One cp costs two cz and twelve single-qubit gates.

⚠️ Set rotationDepth. Left at 0 the estimator is non-monotonic — 120 rotations reporting fewer qubits than 90 — because it silently switches space–time tradeoff points. A QFT's rotations are sequential, so rotationDepth ≈ rotationCount is the honest input.

Next: Chapter 23 — Shor's algorithm. Simon's algorithm (Chapter 20) over $\mathbb{Z}_N$ instead of $(\mathbb{Z}_2)^n$, with this chapter's phase estimation in place of the Hadamard layer and continued fractions in place of Gaussian elimination. It is the algorithm that made everyone care, and the one place in this book where an exponential speedup, a useful problem, and a satisfiable set of conditions all coincide.