A Low-Resource Quantum Factoring Algorithm

In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just \((\log N)^{2/3+o(1)}\) qubits to factor an integer N in time \(L^{q+o(1)}\) where \(L = \exp ((\log N)^{1/3}(\log \log N)^{2/3})\) and \(q=\root 3 \of {8/3}\approx 1.387\). For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is \(L^{p+o(1)}\) where \(p>1.9\). The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.

Authors and Affiliations

1. Department of Computer Science, University of Illinois at Chicago, Chicago, USA

   Daniel J. Bernstein

2. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands

   Daniel J. Bernstein

3. Department of Mathematics and Statistics, University of South Florida, Tampa, USA

   Jean-François Biasse

4. Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

   Michele Mosca

5. Perimeter Institute for Theoretical Physics, Waterloo, Canada

   Michele Mosca

6. Canadian Institute for Advanced Research, Toronto, Canada

   Michele Mosca

Corresponding authors

Correspondence to Daniel J. Bernstein , Jean-François Biasse or Michele Mosca .

Editors and Affiliations

1. Technische Universiteit Eindhoven, Eindhoven, The Netherlands

   Tanja Lange

2. Kyushu University , Fukuoka, Japan

   Tsuyoshi Takagi

A Number of Iterations for the Serial Construction

This appendix justifies the claim in Section 6 that choosing a sufficiently large \(t\in O(\log x\log \log x)\) produces at least \(\log _2 x\) successful iterations except with probability O(1/x).

We abstract and generalize the situation in Section 6 as follows. The algorithm state evolves through t iterations: from state \(S_0\), to state \(S_1=A_1(S_0)\), to state \(S_2=A_2(S_1)\), and so on through state \(S_t=A_t(S_{t-1})\). We are given a positive real number p and a guarantee that each iteration is successful with probability at least p. Our objective is to put an upper bound on the chance that there are fewer than s successful iterations.

More formally: Fix a finite set X. (The algorithm state at each moment will be an element of this set.) Also fix a function \(f:X\rightarrow {\mathbb {Z}}\). (For each algorithm state S, the value f(S) is the total number of successes that occurred as part of producing this algorithm state; we augment the algorithm state if necessary to count the number of successes.) Finally, fix a positive real number p.

Let A be a random function from X to X. (This will be what the algorithm does in one iteration.) Note that “random” does not mean “uniform random”; we are not assuming that A is uniformly distributed over the space of functions from X to X.

Define A as admissible if the following two conditions are both satisfied:

• \(f(A(S))-f(S)\in \mathord {\left\{ {0,1}\right\} }\) for each \(S\in X\).

• \(q(A,S)\ge p\) for each \(S\in X\), where q(A, S) by definition is the probability that \(f(A(S))-f(S)=1\).

(In other words, no matter what the starting state S is, an A iteration starting from S has probability at least p of being successful.)

Let t be a positive integer. (This is the number of iterations in the algorithm.) Let \(A_1,A_2,\dots ,A_t\) be independent admissible random functions from X to X. (\(A_i\) is what the algorithm does in the ith iteration; concretely, these functions are independent if the coin flips used in the ith iteration of the algorithm are independent of the coin flips used in the jth iteration whenever \(i\ne j\).)

Let \(S_0\) be a random element of X. (This is the initial algorithm state.) Note that again we are not assuming a uniform distribution. Recursively define \(S_i=A_i(S_{i-1})\) for each \(i\in \mathord {\left\{ {1,2,\dots ,t}\right\} }\). (\(S_i\) is the state of the algorithm after i iterations.)

Proposition 1

Let s be a positive real number. Assume that \(tp\ge s\). Then \(f(S_t)-f(S_0)\le s\) with probability at most \(\exp (-(1-s/tp)^2 tp/2)\).

In other words, except with probability at most \(\exp (-(1-s/tp)^2 tp/2)\), there are more than s successes in t iterations.

In the application in Section 6, we take \(p\in \varOmega (1/\log \log x)\) to match the analysis of Shor’s algorithm; we take \(s=\log _2 x\); and we compute t as an integer between, say, \((4\log _2 x)/p\) and \((4\log _2 x)/p+1.5\). (Taking a gap noticeably larger than 1 means that we can compute t from a low-precision approximation to \((4\log _2 x)/p\).) Then \(t\in O(\log x\log \log x)\). The condition \(tp\ge s\) in the proposition is satisfied, so there are more than \(\log _2 x\) successes in t iterations, except with probability at most \(\exp (-(1-s/tp)^2 tp/2)\). The quantity tp is at least \(4\log _2 x\), and the quantity \(1-s/tp\) is at least 3/4, so \((1-s/tp)^2 tp/2\ge (9/8)\log _2 x>1.6\log x\), so the probability is below \(1/x^{1.6}\).

Proof

Chernoff’s bound says that if \(v_1,v_2,\dots ,v_t\) are independent random elements of \(\mathord {\left\{ {0,1}\right\} }\), with probabilities \(\mu _1,\mu _2,\dots ,\mu _t\) respectively of being 1 and with \(\mu =\mu _1+\mu _2+\cdots +\mu _t\), then the probability that \(v_1+v_2+\cdots +v_t\le \delta \mu \) is at most \(\exp (-(1-\delta )^2\mu /2)\) for \(0<\delta \le 1\).

It is tempting at this point to define \(v_i=f(S_i)-f(S_{i-1})\), but then there is no reason for \(v_1,v_2,\dots ,v_t\) to be independent.

Instead flip independent coins \(c_1,c_2,\dots ,c_t\), where \(c_i=1\) with probability \(p/q(A_i,S_{i-1})\) and \(c_i=0\) otherwise. Define \(v_i=c_i(f(S_i)-f(S_{i-1}))\).

By assumption \(S_i=A_i(S_{i-1})\), so \(f(S_i)-f(S_{i-1})=f(A_i(S_{i-1}))-f(S_{i-1})\). This difference is 1 with probability exactly \(q(A_i,S_{i-1})\), and 0 otherwise. Hence \(v_i\) is 1 with probability exactly p, and 0 otherwise. This is also true conditioned upon \(v_1,v_2,\dots ,v_{i-1}\), since \(A_i\) and \(c_i\) are independent of \(v_1,v_2,\dots ,v_{i-1}\); hence \(v_1,v_2,\dots ,v_t\) are independent.

Now substitute \(\mu _1=\mu _2=\dots =\mu _t=p\), \(\mu =tp\), and \(\delta =s/tp\) in Chernoff’s bound: we have \(0<\delta \le 1\) (since \(0<s\le tp\)), so the probability that \(v_1+v_2+\cdots +v_t\le s\) is at most \(\exp (-(1-s/tp)^2 tp/2)\).

Note that \(v_i\le f(S_i)-f(S_{i-1})\), so \(v_1+v_2+\dots +v_t\le f(S_t)-f(S_0)\). Hence the probability that \(f(S_t)-f(S_0)\le s\) is at most \(\exp (-(1-s/tp)^2 tp/2)\) as claimed.    \(\square \)

Reprints and permissions

© 2017 Springer International Publishing AG

Policies and ethics