Computational speedups using small quantum devices

Our scenario is related to, but distinct from, the work in [ 13 ] . There, the authors consider how a classical computer can help simulate a given quantum algorithm which requires only slightly more qubits than are available. In contrast, we change the algorithm, i.e. , propose hybrid algorithms which use a significantly smaller quantum device, to speed up a fixed classical algorithm. The two approaches are also complementary in their applicability: the main results of [ 13 ] are most powerful for shallow computations. In particular, their results could only be directly applied for SAT solving if one has access to an exponentially sized quantum computer to begin with, as the computation may be exponentially deep

Cited in the paper.

The O ∗ O^{\ast} notation suppresses the terms which contribute only polynomially, see, e.g

Cited in the paper.

By “interpolate” we mean that the hybrid algorithm’s runtime is characterized by a function h ⁡ ( n , m ) h(n,m) of the size of the quantum device (approx. m m ), and the instance size n n , which is (strictly) monotonically decreasing in m m , and which roughly attains the classical, and fully quantum runtimes for m = 1 m=1 and m = n , m=n, respectively

Cited in the paper.

If a literal appearing in a clause C = { l 1 , l 2 , l 3 } C=\{l_{1},l_{2},l_{3}\} evaluates to 1, then C C is satisfied regardless of the other variable assignments, and can be removed from the formula. If a literal (say l 1 l_{1} ) evaluates to 0, then for C C to be true we need to satisfy the truncated clause C = { l 2 , l 3 } C=\{l_{2},l_{3}\}

Cited in the paper.

Let F 𝐱 F_{\mathbf{x}} be the formula obtained by negating any literal in F F which corresponds to a variable to which 𝐱 \mathbf{x} assigns the value 1 1 , so that F 𝐱 ​ ( 0 , … , 0 ) = F ⁡ ( 𝐱 ) F_{\mathbf{x}}(0,\ldots,0)=F(\mathbf{x}) . By subsuming 𝐱 \mathbf{x} into F F , we mean that we use F 𝐱 F_{\mathbf{x}} instead of F F

Cited in the paper.

More specifically, since we quantum-enhance the algorithm of [ 10 ] , our approach circumvents a threshold phenomenon relative to this algorithm. Since the algorithm of [ 10 ] is referred to as a de-randomization of the algorithm of Schöning, with matching run-time, we for simplicity talk about avoiding the threshold relative to the algorithm of Schöning itself

Cited in the paper.