Runtime-coherence trade-offs for hybrid SAT-solvers
Vahideh Eshaghian Sören Wilkening Johan Åberg David Gross






vahideh@thp.uni-koeln.de

	(1) Institute for Theoretical Physics, University of Cologne, Germany; 
	(2) Institut für Theoretische Physik, Leibniz Universität Hannover, Germany;
	(3) Volkswagen AG, Berliner Ring 2, 38440 Wolfsburg;








	Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts. 
	This raises the question of how to divide computational tasks into  a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. 
	Here, we approach this question via hybrid algorithms for the k-SAT problem. 
	Our analysis is based on Schöning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. 
	The search space of the walk allows for “natural” partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. 
	In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. 
	For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. 
	Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.  




Runtime–coherence trade-offs for hybrid SAT-solvers
    
	Vahideh Eshaghian^(1), 
Sören Wilkening^(2), (3), Johan Åberg^(1), David Gross^(1)

    April 29, 2024
=========================================================================================





§ INTRODUCTION


Consider a quantum algorithm that takes exponential time to run, but still offers a polynomial speedup over the best classical method.
Examples include Grover searches to brute-force a password or for finding the solution  for a combinatorial optimization problem for which no classical heuristics exist.
Fully quantum implementations might not be desirable for two reasons:
(1) Quantum hardware that can sustain very long computations might not be available,
and
(2) quantum algorithms, like Grover's search, might not be easily amenable to parallelization.
One is thus lead to the question of how to best break up such instances into a set of smaller, parallelizable subproblems that can individually be solved on quantum hardware.

We consider the well-known satisfiability problem with k the number of literals in each clause, (k-SAT) and focus particularly on 3-SAT since it provides an attractive test bed to investigate such questions. k-SAT is the archetypical combinatorial optimization problem and represents a class of use cases with considerable practical relevance. 
Moreover, there is a classical randomized algorithm <cit.>
due to Schöning, with a performance close to the best-known algorithms with provable performance, and which furthermore allows for a closed-form asymptotic run-time analysis. And indeed, the algorithm obtained by replacing the classical search of the Schöning-procedure by a Grover search <cit.> yields a quantum-Schöning algorithm with a quadratic improvement vis-à-vis its classical counterpart <cit.>. 
(Below, we will refer to quantum algorithms that arise this way as Groverizations of their classical versions).

However, such `fully quantized' Schöning's SAT-solvers cannot be performed in parallel, which arguably is a relevant feature for algorithms that run in exponential time. Hybrid schemes, based on `partial' Groverizations of Schöning's algorithm, where Grover search procedures are applied only to certain sub-routines, usually do allow for parallelizations.

Starting point of our analysis is the stochastic nature of Schöning's algorithm as a random walk. 
This point of view yields two classes of hybrid algorithms, where one class Groverizes the random choice of the initial state of the walk, while the other class Groverizes the randomness in the walk itself. 
Within an established model of Schöning's algorithm, we optimize the resulting run-times by balancing the resources allocated to the subroutines.



 §.§ Runtime–Coherence Time Trade-Offs



Before specializing the Schöning process, let us briefly outline the trade-offs between runtime and coherence time that can be expected for quantum search problems. 
Consider an algorithm that solves instances of size n with runtime T(n).
For exponential-time algorithms, we work with a somewhat coarser measure, the (asymptotic) runtime rate 

    γ=lim_n→∞1/nlog T(n),

where we drop the base of the logarithm from here on; the base is 2 unless explicitly stated otherwise.
In other words, T∈ O^*(2^γ n), where 
O^* denotes scaling behavior up to polynomial factors.
The aim is to trade it off against the coherence time required to run the algorithm.
If C(n) is the longest time over which coherence has to be maintained while running the algorithm, then the coherence time rate is

    χ=lim_n→∞1/nlog C(n).


Now restrict attention to search algorithms with classical runtime rate γ_C.
A completely Groverized version runs with rate 
γ_G=γ_C/2.
All of its runtime will be spent coherently, specifically executing Grover iterations.
Therefore, 
χ_G=γ_C/2
as well.
We can visualize these two points in a “runtime rate vs coherence time rate”-chart, a mode of visualization that we will employ frequently (Fig. <ref>).

To achieve a trade-off between total runtime and coherence time, we will consider algorithms that apply Grover's procedure only to a subset of the search space.
It is easy to see that any algorithm which results from such a procedure must have coordinates (χ,γ) that lie on or above the line segment

    L={ (χ, γ_C - χ)  | χ∈[0,γ_C/2] }

that connects the purely classical point (0,γ_C) to the completely Groverized one 
( γ_C/2, γ_C/2).

Indeed, take a partial Groverization that achieves parameters (χ,γ).
Then one can replace the Grover part by a classical search.
The resulting classical algorithm will have parameters (0,γ+χ), because the Grover search contributed χ to the runtime rate, but its classical simulation will contribute 2χ instead.
 But if the initial parameters were below the line, i.e. if γ < γ_C - χ, then the resulting classical algorithm runtime rate is
γ + χ < γ_C, 
contradicting the assumption that γ_C describes the classical complexity of the search.



It is not obvious that, conversely, every point on this optimal line segment can actually be realized, much less with an algorithm that is “natural” or easy to implement.
Deciding the parameter ranges for natural partial Groverizations of Schöning's procedure is the main goal of this paper.





  §.§.§ Related work


Dunjko et al. <cit.> have previously considered partial Groverizations of Schöning's algorithm.
They aimed to minimize a different metric:
total number of clean qubits, rather than coherence time.
In fact, they work in a highly constrained regime, where the number of available clean qubits only scales as cn, with 0< c <1 and n the number of variables of the given 3-SAT formula. 
Surprisingly, they show that even this meager allotment of qubits in principle yields a speed-up compared to the classical Schöning's algorithm [According to <cit.>, Supplemental Material Section B.4, the relative speed-up to the classical Schöning's rate is f(c)= (1-log√(3))β(c), where the Beta function up to O(log n /n) is implicitly given as Aβ(c)ln1/β(c)+Bβ(c) = c. As mentioned in <cit.> using a straightforward encoding of each trit into two qubits, one can assume A= 10 and B=50. To be consistent with our encoding, we consider log_23 qubits to encode a trit and then, calculate the maximum speed-up in the rate, i.e. f(1)≈ 0.0028.].

Despite the superficial similarities, their and our papers are quite different.
We allow for qubit-counts that are quasi-linear in n, i.e. O (nlog n), reasoning that for exponential-time algorithms, coherence time and parallelizability might be more limiting than the number of available qubits.
As it will turn out, the setting considered here can interpolate between the classical and the fully Groverized performance, while the runtime rates obtainable in <cit.> stay close to the classical ones.
While <cit.> uses de-randomization techniques, our approach builds more directly on the original Schöning's algorithm. This makes our approach technically less involved, and it also makes the lessons learned more widely applicable, since the basic technique of using Grover search over a subset of all variables, directly generalizes to any NP problem, whereas de-randomizations to a larger extent rely on the particular structure of the problem at hand.



§ SETTING THE STAGE



 §.§ Schöning's algorithm


Here we provide a very brief introduction to the pertinent aspects of Schöning's 3-SAT solver. 
For a more thorough review, we refer the reader to <cit.>. 
In the 3-SAT problem, we are given a collection of clauses C_1,…, C_L on n binary variables, where each clause is of the form C_j = l_0^(j)∨ l_1^(j)∨ l_2^(j), and where each of the literals l_0^(j),  l_1^(j), l_2^(j) is one of the binary variables or its negation. 
The 3-SAT formula is the conjunction of all the given clauses, C:= ∧_j=1^LC_j, and the computational task is to determine whether there exists an assignment of the n binary variables that satisfies C. 
According to Schöning <cit.>, an algorithm exists that, although with run-time that is exponential in n, can perform better than an exhaustive search through all potential assignments.  

Schöning's algorithm (Alg. <ref>) depends on two parameters N, m to be determined later.
It begins by choosing an assignment x∈{0,1}^× n uniformly at random.
The algorithm then performs an m-step random walk over the space of n-bit strings (the inner loop in Alg. <ref>, from Line <ref>).
In every step, it checks (according to a pre-determined order) all the clauses C_1,…, C_L. 
If all are satisfied, then x is a solution and the algorithm terminates. 
Otherwise, it finds the first unsatisfied clause,
chooses one of the three variables corresponding to the literals of that clause uniformly at random.
The value of x is then updated, by negating that variable. 
This concludes the step.
If no solution is found after m steps, the walk is terminated.
Up to N such walks are attempted (the outer loop in Alg. <ref>), each time using a fresh uniformly random starting point x.







 §.§  Analysis of the run-time of Schöning's algorithm


The analysis of the run-time of Schöning's algorithm is sketched in <cit.> and a more in-depth analysis can be found in <cit.>. 
Here we follow a very similar line of reasoning, with our particular ansatz in mind. 
In the following, we present an overview, see Appendix <ref> for a more detailed account.

Assume that there is at least one satisfying assignment x^⋆.
We first aim to lower-bound the probability that a given random walk finds a solution.
Let x_0 be the (random) initial configuration, and x_l the one attained after the l-th step of the random walk.
The probability that any solution is found during any step of the walk is certainly at least as large as the probability P(x_m = x^⋆) that the walk finds x^⋆ at the m-th step.
To analyze P(x_m=x^⋆), we follow in the steps of Schöning <cit.>, and focus on the evolution of the Hamming-distance d_H(x_l, x^⋆) between the current configuration and the selected satisfying assignment x^⋆. 

The fundamental insight is that if a clause C_k is violated at the l-th step, then at least one of the three variables that appear in C_k must differ between x_l and the satisfying assignment x^⋆.
Thus, the random flip decreases the Hamming distance to the solution with probability at least 1/3:

    P( d_H(x_l+1, x^⋆) = d_H(x_l, x^⋆) - 1 )≥1/3.

This suggests to pass from a description of the process on bit strings to its projection
x_l ↦ d_H(x_l,x^⋆) 
onto ℕ.
However, this would generally yield a process that would be no easier to analyze than the original one. 
One may for example note that although Schöning-process  (x_l)_l is Markovian on the space of bit-strings {0,1}^× n, one cannot generally expect its projection (d_H(x_l,x^⋆))_l to be Markovian on ℕ. 

The general idea for the analysis is to replace (via a coupling) the true projection (d_H(x_l,x^⋆))_l with another process (d_l)_l on ℤ, which is Markovian and which moreover upper-bounds the true Hamming-distance,

    d_H(x_l,x^⋆)≤ d_l.

More precisely, the Markov process (d_l)_l is defined by the transition probabilities 

    P(d_l+1 = d_l +1) = 2/3,   P(d_l+1 = d_l -1) = 1/3.


The transition probabilities (<ref>) can be interpreted as worst-case scenarios of each step in the Schöning process.

From the bound (<ref>) it follows that P(x_l = x^⋆) ≥  P(d_l ≤ 0). 
In other words, the success probability of the Schöning-process is lower-bounded by the probability that the substitute-process d_l reaches 0. 


Given the lower bound P(d_m ≤ 0) on the probability of success of each given walk, we expect at least one out of N=1/P(d_m ≤ 0) walks to find x^⋆.
More precisely, if ϵ is the tolerated probability for failure, then the number of repetitions needed in order to find an existing solution satisfies

    N≥logϵ/log(1-P(d_m≤ 0)).




The required number N of repetitions will be exponential in n.
It is then common to take a coarser point of view, and only analyze the corresponding rate 


    γ := -lim_n→∞1/nlog 
    	P(d_m≤ 0),
    	    so that    
    	N=O^*(2^γ n),

