Period finding over the reals

• Recover the period of a periodic function

  Given a function you can evaluate in superposition and a promise that it repeats, find what it repeats by. This is the engine underneath factoring, discrete logarithms and a row of classical number-theory problems that had no efficient algorithm at all — and the whole difficulty is that the period is read out of an interference pattern rather than looked up.

Hallgren is explicit that this is a different method and not a re-run of Shor's: the principal ideal problem "reduces to a discrete log type problem, but there is no longer an underlying group. Instead, a group-like subset of the reals modulo an irrational number is used. This prevents direct application of Shor's algorithms." He names the technique and its limit in the same breath — "Fourier sampling can only be performed over finite groups... In this work we extend Fourier sampling to non-finitely generated groups, as there will be an underlying periodic function over the reals whose period we wish to approximate" — and states where the new difficulty sits: "The general idea for the algorithm is the same as in Shor's discrete log algorithm, but we have new technical difficulties because we are computing modulo an irrational number."

Every step this method names moves its route along, so there is nothing it needs alongside them.

given  f : Z -> X, epsilon-pseudo-periodic with real period S              (Def. 3.1)
       # f(k) = f(k + [iS]) for at least an epsilon-fraction of offsets
       #   k in {0, ..., floor(S)}, where [iS] means iS rounded down OR up --
       #   the discretisation this method needs because S is irrational and
       #   no q makes f exactly periodic on any finite grid
       f injective across that epsilon-fraction of pseudo-periodic offsets  (Alg. 3.1, Input)
       verify(T), an efficient procedure that accepts when T is within 1
           of S, or within 1 of an integer multiple of S                    (Def. 3.2)
       an upper bound M on S                                                (Alg. 3.1, Input)
    # verify() is ASSUMED, not built: the paper takes it "for the sake of
    #   simplicity", noting one exists in the Section 3.2 application       (Sec. 3.1)

requires  S greater than some absolute constant -- below it the success
    probability this method relies on is not claimed to hold. The lemma
    states no numeric value for that constant; the log M >= 262 that
    appears in Claim 3.1 is an interior step of the proof, not a stated
    precondition of the method                                              (Lemma 3.1)

# --- fix a modulus large enough to resolve S from the samples --------------
choose an integer  q >= 3*M^2                                               (Alg. 3.1, step 1)
    # the proof needs q >= 3*S^2 for the continued-fraction bound and
    #   q >= S^2 for the final rounding bound; M >= S makes step 1 cover
    #   both, which is the only reason the bound M is required at all       (Lemma 3.1, proof)

# --- Fourier sample f twice over Z_q ---------------------------------------
c = Fourier-sample f over Z_q
d = Fourier-sample f over Z_q                                               (Alg. 3.1, step 2)
    # each sample lands within 1/2 of an unknown integer multiple of the
    #   irrational q/S:  c = round(k*q/S),  d = round(l*q/S),  for unknown
    #   integers k <= l <= S
    # one sample alone is useless: the multiple is unknown. Dividing the two
    #   cancels q/S and leaves k/l; dividing c back by k then returns q/S
    #   itself, and S with it                                               (Sec. 3.1)

# --- recover k from the continued fraction of the ratio --------------------
expand c/d as a continued fraction, with convergents k_i/l_i                (Alg. 3.1, step 3)
    # written k_i/l_i here rather than the paper's own c_i/d_i, so the names
    #   do not collide with the samples c and d -- one of which the next
    #   line needs by name
    # k/l is a convergent of c/d whenever |c/d - k/l| <= 1/(2*l^2), which
    #   q >= 3*S^2 secures                                                  (Lemma 3.1, proof)
