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

A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted.

1. Function promised to be periodic → The period, recoveredsample twice, test convergents of the ratio

   Algorithm 3.1 treats the period $S$ as an irrational quantity that cannot be landed on exactly: approximation: the periodic function is replaced by an $\varepsilon$-pseudo-periodic one, $f(k)=f(k+[iS])$, where $[iS]$ denotes $iS$ rounded down or up. Given an upper bound $M$ on $S$, it fixes $q\ge 3M^2$, Fourier samples $f$ over $\mathbb{Z}_q$ twice to get integers $c$ and $d$, and takes the continued-fraction expansion of $c/d$; each convergent $k_i/l_i$ approximates the ratio of two integer multiples of $q/S$, so rounding each $k_iq/l_i$ to the nearest integer, testing it against the verification procedure — which also accepts integer multiples of $S$ — and keeping the smallest candidate that passes recovers a value within 1 of $S$. assumption: this needs an efficient procedure that verifies whether a candidate is a multiple of $S$, and $f$ injective on the $\varepsilon$-fraction of offsets where it is pseudo-periodic, succeeding, for any period $S$ above an absolute constant, with probability $\Omega(\varepsilon^2/(\log M)^4)$.

   approximationassumption

The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.

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

Hallgren's later paper calls this a special case of the next method rather than a parallel one: "Solving Pell's equation is a special case of the more general problem of finding the unit group of a number field." The two are kept as separate nodes because the techniques are separably hard rather than nested — the rank-1 construction here does not generalise on its own, and the lattice route needed new machinery for the rounding noise that appears only in higher rank. A reader should hold both facts: mathematically one contains the other, and as algorithms they were solved apart.

• Pell's equation by computing the regulator · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  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.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

• The principal ideal problem in a real quadratic field · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

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

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

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