Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
Cédric Pilatte


Unconditional correctness of recent quantum algorithms]Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms


Mathematical Institute, University of Oxford.
cedric.pilatte@maths.ox.ac.uk

[
    Cédric Pilatte
    Accepted XXX, Received YYY; in original form ZZZ
====================================================





In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in (ℤ/Nℤ)^× that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.




§ INTRODUCTION




 §.§ Context and quantum computing results

Public key cryptography has become a crucial element of our global digital communication infrastructure. Notable examples include the Diffie-Hellman key exchange <cit.> and the RSA (Rivest-Shamir-Adleman) cryptosystem <cit.>, which rely on the difficulty of finding discrete logarithms and factoring large numbers, respectively.

However, in 1994, Peter Shor <cit.> developed an algorithm capable of efficiently solving these problems using a quantum computer.

[Shor[The version of Shor's algorithm stated here incorporates some small improvements from <cit.> (bounded number of calls) and <cit.> (fast integer multiplication). The number of qubits in Shor's algorithm can be brought down to O(n), though this typically requires a larger number of quantum gates (see e.g. <cit.>).]]
There is a quantum circuit having O(n^2log n) quantum gates and O(n log n) qubits with the following property. There is a classical randomised polynomial-time algorithm that solves the factoring problem

    𝐈𝐧𝐩𝐮𝐭:  a composite integer N ≤ 2^n
       𝐎𝐮𝐭𝐩𝐮𝐭:  a non-trivial divisor of N

using O(1) calls to this quantum circuit, and succeeds with probability Θ(1).


Shor's original article <cit.> also includes a similar algorithm to solve the discrete logarithm problem. This advancement prompted the development of post-quantum cryptography, such as lattice-based cryptography, to ensure the security of our communications in the face of potential quantum computing breakthroughs <cit.>. 

Recently, Regev <cit.> devised a multidimensional variant of Shor's factoring algorithm that reduces the size of the quantum circuit, i.e. the number of quantum gates, to O(n^3/2log n). A distinctive feature of Regev's algorithm is that the quantum circuit must be called O(√(n)) times, rather than a constant number of times for Shor's algorithm. This is not considered to be a serious drawback as the various complexity parameters of the quantum circuit are far more relevant metrics in quantum computing.

However, this remarkable work of Regev initially came with two main limitations. 

First, the original version of Regev's algorithm requires O(n^3/2) qubits – many more than Shor's algorithm. The reason for this ultimately lies in the difficulty of performing classical computations on quantum computers in a space-efficient manner, due to the need for any quantum computation to be reversible. In a subsequent paper, Ragavan and Vaikuntanathan <cit.> improved Regev's algorithm to use only O(nlog n) qubits, while maintaining the circuit size at O(n^3/2log n) quantum gates. This work, inspired by ideas of Kalinski <cit.>, essentially matches the space cost of Shor's algorithm. 

The second issue, which we address in this paper, is that Regev's algorithm <cit.> does not have theoretical guarantees, unlike Shor's algorithm. The correctness of Regev's algorithm is based on an ad hoc number-theoretic conjecture which we describe below. This unproven assumption cannot be avoided as it lies at the core of Regev's improvement on the circuit size. The variant of Ragavan and Vaikuntanathan <cit.> also crucially relies on this conjecture.

In this paper, we prove a version of Regev's conjecture. This allows us to unconditionally prove the correctness of (slightly modified versions of) the algorithms of Regev <cit.> and Ragavan and Vaikuntanathan <cit.>. More precisely, we obtain the following algorithmic result.

theoremthmfactoring

There is a quantum circuit having O(n^3/2log^3 n) quantum gates and O(n log^3 n) qubits with the following property. There is a classical randomised polynomial-time algorithm that solves the factoring problem

    𝐈𝐧𝐩𝐮𝐭:  a composite integer N ≤ 2^n
       𝐎𝐮𝐭𝐩𝐮𝐭:  a non-trivial divisor of N

using O(√(n)) calls to this quantum circuit, and succeeds with probability Θ(1).


This unconditionally establishes the results in <cit.> up to logarithmic factors.

Regev's algorithm was adapted by Ekerå and Gärtner <cit.> to the discrete logarithm problem. Their paper <cit.> also uses the space-saving arithmetic of Ragavan and Vaikuntanathan <cit.> to obtain a quantum circuit with O(n^3/2log n) gates and O(nlog n) qubits for computing discrete logarithms.

Once more, the correctness of the algorithm by Ekerå and Gärtner <cit.> relies on an unproven hypothesis, which can be viewed as a stronger form of Regev's conjecture. Our methods also apply to this stronger statement (again, with minor technical adjustments). Thus, we get an analogue of <ref> for the discrete logarithm problem, i.e. an unconditional proof of the results in <cit.> up to logarithmic factors.

theoremthmlogarithm

There is a quantum circuit having O(n^3/2log^3 n) quantum gates and O(n log^3 n) qubits with the following property. There is a classical randomised polynomial-time algorithm that solves the discrete logarithm problem

    𝐈𝐧𝐩𝐮𝐭:  an integer N ≤ 2^n and elements g,y ∈N such that y∈g
       𝐎𝐮𝐭𝐩𝐮𝐭:  an integer x such that g^x ≡ y N

using O(√(n)) calls to this quantum circuit, and succeeds with probability Θ(1).


Moreover, the slight technical modifications that we need to introduce to make all these quantum algorithms unconditional are compatible with the error-correction results of <cit.>. Finally, our results extend to further variants of Regev's algorithm, such as computing discrete logarithms or multiplicative orders modulo N for several elements simultaneously (see <cit.>). 
 


By being slightly more careful in the space usage of our quantum algorithms, it is possible to reduce the number of qubits to O(nlog^2 n) for <ref>. We will not show this here in order to reduce the quantum computing prerequisites to a minimum.





 §.§ An overview of Regev's algorithm


Let us start by recalling the basic idea behind Shor's factoring algorithm <cit.>. 

Let N be the integer to be factored, say odd and with at least two distinct prime factors. The first step is to generate a random integer 1 < a < N, which can be assumed to be coprime to N. Shor proved that there is an efficient quantum algorithm to find the multiplicative order r of a modulo N. It can be shown by elementary means that a^r/2 is a non-trivial square root of 1 modulo N (here we mean that 2| r and a^r/2≢±1) with probability ≥ 1/2. Whenever this is the case, we get a non-trivial divisor of N, namely (N, a^r/2-1).

The reason that Shor's algorithm uses O(n^2log n) quantum gates, where n := ⌈log_2 N⌉, comes from the part of the quantum circuit that performs modular exponentiation. Consider the task of computing a power a^MN on a classical computer, where 1<a<N-1 and M ≤ N. This computation can be performed efficiently using the well-known square-and-multiply method, which involves O(log M) multiplications of two integers modulo N. Since two n-bit integers can be multiplied in time O(nlog n) by <cit.>, the complexity of this modular exponentiation problem is thus O(n^2log n).[Note that, even if a is a small integer, say a=2, this procedure still takes time O(n^2log n), because most multiplications will involve n-bit integers.] For Shor's algorithm, a similar modular exponentiation needs to be performed quantumly, which requires O(n^2log n) quantum gates.

Regev's improvement of Shor's algorithm is made possible by combining two key ideas. 

The first idea in Regev's algorithm is to work in higher dimensional space and replace the random parameter a by several integers b_1, …, b_d (chosen in a specific way, as we explain below). Eventually, the optimal choice of dimension turns out to be d ≍√(log N). Similarly to Shor's algorithm, the problem of factoring N easily reduces to the task of finding a vector (e_1, …, e_d) ∈^d such that ∏_i=1^d b_i^e_i is a non-trivial square root of 1 modulo N. 

Using additional tools such as the LLL lattice reduction algorithm, Regev <cit.> generalised Shor's quantum algorithm to efficiently find all such vectors (e_1, …, e_d) in a ball of radius N^O(1/d) centred at the origin. 

Regev's algorithm only succeeds if there indeed exists a vector v = (e_1, …, e_d) ∈^d such that 

	
  *  v_2 ≤ N^O(1/d), and
	
  *  ∏_i=1^d b_i^e_i is a non-trivial square root of 1 modulo N.


If the parameters b_1, …, b_d are “sufficiently multiplicatively independent” modulo N, one might heuristically expect the existence of a vector v = (e_1, …, e_d) satisfying <ref> and <ref>. This is, roughly speaking, what Regev needs to assume. To state his conjecture properly, it remains to specify how the parameters b_1, …, b_d are chosen. This is a crucial point, as the idea of working in dimension d does not, on its own, offer any advantage over Shor's algorithm. 

The second key insight of Regev is to choose b_1, …, b_d to be very small compared to N. We mentioned that the most costly part of Shor's quantum circuit lies in the modular exponentiation step. Similarly, the number of gates of Regev's circuit is dominated by the cost of computing an expression of the form

    ∏_i=1^d b_i^M_iN
 
in the quantum setting, where the exponents M_1, …, M_d are ≤ N^O(1/d). Regev observed that <ref> can be computed classically in time O(n^3/2log n) if |b_i| ≤ (log N)^O(1) for all i (for d ≍√(n)≍√(log N)). This can be achieved by cleverly ordering the intermediate multiplications so that most of them involve integers with much fewer than n bits. This classical procedure can then be turned into a quantum version that uses O(n^3/2log n) gates.

Shor's algorithm corresponds to the d=1 case of Regev's algorithm where the parameter b_1 is an element of N chosen uniformly at random. In this case, simple considerations from elementary number theory immediately imply the existence of an integer e_1 satisfying <ref> and <ref> with probability ≫ 1. This would hold more generally for d≥ 1 if b_1, …, b_d were independent, uniformly distributed random elements of N. However, for Regev's algorithm, the b_i's are far from uniformly distributed in N as they are constrained to lie in a very small subset of N. 




 §.§ The number-theoretic conjecture behind Regev's algorithm
 Regev's algorithm <cit.> and its space-efficient variant <cit.> crucially rely on the possibility of choosing very small integers b_1, …, b_d such that ∏_i=1^d b_i^e_i is a non-trivial square root of 1 modulo N for some e_1, …, e_d with |e_i| ≤ N^O(1/d). We remind the reader that n ≍log N and d ≍√(n).

The least restrictive bound[The bound stated in Regev's paper <cit.> is |b_i| ≤ (log N)^O(1), but this condition can be relaxed somewhat, as observed by Ragavan (private communication).] on the b_i's that still allows for a quantum circuit with Õ(n^3/2) gates is to have |b_i| ≤exp(Õ(d)), where the Õ(·) notation possibly hides a factor (log n)^O(1). Moreover, it is natural to set the b_i's to be prime numbers (as in <cit.>) in order to avoid obvious multiplicative relations between them.

In this paper, we choose b_1, …, b_d to be independent random prime numbers less than d^10^3d. With these parameters, we can now state a version of Regev's conjecture[Compare with <cit.> or <cit.>.] that follows from our results.



Let N>2 be an integer. Let d := ⌈√(log N)⌉ and X := d^10^3d.

Let _̱1, …, _̱d be i.i.d. random variables, each uniformly distributed in the set of primes ≤ X not dividing N.

Then, with high probability, every x ∈_̱1, …, _̱d can be expressed as

    x ≡∏_i=1^d _̱i^e_iN

for some integers e_i with |e_i|≤ e^O(d) for all 1≤ i≤ d.


The analogue of Regev's algorithm for the discrete logarithm problem, proposed by Ekerå and Gärtner <cit.>, relies on a stronger version of Regev's conjecture. It concerns the geometry of a certain lattice Ł which encodes all multiplicative dependencies between the _̱i's (modulo N). We prove the following version of it.[Compare with <cit.> or <cit.>]



Let N>2 be an integer. Let d := ⌈√(log N)⌉ and X := d^10^3d.

Let _̱1, …, _̱d be i.i.d. random variables, each uniformly distributed in the set of primes ≤ X not dividing N.

Let Ł be the random lattice defined by

    Ł := { (e_1, …, e_d) ∈^d  :  ∏_i=1^d _̱i^e_i≡ 1 N}.

Then, with high probability, this lattice Ł has a basis consisting of vectors of Euclidean norm ≤ e^O(d).


The main technical result of this paper is <ref>, of which <ref> is a special case. <Ref> is a direct consequence <ref>. 



 §.§ Subgroup obstructions

<ref> shows that, with high probability, every element x in the subgroup generated by _̱1, …, _̱d can be written as a short product of these _̱i modulo N. To obtain the full strength of Regev's assumption <cit.>, it would be necessary to show that this subgroup _̱1, …, _̱d contains a non-trivial square root of 1 modulo N. 

Unfortunately, it is not possible to prove this in full generality without considerable advances on the well-known least quadratic non-residue problem in number theory. For any prime number p, write n(p) for the smallest positive integer a which is a quadratic non-residue (i.e. not a square) modulo p. The best known asymptotic upper bound for n(p) is Burgess's classical result <cit.> that

    n(p) ≪_ p^1/4√(e)+.

For simplicity, suppose that the integer N to be factored is a product of two equally-sized primes p_1, p_2≡ 3 4. Recall that, for Regev's algorithm, the parameters _̱i are chosen to be less than exp(Õ(d)). With current techniques, we cannot rule out the possibility that both n(p_1) and n(p_2) are larger than this threshold. If this is the case, all _̱i will be quadratic residues modulo both p_1 and p_2, which implies that _̱1, …, _̱d is contained in the subgroup of squares modulo N. In particular, since p_1, p_2≡ 3 4, the subgroup _̱1, …, _̱d does not contain any non-trivial square roots of 1 modulo N.

This issue can be approached from several perspectives.


	
  * Assuming the Generalised Riemann Hypothesis, Ankeny proved the much stronger bound n(p) ≪ (log p)^2 <cit.>. This suggests that quadratic residues may no longer be an obstruction in this case, and indeed, under GRH, it is straightforward to show that _̱1, …, _̱d contains a non-trivial square root of 1 modulo N with high probability. Assuming GRH would also considerably simplify the proof of <ref> and remove a logarithmic factor for the gate and qubit costs in <ref>. However, in this paper we seek fully unconditional results.
	
  * Using a grand zero-density estimate <cit.> and the Landau-Page theorem <cit.>, it is possible to prove the above result unconditionally for almost all N, which would already have very interesting algorithmic consequences. More precisely, it can be shown that there exists a set of exceptions E⊂ satisfying 
	
    E ∩ [1, x]≪exp((log x)^1/2+o(1))

	for x≥ 1, such that for every odd N∉E with at least two prime factors, the subgroup _̱1, …, _̱d (with _̱i = _̱i(N) as defined earlier) contains a non-trivial square root of 1 modulo N with high probability. From this and <ref>, it would follow that Regev's algorithm finds a non-trivial divisor of N with high probability for almost all N.
	
  * In this paper, we follow a different approach to obtain a completely unconditional result that applies to all N, by slightly modifying the algorithm itself. While the key to the efficiency of Regev's algorithm is that the _̱i's are small, one can tolerate a bounded number of large _̱i's.[In fact, this observation was already needed to adapt Regev's algorithm to the discrete logarithm problem <cit.>.] We use this extra flexibility to overcome the subgroup obstructions. The simplest way to proceed is to allow for one of the parameters, say _̱1, to be uniformly distributed in N. As with Shor's algorithm, this ensures that the subgroup _̱1, and hence also _̱1, …, _̱d, contains a non-trivial square root of 1 with probability ≫ 1.




In his paper <cit.>, Regev proposed to select the parameters b_1, …, b_d deterministically, for example by setting b_i to be the i-th smallest prime for 1≤ i≤ d. While such a deterministic choice of parameters is likely to work for almost all N, this is probably very difficult to prove.




In this paper, the parameters _̱i are chosen to be random primes (not dividing N) under a certain threshold X. Another natural choice would have been to let _̱1, …, _̱d be i.i.d. random variables uniformly distributed in the set of all integers ≤ X coprime to N. The proofs in this paper would carry over to this framework if an analogue of <ref> for short character sums ∑_n≤ xχ(n) were available. Assuming the Generalised Riemann Hypothesis, the work of Granville and Soundararajan <cit.> gives a bound of the required strength. However, this approach does not seem sufficient to obtain an unconditional result (the bounds in <cit.> become too weak when L(s, χ) has zeroes close to the line s = 1).


This paper is organised as follows. Our main technical result is <ref>, which shows that lattices Ł similar to that in <ref> have a basis of short vectors with high probability. Using simple geometry of numbers (see <ref>), we reduce this problem to estimating the number of lattice points in balls of growing radii. Unfortunately, we are unable to obtain a suitable lattice point count for Ł directly. We resolve this by considering a different lattice Ł_M from the start of the argument (using the lemmas in <ref>). In <ref>, we expand the lattice point count for Ł_M in terms of Dirichlet characters modulo N. This produces a main term, which can be estimated precisely, and an error term. The heart of the proof lies in using a zero-density estimate for Dirichlet characters modulo N to bound this error term unconditionally. Finally, we prove our quantum algorithmic applications (<ref>) in <ref>.





§ ACKNOWLEDGEMENTS


The author is supported by the Oxford Mathematical Institute and a Saven European Scholarship. I would like to thank Jane Street for awarding me one of their Graduate Research Fellowships. I am indebted to my advisors, Ben Green and James Maynard, for their invaluable advice and support. Finally, I wish to thank Seyoon Ragavan for his kind explanations, and in particular for showing me that the upper bound for the parameters in Regev's algorithm could be relaxed considerably. 



§ PROOF OF THE EXISTENCE OF A SHORT LATTICE BASIS





 §.§ Notation

We write f≪ g or f = O(g) if |f| ≤ Cg for some absolute constant C>0. If instead, C depends on a parameter θ, we write f ≪_θ g or f = O_θ(g). The notation f≍ g or f = Θ(g) means that f≪ g and g≪ f. 

A character of a finite abelian group G is a homomorphism χ : G→^×. The order of χ, denoted by (χ), is the least positive integer n such that χ^n is the trivial character 1. The group of all characters of G is denoted by G. If g_1, …, g_k∈ G, we write g_1, …, g_k for the subgroup of G generated by these elements. 

A non-trivial square root of 1 modulo N is an element a∈N such that a^2 ≡ 1 N and a≢±1  N. Euler's totient function and the prime counting function are denoted by φ and π, respectively. We use the notation ·_2 for the Euclidean norm. We write log for the natural logarithm and log_2 for the logarithm in base 2.

Random variables are typically written in bold font, such as _̱1, …, _̱d. A statement will be said to occur with high probability if it holds with probability tending to 1 as N→∞.

We refer the reader to <cit.> for a detailed textbook on quantum computing, and <cit.> for a brief overview. 




 §.§ Restricting to a convenient subgroup of N



The goal of this preliminary section is to define a subgroup of the character group of N that does not have too many elements of small order. This will be crucial for <ref>, to reduce the influence of potential counterexamples to the Generalised Riemann Hypothesis. For example, we need to avoid having many characters χ_1, …, χ_k modulo N such that χ_i^2 = ψ for all i, where ψ is an exceptional character (in the sense that L(s, ψ) has a zero very close to the line s = 1). The definition of the suitable subgroup depends on the precise structure of N.



If G is a finite abelian group (written multiplicatively) and M≥ 1, we write G^M := {x^M : x∈ G} for the subgroup of Mth powers in G.[In particular, G^M is not the M-fold direct product of G.]




Let G be a finite abelian group (written multiplicatively) and M≥ 1. There is an isomorphism

    ι : G^MG^M

such that, for any χ∈G^M, ι(χ) = χ^M where χ∈G is an arbitrary extension of χ to G.



Pontryagin duality for finite abelian groups is an equivalence of categories, and therefore an exact functor. In simple terms, this implies that injections turn into surjections when switching to the dual, and vice versa. Hence, the Mth power map G ↠ G^M, g↦ g^M, induces an injection ι : G^MG defined by 

    ι(χ)(g) := χ(g^M)

for every χ∈G^M and g∈ G. Moreover, the restriction map G→G^M is surjective, using exactness of Pontryagin duality again. Thus, every χ∈G^M can be extended to a character χ on G, and

    χ(g^M) = χ(g^M) =  χ^M(g).

This implies that the image of ι is contained in G^M. Since |G^M| = |G^M| = |G^M|, the lemma follows.



Let N ≥ 1. For every h≥ 1 we define 

    K(h) := N/(N)^h.

In other words, K(h) is the size of the kernel of the hth power map in N.




Let N>2 be an integer and d := ⌈√(log N)⌉. 

For every prime p, define m_p to be the largest non-negative integer such that

    K(p^m_p) ≥ p^d m_p/10.

Let = (N) := ∏_p p^m_p. Then the following holds. 

	
  * We have ≤ e^10d.
	
  * For every h≥ 1, we have K( h)/K()≤ h^d/10.





	
  * For every prime p, since K(p^m_p) is a power of p dividing N = ϕ(N), we have 
	
    ∏_p K(p^m_p) |ϕ(N).

	By definition of m_p, we know that K(p^m_p) ≥ p^d m_p/10 for every p, and thus
	
    ^d/10 = ∏_p p^dm_p/10≤∏_p K(p^m_p) ≤ϕ(N) ≤ N.

	Recalling that d = ⌈√(log N)⌉, it follows that ≤ e^10d.
	
  * In any finite abelian group (written multiplicatively) and for any coprime integers a and b, there is an isomorphism
	
    (g↦ g^a) ×(g↦ g^b) ≅(g↦ g^ab).

	Thus, if h = ∏_p p^e_p is the prime factorisation of h, we see that K() = ∏_p K(p^m_p) and K( h) = ∏_p K(p^m_p+e_p), where all products are finite. Whenever e_p≥ 1, we have
	
    K(p^m_p+e_p) < p^d(m_p+e_p)/10,   K(p^m_p) ≥ p^dm_p/10

	by definition of m_p. Thus K(p^m_p+e_p)/K(p^m_p)≤ p^de_p/10, and this last inequality also holds when e_p = 0. We conclude that
	
    K( h)/K() = ∏_p K(p^m_p+e_p)/K(p^m_p)≤∏_p p^de_p/10 = h^d/10.

	as claimed. 




Let N > 2, d := ⌈√(log N)⌉, G := N and let ≥ 1 be the integer defined in the statement of <ref>.

Let h≥ 1. Let χ_1, …, χ_n ∈G^ be distinct characters such that

    χ_1^h = χ_2^h = … = χ_n^h,

Then n ≤ h^d/10.



Let f_h : G^→ G^ be the hth power map, f(χ) := χ^h. By assumption, the n distinct characters χ_1χ_n^-1, χ_2χ_n^-1, …, χ_nχ_n^-1 lie in the kernel of f. Hence,

    n ≤|(f)| = |G^|/|(G^)^h| = |(N)^|/|(N)^ h| = K( h)/K(),

which is ≤ h^d/10 by <ref>.




 §.§ Lattice point counting via characters



To prove <ref>, we will need to study the following quantities.



Let N≥ 1, G = N and χ∈G. For all d≥ 1 and b_1, …, b_d∈ G, we define the quantity

    F_χ,H(b_1, …, b_d) := ∏_i=1^d ∑_|h|≤ Hχ^h(b_i).



The following lemma relates these expressions to a lattice point counting problem.



Let N,M,d,H ≥ 1 be integers. Let b_1, …, b_d∈ G := N. The number of vectors (e_1, …, e_d)∈^d ∩ [-H,H]^d such that 

    ∏_i=1^d b_i^Me_i≡ 1  N

is equal to

    1/|G^M|∑_χ∈G^M F_χ,H(b_1, …, b_d).




By orthogonality of characters in the abelian group G^M, we have

    ∏_i b_i^Me_i≡ 1 N = 1/|G^M|∑_ψ∈G^Mψ(∏_i=1^d b_i^Me_i) = 1/|G^M|∑_ψ∈G^M∏_i=1^d ψ( b_i^Me_i).

Observe that ψ( b_i^Me_i) = ι(ψ) (b_i^e_i), where ι is the isomorphism G^MG^M defined in <ref>. We may thus rewrite this equality as

    ∏_i b_i^Me_i≡ 1 N = 1/|G^M|∑_χ∈G^M∏_i=1^d χ( b_i^e_i).

Therefore, the number of vectors (e_1, …, e_d)∈^d ∩ [-H,H]^d such that ∏_i=1^d b_i^Me_i≡ 1  N is

    ∑_(e_1, …, e_d)∈^d 
    max_i |e_i|≤ H∏_i _̱i^Me_i≡ 1 N = 1/|G^M|∑_χ∈G^M∑_(e_1, …, e_d)∈^d 
    max_i |e_i|≤ H∏_i=1^d χ^e_i (b_i) = 1/|G^M|∑_χ∈G^M F_χ,H(b_1, …, b_d)

as claimed.


It is fairly straightforward to estimate F_χ,H(b_1, …, b_d) when χ is a character of small order in G. The contribution of these small-order characters gives the expected main term for <ref>.



Let N,M,d ≥ 1 be integers. Let b_1, …, b_d∈ G := N. Uniformly for all integers H≥ e^31d, we have 

    1/|G^M|∑_χ∈G^M F_χ,H(b) =  (1 + O(e^31d/H))  (2H+1)^d/|b_1^M, …, b_d^M| + 1/|G^M|∑_χ∈G^M
    (χ) ≥ e^10dF_χ,H(b),

where F_χ,H(b) is short for F_χ,H(b_1, …, b_d).



Define 

    b_1, …, b_d^⊥ := {χ∈G : ∀ i∈ [d], χ(b_i)=1 }.

Observe that

    |b_1, …, b_d^⊥∩G^M | = |{χ∈G^M : ∀ i∈ [d],  χ(b_i^M)=1 }| = |G^M|/|b_1^M, …, b_d^M|

where the first equality follows from <ref> and the second from the canonical isomorphism H_1^⊥≅G_1/H_1 for any subgroup H_1 of a finite abelian group G_1.


Clearly, if χ∈b_1, …, b_d^⊥∩G^M, we have F_χ,H(b) = (2H+1)^d. Hence, by <ref>, those characters contribute

    1/|G^M|∑_χ∈b_1, …, b_d^⊥∩G^M F_χ,H(b) = (2H+1)^d/|b_1^M, …, b_d^M|

to the sum <ref>.

For any character χ∈G^M∖b_1, …, b_d^⊥ of order ≤ e^10d, and any i∈ [d] such that χ(b_i) ≠ 1, we can bound

    ∑_|h| ≤ Hχ(b_i)^h≤(χ) ≤ e^10d

by the geometric series formula. Thus, defining

    I_χ := {i ∈ [d] : χ(b_i) ≠ 1},

we have 

    F_χ,H(b)≤ e^10dI_χ (2H+1)^d - I_χ.


Consequently, 

    ∑_χ∈G^M∖b_1, …, b_d^⊥
    (χ) ≤ e^10dF_χ,H(b)≪∑_I ⊂ [d]
     I≠∅ e^10dI (2H+1)^d - I∑_χ∈G^M
    (χ) ≤ e^10d
     I_χ = I 1.


Fix some non-empty set I ⊂ [d] and complex numbers (z_i)_i∈ I. Let C_I, (z_i) be the set of all characters χ∈G^M such that 

    χ(b_i) = 
    		z_i    if i∈ I
    
    		1    if i∈  [d]∖ I.

Note that C_I, (z_i) is either the empty set, or a coset of b_1, …, b_d^⊥∩G^M in G^M. Moreover, if χ has order ≤ e^10d, this set C_I, (z_i) can only be non-empty if all z_i are roots of unity of order ≤ e^10d, and there are ≤ e^20d such roots of unity. We conclude that

    ∑_χ∈G^M
    (χ) ≤ e^10d
     I_χ = I 1 ≤∑_(z_i)_i∈ IC_I, (z_i)≤ e^20d|I||b_1, …, b_d^⊥∩G^M |.


Thus, we can bound the right-hand side of <ref> by

    ≪ (2H+1)^d|b_1, …, b_d^⊥∩G^M |∑_I ⊂ [d]
     I≠∅(e^30d H^-1)^I≪ (2H+1)^d|b_1, …, b_d^⊥∩G^M |  2^de^30dH^-1

where we used that H≥ e^30d in the last step. By <ref>, this means that

    1/|G^M|∑_χ∈G^M∖b_1, …, b_d^⊥
    (χ) ≤ e^10dF_χ,H(b)≪ e^31dH^-1(2H+1)^d/|b_1^M, …, b_d^M|,

which completes the proof.




 §.§ Bounding the contribution of large-order characters



In this section, we bound the error term coming from large-order characters, on average over primes b_1, …, b_d in a short interval. 

We will need the following ingredients from classical analytic number theory.



Let 1/2 ≤α≤ 1. Let q, x≥ 2. Let χ be a non-principal character modulo q whose Dirichlet L-function L(s, χ) has no zero in the rectangle

    αx^1-α.

Then

    1/π(x)∑_p≤ xχ(p) ≪ x^-(1-α)log^3 (qx).



<ref> is a standard consequence of the explicit formula for L(s, χ) and is proved in <ref>. The logarithmic factors can be somewhat improved, but such refinements are irrelevant here.

The Generalised Riemann Hypothesis is the claim that, for every Dirichlet character χ, L(s, χ) has no zero ρ with 1/2 < ρ < 1. Assuming GRH, <ref> thus implies almost square-root cancellation for character sums over primes. <Ref> will serve as an unconditional substitute for GRH.



Uniformly for 45 ≤α≤ 1 and q, T≥ 1, we have

    ∑_χ q(α, T, χ) ≪_ (qT)^(2+)(1-α).

where (α, T, χ) denotes the number of zeros (with multiplicity) of L(s, χ) in the rectangle 

    αT.



This is <cit.>.


Our goal is to control the total contribution of all large-order characters in <ref>. We will do so in <ref> (restricting to a suitable sugbroup of G). We first prove the following L^2 bound for a single large-order character.



Let N > 2 be an integer and let G = N. Let d = ⌈√(log N)⌉ and X =  d^10^3 d. 

Let _̱1, …, _̱d be i.i.d. random variables, each uniformly distributed in the set of primes less than X not dividing N. Let χ∈G be a character of order ≥ e^10d. Then, for every H≥ e^10d,

    |F_χ,H(_̱1, …, _̱d)|^2 ≪ d^-10d H^2d.




By <ref>, the number of Dirichlet characters modulo N whose associated L-function has a zero in the region

    1-1/10dX.

is

    ≪ (NX)^(2+1)/(10d)≪ e^d.


If a non-principal character ψ modulo N has no zero in the region <ref>, then by <ref> we have

    ψ(_̱1)≪ X^-1/(10d)(log (NX))^3  ≪ d^-100 d^6 ≪ d^-15.


We now expand |F_χ,H(_̱1, …, _̱d)|^2 as

    |∏_i=1^d ∑_|h|≤ Hχ^h(_̱i) |^2    = ∏_i=1^d |∑_|h|≤ Hχ^h(_̱i)|^2 
       = (∑_|h_1|≤ H∑_|h_2|≤ Hχ^h_1-h_2(_̱1))^d
       ≤ (2H+1)^d (∑_|h|≤ 2Hχ^h(_̱1))^d.

We can use <ref> to bound the term χ^h(_̱1), unless χ^h is principal or L(s, χ^h) has a zero in the region <ref>. By <ref>, the number of values of h with |h|≤ 2H for which one of these two situations occurs is

    ≪(1+H/(χ))  e^d≪ e^-10d e^dH  ≪ e^-dH.

By <ref>, we deduce that, for all but O(e^-dH) values of |h|≤ 2H, the bound χ^h(_̱1)≪ d^-15 holds. Hence 

    |F_χ,H(_̱1, …, _̱d)|^2 ≤ (2H+1)^d (O(e^-dH) + O(d^-15H))^d ≪ d^-10d H^2d

as desired.


<ref> applies to all characters χ of order ≥ e^10d, but gives a relatively weak upper bound. In <ref>, we will prove that a stronger bound can be obtained if a small set of exceptions is allowed. We begin by describing the exceptional characters in the following lemma.



There is some absolute constant t_0≥ 1 such that the following holds.

Let N,G,d,X and _̱i be as in <ref>. Let H≥ e^10d. 

Let χ∈G be a character of order ≥ e^10d such that

    |F_χ,H(_̱1, …, _̱d)|^2  > e^-2td H^2d

for some t with t_0 ≤ t≤ 2d.

Then there are integers -2H ≤ h_1, h_2≤ 2H with 0 < h_2-h_1 ≤ e^3t such that both L(s, χ^h_1) and L(s, χ^h_2) have a zero in the region

    1-t/100dX.




As in the proof of <ref>, we have

    |F_χ,H(_̱1, …, _̱d)|^2  = |∏_i=1^d ∑_|h|≤ Hχ^h(_̱i) |^2 ≤ (2H+1)^d (∑_|h|≤ 2Hχ^h(_̱1))^d.

Let I_1 be the set of all -2H≤ h≤ 2H such that χ^h is principal. Since χ has order ≥ e^10d, we have

    |I_1| ≪ 1+e^-10dH ≪ e^-10dH.
 

Let I_2 be the set of all -2H≤ h≤ 2H such that L(s, χ^h) has a zero in the region <ref>. By contradiction, suppose that the conclusion of <ref> does not hold. Then any sub-interval of [-2H, 2H] of length e^3t contains at most one element of I_2. This implies that 

    I_2≪ 1+e^-3tH ≪ e^-3tH.


Moreover, for any integer h∈ [-2H, 2H]∖ (I_1∪ I_2), the character χ^h is non-principal and has no zero in the region <ref>, which by <ref> implies that 

    χ^h(_̱1)≪ X^-t/(100d)(log (NX))^3 ≪ d^-10t d^6  ≪ e^-3t.


Therefore, we can bound

    ∑_|h|≤ 2Hχ^h(_̱1)≪ |I_1| + |I_2| + e^-3tH ≪ e^-10dH+e^-3tH ≪ e^-3tH.

Hence, by <ref> we get

    |F_χ,H(_̱1, …, _̱d)|^2 ≤ e^O(d)e^-3tdH^2d,

which contradicts the assumption in the statement if t_0 is chosen to be sufficiently large.


We wish to use a zero-density estimate again to show that there are few characters satisfying the conclusion of <ref>. For this step to work, we need to restrict to the subgroup G^ of the full character group G, where  is the integer defined in <ref>.



Let t_0≥ 1 be the constant from <ref>. Let N,G,d,X and _̱i be as in <ref>. Let H≥ e^10d and let ≥ 1 be the integer defined in <ref>.

For every t≥ t_0,

    {χ∈G^ : (χ) ≥ e^10d,  |F_χ,H(_̱1, …, _̱d)|^2  > e^-2td H^2d}≪ e^td/2.




If t≥ 2d, the bound <ref> is trivially satisfied as the right-hand side is ≫ N. We may thus assume that t_0 ≤ t≤ 2d, in which case <ref> applies.

Let E_t be the set of all characters ψ modulo N such that L(s, ψ) has a zero in the rectangle defined in <ref>. By <ref>, this set E_t has size 

    E_t≪ (NX)^(2+1/2)t/(100 d)≪ e^td/20.


For every χ∈G of order ≥ e^10d, if |F_χ,H(_̱1, …, _̱d)|^2  > e^-2td H^2d then by <ref> we can write 

    χ^h = ψ_1 ψ_2

for some integer 0< h < e^3t and some characters ψ_1, ψ_2∈ E_t. Hence, the left-hand side of <ref> is

    ≤∑_ψ_1,ψ_2∈ E_t∑_0 < h < e^3t{χ∈G^M  :  χ^h = ψ_1ψ_2}.

Since G^ and G^ are isomorphic, <ref> implies that

    {χ∈G^ :  χ^h = ψ_1ψ_2}≤ h^d/10≤ e^3td/10.


Inserting <ref> into <ref>, we conclude that the left-hand side of <ref> is

    ≤ |E_t|^2 e^3t e^3td/10≤ e^3t e^4td/10≪ e^td/2

as claimed.


Combining the previous lemmas, we obtain a suitable bound for the sum of second moments of F_χ,H(_̱1, …, _̱d) over all large-order characters in G^.



Let N,G,d,X and _̱i be as in <ref>. Let ≥ 1 be the integer defined in <ref>. For H≥ e^10d, we have

    ∑_χ∈G^
    (χ) ≥ e^10d |F_χ,H(_̱1, …, _̱d)|^2^1/2≪ d^-2d H^d.




By <ref>, we know that |F_χ,H()|^2^1/2≤ C d^-5d H^d for all characters χ∈G of order ≥ e^10d, where C>0 is an absolute constant (as before,  stands for _̱1, …, _̱d). Therefore, 

    ∑_χ∈G^
    (χ) ≥ e^10d |F_χ,H()|^2^1/2≤∑_m = m_0^+∞∑_χ∈G^
    (χ) ≥ e^10d e^-m+1H^d e^-m <  |F_χ,H()|^2^1/2 H^-d≤ e^-m+1(χ)

where m_0 := ⌊ 5dlog d - log C + 1⌋. We may assume that m_0 ≥max(t_0d, 4dlog d), since otherwise d≪ 1 and <ref> is trivially satisfied (given that |G^| ≤ N ≪ 1 when d≪ 1).

Applying <ref> with t := m/d, we obtain that for every m ≥ t_0d,

    {χ∈G^ : (χ) ≥ e^10d,  |F_χ,H()|^2^1/2 > e^-mH^d}≪ e^m/2.

Therefore, 

    ∑_χ∈G^
    (χ) ≥ e^10d |F_χ,H()|^2^1/2≪∑_m = m_0^+∞ e^m/2 e^-m+1 H^d ≪ e^-m_0/2 H^d

which is ≪ d^-2d H^d as m_0 ≥ 4dlog d.





 §.§ Geometry of numbers



In this section, we show how to pass from good estimates on the number of lattice points in certain regions to the existence of a short basis for the lattice. 



Let L≥ 1 be an integer. Cover the cube [-L,L]^d by (2L)^d cubes of side length 1 in the obvious way. Label these unit cubes C_1, …, C_(2L)^d (in any order). Let V⊂^d be a hyperplane through the origin. Then the number of unit cubes C_i intersecting V is

    ≤ (d+1) (2L)^d-1.




Let e_1, …, e_d be the standard basis for ^d. Let v∈^d be a unit vector orthogonal to V. Without loss of generality, since v_2 = 1, we may assume that v, e_1≥ 1/√(d). 

Suppose that V intersects two unit cubes C_i and C_j where C_i = C_j + ke_1 for some integer k ≥ 0. Then, there is some p∈ C_i and some w∈^d with w_∞≤ 1 such that p∈ V and p+ke_1+w∈ V. Therefore, ke_1+w ∈ V and thus ke_1+w,v = 0. Noting that

    ke_1+w, v≥ k e_1, v - w_2v_2≥k/√(d) - √(d),

we deduce that k≤ d.

We have thus proved that, for any cube C_i, there are at most d+1 cubes of the form C_i+ke_1 for some k∈ which intersect V. The lemma follows. 


The next lemma allows us to convert information about the number of lattice points in cubes into the existence of short linearly independent lattice vectors.



Let d ≥ 1. Let Λ⊂^d be a full-rank lattice. Let 2≤ H_0 < H_1 be real numbers such that H_1/H_0 is an integer. Suppose that, for i∈{0, 1},

    Λ∩ [-H_i, H_i]^d = θ_i (2H_i+1)^d/(^d/Λ)

where θ_0, θ_1>0 satisfy H_1/H_0 > θ_0/θ_1 d (52)^d. Then Λ∩ [-H_1, H_1]^d contains d linearly independent vectors.



By contradiction, suppose that there exists a linear hyperplane V containing all the points v∈Λ∩ [-H_1, H_1]^d.

Let L = H_1/H_0. The large cube [-H_1, H_1]^d can be covered by (2L)^d axis-parallel cubes of side length H_0 in the natural way. By <ref>, we can bound

    Λ∩ [-H_1, H_1]^d≤ (d+1) (2L)^d-1sup_C Λ∩ C,

where the supremum runs over all (not necessarily centred) axis-parallel cubes C⊂^d of side length H_0. If C is such a cube and v∈Λ∩ C, then C ⊂ v + [-H_0, H_0]^d, which implies that 

    Λ∩ C≤Λ∩(v + [-H_0, H_0]^d) = Λ∩ [-H_0, H_0]^d.

Thus,

    Λ∩ [-H_1, H_1]^d≤ (d+1) (2L)^d-1Λ∩ [-H_0, H_0]^d.

Plugging in our lattice point estimate <ref>, we get

    θ_1 (2H_1+1)^d≤ (d+1) (2L)^d-1θ_0 (2H_0+1)^d.

Using 2H_1+1 ≥ 2LH_0 and d+1 ≤ 2d, this implies that L ≤θ_0/θ_1 d (2+1/H_0)^d, contradicting the inequality in the statement of the lemma.


The linearly independent vectors given by <ref> can be upgraded to a genuine basis for Λ by standard geometry of numbers, namely Mahler's theorem. We state this fact in a slightly more general situation.



Let d≥ 1. Let Λ_1, Λ_2 ⊂^d be full-rank lattices such that M Λ_1 ⊂Λ_2 for some integer M≥ 1. Suppose that Λ_1 contains d linearly independent vectors in [-H, H]^d for some H>0. Then, Λ_2 admits a basis where each basis vector has Euclidean norm ≤ d^3/2MH.



By assumption, there are linearly independent vectors v_1, …, v_d ∈Λ_1 ∩ [-H, H]^d. Then Mv_1, …, Mv_d are linearly independent vectors of Λ_2 such that max_i∈ [d]Mv_i_2 ≤√(d) MH. 

Let B⊂^d be the unit ball for the Euclidean norm. Let 0 < λ_1 ≤⋯≤λ_d be the successive minima[See <cit.> for the definition of successive minima.] of B with respect to Λ_2. Since Mv_1, …, Mv_d ∈Λ_2 are linearly independent, we deduce from the above that λ_d ≤√(d) MH.

By Mahler's theorem (see <cit.>), we conclude that Λ_2 admits a basis of vectors of Euclidean norm 

    ≤ d λ_d ≤ d^3/2MH,

which is what we needed to show.





 §.§ Short basis vectors


We can now prove our main technical result, which may be of independent interest.



Let N>2 be an integer. Let d := ⌈√(log N)⌉ and X := d^10^3d.

Let _̱1, …, _̱d be i.i.d. random variables, each uniformly distributed in the set of primes ≤ X not dividing N. Let r≥ 0 and let _1, …, _r be arbitrary[In particular, the _i are not assumed to be independent or identically distributed.] random variables taking values in N.

Then, with probability 1 - O(d^-d), the lattice

    Ł := { (e_1, …, e_d, f_1, …, f_r) ∈^d+r :  ∏_i=1^d _̱i^e_i∏_i=1^r _i^f_i≡ 1 N}

has a basis consisting of vectors of Euclidean norm ≪ e^42(d+r).




The constant 42 in the exponent is by no means the limit our techniques. For example, using smooth cutoffs in <ref> would significantly reduce the error term in <ref> and hence lower this constant. We have not performed such optimisations to keep the paper as simple as possible.



Let M := (N) be the integer defined in <ref>. We introduce the auxiliary lattice

    Ł_M :=  { (e_1, …, e_d, f_1, …, f_r) ∈^d+r :  ∏_i=1^d _̱i^M e_i∏_i=1^r _i^M f_i≡ 1 N}.

By <ref>, we have the lattice point estimate

    Ł_M∩ [-H, H]^d+r = (1 + O(e^31(d+r)H^-1)) (2H+1)^d+r/|_̱1^M, …, _̱d^M, _1^M, …, _r^M | + 1/|G^M|∑_χ∈G^M
    (χ) ≥ e^10dF_χ,H(, )

for every integer H≥ e^31(d+r), where

    F_χ,H(, ) := F_χ, H(_̱1, …, _̱d, _1, …, _r) = (∏_i=1^d ∑_|h|≤ Hχ^h(_̱i)) (∏_i=1^r ∑_|h|≤ Hχ^h(_i)).

Since the _i have unknown distributions, we will use the trivial bound

    F_χ,H(,)≤ (2H+1)^r F_χ,H(_̱1, …, _̱d).

Applying <ref>, we deduce that, for all H≥ e^10d,

    ∑_χ∈G^
    (χ) ≥ e^10d |F_χ,H(, )|^2^1/2≪ d^-2d (2H+1)^d+r.

By the L^2 triangle inequality and Chebyshev's inequality, this implies that, for fixed H≥ e^10d,

    (∑_χ∈G^M
    (χ) ≥ e^10dF_χ,H(, ) > d^-d(2H+1)^d+r) ≪ d^-2d.


Let H_0 := d ⌈ e^31(d+r)⌉ and H_1 := ⌈ d (d+r) (5/2)^d+r⌉ H_0. We apply <ref> twice, once with H = H_0 and once with H = H_1 to obtain the following: with probability 1-O(d^-d), the two estimates

    Ł_M∩ [-H_0, H_0]^d+r = (1 + O(1/d)) (2H_0+1)^d+r/|_̱1^M, …, _̱d^M, _1^M, …, _r^M |

and

    Ł_M∩ [-H_1, H_1]^d+r = (1 + O(1/d)) (2H_1+1)^d+r/|_̱1^M, …, _̱d^M, _1^M, …, _r^M |

simultaneously hold. 

We now apply <ref>. By our choice of H_0 and H_1, the inequality in the statement is satisfied provided that d is sufficiently large. We can assume that d is large enough as, for d≪ 1, we have N ≪ 1 and <ref> is trivially true. Thus, <ref> implies that Ł_M ∩ [-H_1, H_1]^d+r contains d+r linearly independent vectors, with probability 1-O(d^-d). By <ref>, since MŁ⊂Ł_M, we conclude that, with probability 1-O(d^-d), Ł admits a basis of vectors of Euclidean norm 

    ≪ d^3/2 M H_1 ≪ d^3/2 e^10d d^2 (d+r) (5/2)^d+r e^31(d+r)≪ e^42(d+r)

using the bound M ≤ e^10d given by <ref>. This completes the proof.





§ APPLICATIONS TO QUANTUM COMPUTING



In this section, we prove the correctness of efficient quantum algorithms for factoring and for the discrete logarithm problem by applying our version of Regev's number-theoretic conjecture, <ref>.



 §.§ Preparatory lemmas




Let N, d, m ≥ 2 be integers. There is a classical algorithm that, given integers 0≤ a_1, …, a_d≤ 2^m and exponents t_1, …, t_d ∈{0, 1}, computes the product

    ∏_i=1^d a_i^t_iN

in time O(md (log d) log(md)).



This is similar to <cit.> or <cit.> but for a general value of m. Without loss of generality, assume that d is a power of 2, say d = 2^l. We proceed to compute this product in a binary tree fashion. Let T(k) be the complexity of multiplying any k of these numbers a_i^t_i modulo N. Note that T(2k) ≤ 2T(k) + O(M(mk)) where M(x) is the time needed to multiply two integers having at most x bits. By the work of Harvey and van der Hoeven <cit.>, it is known that M(x) = O(xlog x), which leads to the bound

    T(d) ≪∑_j=0^l 2^j M(md/2^j+1) ≪∑_j=0^l md log(md/2^j+1) ≪ md (log d) log(md).

as claimed.


We can turn this into a quantum circuit with the following well-known fact.



Any classical circuit can be “compiled” into a reversible quantum circuit that carries out the same computations, with the number of gates and qubits used being proportional to the size of the classical circuit.



This well-known fact is explained in <cit.>.




Let N be a sufficiently large integer. Let d := ⌈√(log N)⌉ and X = d^10^3d. Let k = d^4.

Let _1, …, _k be i.i.d. random random variables uniformly distributed in {1, …, X}. Then, the probability that at least d of these _i are prime numbers not dividing N is ≥ 1 - O(1/N).



Since N has ≪log N prime factors, and since the number of primes ≤ X is ≫ X/log X, we have 

    _1  is prime and _1∤ N≥c/log X

for some absolute constant c>0. Thus, if E_i is the event that _i is not prime or divides N, then by the union bound and independence,

    (⋃_I ⊂ [k]
     |I|> k-d⋂_i∈ I E_i) ≤∑_l< dk  l(1-c/log X)^k-l≤ dk^d e^-c(k-d)/log X≪ e^-d^2

as needed.





 §.§ The discrete logarithm problem


We now prove <ref>. For convenience, we restate it here.

*


Suppose we are given an integer N>2 and elements g,y∈N such that y lies in the subgroup generated by g in N. Let d := ⌈√(log N)⌉ and X := d^10^3d. Let _̱1, …, _̱d be i.i.d. random variables, each uniformly distributed in the set of primes ≤ X not dividing N.

Consider the random lattice

    Ł_,g,y := {(e_1, …, e_d, f_1, f_2) ∈^d+2 :  (∏_i=1^d _̱i^e_i) g^f_1 y^f_2≡ 1 N}.

By <ref>, with probability 1 - O(d^-d), this lattice has a basis consisting of vectors of Euclidean norm ≪ e^42d. 

Computing the discrete logarithm of y with respect to the base g reduces (with a polynomial-time classical algorithm) to computing a short basis for Ł_,g,y. To see why this is the case, suppose that we managed to compute a basis v_1, …, v_d+2 for Ł_,g,y with max_i v_i_2 ≪ e^42d. It is then easy to find a vector in Ł_,g,y of the form (0, …, 0, x, 1) for some integer x (note that such a vector exists since we assume that y∈g). Indeed, this amounts to solving a linear system with integer coefficients. The complexity of solving an integer linear system is polynomial in the dimensions of the matrix and the number of bits of the coefficients, which are both O(d) since max_i v_i_2 ≪ e^42d (see <cit.>). This yields an integer x such that g^x ≡ y N.

The algorithm for solving the discrete logarithm problem thus proceeds as follows.

	
  * Generate d primes b_1, …, b_d independently and uniformly at random in the set of primes ≤ X not dividing N. To do this, it suffices to generate d^4 independent random integers ≤ X. By <ref>, the required conditions will be satisfied for at least d of those with probability 1-O(1/N). This first step takes polynomial time on a classical computer using the AKS primality test <cit.>.
	
  * Use the procedure described by Ekerå and Gärtner <cit.> to obtain a basis for the lattice Ł_b,g,y. This involves making O(d) calls to a quantum circuit, followed by polynomial-time classical post-processing. This step is now guaranteed to succeed with probability Θ(1), using the fact that Ł_b,g,y has a basis of vectors of Euclidean norm ≪ e^42d with probability 1 - O(d^-d) (<ref>).
	
  * Compute the discrete logarithm of y in classical polynomial time using this basis, as explained above. 


It remains to analyse the gate and space costs of the quantum part of this algorithm. 

The only modification needed to the analysis of the quantum circuit in <cit.> comes from the fact that b_1, …, b_d are not quite as small as in <cit.>. In <cit.> (and more generally in <cit.>), the primes b_i are assumed to have O(log d) bits. In the present situation, we instead have the bound b_i≤ X = d^10^3d, i.e. each b_i has O(dlog d) bits. 

The only place in <cit.> where the assumption on the size of the b_i's are used is in <cit.>. In turn, the only point in the proof of <cit.> where this assumption is needed in when <cit.> is invoked (as a black box). The proof of <cit.> is given in <cit.>, and the size assumption on the b_i's only comes up in <cit.>.

The result <cit.> essentially[There are extra details pertaining to the precise use of qubits (e.g. restoring the ancilla qubits to |0⟩), but these will be the same in our setup.] states that there is a quantum circuit using O(d log^3d) gates and O(d log^3d) qubits to perform the computation of ∏_i=1^d a_i^t_i where t_i∈{0, 1} and a_i are integers on O(log d) bits. This is a special case of <ref> (used together with <ref>) applied with m = O(log d). In our case, we just apply <ref> with m = O(dlog d), together with  <ref> to convert the classical circuit into a quantum one. This yields a quantum circuit having O(d^2log^3 d) gates and O(d^2log^3 d) qubits to compute ∏_i=1^d b_i^t_i.

The number of gates of the quantum circuit <cit.> is 

    O( d (nlog n + dlog^3 d) ) = O(n^3/2log n)

(because <cit.> is used O(d) times, see <cit.> and the surrounding explanations). Note that this is the same as for Regev's algorithm (see <cit.>). In our case, the number of gates is

    O( d (nlog n + d^2log^3 d) ) = O(n^3/2log^3 n).


The space optimisations of Ragavan and Vaikuntanathan keep the total number of qubits for their circuit <cit.> under

    O(nlog n + dlog^3 d) = O(nlog n),

due to the way the qubits are used and restored in the main loop of <cit.>. In our situation, the number of qubits is

    O(nlog n + d^2log^3 d) = O(nlog^3 n).


In summary, our final quantum circuit has O(n^3/2log^3 n) gates and O(n log^3 n) qubits. As noted in <cit.>, the fact that the two elements g and y are not small (g and y can be as large as N, as opposed to the b_i's) does not affect these complexity bounds.




In the proof of <ref>, we used the naive <ref> to convert a classical circuit into a quantum one. As mentioned in <ref>, it is possible to save a factor of log n in the space cost for <ref> by reusing certain qubits when performing the quantum computation corresponding to <ref>. 





 §.§ Factoring integers


In this section, we prove <ref>. 



Let N>1 be an odd integer with at least two distinct prime factors. Let  be a random variable, uniformly distributed in N. Then  contains a non-trivial square root of 1 modulo N with probability ≥ 1/2.


This elementary number-theoretic fact is well-known – it was already needed for Shor's algorithm <cit.>. See <cit.> for a detailed proof.



*


We can assume that N is odd and not a perfect prime power, as otherwise it is easy to factor N in polynomial time with a classical computer (see <cit.>). 

Let d := ⌈√(log N)⌉ and X := d^10^3d. The probabilistic algorithm to find a non-trivial divisor of N goes as follows.


	
  * Generate d primes b_1, …, b_d independently and uniformly at random in the set of primes ≤ X not dividing N. Sample another integer x uniformly chosen in N. As in the proof of <ref>, this can be done classically in polynomial time with probability 1-O(1/N).
	
  * Use the algorithm of Ekerå and Gärtner <cit.> to obtain a basis for the lattice
	
    Ł_b,x := {(e_1, …, e_d, f) ∈^d+1 :  (∏_i=1^d b_i^e_i) x^f ≡ 1 N}.

	 This involves making O(d) calls to a quantum circuit, followed by polynomial-time classical post-processing. By <ref>, Ł_b,x has a basis of vectors of Euclidean norm ≪ e^42d with probability 1 - O(d^-d), which means that this step is guaranteed to work with probability Θ(1).
	
  * Using the short basis for Ł_b,x computed in the previous step, find the vector of the form (0, …, 0, r) in Ł_b,x with r≥ 1 as small as possible. This involves solving a linear system with integer coefficients, which can be done efficiently as in the proof of <ref>. This integer r is the order of x in N. By <ref>, with probability ≥ 1/2, this order r will be even and the element x^r/2 will be a non-trivial square root of 1 modulo N. Hence, N divides the product (x^r/2-1)(x^r/2+1) but neither term individually, which implies that (N,  x^r/2-1 N) is a non-trivial divisor of N.


The analysis of this algorithm is identical to the corresponding part of the proof of <ref>.






§ BOUNDS FOR CHARACTER SUMS OVER PRIMES



In this appendix, we prove <ref>. We start by stating the truncated explicit formula for L(s, χ).



Let q≥ 2. Let χ be a non-principal Dirichlet character modulo q. For x≥ T≥ 2, we have

    ∑_n≤ xχ(n) Λ(n) = -∑_ρ = β+iγ
    γ≤ Tx^ρ-1/ρ + O(x log^2(xq)/T)

where the sum runs over all non-trivial zeros ρ of L(s, χ) with multiplicity.


This is <cit.>.


We will also need the following standard bound for the number of zeros of L(s, χ) in the critical strip at some height t.


Let q≥ 1 and let χ be a Dirichlet character modulo q. Let t∈. The number of zeros ρ = β + i γ of L(s, χ) in the rectangle 0≤β≤ 1, t≤γ≤ t+1 is ≪log(q(|t|+2)), where zeros are counted with multiplicity.


This is <cit.>.




By <ref>, choosing T = x^1-α - 1, we have

    ∑_n≤ xχ(n) Λ(n) ≪log(qx)  ∑_t∈
     |t| ≤ x^1-α-1max_ρ = β+iγ
    γ - t≤ 1/2x^ρ-1/ρ + x^αlog^2(qx),

where the maximum is over all zeros of L(s, χ) in the specified region. Since x^ρ≤ x^α for all zeros ρ = β + iγ with imaginary part |γ|≤ x^1-α by our zero-free rectangle assumption, we can bound

    x^ρ-1/ρ≪x^α/1+|γ|

(using for example that x^ρ-1/ρ = ∫_1^x t^ρ-1 dt for |γ|<1). Thus, we obtain

    ∑_n≤ xχ(n) Λ(n) ≪log(qx) x^α∑_|t|≤ x1/1+|t|+ x^αlog^2(qx)≪ x^αlog^2(qx).

Discarding perfect prime powers, which contribute O(x^1/2log x), and using partial summation, we get

    ∑_p≤ xχ(p) ≪x^αlog^2(qx)/(1-α)log x.

We may assume that 1-α≥1/log x, as otherwise <ref> is trivial. If this is the case, we conclude that

    1/π(x)∑_p≤ xχ(p) ≪x^αlog^2(qx)/π(x)≪ x^-(1-α)log^3 (qx)

as claimed.






amsplain




