<p><b>First some background</b> (that does not fit the comments section) since you asked for pointers:</p>
<ul>
<li><p>The continued fractions-based post-processing algorithm in Shor's order-finding algorithm <a href="https://doi.org/10.1109%2Fsfcs.1994.365700" rel="nofollow noreferrer">[Shor94]</a> <a href="https://doi.org/10.1137%2FS0097539795293172" rel="nofollow noreferrer">[Shor97]</a> can be perceived as a lattice-based post-processing algorithm, that recovers the shortest non-zero vector (solves SVP) in a two-dimensional lattice, see <a href="https://doi.org/10.1145/3655026" rel="nofollow noreferrer">[E24]</a> for the full details (and a literature survey of related previous works, such as <a href="https://doi.org/10.48550/arXiv.1210.3003" rel="nofollow noreferrer">[KW12p]</a>).</p>
<p>The SVP may then in turn be solved using Lagrange's lattice basis reduction algorithm (or with LLL, if you wish, although LLL reduces to Lagrange's algorithm in two dimensions).</p>
<p>(Also, as explained in <a href="https://doi.org/10.1007/s11128-021-03069-1" rel="nofollow noreferrer">[E21b]</a> and <a href="https://doi.org/10.1145/3655026" rel="nofollow noreferrer">[E24]</a>, in general we do not expect to have to run the quantum part of the algorithm more than once to find the order <span class="math-container">$r$</span>, nor to factor <span class="math-container">$N$</span> completely via <span class="math-container">$r$</span>, when using the more elaborate classical post-processing described in these works.)</p>
<ul>
<li><p>To give a brief summary of <a href="https://doi.org/10.1145/3655026" rel="nofollow noreferrer">[E24]</a>:</p>
<p>The frequency <span class="math-container">$j$</span> read out from the quantum part of the order-finding algorithm is likely to be close to an optimal frequency <span class="math-container">$j_0(z) = \lfloor 2^{m+\ell} z \, / \, r \rceil$</span>, where <span class="math-container">$m+\ell$</span> is the control register length, <span class="math-container">$r$</span> is the order and <span class="math-container">$z$</span> is uniformly selected from <span class="math-container">$[0, r) \cap \mathbb Z$</span>. This implies that if we post-process <span class="math-container">$j$</span>, <span class="math-container">$j \pm 1$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$j \pm B$</span>, for <span class="math-container">$B$</span> some bound, then we are like to post-process <span class="math-container">$j_0(z)$</span>.</p>
<p>Consider the two-dimensional lattice <span class="math-container">$\mathcal L$</span> generated by integer multiples of <span class="math-container">$(j_0(z), 1/2)$</span> and <span class="math-container">$(2^{m+\ell}, 0)$</span>. Then the last component of the shortest non-zero vector of <span class="math-container">$\mathcal L$</span> is <span class="math-container">$r / (2 \gcd(r, z))$</span> up to sign, and so we can recover <span class="math-container">$r / \gcd(r, z)$</span>, assuming <span class="math-container">$2^{m+\ell} &gt; r^2$</span>, see Lemma 4.2 in <a href="https://doi.org/10.1145/3655026" rel="nofollow noreferrer">[E24]</a>. See also Lemma 4.1 for the corresponding result for continued fractions-based post-processing, for comparison, and Lemma 4.3 for lattice-based post-processing with enumeration.</p>
<p>This establishes the connection between the continued fraction (CF) algorithm and Lagrange's algorithm (or LLL, if you wish), and shows how the co-primality (CP) requirement enters into the picture, when working in two dimensions.</p>
</li>
</ul>
</li>
<li><p>The idea of generalizing the continued fractions-based post-processing algorithm in Shor's algorithm to higher dimensions was — as far as I know — first introduced by Seifert in <a href="https://doi.org/10.1007/3-540-45353-9_24" rel="nofollow noreferrer">[Seifert01]</a>. The idea is to perform <span class="math-container">$n$</span> smaller runs on the quantum computer, and to jointly post-process the outputs from these runs classically.</p>
<p>Seifert does not speak of lattice-based post-processing, but as explained in App. A and Sect. 6.2 to <a href="https://doi.org/10.1515/jmc-2020-0006" rel="nofollow noreferrer">[E21]</a>, it is possible to use lattice-based post-processing for Seifert's algorithm in analogy with Shor's algorithm.</p>
<ul>
<li><p>To give a brief summary of App. A and Sect. 6.2 in <a href="https://doi.org/10.1515/jmc-2020-0006" rel="nofollow noreferrer">[E21]</a>:</p>
<p>For <span class="math-container">$j_1$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$j_n$</span> the frequencies read out, use LLL (or some other lattice basis reduction algorithm, such as BKZ) to solve SVP or to enumerate all short non-zero vectors in the lattice <span class="math-container">$\mathcal L$</span> generated by <span class="math-container">$(j_1, \ldots, j_n, 1)$</span> and <span class="math-container">$(2^{m+\ell}, 0, \ldots, 0)$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$(0, \ldots, 2^{m+\ell}, 0)$</span>. This with the aim of finding the short vector <span class="math-container">$\vec u = (\alpha_1, \ldots, \alpha_n, r)$</span> and hence <span class="math-container">$r$</span>‚ where <span class="math-container">$\alpha_i = \{ r j_i \}_{2^{m+\ell}}$</span>.</p>
<p>As for the co-primality (CP) requirement, let <span class="math-container">$\gcd(\alpha_1, \ldots, \alpha_n, r) = 2^\kappa o$</span> for <span class="math-container">$o$</span> odd. Then <span class="math-container">$\vec u / (2^t o) \in \mathcal L$</span> for some <span class="math-container">$t \in [0, \kappa] \cap \mathbb Z$</span>, so we risk losing a factor <span class="math-container">$2^t o$</span> for the largest such <span class="math-container">$t$</span>. (In practice, this problem can be solved by more elaborate post-processing. Note also that the problem becomes smaller as <span class="math-container">$n$</span> increases, since <span class="math-container">$\alpha_1$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$\alpha_n$</span> are essentially random.) The analogy to the continued fractions (CF) algorithm is the LLL algorithm.</p>
</li>
</ul>
</li>
</ul>
<p><b>As for Regev's algorithm:</b></p>
<ul>
<li><p>Regev <a href="https://doi.org/10.48550/arXiv.2308.06572" rel="nofollow noreferrer">[Regev23]</a> uses the LLL algorithm to recover vectors in a <span class="math-container">$d$</span>-dimensional lattice <span class="math-container">$\mathcal L$</span> given <span class="math-container">$m$</span> noisy vectors <span class="math-container">$\vec w_1, \ldots, \vec w_m$</span> at most a given distance from vectors <span class="math-container">$\vec v_1, \ldots, \vec v_m$</span> sampled uniformly at random from <span class="math-container">$\mathcal L^* / \mathbb Z^d$</span>. The vectors recovered give rise to factoring relations with a certain probability of success, under a heuristic assumption. That is to say, Regev is not directly performing order finding with respect to a given <span class="math-container">$g \in \mathbb Z_N^*$</span>, as do Shor and Seifert, even if it is a form of order finding.</p>
<p>I discussed your question a bit with my co-author Joel Gärtner today, and as we see it the analogy to the co-primality (CP) requirement in Regev's post-processing is the requirement that the vectors <span class="math-container">$\vec v_1, \ldots, \vec v_m$</span> alongside <span class="math-container">$\mathbb Z^d$</span> generate <span class="math-container">$\mathcal L^*$</span>. Note that by Corollary 4.2 in <a href="https://doi.org/10.48550/arXiv.2308.06572" rel="nofollow noreferrer">[Regev23]</a>, with probability at least <span class="math-container">$1/2$</span>, it suffices to take <span class="math-container">$m = d + 4$</span> for the vectors <span class="math-container">$\vec v_1, \ldots, \vec v_m$</span> to generate <span class="math-container">$\mathcal L^* / \mathbb Z^d$</span>, which is the same requirement. The analogy to continued fractions (CF) is the LLL algorithm.</p>
</li>
<li><p>On a side note, and since you asked for pointers, it is possible to extend Regev's algorithm to an algorithm that performs order finding, with the goal of finding the order <span class="math-container">$\varphi(N)$</span> of <span class="math-container">$\mathbb Z_N^*$</span>, or the order <span class="math-container">$r$</span> of an element <span class="math-container">$g \in \mathbb Z_N^*$</span>. This is explained in App. A to <a href="https://doi.org/10.48550/arXiv.2311.05545" rel="nofollow noreferrer">[EG23p]</a>, connecting Regev's algorithm to the above background section on order finding in a natural way.</p>
<p>(In the former case of computing <span class="math-container">$\varphi(N)$</span>, one can then proceed to factor <span class="math-container">$N$</span>, for instance by randomizing <a href="https://doi.org/10.1016/S0022-0000(76)80043-8" rel="nofollow noreferrer">[Miller76]</a> as explained in <a href="https://doi.org/10.1007/s11128-021-03069-1" rel="nofollow noreferrer">[E21b]</a>. One does furthermore forego squaring the primes in your Step I–II when taking this route, which leads to slight efficiency improvements. In the latter case of computing <span class="math-container">$r$</span>, one has to include <span class="math-container">$g$</span> in the product in your Step II. Again, one can factor efficiently via <a href="https://doi.org/10.1007/s11128-021-03069-1" rel="nofollow noreferrer">[E21b]</a> given the order <span class="math-container">$r$</span> of <span class="math-container">$g$</span>, provided that <span class="math-container">$g$</span> is selected uniformly at random from <span class="math-container">$\mathbb Z_N^*$</span>.)</p>
</li>
</ul>
<p>I do not know if this completely answers all your questions, but it may provide a starting point.</p>

