On speeding up factoring with quantum SAT solvers


The circuit SAT problem asks whether there exists an input for a given Boolean circuit, encoded as a SAT instance, such that the output will be TRUE. For a satisfiable circuit SAT formula in v variables one can easily find a solution with v queries to a decision oracle for SAT. In practice, the best known algorithms for deciding SAT implicitly also provide a solution and thus the repeated applications of a SAT decision algorithm are not necessary. Using binary encoding for integers we construct circuits that encode a predicate on numbers, so that solving the corresponding SAT instance is a search for numbers satisfying the predicate. From here on we refer to this process as “solving the circuit”.

Instead of using Grover’s search to look for ((a,b) in T) as in the low-resource quantum NFS4, we let a SAT solver find these using the encoded circuit. In particular, we encode the predicate “F(ab) is a y-smooth number” on the input pair (ab), while we assume the conditions (|a| le u) and (0 < b le u) are enforced by the input encoding. Similar to the low-resource quantum NFS, we assume that the case (gcd {a,b} > 1) is handled by post-processing.

A naive algorithm for circuit SAT simply evaluates the full circuit for every possible input until a one is found at the output. For a circuit with v input variables and size g this strategy has runtime (O(2^v g)), which is the runtime we assume for solving circuits. Given that circuit SAT is an NP-complete problem, it is widely believed that no efficient algorithm exists. However, in practice modern SAT solvers perform well on solving large SAT instances for certain problems, so that the conjectured runtime requires some confirmation in the form of benchmark results.

In this section we analyze a few natural circuits for implementing the required predicate and prove the approach does not offer any improvement over the classical NFS. We show that, in general, circuits encoding all primes (p_ile y) or the prime exponents (e_i) can not be solved efficient enough. On the other hand, solving a circuit implementing the Elliptic Curve Method (ECM)6 is shown to achieve runtimes comparable to that of the classical NFS. We recall a few results important for the analysis.

Lemma 1

  1. 1.

    (|(a+bm)| le 2 u N ^{1/d})
    and
    (|g(a,b)| le (d+1) N^{1/d} u^{d})

  2. 2.

    (log |F(a,b)| in O((log N)^{2/3}(log log N)^{1/3}))

  3. 3.

    (log log |F(a,b)| in O(log log N))

Proof

  1. 1.

    Follows directly from the definitions of g and m.

  2. 2.

    (log |F(a,b)| le log 2(d+1) + frac{2log N}{d} + (d+1) log u in O(frac{log N}{d} + d log u)). Now

    $$begin{aligned} frac{log N}{d} + d log u =&(epsilon delta + delta ^{-1} + o(1))(log N)^{2/3}(log log N)^{1/3} nonumber \&subseteq O((log N)^{2/3}(log log N)^{1/3}). end{aligned}$$

    (4)

  3. 3.

    Taking logs of the expression above, the dominant term is (log log N).

(square)

Lemma 2

If F(ab) is y-smooth, then (omega (F(a,b)) in O((log N)^{2/3}(log log N)^{1/3})), where (omega (n))is the number of prime divisors of n without multiplicity.

Proof

All the prime factors of F(ab) are at least 2, so (Omega (F(a,b)) le log _2 F(a,b)), where (Omega (n)) is the number of prime divisors of n with multiplicity. Since (omega (n) le Omega (n)), the result follows from Lemma 1. (square)

Circuit with variable exponents

A natural idea is to hard-code all the primes (p_i le y) into the circuit (see Fig. 1), and let ab and (e_i) be the variables, where (1 le i le pi (y)), and (pi (x)) counts the number of primes (le x). A satisfying assignment finds the exponent (e_i) for each prime (p_i) that forms the factorization of F(ab):

$$begin{aligned} F(a,b) = prod _{i=1}^{pi (y)}p_i^{e_i} end{aligned}$$

(5)

Figure 1

Circuit directly encoding Eq. (5). Variables are shown in boldface. The (Pi) gate outputs the product of all input values.

The circuit provides no improvement over the classical NFS. Indeed, the number of bits necessary to represent (vec {e} = (e_1, e_2,…,e_{pi (y)})) is lower-bounded by (pi (y) in y^{1+o(1)}), which implies that the time to solve the circuit is at least exponential in (L^{beta +o(1)}), much larger than the overall NFS complexity. This also proves the following.

Proposition 1

Any circuit that has
(vec {e})
as variable input to be found by an exponential-time SAT solver is not sufficient to speed up integer factorization.

Despite the theoretical result above, one might hope that SAT solvers are able to pick up on specific patterns of this circuit and exploit them to improve the overall runtime. In order to investigate this possibility, we encoded this circuit into a satisfiability instance and ran benchmarks using MapleCOMSPS11.

