Period finding in a finite cyclic group

What it fills

• 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.

When it applies

Shor's paper gives the two algorithms separately — "In §5, we give our algorithm for prime factorization, and in §6, we give our algorithm for extracting discrete logarithms" — and both land here because both recover a period in a finite cyclic group. The extraction step is stated as classical post-processing, not as a quantum readout: "We then perform our Fourier transform $A_q$ on the first register... This fraction can be found in polynomial time by using a continued fraction expansion of $c/q$, which finds all the best approximations of $c/q$ by fractions." Discrete log costs more of the same machinery rather than different machinery — "two modular exponentiations and two quantum Fourier transforms" against order finding's one of each — and Shor ties the two together explicitly: "The order of the generator could in fact be computed using the quantum order-finding algorithm given in §5 of this paper."

Requires

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

Example

given  integers n > 1 and x, with r = ord_n(x) the least r > 0 such that
       x^r == 1 (mod n) -- the quantity this procedure recovers   (Sec. 5, before Eq. 5.1)
       a reversible gate array computing a -> x^a mod n                     (Sec. 3)

requires  q, the power of 2 with n^2 <= q < 2n^2; this specific bound is
    what makes d/r unique below                            (Sec. 5, before Eq. 5.1)
    # n, x and q are constants of the run and are never changed, so they
    #   are not written as part of the machine state. The paper adds that
    #   a gate array "need not even keep these values in memory", as they
    #   can be built into the structure of the array -- a permitted
    #   implementation, not a requirement of the construction
    #                                                      (Sec. 5, before Eq. 5.1)

repeat until a candidate r is accepted below:
    # one pass = one "experiment" in the paper's sense, state preparation
    #   through continued-fraction extraction              (Sec. 5, after Eq. 5.13)

    # --- prepare a uniform superposition over the exponent register -------
    |psi_0>  =  (1/sqrt(q))  sum_{a=0}^{q-1}  |a>|0>                    (Eq. 5.1)

    # --- evaluate the function into the second register -------------------
    |psi_1>  =  (1/sqrt(q))  sum_{a=0}^{q-1}  |a>|x^a mod n>            (Eq. 5.2)
        # computed reversibly by the Sec. 3 gate array, kept exact (not
        #   approximated) -- modular exponentiation, not the transform
        #   below, is the bottleneck of the algorithm                   (Sec. 3)

    # --- Fourier transform the first register -----------------------------
    apply A_q : |a> -> (1/sqrt(q)) sum_{c=0}^{q-1} exp(2*pi*i*a*c/q)|c> (Eq. 5.3)
    |psi_2>  =  (1/q)  sum_{a,c}  exp(2*pi*i*a*c/q)  |c>|x^a mod n>     (Eq. 5.4)

    # --- measure both registers -------------------------------------------
    measure  ->  c  and  x^k mod n   for some 0 <= k < r
        # r is never read off directly -- only c and x^k are observed.
        #   Observing c alone would suffice; the second register is kept
        #   only for clarity of the analysis                (Sec. 5, after Eq. 5.4)
        # the analysis shows c concentrates where |{rc}_q| <= r/2  (Eq. 5.7, 5.11)

    # --- classical continued-fraction post-processing ---------------------
    # the concentration condition above is equivalent to
    |c/q - d/r| <= 1/(2q)   for some integers d, r with r < n          (Eq. 5.13)
        # because q > n^2, at most one fraction d/r with denominator below
        #   n satisfies this for the observed c -- so rounding c/q to the
        #   nearest such fraction recovers d/r UNIQUELY   (Sec. 5, after Eq. 5.13)
    expand c/q as a continued fraction; take d/r, in lowest terms, to be the
        best approximation it yields with denominator < n  (Sec. 5, after Eq. 5.13)
        # a classical, polynomial-time computation, not a further quantum
        #   step                                           (Sec. 5, after Eq. 5.13)

    if gcd(d, r) == 1:
        accept r          # leave the loop
    # otherwise this pass yields nothing usable and the loop runs again
    #   from |psi_0> with the same x, n, q
        # a pass reaches the accepting branch with probability at least
        #   phi(r)/(3r), phi = Euler's totient; with phi(r)/r >
        #   delta/log(log(r)) for a constant delta, O(log log r) passes
        #   suffice for high confidence -- proved, not empirical
        #                  (Sec. 5, after Eq. 5.13; Hardy & Wright Thm. 328)