where O^* denotes scaling behavior up to polynomial factors in order to achieve any constant probability of failure ϵ.
With the choice m = n (i.e., the termination time is equal to the number of variables) it turns out <cit.> 
that 
γ≤log4/3≈ 0.415. 


It is surprisingly technically difficult to rigorously derive the “global bound” P(x_l=x^⋆)≥ P(d_l ≤ 0) 
from the  “local bound” (<ref>).
However, the Markovian version (d_l)_l of the Hamming distance random walk is commonly accepted as a good (in fact, conservative) model of the Schöning-process.
In the main body of this paper, we will therefore phrase our arguments in terms of that model.
More technical details on the relation between the two processes are given in Appendix <ref>.




 §.§ Partial Groverizations: The general idea


For random walks we naturally tend to think of the randomness as being generated whenever needed, like when we assign the initial state, or make the random choices along the path.
However, we can alternatively picture the walk as a deterministic process that is fed with an external random string S; a list from which it picks the next entry whenever a random choice is to be made. 
When the purpose of the walk is to find (an efficiently recognizable) solution to some computational problem, one can thus view the walk as a (deterministic) map that designates each input string S as being “successful” or “unsuccessful”, in the sense of the walk reaching the satisfying solution x^⋆ or not. 
To this mapping, we can in principle apply a Grover-search procedure, since the walk (as well as the solution-recognition procedure) can be performed via reversible circuitry, and can thus also be implemented coherently. 

As described in the previous section, Schöning's algorithm proceeds with an initialization, followed by a random walk on the space of 2^n assignments. 
The initialization requires n bits of randomness, S_I, since the initial state is selected uniformly over all 2^n strings. 
A walk of length m requires a string S_W of mlog3 bits to encode the needed randomness. 
The log3-factor is due to the fact that, at each step, the algorithm randomly selects which one of the three literals (of the first violated clause) should be flipped. 
An m-step Schöning-walk can thus be viewed as a map from S = (S_I,S_W) to a binary variable that tells us whether a satisfying assignment has been reached or not.

With a coherent circuit that implements this map, we can thus replace the uniformly distributed random variable S, with a uniform superposition over a corresponding number of qubits, and proceed via standard Grover-iterations <cit.>. 
We would expect such a procedure to yield a satisfying assignment at a run-time that scales as O^*(2^nγ_G) iterations, with γ_G = 1/2log4/3≈ 0.208 <cit.>, i.e., the standard quadratic speed-up. 
Up to a few constant qubits, one needs n + (log3 + log L)m qubits to encode this map as a quantum circuit, where L is the number of clauses in the 3-SAT formula (more details are given in Section <ref>). Since the number of clauses grows linearly in n for the regime of interest by the SAT phase-transition conjecture <cit.>, and for the Schöning walk m = n, the space complexity of such encoding is O(nlog n).

The view of random walks as maps on random input strings opens up for the concept of partial Groverizations. 
Nothing would in principle prevent us from regarding only a part of the input string S as the input of the Grover-procedure, while keeping the rest of the string classical. 
Needless to say, one would generally expect the result to be less efficient than the “full” Groverization. 
However, the gain would be that the partial Groverization breaks the tasks into a collection of subproblems, each of which can be run in parallel on a quantum device that requires shorter coherence time. 

Although it seems reasonable to expect that such a division in principle is always possible, one may also expect that it in general would be challenging to find a quantum circuit that implements it in an economical manner. 
(We can always resort to a full coherent circuit for S in its entirety, putting the “classical part” in a diagonal state.) 
However, there may be “natural” divisions of the process, which can be exploited. 
For  Schöning's algorithm it is close to hand to consider the division S = (S_I, S_W), i.e., the division of the required randomness into the initialization-part and the walk-part. 
One can thus consider two particularly natural classes of “partial” Groverizations of Schöning's algorithm. 
For one of these, the Groverized Initialization (GI), the choice of the initial state is implemented coherently, while the walk is kept “classical”. 
For the Groverized Walk (GW), the choice of initial state is kept classical, while the walk itself is performed coherently. 


As described in Section <ref>, the actual analysis is based on the random walk (d_l)_l on ℤ, rather than the true Schöning walk on strings in {0,1}^× n. 
The idea is nevertheless the same; the required randomness is divided into the initialization and the walk per se, resulting in GI- and GW-processes. 
As described in Section <ref>, the rate of the true Schöning-process can be bounded by the rate of the substitute process (d_l)_l. It turns out that a similar argument can be made for GW (see Appendix <ref>), thus yielding a rigorous bound for the rate also in this case.  However, for the other processes we rather regard the (d_l)_l process as a model of the genuine Schöning-walk, without rigorous guarantees of analogous bounds.




§ PARTIAL GROVERIZATIONS

The previous section introduced two types of partial Groverizations of Schöning's algorithm, GI and GW, based on the division S = (S_I, S_W), i.e. the initial and the walk randomness. In this section, we describe these schemes in detail and further discuss their “fractional” cases.

In the GI scheme, there is an outer loop that classically samples S_W, and is followed by a Grover-search inner loop over the space of all possible S_I. Similarly, GW starts with a classical outer loop that samples S_I and is followed by a Grover-search inner loop over the space of all possible S_W (this space is well-defined as the walk length is fixed).
We obtain Fractional Groverized Initialization (FGI) by adapting GI to a regime where only a fraction z of the variables in the initialization can be searched coherently, with 0≤ z ≤1. 
Fractional Groverized Walk (FGW) is similarly an adaption of GW to a regime where Grover-search can be performed on the randomness of walks of at most m_q steps, with 0 ≤ m_q. 
In both these fractional schemes, two classical outer loops contain a Grover-search inner loop.  
The algorithms introduced here depend on parameters (N_1, N_2, etc), that will be specified explicitly in Section <ref>. 

All Grover searches will use an oracle derived from the function shown in Alg. <ref>:
It tests whether a Schöning-walk with initial configuration x∈{0,1}^n and walk randomness w∈{1,2,3}^m will lead to a satisfying assignment.
For notational convenience, we let the elements of w take ternary in values, with the interpretation that w_l determines which of the three literals occurring in the first violated clause (if any) in step l of the walk is flipped.
For a qubit-based implementation, it is not difficult to re-label the decision variables using ⌈ m log 3⌉ binary variables.




For the different variants of partial Groverizations discussed below, we will fix a subset of arguments to the oracle, and consider it as a function of the remaining ones.
Fixed arguments will be denoted as subscripts, e.g. Oracle_w: x↦Oracle(x,w).
With these conventions, we have:


 



One may note that the Grover search in the Groverized walk only is guaranteed to succeed (with high probability) for a specific collection of initial states. The number of rounds N_1 of the outer loop is selected in such a way that it with high probability hits the set of advantageous initial states at least once, thus allowing the Grover-procedure to reach the satisfying assignment. Similar remarks apply to the other partial Groverizations.


Next, we discuss the “fractional searches”. 
In the first one, the argument x of the oracle is broken up as x=(x_c, x_q) with x_q taking ⌊ z· n ⌋ bits and x_c being ⌈ (1-z)· n ⌉ bits long.
Here, z∈[0,1] is a free parameter whose value will be determined below.



The second fractional algorithm breaks up the walk randomness as w=(w_c, w_q) with w_c∈{1,2,3}^m_c and w_q∈{1,2,3}^m_q respectively.
Again, the values of m_c, m_q are chosen later.



In the final algorithm, a fraction of z∈[0,1] of both types of variables, the ones corresponding to the initialization and the ones corresponding to the walk, will be treated  quantum mechanically.







§ RUN-TIME ANALYSIS



We will now lower-bound the probability of success of the various approaches.
As a preparation, in Sec. <ref>, we give a brief account of the analysis of the classical case, before moving on to the Groverized versions in Sec. <ref>.



 §.§ The classical Schöning process




The main ideas of the classical analysis are close to their presentation in Refs. <cit.>.
We work in the Markovian model (d_l)_l for the behavior of the Hamming distances, as laid out in Sec. <ref>.
Frequently, it will be convenient to measure quantities “in units of n or m”. For example, we will soon choose a number κ∈[0,1] and assume that the initial value d_0 is equal to κ n. 
Of course, this only makes sense if κ n is an integer.
In order to keep the notation clean, we will implicitly assume that such expressions have been rounded to the next integer.


Choose numbers κ, ν∈[0,1].
A given walk (d_l)_l is certainly successful (in the sense that d_m≤ 0) if 

	
  * The initial value is d_0=κ n,
	
  * the random walk decreases the Hamming distance in exactly ν m of its m steps, and
	
  * the condition
		
    κ n ≤ (2ν -1)m

		holds.

Indeed, the right hand side of (<ref>) is the difference between the number of steps where the Hamming distance has been decreased, ν m, and the number of steps where the Hamming distance has been increased, (1-ν )m. 

For any fixed pair of values κ,ν subject to (<ref>), we will now compute the probability of this particular route to success.
Denote the first event by E_1 and the second event by E_2.
They occur with respective probabilities

    P(E_1)    = 1/2^nnκ n,
    					    
        P(E_2)    = mν m(1/3)^ν m(2/3)^(1-ν)m.

Since the two events are independent, 
the success probability of the walk 
is lower-bounded by 


    P(x_m=x^⋆|κ)≥
        P(d_m≤ 0|x)    ≥ P(E_1 E_2) 
        = P(E_1)P(E_2) 
        = 1/2^nnκ nmν m(1/3)^ν m(2/3)^(1-ν)m.

The various binomial coefficients can be conveniently related to entropies.
To this end, recall the definition
of the binary entropy function 

    H(p) = -plog p - (1-p) log(1-p)    for   p ∈ [0,1],

and the relative entropy

    D(p∥ q) = - plog q - (1-p)log(1-q) - H(p)    for   p,q ∈ [0,1].

Then using the well-known estimate <cit.>


    1/n+12^nH(κ)≤nκ n≤ 2^nH(κ),

Equation (<ref>) can, after some straight-forward calculations, be concisely rewritten as

    P(d_m≤ 0|x) ≳ 2^-(1-H(κ))n2^-D(ν∥1/3)m,

where ≳ denotes an inequality holds asymptotically, up to a polynomial factor. 
Equation (<ref>) directly gives an upper bound on the rate γ defined in (<ref>). 
Since the rate expresses the logarithm of the complexity “in units of n”, it makes sense to also express the length of the walk in terms of μ := m/n.
Then:


    γ
    		= - lim_n →∞1/nlog P(d_m≤ 0|x)
    		≤
    		1- H(κ) + μ D(ν∥ 1/3)
    		=:
        γ(μ,κ,ν).

In particular, the infimum of γ(μ,κ,ν) subject to the constraints (<ref>) and 0 ≤μ, 0≤ν,κ≤ 1 is a valid bound for γ.
We will perform such optimizations explicitly for the partially Groverized versions in Sec. <ref>.
For the classical procedure, we just state the final result:

    μ = 1,     κ=1/3,     ν=2/3,     γ_C = log4/3≃ 0.4150.


Remark:
One might be tempted to search a tighter bound by summing the contributions to the probability of success that arise from all consistent values for μ,κ,ν, instead of just considering the extremal value.
However, the rate of a sum of exponentially processes is asymptotically determined by the rate of the dominating summand alone, i.e. for all collections of γ_i>0, it holds that

    lim_n→∞-1/nlog∑_i 2^-γ_i n = sup_iγ_i

(assuming convergence).
Therefore, considering only the dominating term does not affect the overall asymptotic rate.





 §.§ Partially Groverized processes



In this section, we derive the main results of this paper:
Bounds on the asymptotic rates for partially Groverized versions of Schöning's scheme.




  §.§.§ Groverized Initialization, Algorithm <ref>



For the parameters N_1, N_2, we choose constant multiples of 1/P(E_1), 1/P(E_2) respectively.
The value of the constant depends on the acceptable probability ϵ of failure, as exhibited in Eq. (<ref>).
Since this constant does not effect the rate, we will not specify it here.
The probabilities do depend essentially on the parameters μ,κ,ν, though. 
We will therefore write N_1(κ) and N_2(μ,ν).
Because the asymptotic complexity of a Grover search is the square root of the classical complexity,
the rate function of GI 
is then given by

    γ_GI(μ,κ,ν) 
    	   =  
    	lim_n →∞1/nlog(√(N_1(κ))N_2(ν,μ)) 
    	= 
    	1 - H(κ)/2 
    	+  
    	μ D(ν∥ 1/3).

Likewise, the required coherence time scales with the number of Grover iterations, i.e. as O^*(2^χ n), for

    χ(κ) 
    		:=  lim_n →∞1/nlog√(N_1(κ))
    		= 1 - H(κ)/2.

The parameters are constrained by

    0 ≤κ≤ 1,
    			  
    			0 ≤μ,
    			  
    			0 ≤ν≤ 1,
    			  κ/2ν -1≤μ,

where the final condition is a re-arranged version of the success criterion (<ref>).

We now determine the minimal rate γ_GI over the consistent parameters.
Because relative entropy is non-negative, it is always advantageous to reduce the value of μ until it is minimal subject to the constraints.
This is achieved by changing the final inequality in (<ref>) to equality.
Re-arranging, we arrive at

    0 ≤κ≤ 1,
    			  
    			0 ≤μ,
    			  ν = 1/2+κ/2μ,

which allows us to eliminate ν=ν(κ,μ) from the problem.
Varying γ with respect to μ gives rise to the criticality condition

    0
    	!=∂_μγ_GI(κ,μ)
    	= 
    	∂_μ μ D(1/2+κ/(2μ) ∥ 1/3)
    	=
    	1/2log(μ+κ/μ) +1/2log(μ-κ/μ)+log3-3/2.

This can be solved explicitly e.g. using a computer algebra system <cit.>, leading to

    μ = 3κ    ⇒    ν=2/3,
    	  μ D(ν∥ 1/3) = κ.


Eliminating μ, we get

    γ_GI(κ)
    		   =
    		1-H(κ)/2 + κ, 
    χ_GI(κ)
    		   =
    		1-H(κ)/2.


The pair of equations (<ref>) contain all information about the asymptotic behavior of the Groverized Initialization procedure.
Each value of κ gives a solution for the two undetermined constants N_1(κ), N_2(μ=3κ, ν=2/3) in Alg. <ref>, in such a way that it will run with a small probability of returning a false negative.
Varying κ, we thus obtain a family of algorithms that find different compromises between the required coherence time and the total runtime. 
The achievable pairs of values are shown in Fig. <ref>.



Finally, we explicitly determine the minimal rate achievable in the Groverized Initialization scheme.
With the help of a computer algebra system <cit.>, one easily finds

    0 !=∂_κγ_GI(κ)=1/2logκ/1-κ+1
    		  ⇔  log(1/κ-1) = 2 
    		  ⇒  κ = 1/5

which gives

    μ = 3/5, 
    	    γ_GI = 3-log5/2≈ 0.339,
    	    χ_GI≃ 0.139.


Remark:
One can cast the final minimization into the form

    γ_GI = 
    	inf_κγ_GI(κ)
    	=
    	inf_κ(
    		1-H(κ)/2 + κ)
    	=
    	-
    	sup_κ(
    		-κ
    		-	
    		H(κ)-1/2).

This expression shows that the optimization amounts to computing a Legendre transform.
Indeed, with f(κ):=1/2(H(κ)-1), the right hand side equals -f^*(-1).
For physicist readers, it might be amusing to note that S(n κ)=n H(n κ) formally equals the entropy of an n-spin paramagnet as a function of the total magnetization.
The Legendre transform of the entropy is a Massieu thermodynamic potential, equal to F/T (with F the free energy) expressed as a function of the inverse temperature <cit.>.
We will, however, not pursue this analogy here.



  §.§.§ Groverized Walk, Algorithm <ref>


The analysis proceeds in close analogy to the above case.
The asymptotic rate function of GW is 

    γ_GW(κ,μ,ν) 
    		   = 
    		lim_n →∞1/nlog (N_1(κ)√(N_2(ν,μ)))  
        = 
    		1 - H(κ) + μ/2 D(ν∥ 1/3) ,

subject to the set of constraints (<ref>). 
The parameters ν, μ can be treated in exactly the same way as before, leading again to (<ref>).
In particular, the coherence time rate takes the simple form χ=κ/2, which allows us to eliminate κ in favor of χ.
We immediately obtain

    γ_GW(χ) 
    		= 1-H(2χ) + χ.


Again, it is not difficult to solve for the lowest runtime <cit.>: 

    μ
    	=
      3(√(2)-1), 
    	    κ = √(2)-1,
    	    γ_GW≈ 0.228,
    	    χ_GW≃  0.2071.

At the optimal point, the runtime scales with a rate that is very close to the one of a full Groverization of Schöning's process, namely γ_FG=γ_C/2≃ .2075.
The flip side is that the required coherence times are basically identical:

    χ_FG 
    	-
    	χ_GW≃
    	0.0004.



The findings are summarized in Fig. <ref>.





  §.§.§ Fractional Groverized Initialization, Algorithm <ref>



In the case of Alg. <ref>, the initial Hamming distance is the sum of two terms d_0 =  κ_c (1-z)n + κ_q z n, which model d_H(x_c,x_c^⋆) and d_H(x_q,x_q^⋆) respectively.
Define the analogues 

    P(E_1^c) = 1/2^(1-z)n(1-z)nκ_c (1-z)n,
    	    
    	P(E_1^q) = 1/2^z nz nκ_q  zn

of P(E_1) introduced in Eq. (<ref>).
Analogous to the discussion in Sec. <ref>, the parameters N_1^c, N_1^q are defined as the reciprocals of these probabilities, times a constant that influences the probability of a false negative, but will not be discussed as it has no impact on the asymptotic rates.
The success criterion is now

    (1-z)κ_c + zκ_q    ≤ (2ν-1)μ

and the other constraints are

    0 ≤κ_c, κ_q, ν, z ≤ 1, 
    		    
    		0 ≤μ.

The asymptotic rate function for the runtime of FGI reads

    γ_FGI(κ_c,κ_q,ν,μ;z) 
    		   = lim_n→∞1/nlog(N_1^c(κ_c;z)√(N_1^q(κ_q;z))N_2(ν,μ)) 
       = (1-z)(1- H(κ_c)) + z/2(1- H(κ_q)) + μ D(ν∥ 1/3)



Arguing as in Sec. <ref>, the inequality in the success criterion may be replaced by an equality.
Solving for ν gives

    ν= 1/2 + (1-z)κ_c + zκ_q/2μ.

We proceed as in the first two cases. 
Criticality of ∂_μγ_FGI with respect to μ occurs at


    μ = 3((1-z)κ_c + z κ_q)
    	    ⇒    μ D(ν∥ 1/3) = (1-z)κ_c + z κ_q,   ν=2/3.

Plugging in, we arrive at

    γ_FGI(κ_c, κ_q;z) 
    		    = 
    		 (1-z)
    		 (
    			 1- H(κ_c)
    			 +
    			κ_c 
    		 ) 
    		 + 
    		 z(
    			 1- H(κ_q)/2
    			+  κ_q 
    		 ).

In other words, the runtime rate function is a convex combination of the ones for the classical Schöning process and for the GI scheme, with weights (1-z), z respectively.
Because the classical part does not affect the coherence time, we may set κ_c to its optimal value κ_c^*=1/3
(c.f. Eq. (<ref>)).
Geometrically, as we vary z∈[0,1], Eq. (<ref>) describes a line connection (χ_GI(κ_q), γ_GI(κ_q)) with the parameters of the classical Schöning process (0,γ_C).
By the convexity of the GI curve, the fractional algorithm will have a better runtime rate to the left of the value of κ_q at which the line becomes tangent to the curve.
In other words, the critical κ_q is defined by the condition

    ∂γ_GI/∂χ = γ_GI-γ_C/χ.

By a computer calculation <cit.>, this happens for κ_q=1/3 (i.e. equal to κ_c), resulting in the following curve:





  §.§.§ Fractional Groverized Walk, Algorithm <ref>


In the FGW scheme, we assume that the classical and Groverized walks decrease the Hamming distance in exactly ν_cm_c and ν_qm_q steps, respectively, where we have used a subscript to differentiate between the classical and Groverized random walks. 
The probabilities of such walks occurring is given by:

    P(E^c_2)    = m_cν_c m_c(1/3)^ν_c m_c(2/3)^(1-ν_c)m_c,
           
         P(E^q_2)    = m_qν_q m_q(1/3)^ν_q m_q(2/3)^(1-ν_q)m_q

Analogous to the discussion in Sec. <ref>, the parameters N_2^c, N_2^q are defined as the reciprocals of the probabilities P(E^c_2),P(E^q_2), times a constant that influences the probability failure, but will not be discussed as it has no impact on the asymptotic rates.
We further parameterize the walk lengths as m_c = μ_cn and m_q = μ_qn. 
The runtime rate is

    γ_FGW(κ,ν_c,μ_c,ν_q,μ_q)    = lim_n →∞1/nlog(N_1(κ)N_2^c(ν_c,μ_c)√(N_2^q(ν_q,μ_q))) 
       = 
    		1- H(κ) + μ_cD(ν_c∥ 1/3) + 
    		μ_q/2D(ν_q∥ 1/3)

with parameters subject to the constraints


    0    ≤κ≤ 1, 
    
            0    ≤μ_c,μ_q, 
    
            0    ≤ν_c,ν_q ≤ 1,
    κ   ≤ (2ν_c-1)μ_c + (2ν_q-1)μ_q.


The first steps of the analysis should now be familiar.
There is no loss of generality in assuming that the final inequality is tight, which can be re-arranged to give


    ν_q
    	=
    	κ - (2ν_c-1)μ_c/2μ_q + 1/2.

The rate γ_FGW is stationary as a function of μ_q if

    μ_q = 3 (κ - (2ν_c-1)μ_c )
    	    ⇒    ν_q = 2/3,
    	  μ_q/2D(ν_q∥ 1/3)
    	=
    	1/2 (κ - (2ν_c-1)μ_c ) 
    	=
    	χ(κ,ν_c,μ_c).


Eliminating κ in favor of the coherence rate χ gives

    κ = 2χ + (2ν_c-1)μ_c


and thus

    μ_q = 
    	6χ,
    	    γ_FGW(ν_c,μ_c;χ) 
    	   = 
    	1- H( 2 χ + (2ν_c-1)μ_c )
    	+ 
    	μ_c D(ν_c∥ 1/3)
    	+
    	χ.

We now need to minimize γ_FGW for fixed χ as a function of μ_c, ν_c, subject to

    0   ≤
    	2χ + (2ν_c-1)μ_c ≤ 1, 
    
    	0    ≤μ_c, 
    
    	0    ≤ν_c ≤ 1.


We may assume that μ_c≠ 0, for else we are just replicating the GW scheme.
A computer calculation <cit.> gives

    ∂_μ_c 
    	(γln 2)
    	+ 
    	2-4ν_c/4μ_c∂_ν_c 
    	(γln 2)
    	=
    	-arctan(1-2ν_c) + ln(3-3ν_c) - 1/2ln2,

which has zeros at ν_c=1/3 and ν_c=2/3.

For ν_c=1/3, one finds

    ∂_μ_c
    	(γln 2)
    	=
    	2/3arctan(1-4χ+2/3 μ_c)

which has one zero, at μ_c = 3/2(4χ-1).
The constraint μ_c≥ 0 then implies χ≥1/4.
But this is larger than the coherence time rate γ_C/2≃ 0.208 sufficient to implement a completely Groverized version of Schöning's process, so this solution is not of interest.

We turn to the other solution, ν_c=2/3.
For it,

    ∂_μ_c
    	(γln 2)
    	=
    	1/3 (-2 arctanh(1 - 4 χ - (2 μ_c)/3) + ln(2)),

which has one zero:

    μ_c=1-6χ    ⇒    μ_q=6χ,
    	  ν_c=ν_q=2/3,
    	  γ_FGW = γ_C - χ.


The runtime vs coherence rate curve for the FGW scheme is given in the following figure:





  §.§.§ Evenly Fractionalized Grover


The runtime rate is

    γ_EFG   = 
    		(1-z)(
    			1- H(κ_c)
    			+
    			μ_c D(ν_c ∥ 1/3)
    		) 
    		+
    		z/2(
    			1- H(κ_q)
    			+
    			μ_q D(ν_q ∥ 1/3)
    		)

with success criterion

    (1-z)κ_c + zκ_q 
    	=
    	(1-z)(2ν_c-1)μ_c + 
    	z(2ν_q-1)μ_q,

which is in particular true if the following two equations hold

    κ_c 
    	=
    	(2ν_c-1)μ_c,
    	    κ_q
    	=
    	(2ν_q-1)μ_q.

But this is just the convex interpolation between a completely classical and a completely Groverized process.
In particular, by choosing the parameters as for the original Schöning process

    ν_c=ν_q=2/3,
    	  κ_c=κ_q=1/3,
    	  μ_c=μ_q=1,

we obtain a coherence time–runtime rate curve that linearly connects the classical point (0,γ_C) to the completely Groverized one (γ_C/2, γ_C/2) (Fig. <ref>).







 §.§ A heuristic de-randomization of the GI schemes


In this section, we provide evidence that the Groverized initialization schemes can reach further into the  γ–χ chart than what the Markovian model suggests.
To see why this is plausible,
note that the role of randomness for the initial configuration x is very different from the role of randomness for the walk decisions w.
In the first case, there is an “absolute measures of the quality of the initial configuration”, namely the Hamming distance to the solution.
The probability that the walk does find the solution is quite obviously a function of that metric.
Therefore, baring major algorithmic insights, it is unavoidable to consider many different initial configurations before encountering  one that will likely lead to a solution.


In contrast, it is not implausible that “every walk works for equally many initial configurations”, i.e. that there are no choices for w that are “intrinsically better than others”.
More precisely, it seems reasonable to assume that for 
sufficiently large n, and
generic SAT formulas, it holds that with high probability in w

    -1/nlog(
    	_x[ SchoeningWalk(x, w) = x^⋆ |  d_H(x,x^⋆)=h,w] ) 
       ≃
    	-1/nlog(
    		_x,w'[ SchoeningWalk(x, w') = x^⋆ |  d_H(x,x^⋆)=h]
    	).

The right hand side can be easily calculated, as by Ref. <cit.>, for μ=3, 

    _x,w[ SchoeningWalk(x, w) = x^⋆ |  d_H(x,x^⋆)=h]
    	=
    	2^-h.


Under Assumption (<ref>), one can restrict the outer loop over w's from Alg. <ref> to N_2=1 iteration, and compensate by increasing the number of Grover iterations for x to N_1=O^*(2^γ_C/2n).
In other words, the Groverized Initialization scheme with these parameters would lie on the optimal point 
(χ,γ) = (γ_C/2, γ_C/2).

Being even bolder, one could then speculate that the analysis of Sec. <ref> carries 
over and that, as one varies the fraction of initialization bits that are subjected to a Grover search, one could trace out the optimal (χ,γ)-line.
In other words, it does not seem impossible that the following Alg. <ref>, with parameter choice

    N_1^(c) = O^*(2^γ_C(1-z)n),
    	    
    	N_1^(q) = O^*(2^γ_Czn/2),

achieves the optimal trade-off.




To gather evidence in favor of Assumption (<ref>), we have resorted to numerical methods.
A first ansatz is to compute the l.h.s. of Eq. (<ref>) exactly, which is possible for small values of n by iterating over all 2^n assignments to x.
Results are shown in Fig. <ref> for a randomly chosen set of 3-SAT formulas with n=20 variables, L=91 clauses. 
The number of satisfying assignments t_0 of the formulas are varied.
Only the case t_0=1 can be directly compared to the analytic bounds.
However, note that even for this case, the empirically observed rate of γ_GI≃ .12 ± .02 is much lower than the value γ_C/2 ≃ .208 that we would expect theoretically.
Presumably, n=20 is still too small to show the asymptotic behavior.



To test this assumption, we had to turn to numerical heuristics, to at least probe the behavior for much larger values of n, where an exact computation is no longer possible.
The results are shown in Fig. <ref>.
We used a SAT instance with n=1414 variables that we believe to have a single satisfying assignment x^⋆ which is explicitly known.
To generate the instance, a 128-bit plain text was encoded by a 128-bit key using the XTEA block cipher truncated to three rounds.
The formula represents the conditions on an input key to map the known plain text to the known ciphertext. 
The clauses are designed such that they enforce the correct evaluation of bit-wise operations of the algorithm with respect to the given input and output. 
XTEA was restricted to three rounds in order to keep the size of the formula manageable. 
While we have no formal proof, it is reasonable to assume that there is a unique key that satisfies the formula.
This is supported by consistency checks in terms of running SAT solvers on a version of this problems with even fewer rounds <cit.>.

Let us denote the sphere of strings with Hamming distance h from x^⋆ by M^h(x^⋆). For a fixed walk randomness w, and for h=1, … 11, we have drawn x uniformly from M^h(x^⋆).
In order to compare the numerical results to the theory prediction, we have to use the value of the right hand side of Assumption (<ref>) for non-asymptotic values of n.
The following plot shows the empirically estimated probabilities of Schöning's walk (with μ=3) arriving at the solution, when starting from a random initial configuration of given Hamming distance.
The findings show the expected behavior of averaging over w, already for a fixed random value of w.
In this sense, they are compatible with Assumption (<ref>).
We note, however, that we were not able to probe the assumption for larger values of h.
Garnering a better understanding for the concentration properties of the Schöning walk as a function of the walk choices remains therefore an open question.







§ CIRCUITS


In this section, we discuss an implementation of the partial Groverization schemes and present the main building blocks of their quantum circuits. Given n variables and the length of Schöning's walk m, the quantum implementation requires n + m log3 qubits to encode the initializations and walk randomness. 
The oracles of the partial Groverization schemes are some adaptation of one or more Schöning walks, and regardless of the search space they act on, the label of the violated clause at each step needs to be stored in their workspaces. This is necessary since such oracles are typically realized using uncomputation, therefore, log L extra auxiliary qubits are needed at each step, amounting to mlog L qubits in total for the workspace. As a result, encoding any Groverization of Schöning's algorithm asymptotically needs n+(log3+log L)m qubits. 

Figure <ref> represents a single step of Schöning walk, schematically. The first register encodes the space of all possible initialization. The gates ev_j, for j ∈{1,..,L}, act on the first two registers. Each gate consists of a few controlled-gates where the control qubits correspond to the three variables in the j-th clause, and the target qubit is the second register. The second register is an auxiliary qubit, initially set to |0⟩, and is negated as soon as the first violated clause is detected. The third register consists of log L auxiliary qubits that are used to count the number of clauses from where the first violated clause has happened. The last register is a qutrit providing the randomness of the corresponding walk step. The controlled-gates ch_j, for j ∈{1,..,L} act on the first three registers, and take care of variable flipping wherever the first violated clause is detected. The 012 block represents a triple controlled-gate where the control qutrit is the subspaces corresponding to the computational basis states |0⟩,|1⟩,|2⟩. 
Figure <ref> depicts the controlled-gates including ch_j, in detail. The sub-figure on the right shows the corresponding controlled-gate for GI, where the walk randomness is fed classically to the last register.  


All partial Groverization of Schöning algorithm can be implemented using slight modifications.
For the GW algorithm, the n-qubit variable register will not be initialized in the uniform superposition of all possible assignments |+⟩^⊗ n, but rather in a state with classically randomly defined variables |x_1 ⋯ x_n⟩.
For the GI algorithm the qutrit within every Schöning's step can be removed since we can, for every Schöning's step, generate a random number r∈{0, 1, 2} and apply only the X gates based on the classically determined r (see figure <ref>).


   





§ SUMMARY & OUTLOOK



This work considers hybrid schemes for search-based quantum algorithms, with the aim to allow for parallelizability, and to reduce the need for long coherence times. The basic gist is to partition the randomness of an underlying classical probabilistic algorithm into a part that is subject to Grover search, while the rest is sampled classically. Such `partial Groverizations' allow for parallelization of the classical sampling, as well as enable adaption to available coherence times. We consider exponential-time algorithms, why our analysis focuses on the asymptotic run-time rates and coherence-time rates. We argue that these two types of rates are bounded by a general trade-off relation that no hybrid-scheme can beat. For our concrete analysis, we consider hybrid schemes based on  Schöning's algorithm, where the latter solves 3-SAT (or more generally k-SAT) problems by random walks in the space of assignments. The walk-procedure allows for several partial Groverization-schemes.  We determine the corresponding run-times and coherence-times of these schemes, and demonstrate saturation of the general trade-off relation.  Many of these partial Groverizations intuitively lend themselves for efficient circuit implementations, and we provide the main building blocks of these. On a more speculative note, we present numerical evidence that the GI scheme can be partially de-randomized, in the sense that a single `typical' instance of the classical randomness of the walk appears to mimic the effects of the repeated sampling. This would open for an additional flexibility in the implementation of these hybrid-schemes, still maintaining the optional trade-off.


In this investigation, we have focused on partial Groverizations of  Schöning's algorithm. However, this approach should in principle be applicable to any classical probabilistic search scheme, since it essentially only rests on partitions of the underlying randomness. The main concern would be to find `natural' partitions that are algorithmically accessible, in the sense that the partial Groverization can be implemented efficiently.  Explicit run-time and coherence-time rates would also require a classical scheme, as well as partitions, that are sufficiently tractable for analysis, unless one would resort to numerical estimates.


The partial de-randomization of GI-scheme that is suggested by our numerical explorations, would deserve further investigations.    
In particular, the question is to what extent, and in what sense,  the hypothetical relation (<ref>) would be true. Moreover, one may ask if something similar also would apply to fractional GI. For numerical investigations, it would be relevant to extend to larger Hamming distances, further classes of 3-SAT  instances, as well as problem sizes. This would likely involve challenges to design reliable numerical estimates, since exact calculations by the very nature of the problem quickly becomes intractable. For purely analytical approaches, some notion of concentration of measure of walks, would be interesting. 


In the spirit of <cit.> we have in this investigation employed  `the walk on ℤ' as a model of the true Schöning-procedure. In Appendix (see also <cit.>) we in additionally provide bounds for the true rates of Schöning-procedure and the GW-procedure, in terms of the mirroring processes on ℤ. It would be relevant to obtain similar bounds also for the GI-process, as well as for the various fractional schemes.





§ ACKNOWLEDGEMENT


We thank Phillip Keldenich for kindly providing us with the SAT instance that was used for numerical simulations resulted in figure (<ref>). 
We acknowledge support from Bundesministerium für Bildung und Forschung - BMBF under project QuBRA.
The UzK team was also supported by Germany’s Excellence Strategy – Cluster of Excellence Matter and Light for Quantum Computing (ML4Q) EXC 2004/1 (390534769).





99
Schoening99 U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (IEEE, New York, 1999).

SchoeningToranBook U. Schöning and J. Torán, The Satisfiability Problem: Algorithms and Analyses (Lehmanns, Berlin, 2013).

Grover96 L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the 28th ACM Annual Symposium on the Theory of Computing, STOC 96, p. 212 (ACM, NewYork, 1996).

Ambainis04  A. Ambainis, Quantum search algorithms, ACM SIGACT News, 35, 22 (2004).

Dunjko18 V. Dunjko, Y. Ge and J. I. Cirac, Computational speedups using small quantum devices, PRL 121, 250501 (2018).

SwissPhDThesis R.A. Moser, Exact Algorithms for Constraint Satisfaction Problems, Doctoral thesis, ETH Zürich (2012)

SATtransition P. Cheeseman, B.  Kanefsky and W.M. Taylor, Where the Really Hard Problems Are. in Proceedings of the 12th international joint conference on Artificial intelligence - Volume 1, Pages 331–337 (1991)

cover T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd Edition (Wiley-Interscience, New Jersey, 2006) 

our-data  
V. Eshaghian,
S. Wilkening, 
J. Åberg, 
D. Gross,
Data for explicit run-times for hybrid SAT-solvers, <https://github.com/SoerenWilkening/QuantumSchoening>.

callen H. Callen, Thermodynamics and an introduction to thermostatistics, John Wiley, New York, 1985.

philipp-private-commutationDr. Phillip Keldenich, personal communication, March 2024.










§ FROM THE TRUE SCHÖNING-PROCESS  TO THE MARKOV PROCESS ON ℤ





 §.§ The purpose of this appendix


For the calculation of rates, we replace the genuine searches of solutions for 3SAT-problems (the `true  Schöning process'), with a Markovian random walk on  the `Hamming distance' (although we strictly speaking consider a walk on ℤ). This is analogous to Schönings analysis of the performance of Schönings algorithm <cit.>, where it is argued that this substitute-process yields an upper bound on the rates of the run-time of the algorithm. The purpose of this appendix is to give a more detailed argument for why the success probability of Schönings algorithm is lower bounded by the success-probability of the substitute walk on ℤ. The reader may also wish to consult <cit.> for a previous analysis along these lines. Apart from obtaining from bounding the success probability for the true Schöning-process, we also provide the analogous bound for the GW process.










 §.§ The Schöning-process


As described in the main text, the 3SAT problem consists of  a collection of clauses C_1,…, C_L on n binary variables, where each clause is of the form C_j = l_0^(j)∨ l_1^(j)∨ l_2^(j), and where each of the literals l_0^(j),  l_1^(j), l_2^(j) is one of the binary variables, or its negation.   The  3SAT formula is the conjunction of all the given clauses, C := ∧_j=1^LC_j, and the task is to determine whether there exists an assignment x∈{0,1}^× n of the n binary variables, which satisfies C.  In the following analysis we assume that C either has a unique satisfying assignment x^⋆∈{0,1}^× n, or alternatively, that x^⋆ is selected among a set of solutions.

 Schönings procedure can be regarded as a stochastic process (x_l)_l=0^m with  x_l ∈{0,1}^× n. 
The process is initialized by a random assignment x_0 of the bit string, drawn uniformly over all of {0,1}^× n. On this state it checks all the clauses C_1,…,C_L (according to a pre-determined order). If all are satisfied, then the initial string satisfies C and the algorithm terminates. 
 Otherwise, it finds the first unsatisfied clause, and randomly negates one of the three variables corresponding to the literals of that clause. The algorithm continues according to this random walk until it either finds a satisfying assignment, or it reaches  a  pre-determined termination-time K.  For our purposes, it is convenient to think of the state x_l of the process as a function of a collection of random variables. The initialization is represented by the random variable A, which takes values in {0,1}^× n. The randomness in the walk is captured by the variables  B = (B_1,…, B_m) be random variables where each B_l takes values in {0,1,2} (and thus B takes values in {0,1,2}^× m). Hence, B_l represents one of the three possible choices of which literal to flip at step l. 
   We assume that A,B_1,⋯, B_m are independent and uniformly distributed, i.e., for b = (b_1,…, b_m) we have

    P(A= a,B=b) =     P(A=a)P(B=b) = P(A = a)P(B_1 = b_1)⋯ P(B_m = b_m),
    
    P(A = a) =    1/2^n,  ∀ a∈{0,1}^× n
    
     P(B_l=b_l) =    1/3,  ∀ b_l∈0,1,2.

Hence, we can write the Schöning process as (x_l)_l = (x_l(A,B))_l, where

    x_0(a,b) := a,

i.e., a the initial state. At the  l:th step of Schöning's process is based on the state x_l-1 of the previous step. On this state, all the clauses C_1,…,C_L (according to a pre-determined order) are checked. If all are satisfied, then x_l-1 = x^⋆ and the process remains in that state, i.e., x_l = x^⋆.
(In other words, t x^⋆ is an absorbing state for the Schöning-process.)
 Otherwise, it finds the first unsatisfied clause, which we refer to as C_j_l. The selected clause, C_j_l, contains the three literals (l_0^(j),l_1^(j),l_2^(j)). The process constructs x_l by negating the variable corresponding to literal l^(j)_b_l. In other words, it is the l:th component of b that determines which of these three choices that is selected. One may note that the process, by construction, satisfies

    x_l(a,b) = x_l(a,b_1,…,b_l).

Hence, the value of x_l(a,b) only depends on the values of b_1,…, b_l, not any of the `later' variables b_l+1,b_l+1,….
One may also note that A,B_1,B_2,…, B_K encompasses all the randomness in the process. In other words, the state x_l is uniquely determined by a,b_1,…,b_l.





 §.§ The proof idea


As described above, the true Schöning-process (x_l)_l is a walk on bit-strings. However, for the analysis of the optimal rates, we follow in the steps of  Schöning <cit.>, and instead focus on the Hamming-distance to the (selected) solution x^⋆. In principle, nothing prevents us from projecting the state x_l of the  Schöning-process, to the Hamming distance d_H(x_l,x^⋆) (i.e. projecting onto ℕ). However, this would generally yield a  process that would be no easier to analyze than the original Schöning-process. One may for example note that although Schönings-process  (x_l)_l is Markovian on the space of bit-strings, one cannot generally expect its projection (d_H(x_l,x^⋆))_l to be Markovian on ℕ. The general idea for the analysis is to replace (via  a coupling) the true projection   (d_H(x_l,x^⋆))_l with another process (d̃_l)_l on ℕ, which is Markovian and which moreover upper-bounds the true Hamming-distance, d_H(x_l,x^⋆)≤d̃_l. One may note that the Schöning-process is `successful' if it finds the solution x^⋆. Hence,  we can express the success probability at step l as P(x_l = x^⋆) = P(d_H(x_l,x^⋆) = 0). From the bound d_H(x_l,x^⋆)≤d̃_l it follows that 
P(x_l = x^⋆) ≥  P(d̃_l = 0). In other words, the success-probability of the Schöning-process is lower-bounded by the probability that the substitute-process d̃_l reaches 0. The fact that (d̃_l)_l is Markovian makes the analysis more tractable. However, the value 0 corresponds to an absorbing boundary. (If we find the solution at an earlier stage, we should terminate the process rather than walking on.) To further ease the analysis, we remove this boundary and instead introduce yet another walk (d_l)_l on ℤ, which we regard as `successful' whenever d_l≤ 0. For this process we moreover establish the bound P(d̃_l = 0)≥ P(d_l≤ 0), and thus P(x_l = x^⋆)≥ P(d_l≤ 0). By the trivial bound P(d_l≤ 0)≥ P(d_l = 0), we thus ultimately get the bound  P(x_l = x^⋆)≥ P(d_l =  0). For the calculation of the optimal rates, our starting point is an expression for P(d_l =  0). By the inequality P(x_l = x^⋆)≥ P(d_l =  0) it follows that the calculated rates are upper bounds to the true rates of the Schöning-process.






 §.§ Constructing a walk (d̃_l)_l on  ℕ such that d_H(x_l,x^⋆)≤d̃_l


Related to the Schöning-process (x_l)_l, we here wish to construct  another process (d̃_l)_l, where d̃_l takes values in ℕ for all l∈ℕ, and is such that 
   
    d_H(x_l(a,b_1,…, b_l),x^⋆) ≤d̃_l(a,b_1,…, b_l),  ∀ a∈{0,1},  ∀ b∈{0,1,2}^× m,   l = 0,1,2,…,m.

In other words, we want to make sure that  d̃_l always is an upper bound to the Hamming distance between x_l and x^⋆.
This requires a considerable coordination between the two processes. In particular, whenever x_l moves in the `wrong' direction (i.e, increases the Hamming distance to x^⋆) then d̃_l also has to increase. 
To this end, we consider the list of clauses C_1,…, C_L. For each clause C_j  it is the case that C_j(x^⋆) = 1. Hence, for each j, at least one of the literals  l_0^(j),l_1^(j),l_2^(j) is satisfied by x^⋆. Among these satisfied clauses we select one of these satisfied literals, and let r_j∈{0,1,2} be its index. In other words, we are guaranteed that l_j^(r_j)(x^⋆) = 1.  


As already described above, the Schöning-process (x_l(a,b))_l is uniquely determined by (a,b_1,…,b_l), and does in turn uniquely determines the unsatisfied clauses C_j_l, as long as x_l(a,b_1,…, b_l)≠ x^⋆. Consequently, it also uniquely determines a sequence of `selected' literals r_j_l, whenever x_l(a,b_1,…, b_l)≠ x^⋆.
For each l ∈ 1,2,…, we define a mapping (a,b_1,… b_l-1)↦ f_l(a,b_1,…,b_l-1)∈{0,1,2} by

    f_1(a)    :=    {
     0    if     x_0 ≡ a = x^⋆,
    
     r_j_1   if     x_0≡ a ≠ x^⋆.
    .
    
    f_l(a,b_1,…,b_l-1) :=    {
     0    if     x_l-1(a,b_1,…, b_l-1) = x^⋆,
    
     r_j_l   if     x_l-1(a,b_1,…, b_l-1) ≠ x^⋆.
    .   l = 2,3,…

The purpose of f_l(a,b_1,…,b_l-1) is to determine which value of b_l that should correspond to a `successful' move for the (d̃_l)_l-process.
More precisely, we define (d̃_l(a,b))_l by

    d̃_0(a,b) :=      d_H(x_0(a,b),x^⋆) = d_H(a,x^⋆),
    d̃_l(a,b_1,…, b_l) :=    {
    0    if   d̃_l-1(a,b_1,…,b_l-1) = 0
    d̃_l-1(a,b_1,…, b_l-1) + 1    if   d̃_l-1(a,b_1,…, b_l-1) ≠ 0,    b_l ≠ f_l(a,b_1,…, b_l-1)
    d̃_l-1(a,b_1,…, b_l-1) - 1    if   d̃_l-1(a,b_1,…, b_l-1) ≠ 0,   b_l  = f_l(a,b_1,…,b_l-1)
    .    l = 1,2,…

In words, the first condition in the bracket means that 0 is an absorbing state, i.e., if d̃_l(a,b) = 0 for some l, then d̃_l'(a,b) = 0 for all l'≥ l. The other two cases make sure that the d̃_l moves in `coordination' with the  Schöning-process (x_l(a,b))_l, in such a manner that it is guaranteed that d_H(x_l(a,b_1,…,b_l),x^⋆) does not increase above d̃_l(a,b_1,…,b_l).




The Schöning process (x_l)_l∈ℕ and the process (d̃_l)_l∈ℕ as defined by  (<ref>) and (<ref>) satisfy 
  
    d_H(x_l(a,b_1,…,b_l),x^⋆) ≤d̃_l(a,b_1,…,b_l),  ∀ a∈{0,1}^× n,  ∀ b∈{0,1,2}^× l,   l = 0,1,2,….


One may note that (<ref>) holds for every single element in the event-space, and Lemma <ref> does thus not depend on the actual probability distribution of A,B_1,…, B_l. However, there are other steps in our proofs that do depend crucially on these variables being independent and uniformly distributed.


We first note that 

    x_0(a,b) = a,  d̃_0 = d_H(a,x^⋆)

and thus (<ref>) is satisfied for l=0 for all a,b.

Now, assume that (<ref>) holds for some l-1,a,b.
We have the following cases:


  * Case x_l-1(a,b) = x^⋆:  Since we assume that x^⋆ is absorbing, it follows that x_l(a,b) = x^⋆ and consequently d_H(x_l(a,b_1,…,b_l),x^⋆) = 0.  Concerning d̃_l-1, we can distinguish yet two sub-cases:


  * Case d̃_l-1(a,b_1,…,b_l-1) = 0: By construction (first case in (<ref>)) d̃_l(a,b_1,…,b_l) = 0, and (<ref>) is thus satisfied for l,a,b.

  * Case d̃_l-1(a,b_1,…,b_l-1) ≠ 0: Then d̃_l-1(a,b_1,…,b_l-1) ≥ 1. Since the process d can change at most one step, it follows that d̃_l-1(a,b_1,…,b_l-1) ≥ 0, and thus (<ref>) is satisfied for l,a,b.


  * Case x_l-1(a,b) ≠ x^⋆:
Since we assume that (<ref>) holds for l-1,a,b it follows that  d̃_l-1(a,b_1,…,b_l-1) ≥ 1. Moreover, since x_l-1(a,b) ≠ x^⋆, we have f_l(a,b_1,…,b_l-1) = r_j_l. Again, we can distinguish two sub-cases:


  * Case f_l(a,b_1,…,b_l-1) = b_l: In this case, the d-process decreases one step. However, by construction r_j_l is one of the `successful' flips for the Schöning-process, hence the x-process also decreases one step.  By assumption the inequality  (<ref>) is satisfied for  l-1,a,b, and since both the x-process and the d-process decrease one step, (<ref>) remains satisfied for l,a,b.

  * Case f_l(a,b_1,…,b_l-1)≠ b_l:
In this case, the d-process increases one step. The x-process may increase or decrease, but with at most one step, so (<ref>) remains satisfied for l,a,b.


By induction, we can conclude that (<ref>) is satisfied for all l,a,b.








 §.§ (d̃_l)_l is a Markov chain


In the following we wish to show that (d̃_l)_l is a Markov chain. Recall that  both the genuine Schöning-process  (x_l)_l, as well as the walk (d̃_l)_l, are determined by a sequence of  `walk variables' (B_l)_l (and initial-state variable A). The  Schöning-walk itself is Markovian, but it is a priori not  obvious that the process (d̃_l)_l also is Markovian, particularly since the l-th step of the latter is determined by a complicated function  of all the walk-variables up to the l-th step, as described  by  (<ref>). However, in spite appearances, it turns out that (<ref>) defines a mapping from the original set of random variables (B_l)_l to a new set of variables  (B̃_l)_l,  in such a manner that  the change from d̃_m-1 to d̃_m is determined by B̃_m, and only by  B̃_m.  Moreover, it turns out that (B̃_l)_l is an iid sequence. 
Since all the B̃_l are independent, it follows that (d̃_l)_l must be a Markov chain.  In order to show that the new sequence of variables  (B̃_l)_l is iid, what we actually do is to show that  (<ref>) induces a bijection on {0,1}^× n×{0,1,2}^l. Since (A, (B_l)_l) is uniformly distributed (see (<ref>)) it follows by the bijection that  (A, (B̃_l)_l) also is uniformly distributed, and thus in particular that (B̃_l)_l is iid.






 §.§ A bijection



The following lemma introduces functions f_s.  Later, in the proof of Proposition <ref>, we will let these mappings be  the functions f_l(a,b_1,…,b_l-1) in (<ref>). Since the latter  are algorithmically defined, via the  Schöning-process (x_l)_l, it is challenging to get a hold on the properties of these mappings. It is thus worth noting that (apart from domains and ranges) Lemma  <ref> (and Lemma <ref>) makes no assumptions on the properties of the mappings f_s. Hence, our lack of control over the mappings f_l(a,b_1,…,b_l-1) will not be an issue in the subsequent proofs.


As preparation, we make the following observations.
 
If t,t',r∈{0,1,2}, then 

    (t-r)mod  3 = (t'-r)mod  3  ⇔   t = t'.

Moreover, if t,r∈{0,1,2}, then

    ((t+r)mod 3 - r)mod  3 = t.






Let f_1:{0,1}^× n→{0,1,2} and 
 f_s:{0,1}^× n×{0,1,2}^× (s-1)→{0,1,2} for s = 2,…, l be given. 
Define the  mapping {0,1}^× n×{0,1,2}^× l∋ (b_1,…, b_l) ↦ Q(a,b_1,…, b_l) = (ã,b̃_1,…, b̃_l)∈{0,1}^× n×{0,1,2}^× l by

    ã :=     a,
    b̃_1 :=    (b_1-f_1(a))mod  3,
    b̃_2 :=    (b_2-f_2(a,b_1))mod  3,
    b̃_3 :=    ( b_3-f_3(a,b_1,b_2))mod  3,
    ⋮   
    b̃_l :=    ( b_l-f_l(a,b_1,…,b_l-1))mod  3.

Then Q is a  bijection on {0,1}^× n×{0,1,2}^× l.





To show that Q is a bijection, we first show that it is injective, and then that it is surjective.


Let (a,b_1,…,b_l),(a',b'_1,…,b'_l)∈{0,1}^× n×{0,1,2}^× l be such that 

    Q(a,b_1,…,b_l)= Q(a',b'_1,…,b'_l).

By the first line of (<ref>) it follows that 

    a= ã = a'.

By the second line of (<ref>) it follows that

    (b_1-f_1(a))mod  3 = (b'_1-f_1(a'))mod  3,

which combined with (<ref>) yields

    (b_1-f_1(a))mod  3 = (b'_1-f_1(a))mod  3.

Since f_1(a),b_1,b'_1∈{0,1,2} it follows by (<ref>) that  

    b_1 = b'_1.



As an induction hypothesis, assume that  for some s≥ 2, it is the case that 

    a = a',   b_j = b'_j,   j = 1,…, s-1.

The sth line of (<ref>) implies

    (b_s - f_s(a,b_1,…, b_s-1) )mod  3= (b'_s- f_s(a',b'_1,…,b'_s-1))mod  3.

By the induction hypothesis, this implies

    (b_s - f_s(a,b_1,…, b_s-1) )mod  3= (b'_s- f_s(a,b_1,…,b_s-1))mod  3.

Since b_s,b'_s,f_s(a,b_1,…,b_s-1) ∈{0,1,2}, it follows by (<ref>) that  

    b_s = b'_s.

Since the induction hypothesis is true for s= 2, we can conclude that it is true for all s = 2,…, l. We can thus conclude that Q is injective.


Next we wish to show that Q is surjective onto  {0,1}^× n×{0,1,2}^× l.
Let (ã',b̃'_1,…,b̃'_l)∈{0,1}^× n×{0,1,2}^× l. 
Define

    a :=   ã',
    
    b_1 :=    (b̃'_1 +f_1(ã'))mod  3 = (b̃'_1 +f_1(ã'))mod  3,

and the sequence (b_j)_j=2^l recursively by

    b_j := (b̃'_j + f_j(a,b_j-1,…, b_1))mod  3,   j = 2,…, l,

for a' and b_1' as defined in (<ref>).
In the following, we wish to show that  Q(a,b_1,…,b_l) =  (ã',b̃'_1,…,b̃'_l). For notational convenience, we introduce the components Q_0(a,b_1,…,b_l)  := ã and Q_j(a,b_1,…,b_l) := b̃_j, quad j =m2,…,l.  






By the first line of (<ref>) we have

    Q_0(a,b_1,…,b_l) =     a = ã'.

By the second line of (<ref>)

    Q_1(a,b_1,…,b_l) =    (b_1-f_1(a))mod  3
    
    =    ( (b̃'_1 +f_1(ã'))mod  3  -f_1(a))mod  3   
      
    =    ( (b̃'_1 +f_1(ã'))mod  3  -f_1(ã'))mod  3   
        [By (<ref>)]
    
    =    b̃'_1.

For all j≥ 2 we moreover have

    Q_j(a,b_1,…,b_l) =    ( b_j-f_j(a,b_1,…,b_j-1))mod  3
        [By (<ref>)]
    
    =    (  (b̃'_j + f_j(a,b_j-1,…, b_1))   -f_j(a,b_1,…,b_j-1))mod  3
        [By (<ref>)]
    
    =    b̃'_j.

Hence, we can conclude that Q(a,b_1,…,b_l) =  (ã',b̃'_1,…,b̃'_l). Hence Q is surjective, and thus bijective.





 §.§   Transformations that preserve uniformity



We make the following basic observation


Let 𝒮 be some finite set. Let Q:𝒮→𝒮 be invertible. Let R be some random variable on 𝒮. If R is uniformly distributed over 𝒮, the Q(R) is also uniformly distributed over 𝒮.



    P(Q(R) = s) =     P(R = Q^-1(s)) = 1/|𝒮|.





 
Let f_1:{0,1}^× n→{0,1,2} and 
 f_s:{0,1}^× n×{0,1,2}^× (s-1)→{0,1,2} for s = 2,…, l be given. 
Assume that B_1,…,B_l are random variables that take values in {0,1,2}, A be a random variable that takes values in {0,1}^× n, and that these are distributed as 

    P(A = a, B_1 = b_1,…, B_l = b_l) = 1/2^n3^l,  ∀ a∈{0,1}^× n,  ∀ (b_1,…, b_l)∈{0,1,2}^× l.

Define B̃_1,…, B̃_l by

    B̃_1 :=    (B_1-f_1(A))mod  3,
    B̃_2 :=    (B_2 - f_2(A, B_1))mod  3,
    B̃_3 :=    (B_3  - f_3(A, B_1,B_2))mod  3,
    ⋮   
    B̃_l :=    (B_l - f_l(A,B_1,…, B_l-1))mod  3.

Then 

    P(A = a, B̃_1 = b̃_1,…, B̃_l = b̃_l) = 1/2^n3^l,  ∀ a∈{0,1}^× n,  ∀ (b̃_1,…, b̃_l)∈{0,1,2}^× l.
 
Consequently, A,B̃_1,…,B̃_l are independent and uniformly distributed.





By (<ref>) we know that (A,B_1,…,B_l) is uniformly distributed on {0,1}^× n×{0,1,2}^× l.
With the additional definition Ã := A, we note that (<ref>) can be rewritten as

    (Ã,B̃_1,…,B̃_l) := Q(A,B_1,…,B_l),

where Q:{0,1}^× n×{0,1,2}^× l→{0,1}^× n×{0,1,2}^× l is as defined in Lemma
<ref>. By Lemma <ref>, we moreover know that Q is a bijection on {0,1}^× n×{0,1,2}^× l and thus invertible. Hence, by Lemma <ref>, we know that (Ã,B̃_1,…,B̃_l) also is uniformly distributed over {0,1}^× n×{0,1,2}^× l. Since Ã = A, we can conclude that (<ref>) holds. 

By (<ref>) i follows that 

    P(A = a, B̃_1 = b̃_1,…, B̃_l = b̃_l) = P(A = a)P(B̃_1 = b̃_1)⋯ P(B̃_l = b̃_l),
        P(A =a) = 1/2^n,   P(B̃_1 = b̃_1) = 1/3,…,P(B̃_l = b̃_l) = 1/3.

and thus A, B̃_1,…,B̃_l are independent and uniformly distributed.








 §.§  The process (d̃_l)_l is a Markov chain




Let (d̃_l)_l be the process as defined by (<ref>) and (<ref>), with respect  to the variables A, B_1,B_2,… distributed as in (<ref>). For each m there exist
variables B̃_1,⋯,B̃_m that are iid and uniformly distributed on {0,1,2}, and are independent of A, such  that

    d̃_0 :=      d_H(A,x^⋆),
    d̃_l :=    {
    0    if   d̃_l-1 = 0
    d̃_l-1 + 1    if   d̃_l-1≠ 0,  B̃_l  ≠ 0
    d̃_l-1 - 1    if   d̃_l-1≠ 0,  B̃_l  = 0
    .    l = 1,2,…,m

Hence, (d̃_l)_l is a Markov chain described by the transition probabilities

    P(d̃_l+1 = j|d̃_l = k) = δ_j,0δ_k,0 + (1-δ_k,0)(1/3δ_j,k-1 +2/3δ_j,k+1),  ∀ j,k∈ℕ,  ∀ l

with initial distribution

    P(d̃_0 = j) = P(d_H(A,x^⋆)= j).

Moreover, for the distribution of A as in  (<ref>) we have

    P(d̃_0 = j) = {1/2^nnj   ,   0≤ j≤ n
    
    0   otherwise.



In (<ref>), the term δ_j,0δ_k,0 signifies d = 0 being an absorbing state. In the second term, the effect of the factor  (1-δ_k,0) is that if the chain is not in the absorbing state, then the transition probabilities are given by 1/3δ_j,k-1 +2/3δ_j,k+1. Hence, with probability 1/3, it takes a step `down', and with probability 2/3 it takes a step `up'.




For t,r∈{0,1,2} it is the case that 

    t = r   ⇔   (t-r)mod 3 = 0.

By this observation, it follows that (<ref>) can be rewritten as

    d̃_0(a,b) :=      d_H(a,x^⋆),
    d̃_l(a,b_1,…, b_l) :=    {
    0    if   d̃_l-1(a,b_1,…,b_l-1) = 0
    d̃_l-1(a,b_1,…, b_l-1) + 1    if   d̃_l-1(a,b_1,…, b_l-1) ≠ 0,  (b_l -f_l(a,b_1,…, b_l-1))mod 3  ≠ 0
    d̃_l-1(a,b_1,…, b_l-1) - 1    if   d̃_l-1(a,b_1,…, b_l-1) ≠ 0,  (b_l -f_l(a,b_1,…, b_l-1))mod 3  = 0
    .    l = 1,2,…

Next, we rewrite (<ref>) such that we suppress the explicit dependence on the elementary events (a,b).

    d̃_0 :=      d_H(A,x^⋆),
    d̃_l :=    {
    0    if   d̃_l-1 = 0
    d̃_l-1 + 1    if   d̃_l-1≠ 0,  (B_l -f_l(A,B_1,…, B_l-1))mod 3  ≠ 0
    d̃_l-1 - 1    if   d̃_l-1≠ 0,  (B_l -f_l(A,B_1,…, B_l-1))mod 3  = 0
    .    l = 1,2,…

If we define B̃_1,…, B̃_l by

    B̃_1 :=      f_1(A),
    B̃_2 :=    (B_2 - f_2(A, B_1))mod  3,
    B̃_3 :=    (B_3  - f_3(A, B_1, B_2))mod  3,
    ⋮   
    B̃_l :=    (B_l - f_l(A,B_1,…, B_l-1))mod  3,

then we can rewrite (<ref>) as

    d̃_0 :=      d_H(A,x^⋆),
    d̃_l :=    {
    0    if   d̃_l-1 = 0
    d̃_l-1 + 1    if   d̃_l-1≠ 0,  B̃_l  ≠ 0
    d̃_l-1 - 1    if   d̃_l-1≠ 0,  B̃_l  = 0
    .    l = 1,2,…

By Lemma <ref> we know that A,B̃_1,…,B̃_l are independent and uniformly distributed.
Since the l:th step is determined solely by B̃_l, and these are independent of each other, and of A, it follows that (d̃_l)_l is a Markov chain. 
By inspecting (<ref>) we first see that 

    P(d̃_l = j|d̃_l-1 = 0)  = δ_j,0,

while for d̃_l-1 = k≠ 0 we have

    P(d̃_l = j|d̃_l-1 = k)  =    δ_j,k+1 P(B̃_l  ≠ 0) + δ_j,k-1P(B̃_l  = 0)
    
    =    2/3δ_j,k+1 + 1/3δ_j,k-1,

where the last step follows since each B̃_l is uniformly distributed over {0,1,2}.
By combining the cases (<ref>) and (<ref>) we obtain (<ref>). By (<ref>) it moreover follows that P(d̃_0 = j) = P(d_H(A,x^⋆)= j). Since A is uniformly distributed over {0,1}^× n, it means that d_H(A,x^⋆) is binomially distributed. Thus for 0≤ j ≤ n, we have P(d̃_0 = j) =1/2^nnj.







 §.§ Relating probabilities of (x_l)_l and (d̃_l)_l


The reason for why we introduce the walk (d̃_l)_l is in order to bound the relevant success-probabilities of the more complicated true Schöning-walk (x_l)_l.  The lemma below considers two such inequalities, which we will use when we determine the bounds for the Groverized walk. 

 

Let (x_l)_l∈ℕ be the Schöning process for bit strings of length n, with x^⋆ the selected satisfying assignment. Let (d̃_l)_l be the process as defined by (<ref>) and (<ref>).  Then

    P(x_m  = x^⋆)≥ P(d̃_m = 0),


    P(  x_m = x^⋆|d_H(x_0,x^⋆) = j)≥ P(d̃_m = 0|d̃_0 = j),





We begin by proving inequality (<ref>). For the sake of notational simplicity, we let ω denote the elements of the event space (where we could regard ω as (a,b) or (a,b̃)).
By Lemma <ref> we know that 

    d_H(x_m(ω),x^⋆) ≤d̃_m(ω),

which  implies

    d̃_m(ω) = 0  ⇒   d_H(x_m(ω),x^⋆) =0

and thus

    {ω: d̃_m(ω) = 0}⊂{ω: d_H(x_m(ω),x^⋆) = 0} = {ω: x_m(ω) = x^⋆}

and thus 

    P(d̃_m = 0)     = P({ω: d̃_m(ω) = 0}) 
       ≤ P(  {ω: x_m(ω) = x^⋆})
        = P(x_m  = x^⋆),

which proves (<ref>).






We next turn to the proof of (<ref>)
By definition of the walk (d̃_l)_l we have d̃_0(ω) = d_H(x_0(ω),x^⋆), and thus 

    {ω: d̃_0(ω) = j} = {ω: d_H(x_0(ω),x^⋆) = j}

and consequently

    P(d̃_0 = j) = P(d_H(x_0,x^⋆) = j).

By combining (<ref>)  and (<ref>) we obtain

    {ω: d̃_m(ω) = 0}∩{ω: d̃_0(ω) = j}⊂{ω: x_m(ω) = x^⋆}∩{ω: d_H(x_0(ω),x^⋆) = j}

and consequently

    P(d̃_m = 0,d̃_0 = j) 
    =     P({ω: d̃_m(ω) = 0}∩{ω: d̃_0(ω) = j})
    ≤    P( {ω: x_m(ω) = x^⋆}∩{ω: d_H(x_0(ω),x^⋆) = j})
    
    =      P(  x_m = x^⋆, d_H(x_0,x^⋆) = j).

By combining this with (<ref>) we can conclude that

    P(d̃_m = 0|d̃_0 = j) 
    ≤     P(  x_m = x^⋆|d_H(x_0,x^⋆) = j),

which proves (<ref>).









 §.§ From walks  on ℕ to  walks  on ℤ

So far, we have replaced the projection of the Schöning-process (x_l)_l to the Hamming distance d_H(x_m,x^⋆)  with the substitute Markov-chain (d̃_l)_l. Similar to x^⋆ being an absorbing state of (x_l), the process (d̃_l)_l has 0 as absorbing state. As a model of the true Schöning process, this  absorbing state certainly makes sense, since it  corresponds to a setting where we at each step monitor whether a solution has been reached, and the process is terminated once this happens.  For  the sake of obtaining tractable expressions for the relevant probabilities, we  here take one step further and instead consider a walk on ℤ.  Analogously to how Lemma <ref> bounds the relevant probabilities of the true Schöning process, with the corresponding quantities in (d̃_l)_l, Lemma <ref> below, bounds the relevant probabilities of (d̃_l)_l in terms of corresponding quantities for a Markov-chain (d_l)_l extended to the whole of ℤ.

As a bit of a side remark, one may note that the results in (<ref>) does not necessarily refer to the particular Markov-chain defined by  (<ref>) and (<ref>), but could be any Markov chain on ℕ with fixed transition probabilities and absorbing boundary condition at 0. 
 




Let (d̃_l)_l∈ℕ be a Markov chain on ℕ, with transition probabilities

    P(d̃_l+1 = j|d̃_l = k) = δ_j,0δ_k,0 + (1-δ_k,0)((1-q)δ_j,k-1 +qδ_j,k+1),  ∀ j,k∈ℕ,  ∀ l∈ℕ,

for some 0≤ q≤ 1. 
Let (d_l)_l∈ℕ be a Markov chain on ℤ, with transition probabilities

    P(d_l+1 = j|d_l = k) = (1-q)δ_j,k-1 + qδ_j,k+1,  ∀ j,k∈ℤ,  ∀. l∈ℕ.

Then

    P(d_m≤ 0|d_0 = j) ≤ P(d̃_m = 0|d̃_0 = j),  ∀ m∈ℕ,  ∀ j∈ℕ.

Consequently, if the initial state d_0 is such that 

    P(d_0 = j) = {
    P(d̃_0 = j),       j ≥ 0
    
    0 ,        j <0
    .

then

    P(d_m = 0) ≤ P(d_m≤ 0) ≤ P(d̃_m = 0),  ∀ m∈ℕ.





For notational convenience, we define

    M_j,k :=      P(d̃_l+1 = j|d̃_l = k),

and

    M̃_j,k :=     P(d_l+1 = j|d_l = k).

By comparing with (<ref>) and (<ref>) one can see that

    M_j,k = M̃_j,k,  ∀ j>0,  ∀ k>0.

We note that 0 is an absorbing state for (d̃_l)_l. Hence, 

    d̃_s-1 = 0  ⇒  d̃_s = 0,

which implies

    d̃_s>0   ⇒  d̃_s-1>0,

which in turn implies

    P(d̃_s= k_s|d̃_s-1=0) = 0,  if   k_s >0.


We begin by proving (<ref>). For this purpose, assume that j>0. 

    P(d̃_l >0 |d̃_0 = j)
    
     =    ∑_k_l>0P(d̃_l =k_l |d̃_0 = j)
        [By Markovianity]
    
    =    ∑_k_l>0∑_k_l-1,…,k_1 P(d̃_l = k_l|d̃_l-1 = k_l-1)P(d̃_l-1 = k_l-1|d̃_l-2 = k_l-2)⋯ P(d̃_2 = k_2|d̃_1 = k_1)P(d̃_1 = k_1|d̃_0 = j)
    
    =    ∑_k_l>0∑_k_l-1:k_l-1>0∑_k_l-2,…,k_1 P(d̃_l = k_l |d̃_l-1 = k_l-1)P(d̃_l-1 = k_l-1|d̃_l-2 = k_l-2)⋯  P(d̃_1 = k_1|d̃_0 = j)
        + ∑_k_l>0∑_k_l-2,…,k_1 P(d̃_l = k_l|d̃_l-1 = 0)P(d̃_l-1 = 0|d̃_l-2 = k_l-2)⋯ P(d̃_1 = k_1|d̃_0 = j)
    
        [Since k_l> 0 it follows by (<ref>) that P(d̃_l = k_l|d̃_l-1 = 0) = 0.]
    
    =    ∑_k_l>0∑_k_l-1:k_l-1>0∑_k_l-2,…,k_1 P(d̃_l = k_l |d̃_l-1 = k_l-1)P(d̃_l-1 = k_l-1|d̃_l-2 = k_l-2)⋯ P(d̃_1 = k_1|d̃_0 = j)
        [By iteration]
    
    =    ∑_k_l>0∑_k_l-1,…,k_1:k_l-1 >0,…, k_1 >0 P(d̃_l = k_l |d̃_l-1 = k_l-1)P(d̃_l-1 = k_l-1|d̃_l-2 = k_l-2)⋯  P(d̃_1 = k_1|d̃_0 = j)
        [By (<ref>)]
    
    =    ∑_k_l>0∑_k_l-1,…,k_1:k_l-1 >0,…, k_1 >0 M_k_l,k_l-1⋯ M_k_1,j
        [Since k_l > 0,  k_l-1>0,⋯, k_1>0, j>0 if follows by (<ref>) that] 
    
    =    ∑_k_l>0∑_k_l-1,…,k_1:k_l-1 >0,…, k_1 >0M̃_k_l,k_l-1⋯M̃_k_1,j
        [  M̃_k_l,k_l-1≥ 0    ]
    ≤   ∑_k_l>0∑_k_l-1,…, k_1M̃_k_l,k_l-1⋯M̃_k_1,j
        [By (<ref>)]
    
    =    ∑_k_l>0∑_k_l-1,…, k_1P(d_l = k_l |d_l-1 = k_l-1)P(d_l-1 = k_l-1|d_l-2 = k_l-2)⋯  P(d_1 = k_1|d_0 = j)
        [By the Markovianity]
    
    =    ∑_k_l>0P(d_l = k_l|d_0 =j)
    
    =     P(d_l > 0|d_0 =j).

Consequently

    P(d̃_l =0 |d̃_0 = j)=     1- P(d̃_l >0 |d̃_0 = j)
    ≥    1-P(d_l > 0|d_0 =j)
    
    =     P(d_l ≤ 0|d_0 =j),   j>0.

In the case d̃_0 = 0 we know that this is an absorbing state, and thus P(d̃_l =0 |d̃_0 = 0) = 1. Consequently, P(d_l≤ 0|d_0 = 0)≤ P(d̃_l =0 |d̃_0 = 0) = 1.
This thus proves the inequality in  (<ref>).

With the initial distribution (<ref>) we find

    P(d_l≤ 0) =    ∑_j∈ℤP(d_l≤ 0|d_0 = j)P(d_0 = j)
    
    =    ∑_j≥ 0P(d_l≤ 0|d_0 = j)P(d̃_0 = j)
    ≤   ∑_j≥ 0P(d̃_l = 0|d̃_0 = j)P(d̃_0 = j)
    
    =     P(d̃_l = 0).







 



 §.§ Bounds for Schöning Walks and Groverized Walks



Here we combine the previous observations in order to obtain the following lower bounds on the success-probability of the  Schöning process. We also obtain the inequalites needed for determining the desired bound on the success-probability of the the Groverized walk.


Let (x_l)_l∈ℕ be the Schöning process for bit strings of length n, with x^⋆ the selected satisfying assignment. Let (d̃_l)_l be the process as defined by (<ref>) and (<ref>).
Let (d_l)_l be the Markov chain as defined by the transition probabilites (<ref>) for q = 2/3  in Lemma <ref>, for the initial state

    P(d_0 = j) = {
    P(d̃_0 = j) =  P(d_H(x_0,x^⋆) =j) = 1/2^nnj,       n≥ j ≥ 0
    
    0 ,      otherwise.

 Then

    P(x_m = x^⋆) ≥     P(d̃_m= 0) 
    ≥     P(d_m≤ 0)
    
     =    ∑_j,l: j+ m-2l ≤ 0,
     0 ≤ j≤ n,
     0≤ l≤ m1/2^nnjml(1/3)^l(2/3)^m-l

and

    P(x_m = x^⋆|d_H(x_0|x^⋆) = j) ≥    P(d̃_m =  0|d̃_0 = j) 
    ≥    P(d_m≤ 0|d_0 = j)
    
     =    ∑_l: j+ m-2l ≤ 0,
     0≤ l≤ mml(1/3)^l(2/3)^m-l.






By (<ref>) in Lemma <ref> yields the  first  inequality in  (<ref>).

By Proposition <ref> we know that (d̃_l)_l is a Markov chain with transition probabilities as in (<ref>) and initial distribution (<ref>). By these observations, it follows that the  second inequality  in (<ref>) is a direct application of (<ref>) in Lemma <ref>. 
By Lemma <ref>, we also know that the Markov chain (d_l)_l defined by the transition probabilities

    P(d_l+1 = j|d_l = k) = 1/3δ_j,k-1 + 2/3δ_j,k+1,  ∀ j,k∈ℤ,  ∀ l∈ℕ.

and initial distribution

    P(d_0 = j) = {
    P(d̃_0 = j),       j ≥ 0
    
    0 ,        j <0
    .   =  {1/2^nnj,     0≤ j≤ n
    
    0,    otherwise.

From (<ref>) it follows that 

    P(d_m≤ 0|d_0 = j) = ∑_l: j+m-2l≤ 0,  0≤ l≤ mml(1/3)^l(2/3)^m-l

and thus 

    P(d_m≤ 0) =    ∑_j P(d_m≤ 0|d_0 = j)P(d_0 = j)
        [By (<ref>)]
    
     =    ∑_j,l: j+ m-2l ≤ 0,
     0 ≤ j≤ n,
     0≤ l≤ m1/2^nnjml(1/3)^l(2/3)^m-l.




Next, we turn to the inequalities in (<ref>). 
Inequality (<ref>) in Lemma <ref> yields the first inequality in (<ref>). The second inequality in (<ref>) is a direct application of 
(<ref>) in Lemma (<ref>). By (<ref>) we already know the last equality in (<ref>).








 §.§ Relation to the leading order analysis of the Schöning and  GW process

Here we connect to the analysis of the asymptotic scaling in the main text, by obtaining the starting points, so to speak, of the leading order analysis of the Schöning process and the GW process.  





  §.§.§ Schöning process

For the Schöning process, the average number of repetitions needed to find a solution is given by 

    N_Schöning = 1/P(x_m = x^⋆).

 By sequences of lower bounds on the ideal success-probability P(x_m = x^⋆), we thus obtain upper bounds on N_Schöning. The step from the true Schöning process to the walk on Z corresponds to one such inequality, i.e. to 
 
    P(x_m = x^⋆) ≥    P(d_m≤ 0)

  in (<ref>) in Proposition (<ref>).
The leading-order analysis in the main text is based on further such inequalities, with the rationale that the `loss' of probability weight becomes irrelevant for the rates γ = lim_n→∞1/nlog N_Schöning, if the inequalities are chosen to correspond to the leading order contributions.  As a first step along these lines, we restrict to an event where we not only reach the desired solution, but also start the system x_0 at Hamming distance  d_H(x_0,x^⋆) = j.
 Trivially, 

    P(d_m≤ 0) ≥ P(d_m≤ 0, d_0 = j) = P(d_0 = j)P(d_m ≤ 0|d_0 = j),

where can identify P(d_0 = j) with P(E_1) in the main text, i.e. 

    P(d_0 = j)  = P(E_1) = 1/2^nnκ n,   j = κ n.

Next, we wish to connect the remaining factor  in (<ref>), i.e.,  P(d_m≤ 0|d_0 = j), to the probability P(E_2), which we recall from the main text corresponds to the event E_2, where precisely ν m steps decrease the Hamming distance, while precisely (1-ν)m steps increase the Hamming distance. (For the walk on ℤ this extends to  ν m steps in the negative direction, and (1-ν)m steps in the positive direction.) We conclude that the total decrease is 

    d_0-d_m = (2ν-1)m.

Let us also recall that the combination of  E_1 and E_2 is successful, i.e. leads to d_m≤ 0, if 

    (2ν -1)m≥κ n.

It is useful to note that (d_l)_l is not only Markovian, but also translation symmetric, which means that the change d_0-d_m is independent of the initial state d_0, i.e., the joint distribution of these factorize. (As a side remark, this independence also means that P(E_1∩ E_2) = P(E_1)P(E_2).)
 Hence,

    P(d_m≤ 0|d_0 = κ n)
        = P(d_0-d_m≥κ n|d_0 = κ n)
        [Since d_0-d_m is independent of d_0]
        = P(d_0-d_m≥κ n).

By comparison of (<ref>) with (<ref>) it follows that 

    P(d_m≤ 0|d_0 = κ n)
        = P(d_0-d_m≥κ n)
       ≥ P(E_2),  if   (2ν -1)m≥κ n.

Alternatively, we can reach the same conclusion by comparing (<ref>) with  (<ref>) to see  that  

    P(E_2) =  mν m(1/3)^ν m(2/3)^(1-ν)m≤ P(d_m≤ 0|d_0 = κ n),  if   (2ν -1)m≥κ n

By (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>), we can conclude that

    N_Schöning≤1/P(E_1)P(E_2),  if   (2ν -1)m≥κ n.




  §.§.§ GW process


For the GW process, let us recall that it consists of a classical outer loop that at each round assigns a definite (classical) initial state, while the walk-process is Groverized. We assume that the number of iterations of the Grover-procedure is tuned to the density of successful walks, for a specific initial Hamming distance j = κ n, i.e., to the success-probability P(x_m = x^⋆|d_H(x_0|x^⋆) = κ n). In the analysis we lower bound the success-probability by assuming that process fails whenever d_H(x_0,x^⋆) ≠κ n (which may be pessimistic).  The probability to obtain the initial state x_0 with Hamming distance κ n is P(d_H(x_0,x^⋆) =κ n), and thus in average we need to repeat the outer loop 1/P(d_H(x_0,x^⋆) =κ n) times to be guaranteed to at least once reach the initial Hamming distance κ n. In the successful case, the Grover procedure requires 1/√(P(x_m = x^⋆|d_H(x_0|x^⋆) = κ n)) iterations. Consequently, an upper bound on the total number of steps is 

    N_GW≤   1/P(d_H(x_0,x^⋆) =κ n)√(P(x_m = x^⋆|d_H(x_0|x^⋆) = κ n))
        [By Proposition (<ref>)]
    ≤   1/P(d_0 = κ n)√(P(d_m≤ 0|d_0 = κ n))
        [By (<ref>) and (<ref>)]
    ≤   1/P(E_1)√(P(E_2)),  if   (2ν -1)m≥κ n.