A circuit is generated for each number N, with all other parameters generated as described before and by setting (o(1)=0). In order to keep the circuit from growing too large, intermediate values in the computation of (prod p_i^{e_i}) are truncated to (log _2 F(u,u)) bits and multiplication is computed by schoolbook multiplication. Despite these techniques the SAT instances can grow large: on the tested range they contain up to eighty thousand variables after simplification. This is partially explained by the fact that F (both the bound F(uu) and the found values F(ab)) is much larger than N for these small values of N. With the used parameters the desired (F(u,u) < N) will only occur for 140 bit values of N and greater. All code for generating circuits (including tests for correctness), benchmarks and measurements is made available online12.

Figure 2 shows the benchmarking results. For each (N le 2^{18}) we measured the median time of solving the same instance many times, for larger N we report the solver runtime directly. Each measured runtime is multiplied by y(N).

Since there are many (ab) that satisfy the predicate, we could run the solver many times to find multiple ((a,b) in T). Closer inspection of our results indicate that the SAT solver does indeed find many valid pairs. If collisions are a problem, we could arbitrarily partition the search space by putting restrictions on the input and have multiple solvers work in parallel. Alternatively we could encode the negation of found solutions as a new SAT clause. Determining which approach is best is left as an open question, but here we assume that finding y(N) solutions takes y(N) times the resources as finding one solution.

Given the asymptotic behaviour displayed in Fig. 2 it appears that the optimizations from the SAT solver do not seem large enough to provide a speed-up to the NFS. Although this is not a statement about quantum SAT solvers, it is one more argument supporting the lack of speedup attributable to the SAT solver learning specific structures of this problem.

Figure 2
figure2

Scaling of solving times for the variable exponent circuit.

Circuit with variable factors

Exploiting the small number of prime factors of F(ab) following from Lemma 2, one can hope to turn the factors into variables (see Fig. 3). At the end, the factors (q_i) must multiply to F(ab). Note that the (q_i) need not be prime, but only (le y). This restriction could be enforced at no cost by allowing at most (lceil log _2 y rceil) bits to encode each (q_i) or by an efficient test on each input.

Figure 3
figure3

Circuit with variable factors. Variables are shown in boldface. The (Pi) gate outputs the multiplication of all input values.

However, this strategy is too costly. That is, the number of variables in the circuit is (2 log u + sum _{i}log q_i > log prod _{i}q_i). In the very best case that the (q_i) are encoded with the exact number of necessary bits, which is (log F(a,b)), then by Lemma 1, results in (L_N[2/3, cdot ]) time to solve the circuit. This also implies the following.

Proposition 2

If (prod _i q_i = F(a,b)), any circuit that has the (q_i)as variables to be found by an exponential-time SAT solver is not sufficient to speed up integer factorization.

ECM circuit

The Elliptic Curve Method (ECM) is a factoring algorithm devised by Lenstra6. One of its key features is that its runtime is conjectured to depend on the smallest prime factor of the number being factored, making it very suitable for smoothness detection. We create a circuit that executes repeated runs of the ECM to obtain prime factors (p_i le y) of F(ab). For each prime obtained, repeated divisions are performed in order to eliminate that prime from the factorization. Figure 4 shows a simplified circuit. There are implicit operations such as checking if the obtained prime is (le y) and only performing division when the remainder is zero. RAND represents a random choice of parameters for the ECM, more specifically axy, using the notation by Lenstra6, section (2.5). Note that, for a given SAT instance, the random generator seeds are fixed.

This circuit meets the desirable time complexity by decreasing the number of variables significantly. Indeed, the only variables are ab, so the search space is just U. The following theorem establishes the size and probability of success of the ECM circuit.

Figure 4
figure4

Circuit implementing the Elliptic Curve Method (ECM). Variables are shown in boldface. RAND stands for a source of randomness for the parameters of the ECM.

Theorem 3

The ECM circuit can be designed to have size upper-bounded by (L_N[1/6, sqrt{2beta / 3} + o(1)])and probability of success (1 – o(1)).

Proof

From Lenstra’s work6, (2.10), one run of the ECM, with appropriate choice of parameters, finds with probability at least (1-e^{-1}) a non-trivial divisor of n in time K(p)M(n), where p is the least prime divisor of n, (K(p) in L_p[1/2,sqrt{2}+o(1)]) and (M(n) in (log n)^{1+o(1)}). It is uncertain that the found non-trivial divisor is the smallest prime dividing n, but in practical circumstances this will often be the case6, (2.10). For our purposes the divisors are allowed to be any factor of F(ab), as long as it is (le y).

