Comparing Shor's and Regev's Quantum Factoring algorithm

Question

Regev's factoring algorithm 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. 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.

Answer 1

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] [Shor97] 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] for the full details (and a literature survey of related previous works, such as [KW12p]).

  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] and [E24], 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]:

    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]. 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]. 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], 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]:

    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] 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], 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], 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] as explained in [E21b]. 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] 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.