CC BY-SA 4.0
2024-04-05T09:18:13.013Z
Thanks! Indeed, it answers my crucial concern. I can see both algorithms from a common (lattice) perspective. I just finished reading some parts of the references [Ekerå21b/24] and worked out the details to convince myself.
Manish Kumar
CC BY-SA 4.0
2024-04-05T00:41:34.837Z
2024-04-05T00:52:09.510Z
2024-04-05T00:52:09.510Z
Martin Ekerå
<p><a href="https://arxiv.org/pdf/2308.06572.pdf" rel="noreferrer">Regev's factoring algorithm</a> works as follows: (Say, for factoring integer <span class="math-container">$N$</span>; input bitsize <span class="math-container">$n$</span>).</p>
<p><strong>Step I:</strong> Choose <span class="math-container">$a_1,\ ..., a_d$</span> <em>small</em> number (say, squares of first <span class="math-container">$d$</span> primes: (4, 9, 16, ...), where <span class="math-container">$d=\sqrt{n}$</span> (an optimal choice)). [Note-1: This choice paves the way for the speed-up.]</p>
<p><strong>Step II:</strong> Now we solve the muti-dim period-finding problem for the function <span class="math-container">$f:(z_1,..,z_d)\rightarrow \prod_{i=1}^d a_i^{z_i} (mod N)$</span>. [Note-2: Careful examination reveals why we only need to do repeated squaring for <span class="math-container">$\tilde{O}(n^{1.5})$</span>].</p>
<p><strong>Step III:</strong> Similar to the Shor algorithm, (a) use superposition (a Gaussian instead of uniform); (b) implement <span class="math-container">$f$</span> quantumly of step II; (c) use QFT for underlying abelian group.</p>
<p><strong>Step IV:</strong> Now, we run the quantum circuit for <span class="math-container">$\sqrt{n}+4$</span> time (Corollary 4.2) and sample from the state vector. The LLL lattice reduction algorithm guarantees the finding of the period vector with a probability of at least 0.5.</p>
<p>Now, I am trying to relate some of the features of Shor's algorithm to Regev's algorithm.</p>
<p>In Shor's, during the sampling part, it relies on the co-primality fact, i.e., <span class="math-container">$\phi(r)/r\approx \frac{1}{loglog(r)}$</span>, thus repeat the quantum circuit for <span class="math-container">$O(loglog(r))$</span>. This also paves the way for the recovery of the period via continued fraction.</p>
<p>I see Regev's algorithms as a d-dimensional generalization of Shor's algorithms (1-dim problem).</p>
<blockquote>
<p>Can we find the counterpart of co-primality (CP) and continued fraction (CF) in Regev's approach? Or it bypasses these requirements at all.</p>
</blockquote>
<p>My intuition behind the question: I sense Regev's algorithm <strong>might be</strong> generalizing the CP and CF in some way. I suspect the LLL algorithm might be hiding them into its details.</p>
<p><strong>Note</strong>: The LLL algorithm can be seen as a generalization of GCD as per <a href="https://www.di.ens.fr/%7Epnguyen/SLIDES/SlidesLuminy2010.pdf" rel="noreferrer">this</a>. I can see GCD as a test of co-primality. Still, I am expecting to see the connection more explicitly.</p>
<p>I would highly appreciate some pointers in the comment section, too.</p>

