Rational reconstruction from a phase sample

Input. Integers $N\ge 1$, $Q>4N^2$, and $y\in \{0,\dots ,Q-1\}$, with $Q=2^m$ and $y$ the label from Quantum phase estimation when this routine is called from QPE.

Output. A reduced fraction $p\mathrm{/}q$ with $1\le q\le N$, or FAIL.

Instructions. Set $u:=y$, $v:=Q$, and $j:=0$. Repeatedly divide $u$ by the positive integer $v$, obtaining the unique quotient $a_j$ and remainder $r_j$ with $u=a_{j}v+r_j$ and $0\le r_j<v$. Append $a_j$; if $r_j=0$, stop, and otherwise set $(u,v):=(v,r_j)$, increment $j$, and repeat. For $y=0$ this immediately gives the one-digit expansion $[0]$; for every other input, The continued-fraction algorithm terminates exactly on rational numbers gives termination and the resulting normalized finite expansion is the one in Denominator-bounded rational phase reconstruction. Starting from $p_{-2}=0,p_{-1}=1,q_{-2}=1,q_{-1}=0$, process the digits in order using $p_j=a_j{p}_{j-1}+p_{j-2}$ and $q_j=a_j{q}_{j-1}+q_{j-2}$; this lists all convergents including the terminal one by Convergents of a regular continued fraction. For each convergent, reject it if $q>N$; otherwise compute $2\mathrm{\mid }yq-pQ\mathrm{\mid }$ exactly and accept it precisely when this integer is at most $q$. Return the first accepted candidate, or FAIL if none exists. The uniqueness result lem-qa-rational-reconstruction-candidate-uniqueness shows there cannot be two. The algorithm makes no floating-point comparison. Its deterministic bit bound is proved separately in thm-qa-rational-reconstruction-bit-cost, which also establishes that these instructions terminate.