Continued Fractions

After the quantum period-finding circuit runs and you measure the ancilla register, you do not read off the period $r$ directly. What you get is an integer $m$ close to a multiple of $Q/r$, where $Q$ is the size of the ancilla register. Recovering $r$ from $m$ is a classical step that relies on the continued-fraction algorithm.

What the measurement tells you

Suppose the ancilla has $n$ qubits, so $Q = 2^n$. The QFT concentrates probability near the multiples $k\,Q/r$ for $k = 0, 1, \ldots, r-1$. A single measurement gives some integer $m$ that satisfies

$\left|\frac{m}{Q} - \frac{k}{r}\right| \le \frac{1}{2Q}$

for some unknown integer $k$ with $0 \le k < r$. Dividing both sides shows that $m/Q$ is within $1/(2Q)$ of the rational number $k/r$. Because $r \le N$ and we choose $Q \ge N^2$, this bound is tight enough to uniquely identify $k/r$ from $m/Q$ via continued fractions.

Continued fractions in one paragraph

Every real number $x$ has a continued-fraction expansion

$x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots}}}$

where $a_0 = \lfloor x \rfloor$ and the process repeats on the fractional part. The truncated expansions $p_j/q_j$ (called convergents) are the best rational approximations to $x$ with denominator at most $q_j$. The classical algorithm computes them in $O(\log Q)$ steps using the Euclidean algorithm.

The algorithm step by step

Given integer $m$ and register size $Q$, proceed as follows:

1. Set the working fraction to $m / Q$ (track numerator and denominator as integers).
2. Compute partial quotients $a_i = \lfloor \text{num}/\text{den} \rfloor$ and update via $(\text{num}, \text{den}) \leftarrow (\text{den},\; \text{num} - a_i \cdot \text{den})$.
3. Build convergent denominators with the recurrence

$q_i = a_i \, q_{i-1} + q_{i-2}, \quad q_{-1} = 0,\quad q_0 = 1.$

4. Stop at the first $q_i$ that exceeds $N$; the previous $q_{i-1}$ is the candidate period.
5. Verify classically that $a^{q_{i-1}} \equiv 1 \pmod{N}$; if not, re-run the circuit.

A concrete example

Take $N = 15$, $a = 7$, and $n = 8$ qubits so $Q = 256$. The true period is $r = 4$ (since $7^4 = 2401 \equiv 1 \pmod{15}$). The QFT peaks near multiples of $Q/r = 64$.

For the measurement $m = 63$: the fraction is $63/256$. Step by step:

• $a_0 = \lfloor 63/256 \rfloor = 0$, remainder $63$; convergent denominator $q_0 = 1$.
• $a_1 = \lfloor 256/63 \rfloor = 4$, remainder $256 - 4 \cdot 63 = 4$; $q_1 = 4 \cdot 1 + 0 = 4$.
• $a_2 = \lfloor 63/4 \rfloor = 15$; $q_2 = 15 \cdot 4 + 1 = 61 > N = 15$, so stop.

We return $q_1 = 4$. Indeed $7^4 \bmod 15 = 1$, so $r = 4$ is confirmed.

Try it

Implement the continued-fraction convergent finder: given $m$, $Q$, and bound $N$, return the denominator of the best convergent of $m/Q$ whose denominator does not exceed $N$.

The grader checks that your function returns $4$ for the example above ($m=63$, $Q=256$, $N=15$), which is the period $r = 4$ of $7^x \bmod 15$.

Sign in on the full site to ask questions and join the discussion.