for each convergent k_i/l_i:
    candidate = round(k_i * q / c)                                          (Alg. 3.1, step 4)
        # nearest integer. The denominator is the FIRST Fourier sample c --
        #   one fixed integer, the same for every convergent -- not the
        #   convergent's own denominator l_i. Only the numerator k_i is
        #   taken from the convergent; l_i serves only to pick it out
        # this is the quantity the correctness bound is proved for:
        #   if c = round(k*q/S) and q >= S^2 then |S - round(k*q/c)| <= 1    (Lemma 3.1, proof)
    if verify(candidate):
        keep candidate

return  the smallest kept candidate                                         (Alg. 3.1, step 5)
    # an integer within 1 of S, in time polynomial in log S -- an
    #   approximation, not S exactly, since S is irrational and there is no
    #   integer to land on                                                  (Lemma 3.1)
    # succeeds with probability Omega(epsilon^2 / (log M)^4) per attempt.
    #   The three events priced there: f is pseudo-periodic at the measured
    #   offset (probability epsilon, twice over), both samples fall below
    #   q/log M, and k, l are relatively prime                              (Lemma 3.1, proof)
    # that per-attempt figure is far below 1. Repetition is what boosts it,
    #   but Lemma 3.1 itself does not say so -- the boosting statement is
    #   made for the regulator application, where polynomially many
    #   repetitions in log Delta push correctness exponentially close to 1  (Sec. 3.2, Thm. 2 proof)

# if M is not known in advance: start at M = 2, and each time the answer is
#   wrong, double the bound and rerun -- a correct bound is reached, and
#   this method then returns correctly, within a number of doublings
#   polynomial in log S                                                     (Sec. 3.1)
# turning the returned period into a regulator or an ideal's distance is a
#   separate construction, not part of this primitive: the application
#   builds its own pseudo-periodic f_N on the reals and takes N >= 2*sqrt(Delta)
#   to make f_N 1/2-pseudo-periodic with period N*R                         (Lemma 3.2)
# note that q is NOT re-derived against the discriminant there. Its only
#   stated constraint anywhere is step 1's q >= 3*M^2, tied to Delta only
#   indirectly, through M as a bound on the period N*R                      (Sec. 3.1)

Lemma 3.1 prices Algorithm 3.1 itself: given an upper bound $M$ on the period, it returns an integer within 1 of the period $S$ in time polynomial in $\log S$. That is a per-attempt figure — the $\Omega(\varepsilon^2/(\log M)^4)$ success probability recorded above, with $\varepsilon$ the fraction of offsets on which the function is pseudo-periodic, is far below one, so the run has to be repeated. Section 3.2 says what $S$ is for Pell's equation: approximating the regulator $R$ of the order of discriminant $\Delta$ becomes approximating the period $NR$ of a function $f_N$, for an integer $N$ taken large enough relative to $\Delta$, and polynomially many repetitions in $\log \Delta$ push the probability of correctness exponentially close to 1. Theorem 2 is the proved end-to-end statement: the regulator to within $\delta$, in time polynomial in $\log \Delta$ and $\log \delta$.