CC BY-SA 4.0
2024-03-29T15:51:44.707Z
What is the coprimality and CF analogy?
Turbo
CC BY-SA 4.0
2024-03-29T17:50:33.653Z
@Turbo, thanks. I have rephrased it to be more precise about the 'CF analogy' statement.
Manish Kumar
<quantum-computing><factoring><primes><integer-lattice>
Comparing Shor's and Regev's Quantum Factoring algorithm
Manish Kumar
# Comparing Shor's and Regev's Quantum Factoring algorithm

(Asked by: username_0 on 2024-03-29)

[Regev's factoring algorithm](https://arxiv.org/pdf/2308.06572.pdf) works as follows: (Say, for factoring integer $N$; input bitsize $n$).

**Step I:** Choose $a\_1,\ ..., a\_d$ *small* number (say, squares of first $d$ primes: (4, 9, 16, ...), where $d=\sqrt{n}$ (an optimal choice)). [Note-1: This choice paves the way for the speed-up.]

**Step II:** Now we solve the muti-dim period-finding problem for the function $f:(z\_1,..,z\_d)\rightarrow \prod\_{i=1}^d a\_i^{z\_i} (mod N)$. [Note-2: Careful examination reveals why we only need to do repeated squaring for $\tilde{O}(n^{1.5})$].

**Step III:** Similar to the Shor algorithm, (a) use superposition (a Gaussian instead of uniform); (b) implement $f$ quantumly of step II; (c) use QFT for underlying abelian group.

**Step IV:** Now, we run the quantum circuit for $\sqrt{n}+4$ time (Corollary 4.2) and sample from the state vector. The LLL lattice reduction algorithm guarantees the finding of the period vector with a probability of at least 0.5.

Now, I am trying to relate some of the features of Shor's algorithm to Regev's algorithm.

In Shor's, during the sampling part, it relies on the co-primality fact, i.e., $\phi(r)/r\approx \frac{1}{loglog(r)}$, thus repeat the quantum circuit for $O(loglog(r))$. This also paves the way for the recovery of the period via continued fraction.

I see Regev's algorithms as a d-dimensional generalization of Shor's algorithms (1-dim problem).

> Can we find the counterpart of co-primality (CP) and continued fraction (CF) in Regev's approach? Or it bypasses these requirements at all.

My intuition behind the question: I sense Regev's algorithm **might be** generalizing the CP and CF in some way. I suspect the LLL algorithm might be hiding them into its details.

**Note**: The LLL algorithm can be seen as a generalization of GCD as per [this](https://www.di.ens.fr/%7Epnguyen/SLIDES/SlidesLuminy2010.pdf). I can see GCD as a test of co-primality. Still, I am expecting to see the connection more explicitly.

I would highly appreciate some pointers in the comment section, too.

**Tags:** quantum-computing, factoring, primes, integer-lattice

> **Comments:**
> **username_1**: What is the coprimality and CF analogy?  
> **username_0**: @username_1, thanks. I have rephrased it to be more precise about the 'CF analogy' statement.  

---

## 1 answers

### Answer by username_2 on 2024-04-05. Score: 3 | Accepted answer

**First some background** (that does not fit the comments section) since you asked for pointers:

* The continued fractions-based post-processing algorithm in Shor's order-finding algorithm [[Shor94]](https://doi.org/10.1109%2Fsfcs.1994.365700) [[Shor97]](https://doi.org/10.1137%2FS0097539795293172) can be perceived as a lattice-based post-processing algorithm, that recovers the shortest non-zero vector (solves SVP) in a two-dimensional lattice, see [[E24]](https://doi.org/10.1145/3655026) for the full details (and a literature survey of related previous works, such as [[KW12p]](https://doi.org/10.48550/arXiv.1210.3003)).

  The SVP may then in turn be solved using Lagrange's lattice basis reduction algorithm (or with LLL, if you wish, although LLL reduces to Lagrange's algorithm in two dimensions).

  (Also, as explained in [[E21b]](https://doi.org/10.1007/s11128-021-03069-1) and [[E24]](https://doi.org/10.1145/3655026), in general we do not expect to have to run the quantum part of the algorithm more than once to find the order $r$, nor to factor $N$ completely via $r$, when using the more elaborate classical post-processing described in these works.)

  + To give a brief summary of [[E24]](https://doi.org/10.1145/3655026):

    The frequency $j$ read out from the quantum part of the order-finding algorithm is likely to be close to an optimal frequency $j\_0(z) = \lfloor 2^{m+\ell} z \, / \, r \rceil$, where $m+\ell$ is the control register length, $r$ is the order and $z$ is uniformly selected from $[0, r) \cap \mathbb Z$. This implies that if we post-process $j$, $j \pm 1$, $\ldots$, $j \pm B$, for $B$ some bound, then we are like to post-process $j\_0(z)$.

    Consider the two-dimensional lattice $\mathcal L$ generated by integer multiples of $(j\_0(z), 1/2)$ and $(2^{m+\ell}, 0)$. Then the last component of the shortest non-zero vector of $\mathcal L$ is $r / (2 \gcd(r, z))$ up to sign, and so we can recover $r / \gcd(r, z)$, assuming $2^{m+\ell} > r^2$, see Lemma 4.2 in [[E24]](https://doi.org/10.1145/3655026). See also Lemma 4.1 for the corresponding result for continued fractions-based post-processing, for comparison, and Lemma 4.3 for lattice-based post-processing with enumeration.

    This establishes the connection between the continued fraction (CF) algorithm and Lagrange's algorithm (or LLL, if you wish), and shows how the co-primality (CP) requirement enters into the picture, when working in two dimensions.
* The idea of generalizing the continued fractions-based post-processing algorithm in Shor's algorithm to higher dimensions was — as far as I know — first introduced by Seifert in [[Seifert01]](https://doi.org/10.1007/3-540-45353-9_24). The idea is to perform $n$ smaller runs on the quantum computer, and to jointly post-process the outputs from these runs classically.

  Seifert does not speak of lattice-based post-processing, but as explained in App. A and Sect. 6.2 to [[E21]](https://doi.org/10.1515/jmc-2020-0006), it is possible to use lattice-based post-processing for Seifert's algorithm in analogy with Shor's algorithm.

  + To give a brief summary of App. A and Sect. 6.2 in [[E21]](https://doi.org/10.1515/jmc-2020-0006):

    For $j\_1$, $\ldots$, $j\_n$ the frequencies read out, use LLL (or some other lattice basis reduction algorithm, such as BKZ) to solve SVP or to enumerate all short non-zero vectors in the lattice $\mathcal L$ generated by $(j\_1, \ldots, j\_n, 1)$ and $(2^{m+\ell}, 0, \ldots, 0)$, $\ldots$, $(0, \ldots, 2^{m+\ell}, 0)$. This with the aim of finding the short vector $\vec u = (\alpha\_1, \ldots, \alpha\_n, r)$ and hence $r$‚ where $\alpha\_i = \{ r j\_i \}\_{2^{m+\ell}}$.

    As for the co-primality (CP) requirement, let $\gcd(\alpha\_1, \ldots, \alpha\_n, r) = 2^\kappa o$ for $o$ odd. Then $\vec u / (2^t o) \in \mathcal L$ for some $t \in [0, \kappa] \cap \mathbb Z$, so we risk losing a factor $2^t o$ for the largest such $t$. (In practice, this problem can be solved by more elaborate post-processing. Note also that the problem becomes smaller as $n$ increases, since $\alpha\_1$, $\ldots$, $\alpha\_n$ are essentially random.) The analogy to the continued fractions (CF) algorithm is the LLL algorithm.

**As for Regev's algorithm:**

* Regev [[Regev23]](https://doi.org/10.48550/arXiv.2308.06572) uses the LLL algorithm to recover vectors in a $d$-dimensional lattice $\mathcal L$ given $m$ noisy vectors $\vec w\_1, \ldots, \vec w\_m$ at most a given distance from vectors $\vec v\_1, \ldots, \vec v\_m$ sampled uniformly at random from $\mathcal L^\* / \mathbb Z^d$. The vectors recovered give rise to factoring relations with a certain probability of success, under a heuristic assumption. That is to say, Regev is not directly performing order finding with respect to a given $g \in \mathbb Z\_N^\*$, as do Shor and Seifert, even if it is a form of order finding.

  I discussed your question a bit with my co-author Joel Gärtner today, and as we see it the analogy to the co-primality (CP) requirement in Regev's post-processing is the requirement that the vectors $\vec v\_1, \ldots, \vec v\_m$ alongside $\mathbb Z^d$ generate $\mathcal L^\*$. Note that by Corollary 4.2 in [[Regev23]](https://doi.org/10.48550/arXiv.2308.06572), with probability at least $1/2$, it suffices to take $m = d + 4$ for the vectors $\vec v\_1, \ldots, \vec v\_m$ to generate $\mathcal L^\* / \mathbb Z^d$, which is the same requirement. The analogy to continued fractions (CF) is the LLL algorithm.
* On a side note, and since you asked for pointers, it is possible to extend Regev's algorithm to an algorithm that performs order finding, with the goal of finding the order $\varphi(N)$ of $\mathbb Z\_N^\*$, or the order $r$ of an element $g \in \mathbb Z\_N^\*$. This is explained in App. A to [[EG23p]](https://doi.org/10.48550/arXiv.2311.05545), connecting Regev's algorithm to the above background section on order finding in a natural way.

  (In the former case of computing $\varphi(N)$, one can then proceed to factor $N$, for instance by randomizing [[Miller76]](https://doi.org/10.1016/S0022-0000(76)80043-8) as explained in [[E21b]](https://doi.org/10.1007/s11128-021-03069-1). One does furthermore forego squaring the primes in your Step I–II when taking this route, which leads to slight efficiency improvements. In the latter case of computing $r$, one has to include $g$ in the product in your Step II. Again, one can factor efficiently via [[E21b]](https://doi.org/10.1007/s11128-021-03069-1) given the order $r$ of $g$, provided that $g$ is selected uniformly at random from $\mathbb Z\_N^\*$.)

I do not know if this completely answers all your questions, but it may provide a starting point.

> **Comments:**
> **username_0**: Thanks! Indeed, it answers my crucial concern. I can see both algorithms from a common (lattice) perspective. I just finished reading some parts of the references [Ekerå21b/24] and worked out the details to convince myself.  

---