By Lemma 2, one can choose a constant c so that (omega (F(a,b))le c (log N)^{2/3}(log log N)^{1/3}). However, we increase (c rightarrow c + Delta), (Delta > 0), to allow for ECM runs to fail. If there are (B := (c + Delta ) (log N)^{2/3}(log log N)^{1/3}) ECM blocks, the probability of success is the probability of at least (omega (F(a,b))) events out of B succeeding. This can be seen as a binomial process with probability of success (p=1-frac{1}{e}). In the limit (N rightarrow infty implies B rightarrow infty), (text{Binomial}(x;B,p) rightarrow text{Normal}(x; B p, B p (1-p))). We seek

$$begin{aligned} Pr (x ge omega (F(a,b)))&= frac{1}{sqrt{2 pi B p (1-p)}} int _{omega (F(a,b))}^{infty }exp {left[ -frac{(x – B p)^2}{2 B p (1 – p)}right] } dx nonumber \&= frac{1}{2}left[ 1 – {text {erf}}left( frac{(log N)^{2/3}(log log N)^{1/3} (c – pc – pDelta )}{sqrt{2 (c+Delta ) (log N)^{2/3}(log log N)^{1/3} p (1-p)}}right) right] end{aligned}$$

(6)

Note that if we let (Delta in O(1)), that is, (frac{partial Delta }{partial N} = 0), the circuit would not work, since (lim _{N rightarrow infty } Pr (x ge omega (F(a,b))) = 0). However, if we let (Delta = Delta (N)) such that (lim _{N rightarrow infty } Delta (N) = infty), then (lim _{N rightarrow infty } Pr (x ge omega (F(a,b))) = 1), as desired. Hence choosing (Delta in Theta (log log N)) suffices and does not alter the final complexity.

Hence, let the circuit repeat the ECM step (O((log N)^{2/3}(log log N)^{4/3})) times and perform (O((log N)^{2/3}(log log N)^{1/3})) conditional divisions of an obtained prime, since this is the maximum power a prime factor can have in the factorization of F(ab), by Lemma 1. Each ECM has a different run-time since the least prime p changes and n is subsequently divided by the discovered factors. For upper-bound estimations, however, one can fix (p=y) and (n=N). In order to estimate the size of the ECM block, one can multiply the time and space complexity. The former is K(y)M(N) and the latter is estimated to be (O(log N)). This yields a total circuit size of (O((log N)^{2/3}(log log N)^{1/3})O((log N)^{2/3}(log log N)^{4/3}) K(y) M(N) O(log N) subseteq L_N[1/6, sqrt{2 beta /3} + o(1)]). (square)

In order to analyze the runtime of solving the ECM circuit to find smooth F(ab), we need the following.

Definition 1