• Quipper's `cl` program — stage 1 of the class-number algorithm, the circuit that approximates the regulator of $\mathbb{Q}(\sqrt{\Delta})$

  • Quipper: A Scalable Quantum Programming Language
  • Quipper: Concrete Resource Estimation in Quantum Algorithms

  Written to be counted, not to settle a mathematical question. Quipper was built inside IARPA's Quantum Computer Science program, which picked seven algorithms as benchmarks and asked for each to be coded far enough that gates could be tallied; Hallgren's was one of them, and the resource-estimation paper lists it as "Class Number (CL). To approximate the class group of a real quadratic number field". The module header states the target — the program "computes various invariants of a real quadratic number field $K = \mathbb{Q}(\sqrt{\Delta})$, notably the class number and the structure of the class group $CL(K)$", with "the field $K$" specified "by its discriminant $\Delta$, the main input to the algorithm" — and adds that it "may also be adapted to other problems from algebraic number theory, including Pell's equation (finding integer solutions to $x^2 - dy^2 = 1$, for non-square $d$) and the principal ideal problem". Five stages are named there, and the first is exactly this method: "Approximate the regulator of $K$, to low precision, using a version of the the (quantum) HSP algorithm." The doubled word is in the source. Its mathematical references are Hallgren's STOC 2002 paper, which the header notes was "Also published in J. ACM, 54(1), 2007" — this record's own citation — together with Richard Jozsa's 2003 notes on it, which the code follows section by section, and Haase and Maier. The implementation is credited to Keith Kim, Peter LeFanu Lumsdaine and Alexandr Virodov, and is "based on a detailed algorithm specification that was provided to us by the IARPA QCS program and written by Brian J. Matt, Durward McDonell, and David Zaret".

  Stage 1 is `approximate_regulator_circuit` in `Quipper/Algorithms/CL/CL.hs`, and its five commented steps are one Fourier sample rather than a rendering of the method's own five-step listing — all five sit inside step 2 of that listing: initialise a register of `q` qubits, `mapUnary hadamard` across it, apply `q_fN`, measure and `cdiscard` the second register, `qft_int`, measure. The `q` there is a length and not a modulus, and the file says so three lines above the code — "q is the register length, and Q = 2^q (qq in Haskell code) the number of states" — so `q = 2 + 2 * i` fixes the modulus at $Q = 2^q = 4M^2$, with the source's own justification "So 2^q = 4 * (s_bound^2), the first power of 2 assumed to be above 3 S^2"; that is step 1's condition $Q \ge 3M^2$, with the bound $M = 2^i$ supplied as a command-line argument. The two samples the method insists on, rather than one, are taken by `try_approximate_regulator`, which runs that circuit twice under independently drawn random "jitter" offsets from `getStdRandom $ randomR (0, 16*qq - 1)` and then builds candidates by `convergents $ continued_list (fromIntegral c) (fromIntegral d)` and `round $ c_n * (fromIntegral qq) / (fromIntegral c)`. That last expression is the one to read against `Auxiliary.hs`, because it does not say what it looks like it says: `convergents :: (Integral int, Fractional a) => [int] -> [a]` returns each convergent as a value $h_i/k_i$, never as its numerator, so what the code rounds is $h_i Q/(k_i c)$. The lambda's bound variable is even named `c_n`, which is Jozsa's name for the numerator, and Jozsa's Section 10 — the passage the doc comment cites — asks for the numerator alone: "for each convergent $c_n/d_n$ of the continued fraction of $c/d$ we check if $c_n = k$ by computing $m = \lfloor c_n q/c \rceil$". The method's own listing asks for the same thing. Code and source therefore differ by a factor of the convergent's denominator, and nothing in the package exercises the difference: the only two lines that call `convergents` on a continued fraction outside stage 1 are commented out in `Test.hs`. Candidates are then filtered by `verify_period_multiple`, the paper's assumed `verify` made concrete, and it too comes up one step short of its own comment. That comment reasons that since "for any ideal $I$, $\rho(\rho(I))$ is distance $> \ln 2$ from $I$, it suffices to check whether the unit ideal is within 4 steps either way", and Jozsa likewise builds the neighbours "by applying $\rho$ and $\rho^{-1}$ to $I_m$, up to four times"; but the body tests `unit_ideal bigD` for membership in `[jj] ++ (take 4 $ iterate rho jj) ++ (take 4 $ iterate rho_inv jj)`, and `iterate` starts at its own argument, so `take 4` is three applications and seven ideals are tested where nine were asked for. The smallest survivor is returned, `head $ sort $ candidate_ms`. `approximate_regulator` supplies the outer loop over an unknown bound and the repetition that boosts a per-attempt probability far below one, in a single expression: `[ replicate (36*i) (try_approximate_regulator bigD i) | i <- [1..] ]`. The quantum arithmetic beneath $f_N$ is `Quipper/Algorithms/CL/RegulatorQuantum.hs` — `q_normalize`, `q_rho_d`, `q_rho_inv_d`, `q_rho_red_d`, `q_rho_inv_red_d`, `q_dot_prod`, `q_dot_prod_with_dist`, `q_star_prod`, `q_star_square`, and `q_fN` itself, whose header identifies it as "the function $h$ of [Jozsa 2003], Sec. 9, discretized with precision $1/N$" and perturbed by the jitter parameter. Six of those are separately printable from the command line, `rho`, `rhoinv`, `normalize`, `dotprod`, `starprod` and `fn`.

  No dataset, and no file the program reads. The inputs are command-line integers, and there is more than one of them: the discriminant $\Delta$, defaulting to 28 and rejected by `is_valid_bigD` if it is not a discriminant; the stage-1 bound, given either as `-s`, "estimated bound on period S, for stage 1", default 2, or as `-i`, a bound on $\log_2 S$, default 1; the stage-4 parameters `-r`, `-q`, `-k`, `-n` and `-m`; and a random seed. Everything else in a run is derived from $\Delta$ and $i$ inside `Quipper/Algorithms/CL/Types.hs`. `length_for_ab bigD = 3 + (ceiling $ logBase 2 $ fromIntegral bigD)` sets the width of the coefficients of reduced ideals, `length_for_ml` the width for general ideals, `n_of_bigD` the discretisation precision — "Taken to ensure $1/N < 3/(32 \Delta \log \Delta)$" — and `precision_for_fN _ n l = 2 * (n + l)` the intermediate distance precision. Three of those four carry the authors' own warning that no proof stands behind them, and a reader costing this circuit should carry the warning too. `length_for_ml` is annotated "TODO: bound this! Neither Hallgren nor [Jozsa 2003] discusses bounds on the values of $m$ and $l$ that will appear, and we do not yet have a bound. For now we use the same length as for $a$ and $b$, for convenience; this should be considered a dummy bound, quite possibly not sufficient in general". `precision_for_fN` is "just a back-of-the-envelope estimate, which should be sufficient and $O$(correct), but is almost certainly rather larger than necessary". And `length_for_ab`, whose bound the entry above uses, ends its own note "For now, this padding is a seat-of-the-pants estimate". The only non-source files in the released tarball are the README, COPYRIGHT, ChangeLog, the cabal file and documentation images.

  The Hackage package `quipper-algorithms`, version 0.9.0.0, maintained by Peter Selinger, homepage http://www.mathstat.dal.ca/~selinger/quipper/ ; Haskell. Its cabal file declares `license: BSD3` with `license-file: COPYRIGHT`, and COPYRIGHT carries "Copyright (C) 2011-2019. All rights reserved.", a three-clause BSD text whose third clause is "The name of the authors and copyright holders may not be used to endorse or promote products derived from this software without specific prior written permission", and the note that the work "was supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center contract numbers D11PC20168 and D12PC00527". The algorithm is nine modules under `Quipper/Algorithms/CL/`; read from the released tarball on 2026-08-27 they are `Types.hs` at 639 lines, `RegulatorQuantum.hs` at 504, `Auxiliary.hs` at 482, `CL.hs` at 473, `RegulatorClassical.hs` at 417, `Main.hs` at 395, `Test.hs` at 227, `RegulatorTemplate.hs` at 190 and `SmithReduction.hs` at 165 — 3,492 lines together, with `programs/cl.hs` building the `cl` executable on top of them. The ChangeLog dates the release "December 29, 2019: Release 0.9.0.0", and Hackage's `preferred` endpoint returned 0.9.0.0 as the only version on 2026-08-27, so there is no later tag to check against. The same files in their pre-2019 module layout sit as `Algorithms/CL/` in thephoeron/quipper-language, which is an unofficial mirror rather than a GitHub fork — the API reports it as an independent repository — last pushed on 2015-08-31; the eight modules of that vintage total 3,339 lines, `RegulatorTemplate.hs` having not yet been split out, with a Makefile and a Makefile.dep beside them. That mirror is the readable copy, and Hackage is the artefact.

  No gate count for this algorithm appears in either Quipper paper or anywhere in the distribution, and none is quoted here from a neighbouring algorithm; the IARPA-QCS-era QuRE resource report, which may well carry one, could not be retrieved, as apps.dtic.mil answered with HTTP 403. The resource-estimation paper names CL as one of the seven benchmarks and states that all seven "are running, in the sense that one can generate the circuit (and portion thereof)", but the only concrete figure it prints is for triangle finding — "a count of 30,189,977,982,990 (over 30 trillion) total gates and 4676 qubits". The machinery to produce the CL number does ship: `gatecount` is one of the documented output formats and the module's own sample invocation is `./cl -S starprod -d 60 -f gatecount`. No recorded output for it appears anywhere in the distribution, and no Haskell toolchain was present where this was read, so nothing is asserted about what it prints. What the source fixes without any run is the shape of the stage-1 circuit at the defaults $\Delta = 28$ and $i = 1$: register length $q = 4$ and so modulus $Q = 16$, $n = 10$, $l = 4 + q + n = 18$ "Chosen to give: $L = 16QN$", $t = 7$, and $2(n + l) = 56$ bits of intermediate distance precision — arithmetic on the formulas quoted above, not execution, and worth re-deriving rather than trusting, since $n$ is a ceiling of $\log_2 995.2$. Three limits matter more than any count would. Stage 4's quantum functions do not exist — "The key functions for stage 4 are not yet implemented" — and `main_stage4` prints its arguments and stops, so the flag that asks for a stage-4 circuit emits none. `class_number`, the function the whole program is named for, is defined in `CL.hs` and reachable from no command-line flag: `main` dispatches only to the two stages, a named subroutine, the regulator, the fundamental unit and the Pell solution. And the last three of those — the three answers the tool will actually compute — are each labelled by the program itself "by classical period-finding"; the path that simulates the quantum circuit through `run_generic_io` exists inside `try_approximate_regulator`, and nothing on the command line calls it.

• ScaffCC's Class Number benchmark — the oracle for $f_N$ compiled to a flat Toffoli circuit

  • ScaffCC: Scalable Compilation and Analysis of Quantum Programs

  A compiler benchmark rather than a mathematical result, and it reaches this method by way of what was actually compiled. ScaffCC is an LLVM-based compiler for the Scaffold language, and its authors needed programs large enough to test whether compilation scales at all; Class Number is one of the apps shipped in the repository's `Algorithms/` directory, described in the README as "A problem from computational algebraic number theory, to compute the class group of a real quadratic number field", parameterised "by p, the number of digits after the radix point for floating point numbers used in computation". The paper's citation for it is Hallgren's later unit-group and class-group paper, which belongs to the neighbouring method; the artefact that was built does not. The compiled file opens "Class Number Algorithm -- Phase I (estimate the regulator)", byte-identical to the opening of the readable driver `cnum/cnp1.c` sitting beside it, and the oracle inside it is the one this method is about — `cnum/fn.c` calls itself "the main entry point for the oracle function that implements $f_N$, the oracle function which enables approximation of the regulator". The class-group half exists only as uncompiled sketch: `cnp2.c`, "Class Number Algorithm -- Phase II (structure of the class group)", together with `ghat.c`, `fjn.c`, `h.c` and `xd.c`, the four routines its body calls.

  Two layers, and they are not the same artefact. `Algorithms/Class_Number/cnum/` holds readable Scaffold-flavoured C. `cnp1.c` is the Phase-I driver; `fn.c` is its oracle, walking reduced ideals out from the unit ideal, taking two $\rho$ steps, then star-products to jump past the target distance and back down, then $\rho$ steps to land — and it returns nothing at all: `rkqc fn(int bound, int delta, ideal_t *j, int *dist)` has no `return` statement, and its last line writes `floor(N * (bound - j->d))` into the `*dist` out-parameter. `rho.c` gives $\rho$ and $\rho^{-1}$ from the identity that "4a divides $\Delta - b^2$", and its note on the inverse is worth keeping: the GFI "does not specify how to compute" it, so "I did the algebra by hand. It should probably be double-checked by someone (note: I just found parts of Jozsa's paper that back up part of my implementation)". `tau.c`, `product.c`, `st_product.c` and `gcd.c` give the ideal arithmetic; `cnp2.c`, `h.c`, `fjn.c`, `ghat.c` and `xd.c` are the Phase-II side, and the call graph says so rather than the file names: `cnp1.c` calls only `fn`, while `cnp2.c` calls `ghat`, `fjn`, `h` and `xd`. `qft.c`, `cnum.scaffold` and the shared header `fn.h` complete the fifteen files. That directory does not compile as written — `gcd.c` assigns from an undeclared `p`, `st_product.c` dereferences `tmp->d` where `tmp` is a value, `rho.c` calls `tau` with two arguments against a three-argument definition — so it is the specification sketch, not the benchmark. The benchmark is `class_number.n06.scaffold`, and its `main()` is the method's outer shape: prepare a register in uniform superposition with `PrepZ` and `H`, run the oracle, measure the oracle's output register in the $X$ basis, apply `qft(in)`, and measure again for the period. Between those sits a block delimited "BEGIN CTQG COMPILATION OF fn()" and "END CTQG COMPILATION OF fn()" — the classical oracle put through ScaffCC's CTQG sub-compiler and emitted as a flat reversible circuit over six-bit registers `bound`, `delta`, `dist`, `ji_a`, `ji_b`, `ji_d` and `ji_k`, four non-empty ancilla arrays and a zero-length `tof_anc`. One structural caveat governs how the file may be read: the superposition register `in` appears at five code sites in the whole file — its declaration at line 72, the `PrepZ` at line 80, the `H` at line 81, the `qft` call at line 2,099,017 and the final measurement at line 2,099,021 — and not one of them is inside the compiled oracle, whose declarations begin at line 92 and whose gates run to line 2,099,005. The oracle is therefore not controlled on the sampling register, so this is an artefact for counting a circuit, not for running the algorithm, and no period could come out of it as it stands.

  No dataset and no input file. Everything is a compile-time constant at the top of `class_number.n06.scaffold`, lines 14 to 20, and the two that matter most are commented out: the discriminant, a 212-digit integer, is a commented-out `define`, and so is the jitter parameter with its range noted as "0<=jp<=16q-1" — the same $16Q$ range Quipper draws its jitter from, which is one sign that both artefacts descend from the same IARPA specification. What remains live is `#define s 4`, `#define q 4*s*s` annotated "q>3*s^2, and q is power of 2", `#define t 10` annotated "t=2[log2(sq(delta))]+i", and `#define n 100`. So the shipped instance runs a 64-qubit sampling register and a 10-qubit oracle output, and $q = 64$ against $3s^2 = 48$ satisfies its own stated condition, which is the method's step 1 with $s$ read as a bound on the period rather than as its logarithm — the opposite of the Quipper entry's convention, where the identifier `q` is the exponent and the modulus is $2^q$.

  The GitHub repository epiqc/ScaffCC, BSD-2-Clause, its LICENSE beginning "Copyright (c) 2018, Scaffold Compiler Working Group"; Scaffold, with the oracle sources in C. `Algorithms/Class_Number/class_number.n06.scaffold` is 87,009,031 bytes and 2,099,025 lines, read on 2026-08-27; `Algorithms/Class_Number/cnum/` holds fifteen files, of which `cnum.scaffold` is 383 lines, `cnp2.c` 108, `fn.c` 63, `rho.c` 43, `cnp1.c` 40, `fjn.c` 40, `st_product.c` 28 and the shared header `fn.h` 9. The compiled file and the sketch directory have different histories, and the difference is load-bearing. The most recent commit touching `class_number.n06.scaffold` is 4d7bfa03 of 2020-04-23, the merge of pull request 40, "Version 5 Upgrade!", and before it 34c3a53f of 2018-06-20, "class number CNOT fix" — that one is worth knowing about, because release 4.0 reversed the argument order of `CNOT` and `Toffoli` across every benchmark, so a gate read out of this file means something different before and after it. `cnum/` has not been touched since fbf13168 of 2018-06-15, "Fix CRLF", and before that 7aceb7c3 of 2017-01-26 and two commits in 2014; neither of the two commits above reaches it. The latest release is 5.0 of 2020-04-24, tagged `5.0` on commit 4d7bfa03, and the previous tag is `v4.0` of 2018-06-30. The repository has a second life as ajavadia/ScaffCC, last pushed 2017-12-07, which is behind on all of this.

  Nothing was run on hardware and no simulator backend is named. The paper names Class Number in its benchmark list and again in running prose — "a major part of the BF, CN and SHA-1 circuits are compiled using the CTQG sub-compiler, which outputs a flat circuit format" — but prints no per-benchmark gate or qubit table anywhere; its only numbered table is a memoization hash-table for speeding up resource analysis. The numbers that exist are in the file itself, counted on 2026-08-27. The CTQG-compiled oracle block contains 2,071,660 `Toffoli`, 26,549 `CNOT` and 693 `X` and nothing else — no rotation, no Hadamard, no measurement — which is what an irreversible classical oracle looks like after reversible synthesis. Outside that block the whole file holds five more `CNOT`, two `Rz`, two `H`, two `PrepZ`, two `MeasX` and two `Swap`, and not one of them is a gate emitted once: the five `CNOT` and the two `Rz` sit inside the reusable `Swap` and `ControlledRotation` module definitions, one `H` and one `Swap` call sit inside the `qft` module definition, the second `Swap` hit is that module's own header and not a gate call at all, and the two `PrepZ`, the second `H` and the two `MeasX` sit inside `main`'s `for` loops over the 64-qubit and 10-qubit registers. A textual count is the wrong instrument for every one of them. Qubits are declared rather than counted: `I0g[58490]`, `I1g[1417]`, `I00[22]` and `I11[7]` are 59,936 ancillas between them, and adding the seven six-bit registers, the 64-qubit sampling register and the 10-qubit output gives 60,052 by my own sum of the declarations. The README states that "default compiler option is to generate resource estimations (number of qubits and gates)", so a reader with the toolchain can get ScaffCC's own figures from `./scaffold.sh Algorithms/Class_Number/class_number.n06.scaffold`; that was not run here, and the counts above are textual counts of the shipped file, not compiler output.

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Different approaches

• Period finding in a finite cyclic group

  Evaluate the function across a superposition of exponents, transform the input register, and measure. What comes back is a multiple of the sample size divided by the period, near enough that a continued-fraction expansion recovers the period exactly — and once it is exact it can be checked classically, so the whole quantum part may fail and be retried.

• Finding a lattice of periods

  Some functions repeat in several independent directions at once, so what is hidden is not one period but a lattice of them. Sampling the dual lattice and reconstructing a basis from the samples replaces the continued fraction, and the rounding that makes real-valued directions representable is what limits how many directions can be handled.

• Pell's equation by computing the regulator

  Given a positive non-square integer d, Pell's equation is x² − dy² = 1 and the goal is to find all integer solutions. The least solution can have exponentially many bits, so it cannot be written down; the computational problem is instead to compute the integer part of the regulator R = ln(x₁ + y₁√d), from which the solution can be recovered.

• The principal ideal problem in a real quadratic field

  Given an invertible ideal I in a real quadratic field, determine whether there exists an α with I = αZ[√d] — that is, whether the ideal is principal — and if there is, find α.

• Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem↗Sean Hallgren · 2007theory yes · simulation ? · hardware no