return  r

# deliberately NOT part of this procedure:
# -- recovering a FACTOR of n from r (compute gcd(x^(r/2) - 1, n) for a
#      random x coprime to n) is a separate classical reduction, stated
#      before this algorithm                        (Sec. 5, opening paragraphs)
# -- three classical refinements that trade quantum passes for
#      postprocessing: also trying c +- 1, c +- 2, ... near the observed c;
#      testing small multiples 2r', 3r', ... of a rounded r'; and testing
#      lcm(r1, r2) for two candidate orders. These are not all mere
#      heuristics: the first buys a constant factor, while the second is
#      credited with cutting the expected trials for the hardest n from
#      O(log log n) to O(1) [Odlyzko 1995] and the third with reducing
#      them to a constant [Knill 1995]        (Sec. 5, second-to-last paragraph)
# -- nothing above uses multiplication mod n beyond iterating it: for any
#      permutation f of {0, 1, ..., n-1} whose kth iterate f^(k)(a) is
#      computable in time poly(log n, log k), the same procedure finds the
#      least r with f^(r)(a) = a                        (Sec. 5, final paragraph)

Cost, as the source states it

Order finding (Section 5) is dominated by modular exponentiation of $l$-bit numbers ($n$, $x$, $a$ all $l$ bits): Shor gives a reversible gate array computing $x^a \bmod n$ in $O(l)$ space and $O(l^3)$ time with long multiplication, or $O(l^2 \log l \log\log l)$ time using Schönhage-Strassen multiplication; the Fourier transform $A_q$ on $q = 2^l$ (chosen with $n^2 \le q < 2n^2$) costs $l(l-1)/2$ gates. Combined, the paper states $O((\log n)^2 (\log\log n)(\log\log\log n))$ quantum steps plus a polynomial classical continued-fraction pass. One run returns the order $r$ of $x$ modulo $n$ with probability at least $\varphi(r)/3r$, where $\varphi(r)$ counts the integers below $r$ coprime to it; Shor invokes $\varphi(r)/r > \delta/\log\log r$ for a constant $\delta$, so $O(\log\log r)$ repetitions give high confidence — proved, but no single run is guaranteed to succeed. In discrete log (Section 6) one experiment yields a usable sample with probability at least $1/480$.

Implementations

• Cirq's examples/shor.py order finder — phase estimation on a ModularExp gate that is never decomposed

  Google's Cirq carries this as a runnable command-line demonstration rather than as a library routine, in `examples/shor.py` — a top-level directory beside the `cirq-*` packages rather than inside any of them. From a clone it is importable: `examples/__init__.py` exists and `examples/examples_test.py` reaches the file as `import examples.shor`. It is not in the published distribution — the `cirq_core-1.7.0-py3-none-any.whl` on PyPI, unzipped 2026-08-27, contains no path under `examples/` at all — so this file is obtained by cloning the repository, not by installing `cirq`. Its module docstring states the split this record cares about: the algorithm "consists of two parts: quantum order-finding subroutine and classical probabilistic reduction of the factoring problem to the order-finding problem", and only the first of those is this method. The second — recovering a factor of $n$ from $r$ — is what this record's own listing marks as deliberately not part of the procedure, and the file carries it anyway because the file is a factoring demo. The docstring describes the subroutine as phase estimation on the multiply-by-$x$ unitary rather than as Fourier sampling: "The subroutine for finding the order r of a number x modulo n consists of two steps. In the first step, Quantum Phase Estimation is applied to a unitary such as ... whose eigenvalues are s/r for s = 0, 1, ..., r - 1. In the second step, the classical continued fractions algorithm is used to recover r from s/r." That is a second description of Shor's circuit rather than a second circuit, and the file says so itself at line 189, in `make_order_finding_circuit`'s own docstring: "The circuit uses two registers: the target register which is acted on by U and the exponent register from which an eigenvalue is read out after measurement at the end." The module docstring names its own failure mode in the same paragraph and resolves it exactly as this record does, by classical checking and retry: "Note that when gcd(s, r) > 1 then an incorrect r is found. This can be detected by verifying that r is indeed the order of x. If it is not, Quantum Phase Estimation algorithm is retried."

  `make_order_finding_circuit(x, n)` passes five arguments to `cirq.Circuit`, one of which, `cirq.H.on_each(*exponent)`, expands to one gate per exponent qubit rather than to one operation. It sets $L$ to `n.bit_length()`, takes `target` as $L$ qubits and `exponent` as `cirq.LineQubit.range(L, 3 * L + 3)`, that is $2L+3$ qubits; puts the target into $\lvert 0\ldots01\rangle$ with a single `cirq.X(target[L - 1])`; puts the exponent register into uniform superposition; applies one `ModularExp` gate across both registers; then `cirq.qft(*exponent, inverse=True)` and `cirq.measure(*exponent, key='exponent')`. Two departures from the paper this method is recorded from sit in those lines. **Only the exponent register is measured** — line 216 measures `exponent`, and nothing measures `target` — which is the shortcut this record's own pseudocode already permits, "Observing c alone would suffice; the second register is kept only for clarity of the analysis". **And the transform size is $q = 2^{2L+3}$**, where the paper fixes $q$ by $n^{2} \le q < 2n^{2}$: since $n < 2^{L}$ gives $2n^{2} < 2^{2L+1}$, this $q$ overshoots the top of the paper's window by more than a factor of 4, spending qubits the paper's bound does not ask for — the half of that bound which makes $d/r$ unique is the lower one, $n^{2} \le q$, and a larger $q$ only strengthens it. `ModularExp` overrides the three methods `cirq.ArithmeticGate` requires — the parent's class docstring reads "Child classes must override the `registers`, `with_registers`, and `apply` methods" — and adds two more: an `__init__` that raises `ValueError` when the target register is narrower than `modulus.bit_length()`, and a `_circuit_diagram_info_` that `examples/examples_test.py` covers in a test of its own. `apply` returns `target` unchanged when `target >= modulus`, and otherwise `(target * base**exponent) % modulus` — **a Python integer computation, not a circuit**. The unchanged branch is the identity arm the class docstring writes as $V\lvert y\rangle\lvert e\rangle = \lvert y\rangle\lvert e\rangle$ for $n \le y$, and it is what makes the operator a permutation rather than a partial map. That is the load-bearing qualifier for this entry: `cirq.ArithmeticGate` in `cirq-core/cirq/ops/arithmetic_operation.py` defines `_apply_unitary_` and no `_decompose_` at all — the string "decompose" does not occur in that file — and its own docstring says it "handles the details of ensuring that the scaling of implementing the gate is $O(2^{n})$ instead of $O(4^{n})$ where n is the number of qubits being acted on, by implementing an `_apply_unitary_` function in terms of the registers and the apply function of the child class." The modular exponentiation is therefore executed as a permutation of simulator amplitudes and is never expanded into elementary gates, so this artefact produces no gate count, no $T$-count and nothing a hardware backend could accept — the opposite trade from the Qrisp entry beside it. `quantum_order_finder(x, n)` runs one shot (`cirq.sample(circuit)`, whose `repetitions` parameter defaults to 1 in `cirq-core/cirq/sim/mux.py`), converts the measured integer to a phase in `read_eigenphase` as `exponent_as_integer / 2**exponent_num_bits`, and performs the continued-fraction step with Python's standard library rather than a hand-written expansion: `fractions.Fraction.from_float(eigenphase).limit_denominator(n)`. Note the bound there is $\le n$, where this record's own statement of the algorithm takes the denominator strictly below $n$. It then returns `None` on a zero numerator and, per the record's accept-or-retry structure, on a failed classical check: `if x**r % n != 1: return None`.

  No dataset, and no file is read. The demo's only input is the positional command-line integer `n` (`parser.add_argument('n', type=int, help='composite integer to factor')`) plus a `--order_finder` flag whose choices are `('naive', 'quantum')` and whose default is `'naive'`. The base whose order is sought is not supplied by the user at all: `find_factor` draws it inside its retry loop with `x = random.randint(2, n - 1)`. Everything else — both register widths, the transform size $q = 2^{2L+3}$ implied by the exponent register, the continued-fraction denominator bound — is derived from $n$ inside the code. The only fixed inputs anywhere are the `pytest.mark.parametrize` tuples in `examples/examples_test.py`, quoted under results.

  `examples/shor.py` on the `main` branch of github.com/quantumlib/Cirq — Python, 348 lines and 12861 bytes read 2026-08-27, repository HEAD 18c65870. The repository is Apache-2.0, but **this file carries no copyright header of its own**: its first line is `# pylint: disable=wrong-or-nonexistent-copyright-notice`. The most recent commit touching the file is ea7c94e2, 2025-11-12, "ruff - enable and fix a series of UPNNN rules (pull request 7748)"; the two commits before it are a type-annotation sweep (c45df8b1, 2025-05-20) and a coverage-pragma fix (2fcdeb8d, 2023-08-15), so no commit in this window touched the algorithm. The latest release is v1.7.0 (2026-06-30) and the file is present at that tag, byte-for-byte the same 348 lines. A reader should open, in this order: the module docstring, which is lines 2 to 48 — line 1 is the pylint pragma, and line 47 is the file's only citation, arXiv:quant-ph/9508027; `class ModularExp(cirq.ArithmeticGate)` at line 105, with `apply` at 162; `make_order_finding_circuit` at 180; `read_eigenphase` at 220; and `quantum_order_finder` at 243. Everything below those — `find_factor_of_prime_power`, `find_factor` and `main` at 330 — is the classical factoring reduction this method excludes. `naive_order_finder` is a pure-Python `while y != 1` loop kept as the default so the demo runs without simulation. Tests live in `examples/examples_test.py`, not in a `shor_test.py`; there is no such file in `examples/`.

  **No hardware and no benchmark. The only numbers in the artefact are in the repository's own tests, and they are weaker than they look.** `examples/examples_test.py` exercises the quantum order finder on four pairs, `@pytest.mark.parametrize('x, n', ((2, 3), (5, 6), (2, 7), (6, 7)))`, and wraps each in a retry loop — `for _ in range(15): r = examples.shor.quantum_order_finder(x, n); if r is not None: break` — which is this record's repeat-until-accepted loop written as a test. The largest modulus a circuit is ever built for in that test is $n = 7$, giving $L = 3$ and a 12-qubit circuit. The end-to-end test that uses the quantum order finder is `@pytest.mark.parametrize('n', (4, 6, 15, 125))`, and of those four composites **only $n = 15$ can reach the quantum subroutine at all**: `find_factor` returns 2 for 4 and for 6 at `if n % 2 == 0`, and returns 5 for 125 at `find_factor_of_prime_power`, both before `order_finder` is called. Even $n = 15$ reaches it only sometimes, because `find_factor` draws `x = random.randint(2, n - 1)` and returns immediately when `1 < math.gcd(x, n) < n`, which holds for 6 of the 13 possible draws. The one test that names a large number, `@pytest.mark.parametrize('n', (2, 3, 15, 17, 2**89 - 1))`, calls `examples.shor.main(n=n)`, and **four of those five are not factored at all**: 2, 3, 17 and $2^{89} - 1$, which is the Mersenne prime M89, all return at `find_factor`'s opening `if sympy.isprime(n): return None` at line 305, before any order finder is reached, and `main` prints that $n$ is probably a prime. Only $n = 15$ in that list is factored, and by `naive_order_finder`, which is `main`'s default at line 330. That same prime guard is what makes `test_example_shor_find_factor_with_prime_n` cheap: it runs the seven primes `(2, 3, 5, 11, 101, 127, 907)` against both finders, `examples.shor.quantum_order_finder` included, and asserts `d is None`. The file's own honest summary of the cost is in its argument parser: "note that in practice "quantum" is substantially slower since it incurs the overhead of classical simulation."

• Qrisp's find_order — controlled in-place multiplication on a QuantumModulus, under Montgomery reduction

  • Qrisp: A Framework for Compilable High-Level Programming of Gate-Based Quantum Computers

  Eclipse Qrisp is a Python framework from Fraunhofer FOKUS whose stated distinguishing feature is that its high-level programs compile all the way down to circuits, and its Shor implementation is the example the framework's own paper uses to argue that: the abstract ends "we present a set of code examples, including an implementation of Shor's factoring algorithm. For the latter, the resulting circuit shows significantly reduced quantum resource requirements, strongly supporting the claim that systematic quantum algorithm development can give quantitative benefits." Section 5.4 states the subroutine in the same phase-estimation form the Cirq entry uses — "The quantum subroutine of Shor's algorithm is supposed to find the order of a classically known integer a by performing a quantum phase estimation of an operator, which achieves a modular exponentiation of a. In turn, this is usually translated into a series of controlled modular in-place multiplications followed by an inverse Quantum Fourier Transform" — where the three markers the printed sentence carries have been dropped: two are citations, and the third is a footnote marker sitting immediately after the word "order", pointing at the paper's own definition, "The order of a modular number $a \in \mathbb{Z}/N\mathbb{Z}$ is an integer $r$ such that $a^{r} = 1 \bmod N$". What the paper prints under that sentence is an eleven-line `find_order`, and **it is the tutorial's, not the repository's**: two parameters rather than four, and it ends `return qpe_res.get_measurement()`, so the classical extraction that turns a measured phase into $r$ — the whole post-measurement half of this record's own procedure — appears nowhere in the paper. Where this artefact differs from the Cirq entry is entirely below the surface of that snippet: the paper says its modular arithmetic is built on "The Montgomery reduction algorithm", contrasting it with the construction it displaces, "implementations like [30], which constructs the modular multiplication by performing modular reduction after each addition. While this approach amounts to a more straightforward implementation, the overall amount of non-modular adders is much higher compared to Montgomery reduction" — reference 30 being Beauregard's $2n+3$-qubit circuit for Shor's algorithm. The Montgomery layer follows Rines and Chuang, arXiv:1801.01081, which the framework's Shor tutorial links as "the approach that we are using here".

  `find_order(a, N, inpl_adder=None, mes_kwargs={})` at line 74 allocates a `QuantumModulus(N, inpl_adder)` set to 1, allocates `qpe_res = QuantumFloat(2 * qg.size + 1, exponent=-(2 * qg.size + 1))` — the phase register, sized $2n+1$, with the exponent keyword making it a fixed-point fraction — applies `h(qpe_res)`, and then runs the repeated-squaring ladder: for each index $i$, `with control(qpe_res[i]): qg *= a` followed by `a = (a * a) % N`. There is no inner loop over $2^{i}$ repetitions, and the paper says why: "the group homomorphism property of the in-place multiplication operator $U_x$ can be used to fuse the loop into a singular multiplication with a classically pre-computed multiplication factor", Eq. (19), $(U_x)^n = U_{x^n}$. `QFT(qpe_res, inv=True, inpl_adder=inpl_adder)` closes the estimation and `qpe_res.get_measurement(**mes_kwargs)` reads it. The classical extraction is `extract_order`, which pops measured approximations one at a time, hands each to `get_r_values` — sympy's `continued_fraction_convergents(continued_fraction_iterator(Rational(approx)))`, keeping every convergent denominator greater than 1 — accepts the first $r$ with `(a**r) % N == 1`, and on exhaustion falls back to `np.lcm.reduce` over the Cartesian product of the candidate sets collected so far, which is the third of the classical refinements this record's listing attributes to Knill. **One detail a reader must not skim: the ladder reassigns `a`, so the value `find_order` passes to `extract_order` at line 87 is the fully squared base rather than the original $a$, and `extract_order`'s acceptance test at line 105, `(a**r) % N == 1`, is applied to that value.** Neither the paper's snippet nor the tutorial's own packaged `find_order` — cell 25 of `documentation/source/general/tutorial/Shor.ipynb` — can be set against the repository on that point, because both reassign `a` in place in exactly the same way and neither does any classical extraction at all: both end `return qpe_res.get_measurement()`. The only acceptance test anywhere in the documentation is in the step-by-step walkthrough, where cell 13 keeps a separate `x = a` and cell 21 tests `(a**cand) % N == 1` against the untouched `a`; that walkthrough also drops a filter the shipped code applies, its `get_r_candidates` in cell 17 returning every convergent denominator where `get_r_values` keeps only those greater than 1. `shors_alg(N, ...)` sits above `find_order`: it returns 2 immediately when $N$ is even, otherwise calls `find_optimal_a(N)`, which scans `range(2, min(100, N - 1))` for bases coprime to $N$ and sorts them by a cost built from `find_optimal_m` — the Montgomery shift a given multiplier needs — so the base is chosen to minimise arithmetic width rather than at random, then loops over that sorted list applying the classical reduction `np.gcd(a ** (r // 2) + 1, N)`.

  No dataset; the inputs are two classical Python integers and everything else is derived. `find_order` takes `a` and `N` plus an optional `inpl_adder` callable and a `mes_kwargs` dictionary that, per `shors_alg`'s docstring, "especially allows you to specify an execution backend". The base is not drawn at random: `find_optimal_a` enumerates at most 98 candidates and ranks them by `sum(m_values) + max(m_values) * 1e-5` over the Montgomery shifts of $a^{2^{k}} \bmod N$ and of the modular inverse of its negation, for $k$ up to $2n$. The concrete values that appear anywhere in the documentation are small: $N = 65$ in the `shors_alg` docstring, $N = 99$ with $a = 10$ in the tutorial notebook, $N = 13$ for the `QuantumModulus` warm-up, and $N = 3295$ with multiplier 953 in the fault-tolerant compilation benchmark.

  `src/qrisp/algorithms/shor/shors_algorithm.py` on the `main` branch of github.com/eclipse-qrisp/Qrisp — Python, 171 lines read 2026-08-27, repository HEAD 1366b4dd. Licence is in the file's own header: "Copyright (c) 2026 the Qrisp authors ... SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0". The most recent commit to that file is 798b3ce0, 2026-06-22, "format + quick lint fixes"; the latest release tag is 0.9, published the same day. Five functions to open, all module-level in that file and all reachable as `qrisp.shor` names because `src/qrisp/algorithms/shor/__init__.py` star-imports the module and the module declares no `__all__`: `find_optimal_a` at line 30, `find_order` at 74, `extract_order` at 90, `get_r_values` at 117 and `shors_alg` at 122. Note that **only `shors_alg` and the RSA helpers are on the public API page** — `documentation/source/reference/Algorithms/Shor.rst` autodocs `shors_alg` and autosummarises `rsa_encrypt`, `rsa_decrypt`, `rsa_encrypt_string` and `rsa_decrypt_string`, and the string "find_order" does not occur in it — so the routine that is this method is reachable but undocumented as an entry point. The arithmetic is two directories away and is where the work is: `src/qrisp/alg_primitives/arithmetic/modular_arithmetic/modular_multiplication.py` holds `QREDC` (line 96), `montgomery_red` (157), `find_best_montgomery_shift` (191) and `montgomery_mod_semi_mul` (207) under the line-37 comment "In this file we implement the described techniques for Montgomery reduction"; `find_optimal_m`, which `shors_algorithm.py` imports, is at line 60 of the sibling `modular_qft_multiplication.py`; `montgomery_decoder`, `montgomery_encoder`, `egcd` and `modinv` are in `mod_tools.py`. The `inpl_adder` argument threads an adder choice all the way down, and `documentation/source/reference/Examples/Shor.rst` lists four pre-implemented ones: `fourier_adder`, which it calls the default because "The low qubit count makes it suitable for simulation", `gidney_adder`, `qcla`, and one whose display text there is `cucarro_adder` — a typo, since its own link target is `qrisp.cuccaro_adder`.

  **No hardware run is reported anywhere, and the documented figures are for one primitive, not for a completed order-finding run.** The only end-to-end number is in the `shors_alg` docstring's Examples block, "We factor 65: >>> shors_alg(65)" returning 5, which is a simulator result with no backend, shot count or wall time attached. The resource figures are all for a single controlled modular in-place multiplication at $N = 3295$ by 953, compiled with `t_depth_indicator` at $\varepsilon = 2^{-10}$ and `compile_mcm=True` — and **that worked example exists in two copies which disagree, only one of them executed**. The notebook copy, `documentation/source/general/tutorial/FT_compilation.ipynb`, carries stored stdout: $T$-depth 581 on 68 qubits with `gidney_adder` (cell 25), and $T$-depth 854 on 66 qubits with `qcla` given 10 workspace qubits (cell 27). The markdown immediately below, cell 28, reads "We see that the T-depth is reduced by $\approx 20 \%$", which the two outputs above it reverse, 854 being larger than 581. The second copy, in `documentation/source/reference/Examples/Shor.rst`, carries that identical sentence beside inline figures that would support it — "# Yields 956" and "# Yields 79" for `gidney_adder` against "# Yields 784" and "# Yields 88" for `qcla` — but that copy has not been executed as written: it contains the typo `print(qc.t_depth())s`, and its `qcla` block multiplies by 10 rather than by 953, so its two figures are not one operation measured twice. The framework paper's own comparison is Figure 4, a plot of "Several KPIs of the Shor implementation as described within section 5.4", supporting the claim its Conclusion makes, that "the Qrisp implementation of Shor's algorithm outperformed every Open-Source implementation that we could find". The caption states the assumption that makes the plot readable and warns which way it biases — "we take the extremely conservative assumption, that any arbitrary angle gate has T-count/depth 1. A more realistic estimate would give the Qrisp implementation an edge of approximately 3 orders of magnitude" — so the plotted margin is a floor the authors themselves say understates their result, and no absolute qubit or $T$-count for a full factoring run appears in the paper's text.

What it needs

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

Other ways to fill the same slot

Different approaches

• Period finding over the reals

  When the period is irrational there is no exact answer to land on, so the function is evaluated on a discretisation of the reals and the period is approximated instead. Two samples are taken rather than one, and the continued-fraction step runs on their ratio — the same idea as the integer route, doing a job the integer route cannot do at all.

• 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.

In the Atlas

• Shor period finding

  The cryptography-facing quantum algorithm record, with the assumptions that make its security relevance precise.

• Discrete logarithm on a quantum computer

  Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s.

• Primality proving by quantum order finding

  Prove that a given integer N is prime, or in most cases prove it composite and produce a witness, rather than merely declaring it probably prime as a randomized primality test does.

• Resource counts for elliptic-curve discrete logarithms

  Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level.

Sources

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer↗Peter W. Shor · 1995theory yes · simulation ? · hardware no
• A quantum primality test with order finding↗Alvaro Donis-Vela, Juan Carlos Garcia-Escartin · 2017theory yes · simulation ? · hardware no
• Shor's discrete logarithm quantum algorithm for elliptic curves↗John Proos, Christof Zalka · 2003theory yes · simulation ? · hardware no