If a search space E has size (#E), an algorithm that is able to search through E within time (O(#E^{1/gamma })) is said to achieve a (gamma)-speedup.

For instance, Grover’s search achieves a 2-speedup. The following establishes a generalization of the runtime analysis by Bernstein, Biasse and Mosca4.

Theorem 4

If an algorithm A achieves a (gamma)speedup, for (gamma >0), and the linear algebra step in the NFS is assumed to take (L^{2beta +o(1)}), the NFS can use A to run in time (L^{root 3 of {frac{32(gamma +1)}{9gamma ^2}} + o(1)}).

Proof

By Lemma 1, (|F(a,b)| le 2(d+1)N^{2/d}u^{d+1}). As shown in4, section 3, a uniform random integer in (big [1, 2(d+1)N^{2/d}u^{d+1}big ]) has a smoothness probability of (L^{-(2/delta + delta epsilon + o(1))/(3beta )}). We use the same heuristic and assume that this is also the smoothness probability of F(ab). Since there need to be (L^{beta +o(1)}) smooth F(ab) in the search space U of size (#U in L^{2epsilon +o(1)}), we must have (2epsilon ge beta + (2/delta + delta epsilon )/(3beta )). Since the constants are positive, (epsilon big (2-frac{delta }{3beta }big ) ge beta + frac{2}{3beta delta }) and (6beta /delta > 1). With this relation, the smoothness probability becomes (L^{beta – 2epsilon + o(1)}).

Now, as in the analysis of the low-resource algorithm4, we partition U in any systematic fashion into (L^{beta +o(1)}) parts of size (L^{2epsilon -beta +o(1)}), each containing (L^{o(1)}) smooth F(ab) with very high probability. Algorithm A can search each part in (L^{(2epsilon -beta )/gamma + o(1)}) time, for a total time of (L^{2epsilon /gamma + beta (1-1/gamma ) + o(1)}).

When balancing against the linear algebra step of (L^{2beta +o(1)}) time, we obtain (epsilon = beta big (frac{gamma +1}{2}big )). Hence (beta = frac{(gamma +1)delta + sqrt{delta ^2 + 96gamma /((gamma +1)^2delta )}}{12gamma }), since (frac{(gamma +1)delta – sqrt{delta ^2 + 96gamma /((gamma +1)^2delta )}}{12gamma }) is negative. By minimizing this as a function of (delta), we obtain a minimum of (beta = root 3 of {big (frac{2}{3gamma }big )^2(gamma +1)}) given by (delta = root 3 of {frac{12 gamma }{(gamma +1)^2}}). Note that (6beta /delta = 2(1+frac{1}{gamma }) > 1). This yields a final NFS runtime of (L^{root 3 of {frac{32(gamma +1)}{9gamma ^2}}+o(1)}). (square)

The following two corollaries are restatements of the results for the low-resource algorithm4.

Corollary 5

4The classical NFS runs in (L^{root 3 of {64/9} + o(1)})time, where (root 3 of {64/9} approx 1.923).

Proof

Set (gamma =1) in Theorem 4. (square)

Corollary 6

4The low-resource quantum algorithm runs in (L^{root 3 of {8/3} + o(1)})time, where (root 3 of {8/3} approx 1.387).

Proof

Set (gamma =2) in Theorem 4. (square)

The final runtime of circuit-NFS depends on the runtime of the SAT solver used. Figure 5 shows the exponent (alpha) in the final runtime (L^{alpha +o(1)}) of circuit-NFS achieved if the SAT solver used achieves a (gamma)-speedup, that is, solves a circuit with v variables in (2^{v/gamma + o(1)}) time.

Figure 5
figure5

Exponent (alpha) of the final NFS runtime (L^{alpha +o(1)}) with the use of a SAT solver with (gamma)-speedup. The relation between (alpha) and (gamma) is given in Theorem 4.

The following results portray the two extreme scenarios highlighted in Fig. 5: a classical solver with (2^{v+o(1)}) runtime versus an ideal quantum SAT solver that achieves a (2^{v/2+o(1)}) runtime. The naive circuit SAT algorithm applied to the ECM circuit achieves runtime (O(2^{2log _2 u} L_N[1/6, cdot ]) = L^{root 3 of {64/9} + o(1)}), corresponding to (gamma = 1). Note that we do not expect (gamma >2) since (gamma =2) has been proved optimal for a quantum computer13 in a black-box context.

Theorem 7

With a classical circuit SAT solver, one can factor an integer N in (L^{root 3 of {64/9} + o(1)})time, where (root 3 of {64/9} approx 1.923).

Theorem 8

If a quantum SAT solver is assumed to achieve a full 2-speedup, it can be used to factor an integer N in (L^{root 3 of {8/3} + o(1)})time, where (root 3 of {8/3} approx 1.387).

Theorem 7 is not an improvement on the classical NFS, but it shows that the circuit-NFS approach is asymptotically at least as good. Under the assumption that quantum annealears can achieve the aforementioned 2-speedup in solving SAT circuits, one can obtain the same asymptotic runtime as the low-resource quantum algorithm. However, this does not require a fault-tolerant quantum computer capable of running Grover’s algorithm.

We emphasize that the speedup is computed over the naive circuit SAT algorithm. A standard translation of the circuit to CNF-SAT results in a SAT instance of size (L_N[1/6,cdot {}]) and a superpolynomial speedup over exponential-time CNF-SAT solvers would be required for speeding up factoring. Given the highly structured nature of the resulting SAT instance this might be feasible. Alternative solutions to avoid the superpolynomial overhead, such as direct translations from the ECM method to quantum annealer instances, are left as an open question for future work.

It is harder to make a statement about the qubit requirement of circuit-NFS. Instead of SAT, one can reduce to other NP-hard problems like QUBO for more direct application of DWave’s quantum annealer. If the smoothness detection circuit could be simplified and written as an instance of QUBO in terms of the variables ab only, that would total (2 log u in (log N)^{1/3+o(1)}) qubits. However, simplification is not trivial and does not seem to come without overhead, given our preliminary tests. It is more likely that intermediate wires of the circuit would also have to be QUBO variables, increasing the qubit requirement up to the full circuit size (L_N[1/6, sqrt{2beta /3} + o(1)]). Therefore it remains an open question how many annealing qubits circuit-NFS requires. On the other hand, annealing qubits are currently produced in much higher quantity than other types of qubits, suggesting the possibility that circuit-NFS could be implemented sooner than the low-resource quantum NFS.



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *