1 Introduction↩︎

Streaming algorithms provide a framework for processing massive datasets, especially in settings where the input is too large to be stored in memory [1], [2]. In this model, data elements arrive sequentially, and the algorithm must process each element as it appears while using only limited working space. Because of their space efficiency, streaming algorithms have found many applications, including the computation of statistics over data streams [3], [4] and the estimation of parameters of massive graphs [5], [6].

Quantum computing offers the possibility of large resource advantages over classical systems. The main focus has traditionally been time complexity [7], for example, Shor’s algorithm for integer factorization [8] gives an exponential speedup over the best-known classical algorithms. However, proving unconditional exponential time separations from all classical algorithms remains a major challenge [9], [10]. Space is another crucial resource, especially in the quantum setting, where fault-tolerant qubits are scarce and costly [11], [12]. Quantum streaming algorithms provide a natural framework for studying space-efficient quantum computation and for seeking quantum advantages in space usage [13]–[15].

Provable exponential space advantages for quantum streaming algorithms were first obtained in the seminal work of Gavinsky, Kempe, Kerenidis, Raz, and de Wolf [16]. Their problem is designed for this separation, and leaves open whether such advantages could be obtained for natural problems of independent classical interest. Several natural candidates such as \(\mathrm{Dyck}(2)\) language [14], [17] and triangle counting [15] were subsequently studied. Kallaugher, Parekh, and Voronova achieved the first exponential quantum space advantage for a natural streaming problem [18]. They gave a polylogarithmic-space quantum streaming algorithm that achieves a \(0.4844\)-approximation for Max-DiCut. In contrast, previous work of Chou, Golovnev, and Velusamy [19] implies that any classical streaming algorithm achieving an approximation ratio better than \(4/9 \approx 0.444\) requires \(\Omega(\sqrt n)\) space.

Since Max-DiCut is only one particular Max-CSP, it naturally raises a broader question about the scope of quantum space advantages for streaming CSPs.

Which constraint satisfaction problems (CSPs) admit an exponential quantum space advantage in the streaming model?

In this paper, we prove an exponential quantum space advantage for Max-\(k\)SAT in the streaming setting. Max-\(k\)SAT is one of the most standard and widely studied Max-CSPs, where each constraint is a disjunction of at most \(k\) literals. Our result also completes the classification of quantum space advantages for Boolean Max-2CSPs when combined with prior work.

1.1 Our contributions↩︎

Our main contribution is a polylogarithmic-space one-pass quantum streaming algorithm for Max-\(k\)SAT with approximation ratio \(0.7172\).

In contrast, prior work by [19] implies that achieving an approximation ratio better than \(\sqrt{2}/2 \approx 0.7071\) for Max-\(k\)SAT requires \(\Omega(\sqrt{n})\) space for any classical streaming algorithm.

To better understand our result, we classify \(2\)-variable Boolean predicates \(f \colon \{0,1\}^2 \to \{0,1\}\) into four standard types based on their truth tables: TR (depends on \(\le 1\) input), OR (exactly one zero), XOR (depends on both inputs; exactly two zeros), and AND (exactly three zeros). For any \(\Lambda \in \{\mathrm{OR}, \mathrm{XOR}, \mathrm{AND}\}\), the Max-2CSP problem is denoted \(\text{Max-2E}\Lambda\) if its allowed predicate set \(\mathcal{F}\) contains only \(\Lambda\)-type predicates (exact arity two), and \(\text{Max-2}\Lambda\) if \(\mathcal{F}\) also includes TR-type predicates. Identifying a predicate family with its contained types, every Boolean Max-2CSP is thus uniquely specified by a subset \(\mathcal{F} \subseteq \{\mathrm{TR}, \mathrm{OR}, \mathrm{XOR}, \mathrm{AND}\}\).

Theorem 1 also gives a quantum streaming algorithm for Max-\(2\)OR, since Max-\(2\)OR is equivalent to Max-\(2\)SAT. We also optimize the approximation ratio for Max-\(2\)OR. The proof is deferred to Appendix 9.

Combining Corollary 1 with the known results [19], [20] gives a complete classification of quantum space advantages for Boolean Max-2CSPs, summarized in Table 1. Previous work had already settled several cases.

• For pure OR-type constraints (Max-2EOR) and XOR-type constraints (Max-Cut), quantum streaming algorithms satisfy the same space lower bounds as classical algorithms [20], and hence give no quantum space advantage.

• For AND-type constraints (Max-DiCut), Kallaugher, Parekh, and Voronova give a polylogarithmic-space quantum streaming algorithm achieving a \(0.4844\)-approximation [18], whereas the classical lower bound of Chou, Golovnev, and Velusamy rules out any ratio better than \(4/9\) in \(o(\sqrt n)\) space [19].

Thus, only the TR+OR case, corresponding to Max-\(2\)OR / Max-\(2\)SAT, remained open. Our result closes this gap by showing that this problem also has a quantum space advantage in the streaming setting.

To complement our results, we also prove a quantum streaming lower bound for Max-\(k\)SAT. This is achieved via a simple reduction from Max-Cut, leveraging its known quantum streaming space lower bound [20]. The proof is deferred to Appendix 7.

Theorem 2 also holds for Exact Max-\(k\)SAT. As a byproduct, it separates Max-\(k\)SAT from Exact Max-\(k\)SAT in terms of quantum space advantage.

1.2 Related work↩︎

1.2.0.1 Classical streaming bounds for Max-\(k\)SAT

The streaming approximability of CSPs has been studied for more than a decade; see the surveys and expository articles [21]–[23]. Chou, Golovnev, and Velusamy [19] established a tight space complexity threshold for Max-\(k\)SAT around the approximation ratio of \(\sqrt{2}/2 \approx 0.707\). Specifically, they demonstrated that a \((\sqrt{2}/2 - \varepsilon)\)-approximation streaming algorithm for Max-\(k\)SAT can be achieved using only \(O(\varepsilon^{-2} \log n)\) space. On the negative side, they proved a matching lower bound: for any \(k \ge 2\) and \(\varepsilon > 0\), any streaming algorithm achieving a strictly better approximation ratio of \((\sqrt{2}/2 + \varepsilon)\) for Max-\(k\)-SAT requires \(\Omega(\sqrt{n})\) space.

1.2.0.2 Quantum streaming algorithms for Max-CSPs

Quantum streaming algorithms for CSP-type problems were previously studied by Kallaugher and Parekh [20], who showed any quantum streaming algorithms need \(\Omega(n)\) space to beat the trivial \(1/2\) approximation for Max-Cut problem. In contrast, Kallaugher, Parekh, and Voronova recently proved an exponential quantum space advantage for Max-DiCut [18]: they gave a polylogarithmic-space quantum streaming algorithm with approximation ratio \(0.4844\), while the classical lower bound of [19] rules out any ratio better than \(4/9\approx 0.4444\) in \(o(\sqrt n)\) space.

1.3 Technical overview↩︎

Our proof extends the snapshot-to-pseudosnapshot framework of Kallaugher, Parekh, and Voronova [18] from Max-DiCut to Max-\(k\)SAT. At a high level, we first reduce Max-\(k\)SAT to estimating a weighted snapshot, then replace this final-stream object by a one-pass pseudosnapshot, and finally estimate the pseudosnapshot using quantum sketches.

1.3.0.1 Step 1: From Max-\(k\)SAT to a weighted snapshot.

The first step is to reduce Max-\(k\)SAT to estimating a weighted snapshot. The snapshot is designed for a fixed oblivious rounding rule: each variable is placed into a bucket according to its weighted signed bias, and the rounding probability of each literal is then determined only by this bucket and the literal sign.

Snapshot-based estimation was introduced for Max-DiCut by Saxena, Singer, Sudan, and Velusamy [24], who asked whether the approach can be extended beyond Max-DiCut. We answer this question for Max-\(k\)SAT. Interestingly, combining our approach with the streaming algorithm of [24] also yields a \(0.7425\)-approximation classical streaming algorithm for Max-2SAT in \(\tilde{O}(\sqrt{n})\) space, thereby resolving an open problem from [19]. Since this paper focuses on quantum advantage, we omit the details of this classical variant.

An edge in Max-DiCut has only two ordered endpoints, whereas a SAT clause is characterized by both its length and the signs of its literals. We therefore defined a weighted snapshot. For each variable, we compute a weighted signed bias from its occurrences in clauses with length at most three; the weights make endpoints in shorter clauses count more. Each endpoint is then assigned a sign-bucket pair, consisting of its literal sign and the bias bucket of its variable, and the weighted snapshot \(\operatorname{WSnap}(\Phi)\) records the resulting histograms over these pairs.

The goal of this step is to construct a linear score \(L_{\le k}(\operatorname{WSnap}(\Phi))\) such that \[\rho\,\operatorname{OPT}(\Phi)\le L_{\le k}(\operatorname{WSnap}(\Phi))\le \operatorname{OPT}(\Phi).\]

Compared with [18], the main barrier is that in Max-\(k\)SAT, clauses have different lengths. As the number of endpoints processed simultaneously increases, the operations and analysis associated with quantum algorithms become extremely complex and intractable. In order to bypass this technical barrier, we handle clauses of length at least four separately. Under the certified rounding rule, every such clause is satisfied with probability at least the target ratio \(\rho\). Thus these long clauses get the fixed contribution \(\rho m_{\ge 4}\), and all nontrivial snapshot work is only for clauses of length at most three. In other words, \[L_{\le k}(\operatorname{WSnap}(\Phi)) = L_{\le 3}(\mathrm{WSnap}(\Phi_{\le 3})) + \rho m_{\ge 4}.\]

The main difficulty inside \(L_{\le 3}(\mathrm{WSnap}(\Phi_{\le 3}))\) is the ternary case. The exact satisfaction probability of a ternary clause depends on three endpoints at once, but directly querying three endpoints would still make the quantum bookkeeping hard to control ³. We therefore replace the exact ternary score by a pairwise-decomposable surrogate, namely a linear combination of one-endpoint and two-endpoint quantities. The unary and binary scores are kept as their exact independent-rounding satisfaction probabilities.

We certify that this surrogate is still good enough: the resulting short-clause score \(L_{\le 3}(\operatorname{WSnap}(\Phi))\) achieves ratio \(\rho = 0.717275\). This is done by solving a finite linear program and verifying the resulting rational certificate exactly over \(\mathbb{Q}\).

1.3.0.2 Step 2: The weighted snapshot and pseudosnapshot are close.

The weighted snapshot uses final variable biases, which are only known after the stream ends. As in [18], we replace it by a weighted pseudosnapshot, whose endpoint sign-bucket pairs are assigned when a clause arrives so that the it can be estimated in one pass.

The idea is to use prefix information at the time of arrival together with exact suffix information: the sketch encodes the prefix before the query, and once a query selects a endpoint, the remaining suffix counts can be computed exactly.

For Max-\(k\)SAT, the data being tracked are different from Max-DiCut. We must track tagged total degrees and tagged positive counts, instead of only directed degree and out-degree quantities, and the same sign-bucket assignment rule must handle unary, binary, and ternary clauses. Our modification is to duplicate each endpoint from a short clause into multiple copies, called tagged units. If the clause length is \(\ell\), the endpoint creates \(w_\ell\) copies; this multiplicity records the clause length. Each copy also carries a positive/negative tag, recording the literal sign. Thus every variable has a tagged total degree and a tagged positive count, which play the role of the degree and out-degree quantities in [18]. We then use the same high-degree/low-degree split: On high-degree scales, the prefix total degree is rounded to the lower end of its scale, and the positive prefix count is sampled randomly. On low-degree scales, both prefix quantities are kept exactly.

To compare these arrival-time sign-bucket pairs with a fixed bucket assignment, we add smoothing noise to the final biases and prove that the pseudosnapshot is \(O(\varepsilon m)\)-close to the fixed-label snapshot in \(\ell_1\) distance. The fixed bucket assignment obtained this way may not satisfy the original bucket constraints exactly; they are only \(\varepsilon\)-admissible. We therefore prove a robust version of the finite certificate, which tolerates these approximate labels and loses only \(O(\varepsilon m)\) in the snapshot score.

1.3.0.3 Step 3: Quantum estimation of the pseudosnapshot.

The third step is to estimate the weighted pseudosnapshot in one pass. Kallaugher, Parekh, and Voronova [18] estimate the Max-DiCut pseudosnapshot by running a hidden-matching-style sketch separately for each pair of head/tail degree ranges. Their sketch maintains four degree-test families of basis states, corresponding to lower and upper degree tests for the head endpoint and lower and upper degree tests for the tail endpoint; sampled out-degree information is encoded in separated counter blocks. Edge updates are implemented by swaps. After each edge measurement, a cleanup measurement handles boundary basis states so that the state keeps the invariant needed for the lower/upper inclusion-exclusion over the queried degree ranges.

We follow the same high-level idea, but use a different quantum implementation. For the current clause, our sketch tests either one endpoint or a pair of endpoints. Each test asks whether certain threshold basis states are present in the current superposition. The updates are elementary shifts along threshold-state chains, and the measurements are only single-threshold or pair-threshold queries. Thus the coordinates of the weighted pseudosnapshot are estimated by the same basic operation: test whether the relevant threshold basis states are present when the clause arrives.

For each tested endpoint, the sketch needs two prefix numbers of the underlying variable: the tagged total prefix degree \(d\) and a positive prefix count \(c\). On high-degree scales, \(c\) is the sampled positive prefix count; on low-degree scales, it is the exact positive prefix count. To implement the update by shifts, we encode these two numbers into one counter \[\Gamma(d,c) = d + B c,\] where the multiplier \(B\) is chosen randomly for the current degree range. The price of this simple encoding is impersonation. An endpoint whose true prefix degree is outside the queried scale may still land on a queried level of \(\Gamma\) and be counted by mistake. The random choice of \(B\) makes these accidental hits rare. We charge impersonation and show that its total contribution is \(O(\varepsilon m)\). This avoids the separate cleanup measurement used in [18].

Combining the first three steps gives a constant-success one-pass quantum algorithm for Max-\(k\)SAT. Finally, we amplify over independent public seeds and take a median, obtaining success probability \(1-\delta\) while keeping polylogarithmic space.

2 Preliminaries↩︎

As a well-known specific example, the Max-\(k\)SAT problem is a special case of Max-CSP where a constraint is a clause, and a clause in \(\Phi\) is a disjunction (OR) of at most \(k\) literals (where a literal is either a variable \(x_i\) or its negation \(\neg x_i\)).

2.0.0.1 Quantum streaming for Max-CSP

In this paper, we consider the Max-CSP(\(\Pi\)) problem processed by a one-pass quantum streaming algorithm. The algorithm has sequential access to an input instance \(\Phi\), which it processes left-to-right using a limited quantum workspace.

First, the algorithm receives the number of variables \(n\) and the stream length \(m\) (equivalently, any constant-factor upper bound on \(m\)). It then initializes a quantum work register \(W\) consisting of \(s(n)\) qubits to a fixed state \(\rho_0\), typically \(\rho_0=\ket{0^{s(n)}}\bra{0^{s(n)}}\).

The algorithm receives the constraints \(C_1, \ldots, C_m\) in \(\Phi\) one by one (in a possibly adversarial order). Let \(\Sigma\) be the set of all possible constraints on \(n\) variables. For each constraint \(\sigma \in \Sigma\), the algorithm possesses a corresponding quantum channel \(\mathcal{A}_\sigma\) acting on \(W\). As the stream is processed, the state of the work register evolves as: \[\rho_i = \mathcal{A}_{C_i}(\rho_{i-1}), \qquad i=1,2,\ldots,m.\]

After the last update, the algorithm measures the work register \(W\). Based on the measurement outcome, it outputs a value \(Z\).

Throughout this framework, the space complexity of the algorithm is the number of qubits \(s(n)\) stored in the work register between two consecutive constraint stream updates, where \(s\) is typically a small function of \(n\). We place no restriction on the running time or computational complexity of the quantum update channels. We also allow the algorithm read-only access to public random bits, and these random bits are not stored in the work register and are not charged to the streaming space.

3 Reducing Max-\(k\)SAT to weighted snapshot estimation↩︎

In this section, we reduce Max-\(k\)SAT to the problem of estimating a weighted snapshot. The snapshot is designed to support a fixed oblivious rounding rule: each variable is first assigned a type according to its signed bias, and the rounding probability of each literal is then determined only by this type and by the literal sign.

We first simplify clauses. First, we can delete the repeated literals. Clauses that contain both a literal and its negation are always satisfied, so they are removed from the stream and accounted for by an exact offset maintained separately. For the remaining simplified instance \(\Phi\), let \[\Phi_{\le3}:=\{C\in\Phi: |C|\in\{1,2,3\}\}, \qquad \Phi_{\ge4}:=\{C\in\Phi: |C|\ge4\}, \qquad m_{\ge4}:=|\Phi_{\ge4}|.\] Only the short-clause subinstance \(\Phi_{\le3}\) is used to define these variable types and the snapshot score. Clauses in \(\Phi_{\ge4}\) do not enter the snapshot; since they have at least four literals, they are handled separately by a deterministic floor \(\rho \cdot m_{\ge4}\), where \(\rho\) is a constant determined later.

Before defining the "snapshot" of instances, we first define the bias of the variables in \(\Phi_{\le3}\).

Note that \(b_v\in [-1,1]\). The optimized weights \((4,2,1)\) determine how strongly unary, binary, and ternary endpoints contribute to the signed type of a variable.

The next definition turns these signed types into a rounding rule.

Once \([-1,1]\) is partitioned into buckets, a variable \(v\) with \(b_v\in I_i\) is rounded to true with probability \(r_i\). Thus, a positive literal is satisfied with probability \(r_i\), while a negative literal is satisfied with probability \(1-r_i\). The snapshot will only remember the literal sign and the bucket index, not the exact value of \(b_v\).

After the rounding probabilities are fixed, every endpoint of a short clause has a constant-size label \(\alpha=(s, i)\): the literal sign \(s\), together with the bucket \(i\) of its variable. The snapshot below records only the histograms of these labels that will be needed. We only keep one-endpoint and two-endpoint projections, because these are the statistics that the quantum estimator can handle.

The true satisfaction probability of a ternary clause, \(1-\prod_{j=1}^3(1-q_{\alpha_j})\), is a three-variable function. If we used it directly, the snapshot would have to store a full three-dimensional histogram of ternary endpoint labels. To avoid using ternary endpoint labels, we define a pairwise-decomposable score \(H\) that relies only on a one-endpoint function, \[c_0\in\mathbb{Q},\qquad u_j:\{+,-\}\times\{0,\ldots,L-1\}\to\mathbb{Q} \quad (j=1,2,3)\] and a two-endpoint function, \[p_{jt}:\bigl(\{+,-\}\times\{0,\ldots,L-1\}\bigr)^2\to\mathbb{Q} \quad (1\le j<t\le3).\]

Thus, the total ternary contribution can be written using only \(M_3\), the one-endpoint marginals \(U_{3,j,\alpha}\), and two-endpoint marginals \(P_{3,j,t,\alpha,\beta}\).

We can now assign a numerical value to a weighted snapshot.

The first line scores unary and binary clauses by their exact independent-rounding satisfaction probabilities. The second line scores ternary clauses using the pairwise-decomposable function \(H\), expanded in terms of the coordinates stored in \(\operatorname{WSnap}(\Phi_{\le 3})\).

4 Closeness of the Weighted Snapshot and Pseudosnapshot↩︎

In section 3, the Max-\(k\)-SAT value was reduced to the weighted snapshot score \(L_{\le3}\) together with the deterministic long-clause term \(\rho \cdot m_{\ge4}\). The obstacle is that the true short snapshot \(\operatorname{WSnap}\) depends on final variable biases, which are not available during the stream.

To obtain a one-pass streaming algorithm, we replace the weighted snapshot by a weighted pseudosnapshot that can be estimated in the streaming setting. Throughout this subsection, we fix the optimized tuple \(\Theta^*\) and the ratio \(\rho\) from Lemma 1 and Lemma 2. We suppress the superscript \(\Theta^*\) from \(L_{\le3}\).

We define the degree of a variable \(v_j (C)\) as the total number of occurrences of its associated tagged units. We then partition the degree range into the following scales. Fix \(\varepsilon\in(0,1/100)\), and define geometric scales for \[D_0:=0,\qquad D_a:=\lfloor(1+\varepsilon^3)^a\rfloor \quad (a=1,\ldots,A),\] where \(A\) is the smallest interger that satisfies \(D_A\ge 4m\). In particular \(A=O_{\varepsilon}(\log m)\). When a positive tagged unit arrives in the streaming, our algorithm employs a hash function to probabilistically decide whether it should be counted. This selective counting strategy is designed to save memory space.

When \(2D_a<\kappa\), the cost of counting the exact degree is cheap, so no hash function is needed for these scales. Let \(g: V\to[-\varepsilon,\varepsilon]\) be independent uniform smoothing noise. We define the weighted pseudobias as follows.

We now use these arrival-time pseudobiases to assign the same sign-bucket labels that were used in the weighted snapshot, but separately for each endpoint at the moment its clause arrives.

Thus \(\operatorname{WPsSnap}(\Phi_{\le3})\) has the same coordinate set as \(\operatorname{WSnap}(\Phi_{\le3})\), but endpoint labels are assigned using the arrival-time pseudobias \(\widetilde{b}_v^{\,C}\) rather than the final bias \(b_v\).

The pseudosnapshot still uses labels that may vary with the arrival time of a clause. For the analysis, it is useful to compare it with a simpler object in which every variable has one fixed label throughout the whole stream. We obtain this fixed label by applying the same smoothing noise to the final bias \(b_v\).

Next, we show that with high probability over the public randomness, the pseudosnapshot is close to a fixed-label snapshot. The fixed labels need not be the true final buckets, but they are close enough: if a variable is labeled by bucket \(I_i\), then its true bias lies within an \(\varepsilon\)-neighborhood of \(I_i\).

Lemma 3 reduces the analysis of the pseudosnapshot to the analysis of a fixed-label snapshot whose labels are only approximately feasible. We therefore need a robust version of the finite certificate from Lemma 1: the certificate should still give a good lower bound when the bucket constraints hold with a small additive slack.

We now combine the two ingredients. Lemma 3 shows that \(\operatorname{WPsSnap}(\Phi_{\le3})\) is close to \(\operatorname{WSnap}_\beta(\Phi_{\le3})\) for an \(\varepsilon\)-admissible label map \(\beta\). Lemma 4 then applies to this fixed-label snapshot and loses only \(O(\varepsilon m)\). Since \(L_{\le3}\) is a fixed linear functional, the \(L_1\)-closeness of the two snapshots changes the score by only \(O(\varepsilon m)\). Adding the deterministic long-clause term \(\rho m_{\ge4}\) gives the approximate value guarantee below.

5 Quantum algorithm for weighted pseudosnapshot estimation↩︎

In this section, we give a quantum streaming algorithm for the pseudosnapshot.

Throughout this section, we use the tagged units from Definition 7, the public hash functions \(f_a\) from Definition 8, the weighted pseudobias notation from Definition 9, and the buckets from Definition 3. We take \(A\) to be the smallest index with \(D_A\ge4m\). Hence every \(D_{a}=O_\varepsilon(m)\) and \(A=O_{\varepsilon}(\log m)\). Empty scales with \(D_a=D_{a+1}\) are ignored. We also choose \(\kappa\) to be a sufficiently large positive integer.

For a clause \(C\) and \(j\in\{1,\ldots,|C|\}\), let \(v_j(C)\) be the variable of the \(j\)-th literal. The endpoint \(v_j(C)\) has a sign \(s\in\{+,-\}\), and the pseudobias \(\widetilde{b}_{v_j(C)}\). \(\widetilde{b}_{v_j(C)}\) can be computed at the arrival of \(C\). It lies in a bucket among \([-1,1]\), which is indexed by \(i\in\{0,\ldots,L-1\}\). Let \[\lambda_j(C) := (s,i) \in\{+,-\}\times\{0,\ldots,L-1\}\] denote the sign-bucket pair. All clauses considered in this section are short clauses, with \(\ell:=|C|\le 3\). Each endpoint of an \(\ell\)-clause generates \(w_\ell\) tagged units on the same variable, where \(w_1=4\), \(w_2=2\), and \(w_3=1\). A tagged unit is positive if the corresponding literal is positive.

For later reference, define the true scale of the endpoint \((C,r)\) by \[a(C,r) := \min\left\{ s:\;s\text{ is nonempty and } D_s<d_{v_r(C)}^{\le C}\le D_{s+1} \right\}.\] Thus \(a(C,r)\) is the scale that the \(r\)-th endpoint of \(C\) actually belongs to, according to its prefix total degree at the arrival of \(C\).

We will use a scale refinement of the coordinates of \(\operatorname{WPsSnap}(\Phi_{\le3})\) as follows. Each original one-endpoint or two-endpoint coordinate is split according to the scale of the relevant prefix total degree. For each original coordinate, the sum of its scale-refined coordinates over all relevant scales is exactly the corresponding coordinate of \(\operatorname{WPsSnap}(\Phi_{\le3})\). Moreover, we partition clauses by scales \((D_a,D_{a+1}]\). For the indices \(a,b\in\{0,\ldots,A-1\}\) where \(A=O_{\varepsilon}(\log m )\), and the sign-bucket pairs \(\alpha,\beta\in\{+,-\}\times\{0,\ldots,L-1\}\), define \[\begin{align} U_{1,1,\alpha}^{(a)} &:=\#\Bigl\{C\in\Phi_{\le3}: \substack{|C|=1, D_a<d_{v_1(C)}^{\le C}\le D_{a+1},\; \lambda_1(C)=\alpha}\Bigr\},\\ P_{2,1,2,\alpha,\beta}^{(a,b)} &:=\#\Bigl\{C\in\Phi_{\le3}: \substack{|C|=2, D_a<d_{v_1(C)}^{\le C}\le D_{a+1}, D_b<d_{v_2(C)}^{\le C}\le D_{b+1}, (\lambda_1(C),\lambda_2(C))=(\alpha,\beta)}\Bigr\},\\ U_{3,j,\alpha}^{(a)} &:=\#\Bigl\{C\in\Phi_{\le3}: \substack{|C|=3, D_a<d_{v_j(C)}^{\le C}\le D_{a+1}, \lambda_j(C)=\alpha}\Bigr\},\\ P_{3,j,t,\alpha,\beta}^{(a,b)} &:=\#\Bigl\{C\in\Phi_{\le3}: \substack{|C|=3, D_a<d_{v_j(C)}^{\le C}\le D_{a+1}, D_b<d_{v_t(C)}^{\le C}\le D_{b+1}, (\lambda_j(C),\lambda_t(C))=(\alpha,\beta)}\Bigr\}. \end{align}\]

With this scale refinement, the weighted pseudosnapshot score admits the decomposition \[\label{eq:maxksat-pseudosnap-score-decomp} \begin{align} L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) &= \sum_a\sum_{\alpha} q_\alpha U_{1,1,\alpha}^{(a)} +\sum_{a,b}\sum_{\alpha,\beta} \bigl(1-(1-q_\alpha)(1-q_\beta)\bigr) \cdot P_{2,1,2,\alpha,\beta}^{(a,b)}\\ & +c_0M_3 +\sum_{j=1}^3\sum_a\sum_{\alpha}u_j(\alpha)U_{3,j,\alpha}^{(a)} +\sum_{1\le j<t\le3}\sum_{a,b}\sum_{\alpha,\beta} p_{jt}(\alpha,\beta) \cdot P_{3,j,t,\alpha,\beta}^{(a,b)}. \end{align}\tag{4}\]

The coefficients \(q_\alpha,q_\beta,c_0,u_j(\alpha)\), and \(p_{jt}(\alpha,\beta)\) are fixed constants from Lemma 1. The term \(M_3\) is the number of length-\(3\) clauses, and it can be counted exactly with \(O(\log m)\) classical bits.

It remains to estimate the four kinds of scale-refined coordinates above. We call \(U_{1,1,\alpha}^{(a)}\) and \(U_{3,j,\alpha}^{(a)}\) one-endpoint coordinates, because they test one endpoint of a clause. We call \(P_{2,1,2,\alpha,\beta}^{(a,b)}\) and \(P_{3,j,t,\alpha,\beta}^{(a,b)}\) two-endpoint coordinates. For each coordinate, we run a quantum sketch algorithm, described in Sections 5.2 and 5.3. The sketches are combined to form the target quantum algorithm, and we prove Lemma 6 in Section 5.4. We first record the quantum-register notation used by all sketches.

5.1 Quantum register↩︎

We use a label \(S\) to denote the corresponding basis state \(\ket{S}\). For convenience, we do not distinguish between them unless necessary. Let \(U\) be the set of all labels. If a basis state has a nonzero amplitude, we call it live. Let \(T\subseteq U\) be the set of live non-anchor labels. We write \[\ket{Q(T)} := \frac{\ket{\bot}+\sum_{x\in T}|x\rangle\,}{\sqrt{1+|T|}}.\] Here \(\ket{\bot}\) is a fixed anchor basis state. It is never measured; it is included only so that after every failed measurement, the post-measurement state is still valid, including the case \(T=\emptyset\). In all sketches below, we will use the quantum register with size \[M:=\lceil C_{\varepsilon} m \rceil,\]where \(C_{\varepsilon}\) is a large enough constant.

We mainly use the following three quantum operations in our algorithm.

• Permutation. For a permutation \(\pi\) of \(U\), apply the unitary that fixes \(\ket{\bot}\) and sends \(\ket{x}\) to \(\ket{\pi(x)}\).

• Single-query. For \(x\in U\), measure \(\ket{Q(T)}\) with \(\{\ket{x}\!\bra{x},I-\ket{x}\!\bra{x}\}\).

  For \(x\in T\): if we get \(\ket{x}\), output \(1\), and the quantum state collapses. Otherwise, output 0 and the new state becomes \(\ket{Q(T\setminus\{x\})}\);

  For \(x\notin T\): it outputs 0, and the state is unchanged.

• Pair-query. For distinct \(x,y\in U\), measure \(\ket{Q(T)}\) with \[\ket{\psi^+_{x,y}}:=\frac{\ket{x}+\ket{y}}{\sqrt2}, \qquad \ket{\psi^-_{x,y}}:=\frac{\ket{x}-\ket{y}}{\sqrt2},\] and their orthogonal complement. The query outputs \(1\) on outcome \(\ket{\psi^+_{x,y}}\), outputs \(-1\) on outcome \(\ket{\psi^-_{x,y}}\), and outputs \(0\) on the orthogonal-complement outcome. The state update and probabilities are:

  1. If both \(x\) and \(y\) belong to \(T\), then \[\Pr[+1]=\frac{2}{1+|T|}, \qquad \Pr[-1]=0.\] If we get the orthogonal complement, the new state becomes \(\ket{Q(T\setminus \{x,y\})}\).

  2. If exactly one of them, say \(z\), belongs to \(T\), then \[\Pr[+1]=\Pr[-1]=\frac{1}{2(1+|T|)}.\] If the outcome is the orthogonal complement, the new state is \(\ket{Q(T\setminus\{z\})}\).

  3. If neither belongs to \(T\), the state is unchanged.

5.1.0.1 Formulas of single/pair-query.

The single-query and pair-query operations satisfy the following expectation formulas. If the state before the query is \(\left|Q(T)\right\rangle\), then:

• if \(x\in U\) and \(\zeta_x\in\{0,1\}\) is the output of the single-query, then \[\mathbb{E}[\zeta_x\mid \left|Q(T)\right\rangle] = \frac{1}{|T|+1}\,\mathbf{1}[x\in T];\]

• if \(x,y\in U\) and \(\chi_{x,y}\in\{-1,0,+1\}\) is the output of the pair-query, then \[\mathbb{E}[\chi_{x,y}\mid \left|Q(T)\right\rangle] = \frac{2}{|T|+1}\,\mathbf{1}[x\in T]\,\mathbf{1}[y\in T].\]

5.2 One-endpoint estimation↩︎

Fix a one-endpoint coordinate \(U^{(a)}_{\ell,j,\alpha}\), where \(\alpha = (s_\alpha, i_\alpha)\) denotes a sign-bucket pair. Recall that when \(D_a\ge\kappa/2\), we call \(U^{(a)}_{\ell,j,\alpha}\) high-degree. Otherwise, so \(D_a<\kappa/2\), call it low-degree. We handle these two cases with slightly different strategies in Section 5.2.1 and Section 5.2.2, respectively.

The rough idea is to sample a clause during the stream with low probability. If a sampled clause belongs to \(U^{(a)}_{\ell,j,\alpha}\), the output is scaled by \(M\) or \(M/2\) to cancel the low probability; otherwise it outputs \(0\).

Thus, to test if the clause belongs to \(U^{(a)}_{\ell,j,\alpha}\), we should check all the relative constraints on the scale \(a\), clause length \(\ell\), endpoint position \(j\), literal sign \(s_\alpha\) and bucket index \(i_{\alpha}\). Indeed, the clause length, endpoint position, and literal sign are known when the clause arrives. The scale test is handled by quantum labels that track prefix degree. The bucket test is evaluated only after a successful query, using the queried candidate prefix value and the exact suffix counts.

Moreover, for the scale and bucket tests, the sketch needs the prefix total degree \(d\) and the prefix positive count \(c\). To implement the updates by simple shifts, we store these two counts through the single threshold value \(\Gamma_a(d,c)=d+B_ac\). A different pair \((d',c')\) can sometimes reach the same queried threshold, especially when the endpoint is outside the queried scale. These accidental threshold crossings are the only extra counts considered below. We define the degree condition under which they can occur and record the properties needed later.

5.2.0.1 Random-base threshold encoding.

Fix a sufficiently large constant \(K_{\mathrm{base}}:=K_{\mathrm{base}}(\varepsilon)\). For every nonempty scale \(a\), choose an independent public-random integer \(B_a\) uniformly from \[\Bigl\{\lceil K_{\mathrm{base}}D_{a+1}\rceil,\, \lceil K_{\mathrm{base}}D_{a+1}\rceil+1,\, \ldots,\, \lceil 2K_{\mathrm{base}}D_{a+1}\rceil\Bigr\}.\] In particular, after enlarging \(K_{\mathrm{base}}\) if needed, we have \(B_a>D_{a+1}+1\) for every scale \(a\). For a prefix positive count \(c\), define \[\Gamma_a(d,c):=d+B_a c.\] In a high-degree sketch, \(c\) is the sampled positive-prefix count \(s_v^{\le C}\), while in a low-degree sketch, \(c\) is the exact positive-prefix count \(p_v^{\le C}\).

For every \(q\in\{0,\ldots,\kappa-1\}\) and every in-range degree \(D_a<d\le D_{a+1}\), \[\label{eq:one-endpoint-ordinary-high-id} \mathbf{1}[\Gamma_a(d,c)\ge B_a q+D_a+1] -\mathbf{1}[\Gamma_a(d,c)\ge B_a q+D_{a+1}+1] = \mathbf{1}[c=q].\tag{5}\] Likewise, for every \(D_a<d,d_0\le D_{a+1}\) and every \(c_0\ge0\), \[\label{eq:one-endpoint-ordinary-low-id} \mathbf{1}[\Gamma_a(d,c)\ge B_a c_0+d_0] -\mathbf{1}[\Gamma_a(d,c)\ge B_a c_0 +d_0+1] = \mathbf{1}[d=d_0,\;c=c_0].\tag{6}\] These are the only identities needed on genuine scale-\(a\) endpoints. For the high-degree one-endpoint coordinate output, we will also use the cumulative form: for every \(q\ge1\), every integer \(c\ge0\), and every \(D_a<d\le D_{a+1}\), \[\label{eq:one-endpoint-cumulative-high-id} \mathbf{1}[\Gamma_a(d,c)\ge qB_a]=\mathbf{1}[c\ge q].\tag{7}\] This follows from \(B_a>D_{a+1}\).

For later use, set the largest multiplier of \(B_a\) that can appear in the false-scale condition \[H_a:= \begin{cases} \kappa, & D_a\ge \kappa/2,\\ D_{a+1}, & D_a< \kappa/2. \end{cases}\]

5.2.0.2 Impersonation.

We say that an endpoint with prefix degree \(d\) impersonates scale \(a\) if \(d>D_{a+1}\) and \[\label{eq:scale-a-impersonation-def} d\in \bigcup_{h=1}^{H_a} \bigl[hB_a+D_a+1,\;hB_a+D_{a+1}\bigr].\tag{8}\]

To make the subsequent formulas more concise, let \(\mathsf{Imp}^{a}_{C,r}\) be the event that endpoint \((C,r)\) impersonates scale \(a\).

This condition is deliberately broader than the event that the endpoint actually gives a nonzero contribution to the wrong queried scale. Every such nonzero contribution from outside the queried scale satisfies this condition, but some endpoints satisfying it may still contribute zero because their positive-prefix count does not put the encoded value \(d+B_a c\) at the queried level.

Thus, in a low-degree single-level query, every nonzero contribution from outside the queried scale is counted by the impersonation condition.

5.2.1 High-degree case↩︎

For each \(q\in\{0,1,\ldots,\kappa\}\), we maintain an independent \(q\)-Sketch. The case \(q=\kappa\) accounts for all endpoints with \(s_v^{\le C}\ge\kappa\) through the capped value \(\min\{s_v^{\le C},\kappa\}\), so high-degree one-endpoint coordinates need no separate overflow term.

Each \(q\)-Sketch consists of two independent sub-sketches, called the Upper-\(q\)-Sketch and the Lower-\(q\)-Sketch. Their outputs are combined to give an estimate for the high-degree coordinate.

We describe the explicit form of the quantum register as follows. There are six kinds of labels/basic states in \(U\). We use the global register size \(M=\lceil C_\varepsilon m\rceil\), with \(C_\varepsilon\) chosen large enough for the fixed \(\varepsilon>0\).

1. The fixed anchor basis state \(\ket{\bot}\);

2. Spare labels: \(S_1,\ldots, S_M\);

3. \(H\)-labels: \(H(v,t)\), where \(v\in [n]\), \(t\in [M]\);

4. \(E\)-labels: \(E(v,t)\), where \(v\in [n]\), \(t\in [M]\);

5. \(H\)-garbage-labels: \(G_{H}(v,t)\),where \(v\in [n]\), \(t\in [M]\);

6. \(E\)-garbage-labels: \(G_{E}(v,t)\),where \(v\in [n]\), \(t\in [M]\);

Besides, we maintain a pointer \(\mathcal{P}\) for the spare labels via classical register, which costs \(O(\log M)=O(\log m)\) bits. Because the basis state is specified by a variable index and a level in \([M]\), this quantum register costs \(O(\log (nm))=O(\log n )\) qubits, for \(m=\mathrm{poly} (n)\).

5.2.1.1 What the labels are for.

The spare labels are only temporary labels used to make every update a permutation. They are not queried directly.

The \(H\)-labels stores the prefix total degree information. Every time a tagged unit on \(u\) arrives, we increase the \(H(u,\cdot)\) labels, so the queried label \(H(u,t)\) should be thought of as the level \(t\) of the prefix total degree.The queries on \(H\)-labels will tell us whether the prefix degree has already entered the scale \((D_a,D_{a+1}]\).

The \(E\)-labels stores the encoded quantity. Besides the one-step update for every tagged unit, a selected positive tagged unit applies \(B_a\) additional one-step shifts to the \(E\)-labels. So the queried label \(E(u,t)\) should be thought of as recording \[\Gamma_a(d_u^{\le C},s_u^{\le C}) =B_a s_u^{\le C}+d_u^{\le C}.\] The queries on \(E\)-labels will tell us which sampled positive-prefix count is consistent with the current prefix.

The garbage labels do not store any statistic we need. They are only there so that every update is a permutation on a finite set of basis labels.

The concrete implementations differ slightly for the four sub-sketches: Lower-\(q\)-Sketch (\(q\ge 1\)), Upper-\(q\)-Sketch (\(q\ge 1\)), Lower-\(0\)-Sketch and Upper-\(0\)-Sketch. But the overall structure of the algorithm is the same. Therefore, we present the Lower-\(q\)-Sketch (\(q\ge 1\)) in detail, while for other sub-sketches we focus primarily on the aspects that differ. In this subsection, call a clause \(C\) target-shape for the one-endpoint coordinate \(U^{(a)}_{\ell,j,\alpha}\) if \(|C|=\ell\) and the \(j\)-th literal has sign \(s_\alpha\). To make the subsequent formulas more concise, let \(\mathsf{Tgt}^{\ell,j,\alpha}_{C}\) be the event that \(C\) is target-type for \(U^{(a)}_{\ell,j,\alpha}\).

5.2.1.2 Initialization:

The quantum register is initialized as: \[\left|Q(T_0)\right\rangle = \frac{|\perp\rangle+|S_1\rangle+\cdots+|S_{M-1}\rangle}{\sqrt M},\] where the live set \[T_0:=\{S_1,S_2,\dots,S_{M-1}\}.\] Initialize \(\mathcal{P}=1\).

When a clause \(C\) arrives, the quantum algorithm performs two types of operations in turn: update and query.

5.2.1.3 Update.

Decompose the clause \(C\) into tagged units and handle them one by one. Suppose the tagged unit is on variable \(u\) and the live set is \(T\). Perform the following increment operations in turn. Each operation applies a unitary permutation to the quantum register and updates the pointer as specified above.

Step-1. \(\mathrm{inc}(H,u,1).\)

Step-2. \(\mathrm{inc}(E,u,1).\)

Step-3. If this tagged unit is positive and selected by \(f_a\) (See Definition 8 for details), perform \(\mathrm{inc}(E,u,B_a).\)

5.2.1.4 Query.

If the clause \(C\) is not target-shape, do nothing and end. Otherwise denote the \(j\)-th literal by \(v:=v_j(C).\) Perform the pair-query \[(H(v,D_{a}+1), E(v,qB_a ))\] on the current quantum register. Denote the output of pair-query by \(\chi_{C}^{\ell}\in \{-1,0,+1\}\).

Branch 1: if \(\chi_{C}^{\ell} = 0\), we say this query fails. Then do nothing and end.

Branch 2: if \(\chi_{C}^{\ell}\in \{-1,+1\}\), we say this query is successful. Then this quantum register performs no further updates or queries. During the rest of the stream, the sub-sketch only keeps the following classical data:

1. store the variable \(v\) and clause \(C\);

2. store the nonzero measurement outcome \(\chi_C^\ell\);

3. store \(q\);

4. in the following streaming of clauses, count the suffix total degree \(d_{v}^{>C}\) and suffix positive count \(p_{v}^{>C}\) accurately.

The classical part costs \(O(\log (n+m))\) bits. We say a sub-sketch is active if the quantum part has not ended, equivalently, if it has not entered Branch 2 yet.

5.2.1.5 Output.

If a high-degree sub-sketch succeeds on \(C\), then after the rest of the stream has been processed it has the exact suffix counts \(p_v^{>C}\) and \(d_v^{>C}\). For every \(r\in\{0,\ldots,\kappa\}\), define \[F_r(C) := \mathbf{1} \left[ \operatorname{clip}_{[-1,1]} \left( \frac{2\left(\frac{2D_a}{\kappa}r+p_v^{>C}\right)}{D_a+d_v^{>C}} -1+g(v) \right) \in I_{i_\alpha} \right].\] Finally, the Lower-\(q\)-Sketch \((q\ge 1)\) outputs \[L_q(C):=\frac{M}{2}\cdot \chi_{C}^{\ell}\cdot (F_q(C)-F_{q-1}(C)).\] In all other cases, the Lower-\(q\)-Sketch \((q\ge 1)\) outputs \(0\).

Next we describe the other three sub-sketches. Most of the algorithm is the same, so we only describe the parts that differ from the Lower-\(q\)-Sketch \((q\ge1)\).

5.2.1.6 Upper-\(q\)-Sketch (\(q\ge 1\))

In the query step, we perform the pair-query on \[(H(v,D_{a+1}+1), E(v,qB_a ))\] rather than \((H(v,D_{a}+1), E(v,qB_a ))\) for Lower-\(q\)-Sketch.

Similarly, define \(\chi^{u}_{C}\in \{-1,0,1\}\) for the output of the pair-query. In its successful branch, the Upper-\(q\)-Sketch stores the nonzero value of \(\chi_C^u\) together with the same classical data. For Branch \(2\), define the final output as \[U_q(C):=\frac{M}{2}\cdot \chi_{C}^{u}\cdot (F_q(C)-F_{q-1}(C)).\] In all other cases, it outputs \(0\).

5.2.1.7 Lower-\(0\)-Sketch and Upper-\(0\)-Sketch.

For the \(0\) case, the main difference is that the assumed prefix positive count is \(0\). Hence we do not need to maintain this information, and we no longer measure the \(E\)-labels or \(E\)-garbage-labels. The register only needs the \(H\)-labels, and the update step per tagged unit is the single increment \(\mathrm{inc}(H,u,1)\).

In the query step, the Lower-\(0\)-Sketch performs a single-query on \(H(v,D_a+1)\) and the Upper-\(0\)-Sketch performs a single-query on \(H(v,D_{a+1}+1)\).

Define \(\xi_{C}^{\ell}\) and \(\xi_{C}^{u}\) to denote the outputs of the single-query from Lower-\(0\)-Sketch and Upper-\(0\)-Sketch respectively. In a successful branch the sketch stores this nonzero output, which equals \(1\), and the same classical data and suffix counters as above. Define the final outputs as \[L_0(C):=M\cdot \xi_{C}^{\ell}\cdot F_0(C), \qquad U_0(C):=M\cdot \xi_{C}^{u}\cdot F_0(C),\] In all other cases, output \(0\).

5.2.1.8 Correctness.

Fix a one-endpoint sub-sketch and a label \(F(u,t)\) that it may query, where \(F\) could denote \(H\) or \(E\)-labels. We first show that, as long as the pointer has not wrapped around, \(F(u,t)\) is live exactly when \(d_u+Bc_u\ge t\). Lemma 9 will then show that the assumption fails with probability at most \(1/160\).

For this fixed \(F\) and \(u\), the sub-sketch queries only this level \(t\). Just before such a query, let \(d_u\) count the calls \(\operatorname{inc}(F,u,1)\), and let \(c_u\) count the calls \(\operatorname{inc}(F,u,B_a)\). If this family has no such \(\operatorname{inc}(F,u,B_a)\) calls, set \(c_u=0\).

The previous lemma needs two assumptions: the queried level \(t\) is below \(M\), and the total number of elementary shifts in the sub-sketch is below \(M\). The next lemma checks both. The level check is deterministic after \(C_\varepsilon\) is chosen large enough; the shift bound is the part that uses the public randomness. Although the low-degree one-endpoint sketches are described later, we include them in the same statement because they use the same shift operation.

If \(\mathcal{G}_1\) fails, the algorithm still runs legally: the pointer is cyclic, each update is still a permutation of the finite set of labels, and each query is still one of the measurements defined earlier. What may fail is only the simple interpretation of queried labels by prefix counts.

On \(\mathcal{G}_1\), Lemma 8 applies to every label queried by a one-endpoint sketch. Thus, immediately before each query, an \(H\)-label is live exactly when the corresponding prefix degree has reached its queried level, and an \(E\)-label is live exactly when the prefix value encoded by \(\Gamma_a\) has reached its queried level. These are the only facts about the live set used in the estimates below.

5.2.1.9 Estimation and Analysis.

All the following arguments are conditioned on the event \(\mathcal{G}_1\) from Lemma 9.

The lower and upper sketches first isolate the degree range \((D_a,D_{a+1}]\). The \(q\)-sketches then recover the sampled positive-prefix count by a telescoping sum. Thus the proof below has two steps: first isolate the scale, and then use the telescoping sum over \(q\) to evaluate the bucket condition from the sampled positive-prefix count.

Extend the outputs by \(0\) to every clause that is not target-shape. For each clause \(C\), define \[\label{eq:estimation} \widehat U^{(a)}_{\ell,j,\alpha}(C) := L_0(C)-U_0(C)+\sum_{q=1}^{\kappa}\bigl(L_q(C)-U_q(C)\bigr).\tag{9}\] Set \[\widehat U^{(a)}_{\ell,j,\alpha} := \sum_{C\in\Phi_{\le3}}\widehat U^{(a)}_{\ell,j,\alpha}(C).\]

Fix a target-shape clause \(C\) and write \(v:=v_j(C)\). For each \(q\in\{0,1,\ldots,\kappa\}\), let \[F_q(C) := \mathbf{1} \left[ \mathrm{clip}_{[-1,1]}\!\left( \frac{2\left(\frac{2D_a}{\kappa}q+p_v^{>C}\right)}{D_a+d_v^{>C}}-1+g(v) \right)\in I_{i_\alpha} \right].\]

Recall that \(s_v^{\le C}\) denotes the number of positive tagged units on variable \(v\) up to clause \(C\), which are selected by \(f_a\) in Step-3 of the update step. By Definition 9, on the scale \((D_a,D_{a+1}]\) the weighted pseudobias uses \[\widetilde{d}_v^{\le C}=D_a, \qquad \widetilde{p}_v^{\le C} = \frac{2D_a}{\kappa}\min\{s_v^{\le C},\kappa\}.\] Hence \[\mathbf{1}[\lambda_j(C)=\alpha] = F_{\min\{s_v^{\le C},\kappa\}}(C).\] Therefore, \[\label{eq:Fq} \mathbf{1} [\lambda_j(C)=\alpha] = F_0(C)+ \sum_{q=1}^{\kappa} \bigl(F_q(C)-F_{q-1}(C)\bigr)\,\mathbf{1}[s_v^{\le C}\ge q].\tag{10}\]

Recall that a sub-sketch is active if its quantum part has not ended, equivalently, if it has not entered Branch 2 in the query step.

Next, we analyze the levels \(q\in \{1,\ldots,\kappa\}\) and \(q=0\) separately. Recall that \(\mathsf{Tgt}^{\ell,j,\alpha}_{C}\) denotes the event that \(|C|=\ell\) and the \(j\)-th literal of \(C\) has sign \(s_\alpha\), i.e. \(C\) is the target-type for \(U^{(a)}_{\ell,j,\alpha}\).

5.2.1.10 For \(q\in\{1,\ldots,\kappa\}\).

Suppose the live set just before the query on \(C\) has size \(M'-1\).

By definition, \[L_q(C)=\frac{M}{2}\chi_C^{\ell}\bigl(F_q(C)-F_{q-1}(C)\bigr).\] The Lower-\(q\)-Sketch queries the pair \[\bigl(H(v,D_a+1),\,E(v,qB_a)\bigr).\] So the pair-query formula gives \[\mathbb{E}[\chi_C^{\ell}\mid |Q(T)\rangle] = \frac{2}{M'} \mathbf{1}[H(v,D_a+1)\in T]\mathbf{1}[E(v,qB_a)\in T].\] Therefore \[\begin{align} \mathbb{E}[L_q(C)\mid |Q(T)\rangle] &= \frac{M}{M'} \bigl(F_q(C)-F_{q-1}(C)\bigr)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}] \cdot \mathbf{1}[H(v,D_a+1)\in T]\cdot \mathbf{1}[E(v,qB_a)\in T]. \end{align}\] On the event \(\mathcal{G}_1\) from Lemma 9, the queried label \(H(v,D_a+1)\) is live if and only if \[d_v^{\le C}\ge D_a+1,\] and the queried label \(E(v,qB_a)\) is live if and only if \[\Gamma_a(d_v^{\le C},s_v^{\le C})\ge qB_a.\] So \[\begin{align} \mathbb{E}[L_q(C)\mid |Q(T)\rangle] &= \frac{M}{M'} \bigl(F_q(C)-F_{q-1}(C)\bigr)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}]\cdot \mathbf{1}[d_v^{\le C}\ge D_a+1]\cdot \mathbf{1}[\Gamma_a(d_v^{\le C},s_v^{\le C})\ge qB_a]. \end{align}\]

Similarly, \[\begin{align} \mathbb{E}[U_q(C)\mid |Q(T)\rangle] &= \frac{M}{M'} \bigl(F_q(C)-F_{q-1}(C)\bigr)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}]\cdot \mathbf{1}[d_v^{\le C}\ge D_{a+1}+1]\cdot \mathbf{1}[\Gamma_a(d_v^{\le C},s_v^{\le C})\ge qB_a]. \end{align}\]

By Lemma 10, \[\Pr[\text{this sub-sketch is active just before the query on }C] = \frac{M'}{M}.\] Multiplying by this factor gives \[\begin{align} \mathbb{E}[L_q(C)-U_q(C)] &= \bigl(F_q(C)-F_{q-1}(C)\bigr)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}]\cdot \mathbf{1}[D_a<d_v^{\le C}\le D_{a+1}]\cdot \mathbf{1}[\Gamma_a(d_v^{\le C},s_v^{\le C})\ge qB_a]. \end{align}\]

Now assume \[D_a<d_v^{\le C}\le D_{a+1}.\] By 7 , the last condition is equivalent to \(s_v^{\le C}\ge q\). Hence \[\label{eq:bigq} \mathbb{E}[L_q(C)-U_q(C)] = \bigl(F_q(C)-F_{q-1}(C)\bigr) \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C},\;D_a<d_v^{\le C}\le D_{a+1},\;s_v^{\le C}\ge q].\tag{11}\]

5.2.1.11 For \(q=0\).

Now the query is a single-query. Since \[L_0(C)=M\cdot \xi_C^{\ell}\cdot F_0(C),\] and the Lower-\(0\)-Sketch queries \(H(v,D_a+1)\), the single-query formula gives \[\mathbb{E}[\xi_C^{\ell}\mid |Q(T)\rangle] = \frac{1}{M'}\mathbf{1}[H(v,D_a+1)\in T].\] Therefore \[\mathbb{E}[L_0(C)\mid |Q(T)\rangle] = \frac{M}{M'}F_0(C)\, \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}] \mathbf{1}[H(v,D_a+1)\in T].\] On the event \(\mathcal{G}_1\), this becomes \[\mathbb{E}[L_0(C)\mid |Q(T)\rangle] = \frac{M}{M'}F_0(C)\, \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C},\;d_v^{\le C}\ge D_a+1].\]

Similarly, the Upper-\(0\)-Sketch queries \(H(v,D_{a+1}+1)\), so \[\mathbb{E}[U_0(C)\mid |Q(T)\rangle] = \frac{M}{M'}F_0(C)\, \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C},\;d_v^{\le C}\ge D_{a+1}+1].\] Using Lemma 10 again, we get \[\label{0q} \mathbb{E}[L_0(C)-U_0(C)] = F_0(C)\, \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C},\;D_a<d_v^{\le C}\le D_{a+1}].\tag{12}\]

Finally, combining Equality 9  10  11 and  12 , define \[A_a(C):= \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\; D_a<d_v^{\le C}\le D_{a+1} \right].\] Then we have \[\label{eq:one-endpoint-high-coordinate} \begin{align} \mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}(C)\right] &= A_a(C) \left( F_0(C)+ \sum_{q=1}^{\kappa} \bigl(F_q(C)-F_{q-1}(C)\bigr)\mathbf{1}[s_v^{\le C}\ge q] \right) \\ &= \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\; D_a<d_v^{\le C}\le D_{a+1},\; \lambda_j(C)=\alpha \right]. \end{align}\tag{13}\]

Therefore \[\mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}\right] = U^{(a)}_{\ell,j,\alpha}.\]

5.2.2 Low-degree case↩︎

For the low-degree \(U^{(a)}_{\ell,j,\alpha}\), the relevant prefix total degree and prefix positive count of \(v_j(C)\) range over a constant-size set. We perform sketches for all the possible \((d,c)\) pairs, where \(d\in(D_a,D_{a+1}]\) and \(c\in[0,d]\). Each pair represents the candidate values \(d_v^{\le C}=d\) and \(p_v^{\le C}=c\). Moreover, for each \((d,c)\) we maintain a \((d,c)\)-Sketch.

Each \((d,c)\)-Sketch consists of analogous Lower-\((d,c)\)-Sketch and Upper-\((d,c)\)-Sketch. They each have an identical quantum register. The quantum register and update operations are the same as in the high-degree case, except for the positive-count update described next.

For the update step, Step-3 is replaced as follows: if this tagged unit is positive, perform \(\mathrm{inc}(E,u,B_a).\)

For the query step, the Lower-\((d,c)\)-Sketch performs a single-query on \[E(v, B_a c+d )\] and the Upper-\((d,c)\)-Sketch performs single-query on \[E(v, B_a c+d+1 ).\]

In the low-degree sketch, the query tests only the value \(\Gamma_a(d,c)\); it does not separately test whether the prefix degree lies in \((D_a,D_{a+1}]\). Therefore an endpoint whose true prefix degree is outside this interval may still pass the queried threshold. The condition 8 was chosen to count every such possible extra contribution. If this condition does not occur, the queried difference isolates the intended low-degree state \((d,c)\).

5.2.2.1 Output.

After a successful query on a target-shape clause \(C\), the corresponding Lower-\((d,c)\)-Sketch or Upper-\((d,c)\)-Sketch stores the nonzero single-query output, which equals \(1\), and computes \[F_{d,c}(C) := \mathbf{1}\!\left[ \mathrm{clip}_{[-1,1]}\!\left( \frac{2(c+p_v^{>C})}{d+d_v^{>C}}-1+g(v) \right)\in I_{i_\alpha} \right]\] by substituting the exact prefix values \[d_v^{\le C}=d,\qquad p_v^{\le C}=c\] into the weighted pseudobias formula of Definition 9. Define \[L_{d,c}(C):=M\cdot \xi^{\ell}_{d,c}(C)\cdot F_{d,c}(C), \qquad U_{d,c}(C):=M\cdot \xi^{u}_{d,c}(C)\cdot F_{d,c}(C),\] where \(\xi^{\ell}_{d,c}(C),\xi^{u}_{d,c}(C)\in\{0,1\}\) are the one-query outputs of the Lower-\((d,c)\)-Sketch and Upper-\((d,c)\)-Sketch, respectively. Extend both outputs by \(0\) to every clause that is not target-shape.

5.2.2.2 Estimation and Analysis.

For each clause \(C\), define \[\widehat U^{(a)}_{\ell,j,\alpha}(C) := \sum_{d=D_a+1}^{D_{a+1}} \sum_{c=0}^{d} \bigl(L_{d,c}(C)-U_{d,c}(C)\bigr),\] and \[\widehat U^{(a)}_{\ell,j,\alpha} := \sum_{C\in\Phi_{\le3}} \widehat U^{(a)}_{\ell,j,\alpha}(C).\]

Fix a clause \(C\) and write \(v:=v_j(C)\). If the live set just before the query in the Lower-\((d,c)\)-Sketch has size \(M'-1\), then the one-query property gives \[\mathbb{E}\!\left[L_{d,c}(C)\mid |Q(T)\rangle\right] = \frac{M}{M'} F_{d,c}(C)\, \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\, \Gamma_a(d_v^{\le C},p_v^{\le C})\ge B_a c+d \right].\] Similarly, \[\mathbb{E}\!\left[U_{d,c}(C)\mid |Q(T)\rangle\right] = \frac{M}{M'} F_{d,c}(C)\, \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\, \Gamma_a(d_v^{\le C},p_v^{\le C})\ge B_a c+d+1 \right].\] Since the probability that the quantum part of this sub-sketch is active just before the query is \(M'/M\), \[\mathbb{E}\!\left[L_{d,c}(C)-U_{d,c}(C)\right] = F_{d,c}(C)\, \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\, \Gamma_a(d_v^{\le C},p_v^{\le C})=B_a c+d \right].\] If the endpoint \(v_j(C)\) does not impersonate scale \(a\), then Lemma 7 rules out hits from degrees outside \((D_a,D_{a+1}]\), and the threshold identity 6 applies inside the interval. Thus \[\Gamma_a(d_v^{\le C},p_v^{\le C})=B_a c+d \iff d_v^{\le C}=d,\quad p_v^{\le C}=c.\] Therefore, on the event that \(v_j(C)\) does not impersonate scale \(a\), \[\mathbb{E}\!\left[L_{d,c}(C)-U_{d,c}(C)\right] = F_{d,c}(C)\, \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\, d_v^{\le C}=d,\, p_v^{\le C}=c \right].\] Whenever \[d_v^{\le C}=d,\qquad p_v^{\le C}=c,\] the values substituted in \(F_{d,c}(C)\) are exactly those in the weighted pseudobias of Definition 9. By the sign-bucket pair definition in Definition 10, \[F_{d,c}(C)=\mathbf{1}[\lambda_j(C)=\alpha].\] Summing over all pairs \((d,c)\) therefore gives \[\mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}(C)\right] = \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\, D_a<d_v^{\le C}\le D_{a+1},\, \lambda_j(C)=\alpha \right]\] \[\text{whenever the endpoint }v_j(C)\text{ does not impersonate scale }a\text{.}\]

For a fixed clause \(C\) and scale \(a\), at most one pair \((d,c)\) can satisfy \(\Gamma_a(d_v^{\le C},p_v^{\le C})=B_a c+d\) with \(D_a<d\le D_{a+1}\), because equality for two pairs \((d,c)\) and \((d',c')\) would imply \(d-d'=B_a(c'-c)\), and \(|d-d'|<B_a\) forces \(c=c'\) and then \(d=d'\). Hence, for this fixed clause and scale, the total contribution of all low-degree \((d,c)\)-sketches has absolute value at most \(1\). Therefore, in all cases \[\label{eq:one-endpoint-low-coordinate} \begin{align} \left| \mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}(C)\right] - \mathbf{1}\!\left[ \substack{ \mathsf{Tgt}^{\ell,j,\alpha}_{C},\; D_a<d_v^{\le C}\le D_{a+1},\; \lambda_j(C)=\alpha } \right] \right| &\le \mathbf{1}[\mathsf{Tgt}^{\ell,j,\alpha}_{C}]\cdot \mathbf{1}[\mathsf{Imp}^{a}_{C,j}]. \end{align}\tag{14}\] Recall that \(\mathsf{Imp}^{a}_{C,j}\) denotes the event that endpoint \((C,j)\) impersonates scale \(a\).

Hence \[\label{eq:one-endpoint-low-coordinate-total} \left| \mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}\right] - U^{(a)}_{\ell,j,\alpha} \right| \le \sum_{C\in\Phi_{\le3}} \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C}, \mathsf{Imp}^{a}_{C,j} \right].\tag{15}\]

5.3 Two-endpoint estimation↩︎

Fix a two-endpoint coordinate \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\). Here \(1\le j<t\le \ell\), \(\alpha=(s_\alpha,i_\alpha)\) and \(\beta=(s_\beta,i_\beta)\) are sign-bucket pairs. \(a\) and \(b\) correspond to the scales \((D_a,D_{a+1}]\) and \((D_b,D_{b+1}]\).

We call a clause \(C\) target-shape for the two-endpoint coordinate \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\) if \(|C|=\ell\), the \(j\)-th literal of \(C\) has sign \(s_\alpha\), and the \(t\)-th literal of \(C\) has sign \(s_\beta\). To make the subsequent formulas more concise, let \(\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}\) be the event that \(C\) is the target-type for \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\).

For the first endpoint \(v_{j}(C)\), when \(2D_a\ge \kappa\), recall the definition \[s^{\le C}_{v_j(C)} := \#\Bigl\{\text{positive tagged units of }v_j(C) \text{ that are selected by }f_a \text{ up to }C\Bigr\}.\] For the second endpoint \(v_{t}(C)\), when \(2D_b\ge \kappa\), \[s^{\le C}_{v_t(C)} := \#\Bigl\{\text{positive tagged units of }v_t(C) \text{ that are selected by }f_b \text{ up to }C\Bigr\}.\]

Impersonation also plays an important role in the error counting here. Recall that \(a(C,r)\) denotes the true scale of the endpoint \((C,r)\), namely the scale satisfying \[D_{a(C,r)}<d^{\le C}_{v_r(C)}\le D_{a(C,r)+1}.\]

For any queried nonempty scale \(s\), we say that the endpoint \((C,r)\) impersonates scale \(s\) if it satisfies the scale-\(s\) impersonation condition from 8 . In the error count below, we only count such events when \(s\neq a(C,r)\). This condition only checks the prefix degree, and it is chosen to include every case in which \((C,r)\) actually gives a nonzero contribution to a queried wrong scale \(s\).

To see this, let \(c_{\mathrm{enc}}\) be the positive-prefix count encoded by the scale-\(s\) sketch on this endpoint: it is the sampled count on a high-degree scale and the exact positive-prefix count on a low-degree scale. If such a nonzero contribution occurs, then for some queried count index \(c_0\) and some \(d_0\) with \(D_s<d_0\le D_{s+1}\), \[d^{\le C}_{v_r(C)}+B_s c_{\mathrm{enc}}=B_s c_0+d_0.\] Hence \[d^{\le C}_{v_r(C)} = (c_0-c_{\mathrm{enc}})B_s+d_0.\] For a wrong-scale nonzero contribution, the integer \(h:=c_0-c_{\mathrm{enc}}\) is one of the values allowed in 8 . Therefore this endpoint is included in the larger set defined by the impersonation condition. The converse is not claimed: an endpoint may satisfy the interval condition in 8 but still contribute zero, because its encoded positive-prefix count may not place \(d+B_s c_{\mathrm{enc}}\) at the queried level.

The coordinate output defined in this section is the actual algorithmic output for \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\). We compare it directly with the target coordinate, which counts clauses whose two queried endpoints have true scales \(a\) and \(b\). Once the no-wrap event below makes the queried labels represent the intended threshold inequalities, a fixed queried scale pair \((a,b)\) can differ from the target coordinate only in the following two ways:

1. a clause whose true scale pair is not \((a,b)\) can still give a nonzero term to the coordinate output for \((a,b)\), because the first endpoint satisfies the scale-\(a\) impersonation condition or the second endpoint satisfies the scale-\(b\) impersonation condition;

2. a true high-degree endpoint overflows, meaning that its sampled positive-prefix count is at least \(\kappa\) while the sketch only queries the values \(0,1,\ldots,\kappa-1\).

The first case can make the queried coordinate include a clause that the target coordinate does not include; the second case can make the queried coordinate miss a clause that the target coordinate includes.

5.3.1 High-degree on both endpoints↩︎

We first discuss the case \(D_a\ge\kappa/2\) and \(D_b\ge\kappa/2\). The remaining cases, where at least one scale is low-degree, are handled in Section 5.3.2; only the queried levels and positive-count updates change.

In this case both endpoints use the sampled positive-prefix counts \(s_{v}^{\le C}\) from Definition 9, and we keep only the levels \(\{0,1,\ldots,\kappa-1 \}\). We use the random-base threshold encoding from the one-endpoint section on both sides: \[\Gamma_a(d,c)=d+B_a c, \qquad \Gamma_b(d,c)=d+B_b c,\] where \(B_a\) and \(B_b\) are the public-random bases chosen in the one-endpoint section. Set \[\Sigma_a:=\{0,1,\ldots,\kappa-1\}, \qquad \Sigma_b:=\{0,1,\ldots,\kappa-1\}.\] For each pair \((\sigma,\tau)\in\Sigma_a\times\Sigma_b\), we maintain four independent sub-sketches:

1. Lower-Lower-\((\sigma,\tau)\)-Sketch,

2. Lower-Upper-\((\sigma,\tau)\)-Sketch,

3. Upper-Lower-\((\sigma,\tau)\)-Sketch,

4. Upper-Upper-\((\sigma,\tau)\)-Sketch.

5.3.1.1 Quantum register.

Each of the four sub-sketches has an identical quantum register. We use the global register size \(M=\lceil C_{\varepsilon} m\rceil\), with \(C_\varepsilon\) chosen large enough for the fixed \(\varepsilon>0\). The basis labels are:

1. a fixed anchor basis state \(\ket{\bot}\);

2. spare labels \(S_1,\ldots,S_M\);

3. first-family labels \(Z_1(v,r)\), where \(v\in[n]\) and \(r\in[M]\);

4. second-family labels \(Z_2(v,r)\), where \(v\in[n]\) and \(r\in[M]\);

5. first-family garbage labels \(G_1(v,r)\), where \(v\in[n]\) and \(r\in[M]\);

6. second-family garbage labels \(G_2(v,r)\), where \(v\in[n]\) and \(r\in[M]\).

As in the one-endpoint case, we maintain a pointer \(\mathcal{P}\) in a classical register. The pointer runs through the spare labels \(S_1,S_2,\ldots,S_M\): after it reaches \(S_M\), the next shift uses \(S_1\) again.

In the one-endpoint sketch, the \(H\)- and \(E\)-labels are both used for the same endpoint. Here \(Z_1\) is used for \(v_j(C)\) and \(Z_2\) is used for \(v_t(C)\), so each side uses one label family to encode the threshold value for that endpoint. Thus each side uses one label family for the combined value \(\Gamma_a(d,c)\) or \(\Gamma_b(d,c)\), rather than keeping separate labels for the total degree and the positive-prefix count.

For \(i=1,2\), \(\mathrm{inc}(Z_i,u,r)\) means applying the same one-step shift to the chain \(Z_i(u,\cdot)\) exactly \(r\) times; after each one-step shift, the pointer moves to the next spare label, with \(S_M\) followed by \(S_1\). As long as fewer than \(M\) elementary shifts have been applied, the queried labels behave exactly as in the one-way shifts \[S_{\mathcal{P}}\to Z_1(u,1)\to Z_1(u,2)\to \cdots \to Z_1(u,M) \to G_{1}(u,M)\to \cdots \to G_1(u,1)\to S_{\mathcal{P}},\] and \[S_{\mathcal{P}}\to Z_2(u,1)\to Z_2(u,2)\to \cdots \to Z_2(u,M) \to G_2(u,M)\to \cdots \to G_2(u,1)\to S_{\mathcal{P}}.\]

The initial state is \[\left|Q(T_0)\right\rangle = \frac{|\perp\rangle+|S_1\rangle+\cdots+|S_{M-1}\rangle}{\sqrt M}, \qquad T_0:=\{S_1,S_2,\ldots,S_{M-1}\}.\] And initialize \(\mathcal{P}=1\). This register uses \(O(\log (n+m))\) qubits, and the pointer uses \(O(\log(m))\) classical bits.

5.3.1.2 Update.

Process the tagged units of the current clause one by one. Suppose the tagged unit is on variable \(u\). In each of the four sub-sketches, perform

1. \(\mathrm{inc}(Z_1,u,1)\);

2. \(\mathrm{inc}(Z_2,u,1)\);

3. if this tagged unit is positive and selected by \(f_a\), perform \(\mathrm{inc}(Z_1,u,B_a)\);

4. if this tagged unit is positive and selected by \(f_b\), perform \(\mathrm{inc}(Z_2,u,B_b)\).

5.3.1.3 Query.

If the current clause \(C\) is not target-shape, do nothing. Otherwise let \[u:=v_j(C), \qquad v:=v_t(C).\] The Lower-Lower-\((\sigma,\tau)\)-Sketch applies the pair-query to \[\Bigl(Z_1\bigl(u,B_a\sigma+D_a+1\bigr), Z_2\bigl(v,B_b\tau+D_b+1\bigr)\Bigr).\] The other three sub-sketches use the same pair-query with the corresponding threshold: \[\begin{align} &\Bigl(Z_1\bigl(u,B_a\sigma+D_a+1\bigr), Z_2\bigl(v,B_b\tau+D_{b+1}+1\bigr)\Bigr),\\ &\Bigl(Z_1\bigl(u,B_a\sigma+D_{a+1}+1\bigr), Z_2\bigl(v,B_b\tau+D_b+1\bigr)\Bigr),\\ &\Bigl(Z_1\bigl(u,B_a\sigma+D_{a+1}+1\bigr), Z_2\bigl(v,B_b\tau+D_{b+1}+1\bigr)\Bigr). \end{align}\] Denote the four outputs of pair-query by \[\chi^{\ell\ell}_{\sigma,\tau}(C), \qquad \chi^{\ell u}_{\sigma,\tau}(C), \qquad \chi^{u\ell}_{\sigma,\tau}(C), \qquad \chi^{uu}_{\sigma,\tau}(C) \in \{-1,0,1\}.\] If the output is \(0\), the sketch continues. If the output is \(\pm1\), the quantum part of that sub-sketch stops, and we store the nonzero output sign together with \(u\), \(v\), \(\sigma\), and \(\tau\). During the rest of the stream, we count \[d_u^{>C},\;p_u^{>C},\;d_v^{>C},\;p_v^{>C}\] exactly using classical counters.

The no-wrap lemma below justifies these threshold tests before each query.

5.3.1.4 Output.

If the pair-query output is nonzero, the sub-sketch computes\[\widetilde{b}_{u} := \operatorname{clip}_{[-1,1]} \left( \frac{2\left(\frac{2D_a}{\kappa}\sigma+p_u^{>C}\right)}{D_a+d_u^{>C}} -1+g(u) \right),\qquad \widetilde{b}_{v}:= \operatorname{clip}_{[-1,1]} \left( \frac{2\left(\frac{2D_b}{\kappa}\tau+p_v^{>C}\right)}{D_b+d_v^{>C}} -1+g(v) \right),\] and \[\begin{align} F_{\sigma,\tau}(C):= \mathbf{1} \left[\widetilde{b}_{u} \in I_{i_\alpha},\; \widetilde{b}_{v} \in I_{i_\beta} \right]. \end{align}\] This is exactly the indicator that the two endpoints have sign-bucket pairs \((\alpha,\beta)\), when \(\sigma\) and \(\tau\) are used as the candidate sampled positive-prefix counts for the two endpoints. The four final outputs are \[Y^{\ell\ell}_{\sigma,\tau}(C) :=\frac{M}{2}\,\chi^{\ell\ell}_{\sigma,\tau}(C)F_{\sigma,\tau}(C), \qquad Y^{\ell u}_{\sigma,\tau}(C) :=\frac{M}{2}\,\chi^{\ell u}_{\sigma,\tau}(C)F_{\sigma,\tau}(C),\] \[Y^{u\ell}_{\sigma,\tau}(C) :=\frac{M}{2}\,\chi^{u\ell}_{\sigma,\tau}(C)F_{\sigma,\tau}(C), \qquad Y^{uu}_{\sigma,\tau}(C) :=\frac{M}{2}\,\chi^{uu}_{\sigma,\tau}(C)F_{\sigma,\tau}(C).\] If a sub-sketch never has a successful pair-query, its output is \(0\).

5.3.1.5 Correctness.

The same no-wrap issue appears here. Each two-endpoint sub-sketch has two label families, \(Z_1\) and \(Z_2\), but they share one pointer. The analysis only needs the following fact: each queried label represents its intended threshold inequality as long as the sub-sketch performs fewer than \(M\) elementary shifts in total and every queried level lies in \([M]\). Under these two conditions, the pointer never returns to an earlier spare position, so the queried labels still represent the thresholds of \(\Gamma_a\) and \(\Gamma_b\). The following lemma verifies these two conditions for all two-endpoint sub-sketches.

As in the one-endpoint case, the correctness argument only needs the fact from Lemma 8 that a fixed queried label has the intended threshold meaning before each query. Work on \(\mathcal{G}_2\), fix one elementary sub-sketch, and let \(T_a\) and \(T_b\) be the two thresholds queried by that sub-sketch. Immediately before a query on a target-shape clause \(C\), \[Z_1(u,T_a)\in T \iff \Gamma_a(d_u^{\le C},s_u^{\le C})\ge T_a,\] \[Z_2(v,T_b)\in T \iff \Gamma_b(d_v^{\le C},s_v^{\le C})\ge T_b.\] A failed pair-query can delete one queried label from the \(Z_1\)-family, one queried label from the \(Z_2\)-family, or both. Before any later query of the same label, the next clause containing the relevant variable applies the unconditional one-step update on that label family, even if the tagged unit is not positive or is not selected. Therefore the fixed queried level is restored before it is tested again. Each elementary sub-sketch fixes one queried threshold in each label family throughout the run.

5.3.1.6 Estimation of \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\).

All the following argument is on the event \(\mathcal{G}_2\) from Lemma 11.

Extend the outputs of the four sub-sketches by \(0\) to every clause that is not target-shape. For each target-shape clause \(C\), define \[\begin{align} \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) :=\sum_{\sigma=0}^{\kappa-1}\sum_{\tau=0}^{\kappa-1} \Bigl( Y^{\ell\ell}_{\sigma,\tau}(C) -Y^{\ell u}_{\sigma,\tau}(C) -Y^{u\ell}_{\sigma,\tau}(C) +Y^{uu}_{\sigma,\tau}(C) \Bigr), \end{align}\] and then set \[\widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta} := \sum_C \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C).\]

Recall that \(\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}\) denotes the event that \(|C|=\ell\), the \(j\)-th literal has sign \(s_\alpha\), and the \(t\)-th literal has sign \(s_\beta\), i.e. \(C\) is the target-type for \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\).

Fix \(\sigma\in\Sigma_a\), \(\tau\in\Sigma_b\), and one of the four sub-sketches. If the live set just before its query on \(C\) has size \(M'-1\), then by the pair-query property we have \[\begin{align} \mathbb{E}\! \left[ Y^{\ell\ell}_{\sigma,\tau}(C) \,\middle|\, \left|Q(T)\right\rangle \right] = \frac{M}{M'}F_{\sigma,\tau}(C) \cdot \mathbf{1}\Bigl[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}, \Gamma_a(d_u^{\le C},s_u^{\le C})\ge B_a\sigma+D_a+1, \Gamma_b(d_v^{\le C},s_v^{\le C})\ge B_b\tau+D_b+1\Bigr]. \end{align}\] Exactly as in the one-endpoint case, the probability that the sub-sketch is still active just before that query is \(M'/M\), so the unconditional expectation is the same indicator without the prefactor \(M/M'\). The corresponding formulas for \(Y^{\ell u}_{\sigma,\tau}(C)\), \(Y^{u\ell}_{\sigma,\tau}(C)\), and \(Y^{uu}_{\sigma,\tau}(C)\) are obtained by replacing the lower threshold on the first endpoint, the second endpoint, or both, by the corresponding upper threshold.

For the first endpoint, assume that \(v_j(C)\) does not impersonate scale \(a\). Recall that \(a(C,j)\) means the true scale of the first queried endpoint \(v_j(C)\). Then the difference of the two threshold indicators for the first endpoint has the direct interpretation \[\begin{align} &\mathbf{1}[\Gamma_a(d_u^{\le C},s_u^{\le C})\ge B_a\sigma+D_a+1] -\mathbf{1}[\Gamma_a(d_u^{\le C},s_u^{\le C})\ge B_a\sigma+D_{a+1}+1]\\ &\qquad= \begin{cases} \mathbf{1}[D_a<d_u^{\le C}\le D_{a+1},\;s_u^{\le C}=\sigma], & a=a(C,j)\text{ and }s_u^{\le C}<\kappa,\\ 0, & a\neq a(C,j)\text{ or }s_u^{\le C}\ge\kappa. \end{cases} \end{align}\] Indeed, if \(a=a(C,j)\) and \(s_u^{\le C}<\kappa\), this is exactly 5 . If \(a\neq a(C,j)\) and the endpoint does not impersonate scale \(a\), then this difference is \(0\). To see this, if \(d_u^{\le C}\le D_a\), the two threshold indicators are equal; if \(d_u^{\le C}>D_{a+1}\), a nonzero difference would force scale-\(a\) impersonation, contrary to the assumption. If \(a=a(C,j)\) but \(s_u^{\le C}\ge\kappa\), then for every \(\sigma\in\{0,1,\ldots,\kappa-1\}\) both indicators are \(1\), so the difference is again \(0\). The same statement holds for the second endpoint with \((b,\tau)\) in place of \((a,\sigma)\).

Therefore, whenever neither endpoint impersonates its queried scale, we have \[\begin{align} &\mathbb{E}\Bigl[ Y^{\ell\ell}_{\sigma,\tau}(C) -Y^{\ell u}_{\sigma,\tau}(C) -Y^{u\ell}_{\sigma,\tau}(C) +Y^{uu}_{\sigma,\tau}(C) \Bigr]\\ &\qquad= F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\\ &\qquad\quad\cdot \mathbf{1}\bigl[a=a(C,j),\;D_a<d_u^{\le C}\le D_{a+1},\;s_u^{\le C}=\sigma<\kappa\bigr]\\ &\qquad\quad\cdot \mathbf{1}\bigl[b=a(C,t),\;D_b<d_v^{\le C}\le D_{b+1},\;s_v^{\le C}=\tau<\kappa\bigr]. \end{align}\] Whenever the last two indicators are \(1\), the prefix values substituted in \(F_{\sigma,\tau}(C)\) are exactly those in the weighted pseudobias of Definition 9. By the sign-bucket pair definition in Definition 10, \[F_{\sigma,\tau}(C) = \mathbf{1}\bigl[(\lambda_j(C),\lambda_t(C))=(\alpha,\beta)\bigr].\] Summing over \(\sigma\) and \(\tau\) gives \[\mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) \bigr] = \mathbf{1}\bigl[C\text{ contributes to } P^{(a,b)}_{\ell,j,t,\alpha,\beta}\bigr]\] whenever neither endpoint impersonates the queried scale, and neither relevant sampled positive-prefix count overflows.

In all cases, we use a crude bound of absolute value at most \(1\). For a fixed endpoint and fixed queried scale, at most one value of the index can make the corresponding difference of the two threshold indicators nonzero, because the intervals \[[B_a\sigma+D_a+1,\,B_a\sigma+D_{a+1}]\] are disjoint. The same holds for the second endpoint.

Recall that \(\mathsf{Imp}^{a}_{C,r}\) denotes the event that endpoint \((C,r)\) impersonates scale \(a\). Since \(0\le F_{\sigma,\tau}(C)\le1\), every clause contributes at most \(1\) in absolute value to one fixed queried coordinate. Therefore, for every clause \(C\), \[\begin{align} &\left| \mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) \bigr] - \mathbf{1}\bigl[C\text{ contributes to } P^{(a,b)}_{\ell,j,t,\alpha,\beta}\bigr] \right|\\ &\le \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\Bigl( \mathbf{1}[\mathsf{Imp}^{a}_{C,j}] +\mathbf{1}[\mathsf{Imp}^{b}_{C,t}] +\mathbf{1}[a=a(C,j),\;s^{\le C}_{v_j(C)}\ge\kappa] +\mathbf{1}[b=a(C,t),\;s^{\le C}_{v_t(C)}\ge\kappa] \Bigr). \end{align}\] Consequently, \[\label{eq:two-endpoint-high-coordinate-total} \begin{align} & \left| \mathbb{E}\!\left[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta} \right] - P^{(a,b)}_{\ell,j,t,\alpha,\beta} \right| \\ &\le \sum_{C\in\Phi_{\le3}} \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\Bigl( \mathbf{1}[\mathsf{Imp}^{a}_{C,j}] +\mathbf{1}[\mathsf{Imp}^{b}_{C,t}] +\mathbf{1}[a=a(C,j),\;s^{\le C}_{v_j(C)}\ge\kappa] +\mathbf{1}[b=a(C,t),\;s^{\le C}_{v_t(C)}\ge\kappa] \Bigr) \end{align}\tag{16}\]

5.3.1.7 Why overflow remains.

The coordinate output only queries sampled counts \(0,1,\ldots,\kappa-1\). If a true high-degree endpoint has sampled positive-prefix count at least \(\kappa\), then that clause may still belong to the true coordinate \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\), but each queried difference of threshold indicators on that side is zero. The final proof bounds the total loss from these endpoints by the overflow weight \(W_{\mathrm{of}}\).

5.3.2 Other cases↩︎

Assume now that at least one of \(D_a\) and \(D_b\) is low-degree, namely \(D_a<\kappa/2\) or \(D_b<\kappa/2\). We keep the same four sub-sketches, the same register layout, and the same final inclusion-exclusion formula as above. Only the levels, the positive-count updates, and the queried positions change.

For each endpoint we use the exact positive-prefix count on a low-degree scale and the sampled positive-prefix count on a high-degree scale. Accordingly, set \[\Sigma_a:= \begin{cases} \{0,1,\ldots,\kappa-1\}, & D_a\ge\kappa/2,\\ \{(d_1,c_1): D_a<d_1 \le D_{a+1},\;0\le c_1 \le d_1\}, & D_a< \kappa/2, \end{cases}\] \[\Sigma_b:= \begin{cases} \{0,1,\ldots,\kappa-1\}, & D_b\ge\kappa/2,\\ \{(d_2,c_2): D_b<d_2 \le D_{b+1},\;0\le c_2 \le d_2 \}, & D_b< \kappa/2. \end{cases}\]

5.3.2.1 Update.

For every tagged unit on a variable \(u\), first apply the degree update \(\mathrm{inc}(Z_1,u,1)\) and \(\mathrm{inc}(Z_2,u,1)\). Then update the positive count on each side separately. On the first side, apply \(\mathrm{inc}(Z_1,u,B_a)\) if the tagged unit is positive and either \(D_a<\kappa/2\), or \(D_a\ge\kappa/2\) and the unit is selected by \(f_a\). On the second side, apply \(\mathrm{inc}(Z_2,u,B_b)\) under the same rule with \(b\) and \(f_b\). Thus, when both sides are low-degree, a positive tagged unit triggers the \(B_a\)-step update on \(Z_1\) and the \(B_b\)-step update on \(Z_2\).

5.3.2.2 Query.

If the current clause \(C\) is not target-shape, do nothing. Otherwise write \[u:=v_j(C), \qquad v:=v_t(C).\] If the first endpoint is low-degree and \(\sigma=(d_1,c_1)\in\Sigma_a\), then the lower and upper queried positions on the first family labels are \[Z_1\bigl(u,B_a c_1 +d_1 \bigr), \qquad Z_1\bigl(u,B_a c_1 +d_1 +1\bigr).\] If the first endpoint is high-degree \(D_a\ge\kappa/2\) and \(\sigma\in\{0,1,\ldots,\kappa-1\}\), we query like the previous section: \[Z_1\bigl(u,B_a\sigma+D_a+1\bigr), \qquad Z_1\bigl(u,B_a\sigma+D_{a+1}+1\bigr).\] The second endpoint is treated analogously: if \(D_b<\kappa/2\) and \(\tau=(d_2,c_2)\in\Sigma_b\), use \[Z_2\bigl(v,B_b c_2+d_2 \bigr), \qquad Z_2\bigl(v,B_b c_2+d_2 +1\bigr),\] and if \(D_b\ge\kappa/2\) and \(\tau\in\{0,1,\ldots,\kappa-1\}\), use \[Z_2\bigl(v,B_b\tau+D_b+1\bigr), \qquad Z_2\bigl(v,B_b\tau+D_{b+1}+1\bigr).\] The four sub-sketches again apply pair-query to the lower/lower, lower/upper, upper/lower, and upper/upper choices. If such a pair-query has output \(\pm1\), that sub-sketch stops and stores the nonzero sign, the two variables, and the indices \(\sigma,\tau\); the suffix degrees and suffix positive counts are then counted exactly as in the high-high case.

5.3.2.3 Output.

After a successful pair-query on a clause \(C\), compute \(F_{\sigma,\tau}(C)\) by using the following candidate prefix values. If \(D_a< \kappa/2\) and \(\sigma = (d_1,c_1)\in\Sigma_a\), use \[\widehat d_u=d_1, \qquad \widehat p_u=c_1.\] If \(D_a\ge\kappa/2\) and \(\sigma\in\{0,1,\ldots,\kappa-1\}\), use \[\widehat d_u=D_a, \qquad \widehat p_u=\frac{2D_a}{\kappa}\sigma.\] If \(D_b< \kappa/2\) and \(\tau=(d_2,c_2)\in\Sigma_b\), use \[\widehat d_v=d_2, \qquad \widehat p_v=c_2.\] If \(D_b\ge\kappa/2\) and \(\tau\in\{0,1,\ldots,\kappa-1\}\), use \[\widehat d_v=D_b, \qquad \widehat p_v=\frac{2D_b}{\kappa}\tau.\] Then set \[\begin{align} F_{\sigma,\tau}(C):= \mathbf{1}\Biggl[&\operatorname{clip}_{[-1,1]} \left( \frac{2(\widehat p_u+p_u^{>C})}{\widehat d_u+d_u^{>C}} -1+g(u) \right)\in I_{i_\alpha},\\ &\operatorname{clip}_{[-1,1]} \left( \frac{2(\widehat p_v+p_v^{>C})}{\widehat d_v+d_v^{>C}} -1+g(v) \right)\in I_{i_\beta}\Biggr]. \end{align}\]

The four final outputs are \[Y^{\ell\ell}_{\sigma,\tau}(C) := \frac{M}{2}\chi^{\ell\ell}_{\sigma,\tau}(C)F_{\sigma,\tau}(C), \qquad Y^{\ell u}_{\sigma,\tau}(C) := \frac{M}{2}\chi^{\ell u}_{\sigma,\tau}(C)F_{\sigma,\tau}(C),\] \[Y^{u\ell }_{\sigma,\tau}(C) := \frac{M}{2}\chi^{u\ell}_{\sigma,\tau}(C)F_{\sigma,\tau}(C), \qquad Y^{uu}_{\sigma,\tau}(C) := \frac{M}{2}\chi^{uu}_{\sigma,\tau}(C)F_{\sigma,\tau}(C).\] If the sub-sketch never has a successful pair-query, its output is \(0\).

We now give some notations that cover all remaining cases.

5.3.2.4 Endpoint formulas.

For the analysis of a target-shape clause \(C\), write \[u:=v_j(C), \text{ and } v:=v_t(C).\] For the first endpoint, define \[N_a(C) := \begin{cases} \Gamma_a(d_u^{\le C},s_u^{\le C}), & D_a\ge\kappa/2,\\ \Gamma_a(d_u^{\le C},p_u^{\le C}), & D_a< \kappa/2. \end{cases}\] Define \(N_b(C)\) analogously for the second endpoint, using \(\Gamma_b\), \(d_v^{\le C}\), and either \(s_v^{\le C}\) or \(p_v^{\le C}\) according to whether \(D_b\) is high- or low-degree.

If \(D_a\ge\kappa/2\) and \(\sigma\in\{0,1,\dots,\kappa-1\}\), set \[L_a(\sigma)=B_a\sigma+D_a+1, \qquad U_a(\sigma)=B_a\sigma+D_{a+1}+1.\] Define \[\Delta_a(C,\sigma) := \mathbf{1}[N_a(C)\ge L_a(\sigma)] - \mathbf{1}[N_a(C)\ge U_a(\sigma)].\] Whenever the first endpoint does not impersonate scale \(a\), we have \[\Delta_a(C,\sigma) = \begin{cases} \mathbf{1}[D_a<d_u^{\le C}\le D_{a+1},\;s_u^{\le C}=\sigma], & a=a(C,j)\text{ and }s_u^{\le C}<\kappa,\\ 0, & a\neq a(C,j)\text{ or }s_u^{\le C}\ge\kappa. \end{cases}\] For the zero case with \(a\neq a(C,j)\), the same check applies: degrees below the queried scale make the two threshold indicators equal, while degrees above the queried scale would force impersonation if the difference of threshold indicators were nonzero.

If \(D_a< \kappa/2\) and \(\sigma=(d_1,c_1)\), set \[L_a(\sigma)=B_a c_1+d_1, \qquad U_a(\sigma)=B_a c_1+d_1+1.\] Whenever the first endpoint does not impersonate scale \(a\), we have \[\begin{align} &\Delta_a(C,\sigma) =\begin{cases} \mathbf{1}[d_u^{\le C}=d_1,\;p_u^{\le C}=c_1], & a=a(C,j),\\ 0, & a\neq a(C,j). \end{cases} \end{align}\] The second endpoint is identical; the functions \(L_b(\tau)\) and \(U_b(\tau)\) are defined by the same formulas with \(b,v,\tau\) in place of \(a,u,\sigma\).

On \(\mathcal{G}_2\), Lemma 8 says that each queried label is live exactly when its threshold inequality is true. Thus, for a target-shape clause \(C\), \[Z_1(u,L_a(\sigma))\in T\iff N_a(C)\ge L_a(\sigma), \qquad Z_1(u,U_a(\sigma))\in T\iff N_a(C)\ge U_a(\sigma),\] and the same statement holds for \(Z_2\) with \(N_b,L_b,U_b\). This is the only live-label fact used in the expectation calculation below.

5.3.2.5 Estimation.

All the following argument is on the event \(\mathcal{G}_2\) from Lemma 11.

For each clause \(C\), define \[\widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) := \sum_{(\sigma,\tau)\in\Sigma_a\times\Sigma_b} \Bigl( Y^{\ell\ell}_{\sigma,\tau}(C) -Y^{\ell u}_{\sigma,\tau}(C) -Y^{u\ell}_{\sigma,\tau}(C) +Y^{uu}_{\sigma,\tau}(C) \Bigr),\] and then set \[\widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta} := \sum_C \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C).\]

For a clause that is not target-shape, all four outputs are \(0\), so the bound below is immediate. Now fix a target-shape clause \(C\) and one pair \((\sigma,\tau)\in\Sigma_a\times\Sigma_b\), and write \[u:=v_j(C), \qquad v:=v_t(C).\] Suppose the live set just before the query in the current sub-sketch has size \(M'-1\).

The Lower-Lower-\((\sigma, \tau)\)-Sketch queries the pair \[\bigl(Z_1(u,L_a(\sigma)),\,Z_2(v,L_b(\tau))\bigr).\] So the pair-query formula gives \[\begin{align} \mathbb{E}[Y^{\ell\ell}_{\sigma,\tau}(C)\mid |Q(T)\rangle] &= \frac{M}{M'}F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}] \cdot \mathbf{1}[N_a(C)\ge L_a(\sigma)]\cdot \mathbf{1}[N_b(C)\ge L_b(\tau)]. \end{align}\] Similarly, \[\begin{align} \mathbb{E}[Y^{\ell u}_{\sigma,\tau}(C)\mid |Q(T)\rangle] &= \frac{M}{M'}F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\cdot \mathbf{1}[N_a(C)\ge L_a(\sigma)]\cdot \mathbf{1}[N_b(C)\ge U_b(\tau)], \end{align}\] \[\begin{align} \mathbb{E}[Y^{u\ell}_{\sigma,\tau}(C)\mid |Q(T)\rangle] &= \frac{M}{M'}F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\cdot \mathbf{1}[N_a(C)\ge U_a(\sigma)]\cdot \mathbf{1}[N_b(C)\ge L_b(\tau)], \end{align}\] \[\begin{align} \mathbb{E}[Y^{uu}_{\sigma,\tau}(C)\mid |Q(T)\rangle] &= \frac{M}{M'}F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\cdot \mathbf{1}[N_a(C)\ge U_a(\sigma)]\cdot \mathbf{1}[N_b(C)\ge U_b(\tau)]. \end{align}\]

By Lemma 10, the probability that this sub-sketch is still active just before the query is \(M'/M\). Therefore \[\mathbb{E}\!\left[ Y^{\ell\ell}_{\sigma,\tau}(C) -Y^{\ell u}_{\sigma,\tau}(C) -Y^{u\ell}_{\sigma,\tau}(C) +Y^{uu}_{\sigma,\tau}(C) \right] = F_{\sigma,\tau}(C)\cdot \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}] \cdot \Delta_a(C,\sigma) \cdot \Delta_b(C,\tau),\]

Say that the first endpoint is consistent with \(\sigma\) on scale \(a\) if its prefix data agree with the index \(\sigma\) on scale \(a\): on a high-degree side this means \[D_a<d_u^{\le C}\le D_{a+1},\qquad s_u^{\le C}=\sigma,\] and on a low-degree side, if \(\sigma=(d_1,c_1)\), it means \[d_u^{\le C}=d_1,\qquad p_u^{\le C}=c_1.\] Define consistency with \(\tau\) on the second endpoint in the same way. Assume that neither endpoint impersonates its queried scale. Then the endpoint formulas above identify the two differences of the two threshold indicators exactly. If, in addition, every relevant high-degree sampled positive-prefix count is below \(\kappa\) (that is, if \(a=a(C,j)\) and \(D_a\ge\kappa/2\) then \(s_u^{\le C}<\kappa\), and likewise on the second endpoint), we obtain

\[\begin{align} &\mathbb{E}\Bigl[ Y^{\ell\ell}_{\sigma,\tau}(C) -Y^{\ell u}_{\sigma,\tau}(C) -Y^{u\ell}_{\sigma,\tau}(C) +Y^{uu}_{\sigma,\tau}(C) \Bigr]\\ &=F_{\sigma,\tau}(C)\cdot \mathbf{1}\bigl[ \mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}\bigr]\cdot \mathbf{1}[\text{ the first endpoint is consistent with }\sigma]\\ &\qquad\quad\;\;\;\cdot \mathbf{1}\bigl[\text{the second endpoint is consistent with }\tau\bigr]. \end{align}\] Whenever both endpoints are consistent with their indices, the prefix values substituted in \(F_{\sigma,\tau}(C)\) are the true prefix values from Definition 9. Hence, by the sign-bucket pair definition in Definition 10, \[F_{\sigma,\tau}(C) = \mathbf{1}[(\lambda_j(C),\lambda_t(C))=(\alpha,\beta)]\] on that event. Summing over all \((\sigma,\tau)\in\Sigma_a\times\Sigma_b\) gives \[\mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) \bigr] = \mathbf{1}\bigl[ C\text{ contributes to }P^{(a,b)}_{\ell,j,t,\alpha,\beta} \bigr]\] whenever neither endpoint impersonates the queried scale and no relevant high-degree endpoint overflows.

In all cases, the absolute value of the contribution of this fixed clause to this fixed coordinate is at most \(1\). For a fixed endpoint and fixed scale, at most one index in \(\Sigma_a\) can make the difference of the two threshold indicators nonzero: in the high-degree case the intervals \[[B_a\sigma+D_a+1,\,B_a\sigma+D_{a+1}]\] are disjoint, and in the low-degree case the singleton levels \(B_a c_1+d_1\) are distinct because \(B_a>D_{a+1}\). The same holds for the second endpoint, with levels \(B_b c_2+d_2\). Hence, for every clause \(C\),

\[\begin{align} &\left| \mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta}(C) \bigr] - \mathbf{1}\bigl[ C\text{ contributes to }P^{(a,b)}_{\ell,j,t,\alpha,\beta} \bigr] \right|\\ &\le \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\cdot \Bigl( \mathbf{1}[\mathsf{Imp}^{a}_{C,j}] +\mathbf{1}[\mathsf{Imp}^{b}_{C,t}] +\mathbf{1}[a=a(C,j),\;D_a\ge\kappa/2,\;s^{\le C}_{v_j(C)}\ge\kappa]\\&\qquad\qquad\qquad\quad\quad +\mathbf{1}[b=a(C,t),\;D_b\ge\kappa/2,\;s^{\le C}_{v_t(C)}\ge\kappa] \Bigr). \end{align}\] Consequently, \[\label{eq:two-endpoint-remaining-coordinate-total} \begin{align} &\left| \mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta} \bigr] - P^{(a,b)}_{\ell,j,t,\alpha,\beta} \right|\\ &\le \sum_{C\in\Phi_{\le3}} \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\cdot \Bigl( \mathbf{1}[\mathsf{Imp}^{a}_{C,j}] +\mathbf{1}[\mathsf{Imp}^{b}_{C,t}] +\mathbf{1}[a=a(C,j),\;D_a\ge\kappa/2,\;s^{\le C}_{v_j(C)}\ge\kappa]\\&\qquad\qquad\qquad\qquad\qquad\quad +\mathbf{1}[b=a(C,t),\;D_b\ge\kappa/2,\;s^{\le C}_{v_t(C)}\ge\kappa] \Bigr). \end{align}\tag{17}\]

The first two terms upper-bound possible errors from endpoints counted by the impersonation condition for one of the queried scales. The last two terms record overflow on true high-degree endpoints.

5.4 Estimating the weighted pseudosnapshot score↩︎

Run in parallel, during the same pass over the stream, all sketches defined for the one-endpoint and two-endpoint coordinates, together with the exact classical counter for \(M_3\). Let \(Z\) denote the output of one such full run after applying exactly the same linear combination as \(L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3}))\): \[\begin{align} Z &: = \sum_a\sum_\alpha q_\alpha\widehat U^{(a)}_{1,1,\alpha} + \sum_{a,b}\sum_{\alpha,\beta} \bigl(1-(1-q_\alpha)(1-q_\beta)\bigr) \widehat P^{(a,b)}_{2,1,2,\alpha,\beta}\\ &\quad +c_0M_3 + \sum_{j=1}^3\sum_a\sum_\alpha u_j(\alpha)\widehat U^{(a)}_{3,j,\alpha} + \sum_{1\le j<t\le3}\sum_{a,b}\sum_{\alpha,\beta} p_{jt}(\alpha,\beta) \widehat P^{(a,b)}_{3,j,t,\alpha,\beta}. \end{align}\]

Fix the public randomness used for the hash functions, smoothing noise, and the random bases \(B_a\), and call it \(\omega\). All quantities defined from the pseudosnapshot are then deterministic; we suppress their dependence on \(\omega\). In the rest of the proof, whenever \(\omega\) is fixed, every expectation and variance is taken only over the outcomes of the quantum measurements.

The constants are fixed in the following order. First, choose the positive integer \(\kappa\) large enough for the sampled-prefix estimates and the overflow bound used below. With this \(\kappa\) fixed, choose \(K_{\mathrm{base}}\) for the impersonation bound, choose \(K_\varepsilon\) for the no-wrap tail bounds, and finally choose \(C_\varepsilon\) in \(M=\lceil C_{\varepsilon} m\rceil\) so that every update count and queried level fits in the finite register.

Let \(\mathcal{G}_1\) be the good event from Lemma 9, and let \(\mathcal{G}_2\) be the good event from Lemma 11. Define \[\mathcal{G}:=\mathcal{G}_1\cap \mathcal{G}_2.\] By the two lemmas and a union bound, \[\Pr[\mathcal{G}^c]\le \Pr[\mathcal{G}_1^c]+\Pr[\mathcal{G}_2^c] \le \frac{1}{160}+\frac{1}{160} = \frac{1}{80}.\]

For every short-clause endpoint \((C,r)\), let \(a(C,r)\) be its true scale, and let \[\mathcal{I}(C,r) := \{s:\;s\text{ is nonempty},\;s\neq a(C,r),\; (C,r)\text{ impersonates scale }s\}\] be the set of wrong queried scales for which \((C,r)\) satisfies the impersonation condition. Also write \[\mathcal{R}(C,r):=\{a(C,r)\}\cup\mathcal{I}(C,r)\] for the true scale of \((C,r)\) together with these wrong queried scales. Recall that \(\mathsf{Imp}^{s}_{C,r}\) denotes the event that endpoint \((C,r)\) impersonates scale \(s\). Define \[W_{\mathrm{imp}} := \sum_{C\in\Phi_{\le3}}\sum_{r=1}^{|C|} |\mathcal{I}(C,r)| = \sum_{C\in\Phi_{\le3}}\sum_{r=1}^{|C|} \sum_{\substack{s\text{ nonempty}\\s\neq a(C,r)}} \mathbf{1}[\mathsf{Imp}^{s}_{C,r}].\] Thus \(W_{\mathrm{imp}}\) counts all endpoint-scale pairs that may contribute to a wrong queried scale. It may count too many endpoint-scale pairs, but it does not miss any endpoint-scale pair that gives a nonzero contribution to a wrong queried scale.

Let \(W_{\mathrm{of}}\) be the total tagged weight of short-clause endpoints whose true scale \(a(C,r)\) satisfies \(2D_{a(C,r)}\ge\kappa\) and whose sampled positive-prefix count at that scale is at least \(\kappa\): \[W_{\mathrm{of}} := \sum_{C\in\Phi_{\le3}}\sum_{r=1}^{|C|} w_{|C|}\, \mathbf{1}\!\left[ 2D_{a(C,r)}\ge\kappa \text{ and } s_{v_r(C)}^{\le C}\ge\kappa \right].\]

The expectations in the next two auxiliary bounds are over the public randomness before \(\omega\) is fixed. After these bounds, expectations again follow the convention stated at the start of the proof.

The same geometric argument also bounds the number of scales in \(\mathcal{R}(C,r)\): there is a constant \(C^{\mathrm{sc}}_\varepsilon>0\) such that \[\label{eq:maxksat-visible-scale-count} |\mathcal{R}(C,r)| \le C^{\mathrm{sc}}_\varepsilon\log(K_{\mathrm{base}}+2) \qquad\text{for every endpoint } (C,r).\tag{18}\] Indeed, applying the same argument to a fixed endpoint \((C,r)\), with \(d=d^{\le C}_{v_r(C)}\), shows that low-degree wrong scales contribute only \(O_\varepsilon(1)\) possibilities, while the bound above leaves only \(O_\varepsilon(\log(K_{\mathrm{base}}+2))\) possible high-degree scales.

On \(\mathcal{G}\), Lemma 8 says that each queried label is live exactly when its threshold inequality is true. The bounds for fixed coordinates proved in 13 , 15 , 16 , and 17 give the following facts:

1. every high-degree one-endpoint coordinate output is unbiased for its true coordinate;

2. a low-degree one-endpoint coordinate output can differ from its target only when the queried endpoint satisfies the impersonation condition for the queried scale;

3. a two-endpoint coordinate output can differ from its target only when an endpoint satisfies the impersonation condition for one of the queried scales, or when a true high-degree endpoint overflows.

We now combine these fixed-coordinate bounds into a bound for the full linear form. Recall that \(\mathsf{Tgt}^{\ell,j,\alpha}_{C}\) denotes the event that \(C\) is the target-type for \(U^{(a)}_{\ell,j,\alpha}\); \(\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}\) denotes the event that \(C\) is the target-type for \(P^{(a,b)}_{\ell,j,t,\alpha,\beta}\).

5.4.0.1 One-endpoint contribution.

The high-degree one-endpoint coordinates are unbiased, and the counter \(M_3\) is exact on \(\mathcal{G}\). Therefore only the low-degree one-endpoint coordinates can contribute here. 15 gives, for every fixed low-degree coordinate \((\ell,j,\alpha,a)\), \[\left| \mathbb{E}\!\left[\widehat U^{(a)}_{\ell,j,\alpha}\right] - U^{(a)}_{\ell,j,\alpha} \right| \le \sum_{C\in\Phi_{\le3}} \mathbf{1}\!\left[ \mathsf{Tgt}^{\ell,j,\alpha}_{C} \right]\cdot\mathbf{1}\left[\mathsf{Imp}^{a}_{C,j}\right].\]

Fix an event that \((C,r)\) impersonates scale \(a\), where \(a\) is a wrong queried scale in \(\mathcal{I}(C,r)\). Once the clause length, the endpoint position, and the sign of that literal are fixed, only a constant number of one-endpoint coordinates can use this event: the bucket index ranges over a constant-size set, and the coefficients \(q_\alpha\) and \(u_j(\alpha)\) in 4 are fixed constants. Therefore there is a constant \(C^{\mathrm{one}}_\varepsilon>0\) such that the total weighted one-endpoint error is at most \(C^{\mathrm{one}}_\varepsilon W_{\mathrm{imp}}\).

5.4.0.2 Two-endpoint error from wrong scale pairs.

16 and 17 give, for every fixed coordinate \((\ell,j,t,\alpha,\beta,a,b)\),

\[\begin{align} &\left| \mathbb{E}\bigl[ \widehat P^{(a,b)}_{\ell,j,t,\alpha,\beta} \bigr] - P^{(a,b)}_{\ell,j,t,\alpha,\beta} \right|\\ &\qquad\le \sum_{C\in\Phi_{\le3}} \mathbf{1}[\mathsf{Tgt}^{\ell,j,t,\alpha,\beta}_{C}]\Bigl( \mathbf{1}[\mathsf{Imp}^{a}_{C,j}] +\mathbf{1}[\mathsf{Imp}^{b}_{C,t}] +\mathbf{1}[a=a(C,j),\;D_a\ge\kappa/2,\;s^{\le C}_{v_j(C)}\ge\kappa]\\&\qquad\qquad\qquad\qquad\qquad\qquad +\mathbf{1}[b=a(C,t),\;D_b\ge\kappa/2,\;s^{\le C}_{v_t(C)}\ge\kappa] \Bigr). \end{align}\] We first sum the part caused by endpoints counted by the impersonation condition for a scale that is not their true scale.

Fix a clause \(C\) and one ordered pair of relevant endpoints \((C,j)\) and \((C,t)\) with \(1\le j<t\le |C|\). A queried scale pair \((a,b)\) can receive a nonzero term from this clause even though \((a,b)\) is not the true scale pair only in one of the following two ways:

• the first endpoint impersonates the queried first scale, so \(a\in\mathcal{I}(C,j)\), while the second queried scale must still belong to \(\mathcal{R}(C,t)\);

• the second endpoint impersonates the queried second scale, so \(b\in\mathcal{I}(C,t)\), while the first queried scale must belong to \(\mathcal{R}(C,j)\).

Hence the total number of queried scale pairs that can receive such an extra nonzero term from this ordered pair is at most \[|\mathcal{I}(C,j)|\,|\mathcal{R}(C,t)| + |\mathcal{I}(C,t)|\,|\mathcal{R}(C,j)|.\] Using 18 , this is at most \[C^{\mathrm{sc}}_\varepsilon\log(K_{\mathrm{base}}+2) \bigl(|\mathcal{I}(C,j)|+|\mathcal{I}(C,t)|\bigr).\] The clause length, the ordered pair \((j,t)\), and the bucket indices \((\alpha,\beta)\) all range over constant-size sets, and the coefficients in 4 are fixed constants. Therefore there is a constant \(C^{\mathrm{two}}_\varepsilon>0\) such that the total weighted wrong-scale error in all two-endpoint coordinates is at most \[C^{\mathrm{two}}_\varepsilon\log(K_{\mathrm{base}}+2)\,W_{\mathrm{imp}}.\]

5.4.0.3 Overflow contribution.

The weight \(W_{\mathrm{of}}\) counts the high-degree endpoints whose sampled positive-prefix count is at least \(\kappa\). Overflow does not affect one-endpoint coordinates. For two-endpoint coordinates, an overflowing endpoint matters only on its true queried scale, not on wrong scales. Therefore each overflowing endpoint can affect only the constantly many true two-endpoint coordinates that use that endpoint inside its clause. Since all coefficients in 4 are fixed constants, there is a constant \(C_{\mathrm{of}}>0\) such that the total weighted overflow error is at most \(C_{\mathrm{of}}W_{\mathrm{of}}\).

Combining the one-endpoint, two-endpoint, and overflow bounds, there is a constant \(C_{\mathrm{imp}}=O_\varepsilon(\log(K_{\mathrm{base}}+2))\) such that for every \(\omega\in\mathcal{G}\), \[\label{eq:maxksat-one-run-mean} \left| \mathbb{E}[Z\mid \omega] - L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) \right| \le C_{\mathrm{imp}}W_{\mathrm{imp}} + C_{\mathrm{of}}W_{\mathrm{of}}.\tag{19}\]

Choose \(K_{\mathrm{base}}\) large enough so that the \(O_\varepsilon(\log^2(K_{\mathrm{base}}+2)/K_{\mathrm{base}})\) bound from Lemma 13 gives \[C_{\mathrm{imp}}\,\mathbb{E}[W_{\mathrm{imp}}] \le \frac{\varepsilon m}{320}, \qquad\text{hence}\qquad \mathbb{E}[W_{\mathrm{imp}}]\le \frac{\varepsilon m}{320C_{\mathrm{imp}}}.\] The initial choice of \(\kappa=\operatorname{poly}(1/\varepsilon)\) also ensures \[\mathbb{E}[W_{\mathrm{of}}]\le \frac{\varepsilon m}{320C_{\mathrm{of}}};\] this follows from Lemma 12.

Now define \[\mathcal{S} := \left\{ W_{\mathrm{imp}}\le \frac{\varepsilon m}{4C_{\mathrm{imp}}} \right\}, \text{ and } \mathcal{O} := \left\{ W_{\mathrm{of}}\le \frac{\varepsilon m}{4C_{\mathrm{of}}} \right\}.\] By Markov’s inequality, \[\Pr[\mathcal{S}^c]\le \frac{1}{80}, \text{ and } \Pr[\mathcal{O}^c]\le \frac{1}{80}.\] On \(\mathcal{S}\cap\mathcal{O}\), 19 gives \[\label{eq:maxksat-one-run-mean-small} \left| \mathbb{E}[Z\mid \omega] - L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) \right| \le \frac{\varepsilon m}{2} \qquad \text{for every }\omega\in\mathcal{G}\cap\mathcal{S}\cap\mathcal{O}.\tag{20}\]

We now bound the variance of one full run, still with the public randomness fixed. There are \(A=O(\log (n+m))\) scales. The number of one-endpoint coordinates is \(O(\log (n+m))\), and the number of two-endpoint coordinates is \(O(\log^2 (n+m))\), because the clause lengths, endpoint positions, signs, and bucket indices all range over constant-size sets.

For a fixed coordinate, the number of elementary sub-sketches is \(O_\varepsilon(1)\): for one-endpoint coordinates it is \(2\kappa+2\), and for two-endpoint coordinates it is \(4|\Sigma_a||\Sigma_b|=O_\varepsilon(1)\). Every elementary sub-sketch outputs either \(0\) or a number whose absolute value is at most \(M=O_\varepsilon(m)\). Hence the output for one fixed coordinate has variance \(O_\varepsilon(m^2)\). Since different coordinates use independent work registers, \[\label{eq:maxksat-one-run-var} \operatorname{Var}(Z\mid \omega)=O_\varepsilon(m^2\log^2 (n+m)) \qquad \text{for every }\omega\in\mathcal{G}.\tag{21}\]

Take \(R=C^{\mathrm{rep}}_\varepsilon\log^2 (n+m)\) independent full runs, in parallel during the same pass, with the same public randomness \(\omega\), and average their outputs: \[\overline{Z}:=\frac{1}{R}\sum_{r=1}^R Z_r.\] Then, for every \(\omega\in\mathcal{G}\), \[\mathbb{E}[\overline{Z}\mid \omega] = \mathbb{E}[Z\mid \omega], \text{ and } \operatorname{Var}(\overline{Z}\mid \omega)=O_\varepsilon(m^2).\] Choosing \(C^{\mathrm{rep}}_\varepsilon\) large enough, Chebyshev’s inequality gives \[\Pr\left[ \left| \overline{Z}-\mathbb{E}[Z\mid \omega] \right|>\frac{\varepsilon m}{4} \;\middle|\;\omega \right] \le \frac{1}{40} \qquad \text{for every }\omega\in\mathcal{G}.\] Hence on the event \(\mathcal{G}\cap\mathcal{S}\cap\mathcal{O}\cap \{|\overline{Z}-\mathbb{E}[Z\mid\omega]|\le \varepsilon m/4\}\), the triangle inequality and 20 give \[\left| \overline{Z}-L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) \right| \le \frac{3\varepsilon m}{4}<\varepsilon m.\]

Also, as shown above, \[\Pr[\mathcal{G}^c]\le \frac{1}{80}.\] Even on \(\mathcal{G}^c\), the algorithm still runs legally. What fails there is only the estimation guarantee stated above. Therefore \[\begin{align} &\Pr\left[ \left| \overline{Z}-L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) \right|>\varepsilon m \right]\\ &\qquad\le \Pr[\mathcal{G}^c] + \Pr[\mathcal{S}^c] + \Pr[\mathcal{O}^c] + \mathbb{E}_\omega\!\left[ \mathbf{1}[\omega\in\mathcal{G}\cap\mathcal{S}\cap\mathcal{O}] \Pr\left[ \left| \overline{Z}-\mathbb{E}[Z\mid \omega] \right|>\frac{\varepsilon m}{4} \;\middle|\;\omega \right] \right]. \end{align}\] Using the four bounds above, \[\Pr\left[ \left| \overline{Z}-L_{\le3}(\operatorname{WPsSnap}(\Phi_{\le3})) \right|>\varepsilon m \right] \le \frac{1}{80} + \frac{1}{80} + \frac{1}{80} + \frac{1}{40} = \frac{1}{16}.\] So the averaged output \(\widehat L_{\le3}:=\overline{Z}\) succeeds with probability at least \(15/16\).

5.4.0.4 Space complexity.

One sub-sketch uses a quantum register of size \(O(\log (n+m))\) qubits and, after a successful query, only \(O(\log (n+m))\) additional classical bits for storing the variable name, the relevant indices, and the suffix total/positive degree. One full run contains \(O_\varepsilon(\log^2 (n+m))\) elementary sub-sketches, so one full run uses \(O_\varepsilon(\log^3 (n+m))\) qubits and the same order of classical working bits. The averaging factor \(R=\Theta_\varepsilon(\log^2 (n+m))\) multiplies this by another factor \(\Theta_\varepsilon(\log^2 (n+m))\). Therefore, the overall algorithm uses \(O_\varepsilon(\log^5 (n+m))\) qubits, and the classical working space is of the same asymptotic order. Public random coins are shared and are not charged to the working space, as in the rest of the paper. This proves Lemma 6.

6 Quantum algorithm for Max-\(k\)SAT↩︎

We now prove the main theorem.

7 Quantum space lower bound for Max-\(k\)SAT↩︎

We use the following promise-gap form of the quantum streaming lower bound for Max-Cut of Kallaugher and Parekh [20].

8 Exact finite LP certificate for Max-\(k\)SAT↩︎

The proof of Lemma 1 uses a finite rational certificate. The complete certificate data and verifier are available in the repository: https://github.com/Guangxu-Yang/maxksat-lp-certificate.

The verifier contains the exact rational data \[\mathcal{I},\quad r,\quad c_0,\quad \{u_j\}_{j=1}^3,\quad \{p_{jt}\}_{1\le j<t\le3},\quad \{\lambda^{\rm lo}_{i,\tau},\lambda^{\rm up}_{i,\tau}\}_{i,\tau}.\] All arithmetic in the verifier is performed over \(\mathbb{Q}\), using rational integer numerators and denominators. Floating-point numbers are printed only for readability. The bucket partition and rounding vector used by the certificate are \[\begin{array}{c|c|c} i & I_i & r_i\\ \hline 0 & [-1,-3/4) & 0.27083\\ 1 & [-3/4,-1/2) & 0.27083\\ 2 & [-1/2,-1/4) & 0.27083\\ 3 & [-1/4,0) & 0.4069\\ 4 & [0,1/4) & 0.5931\\ 5 & [1/4,1/2) & 0.72917\\ 6 & [1/2,3/4) & 0.72917\\ 7 & [3/4,1] & 0.72917 . \end{array}\] Thus \(L=8\), and the final bucket is closed at \(1\). As in Definition 3, a positive literal in bucket \(I_i\) is satisfied by the independent rounding with probability \(r_i\), and a negative literal in bucket \(I_i\) is satisfied with probability \(1-r_i\). We use codes to check all inequalities exactly over \(\mathbb{Q}\). We can get \(\rho=0.717275\).

9 Finite LP certificate for approximation ratio of Max-2OR↩︎

We only focus on the step that reduces Max-\(2\)OR to the problem of estimating a snapshot. This appendix improves only the approximation constant for the Max-2OR; the streaming and quantum estimation arguments are inherited from the Max-\(k\)SAT framework.

The optimization is instead over a Max-2SAT-specific rounding certificate: the unary endpoint coefficient, the nonuniform bias partition, and the finite list of nine rounding profiles are chosen so that the best profile certifiably beats every feasible mixture of unary and binary typed atoms.

We consider simplified unweighted Max-2SAT instances, meaning finite multisets of unary clauses \((x_v=s)\) and binary clauses \((x_u=s)\vee(x_v=t)\) with \(s,t\in\{+,-\}\), after replacing repeated-literal binary clauses by the corresponding unary clause and removing tautologies. Let \(|\Phi|\) denote the number of remaining clauses.

Before defining the "snapshot" of instances, we first define the bias of the variables in \(\Phi\). The certificate uses the unary endpoint coefficient \(w_{\mathrm u}:=\frac{67}{20}\); this is part of the bias definition, not an input clause weight.

Fix the nonuniform partition\(-1=t_0<t_1<\cdots<t_{450}=1\) from the artifact file ⁵. Let \(I_i=[t_i,t_{i+1})\quad (0\le i\le 448)\) and \(I_{449}=[t_{449},t_{450}]\).

Now, we can define the snapshot score.

We use nine profiles rather than one because no single oblivious rounding curve is best for all mixtures of unary and binary clauses. The profiles are fixed in advance by the certificate. Each \(A_r\) is the expected number of satisfied clauses under the corresponding independent rounding rule, expressed as a linear function of the snapshot; \(A_{\max}\) then chooses the best of these constant many certified rules.

References↩︎

---

1. Penn State University. Email: hjw5492@psu.edu.↩︎

2. University of Southern California. Email: guangxuy@usc.edu. Research supported by NSF CAREER award 2141536.↩︎

3. Our focus is on demonstrating a quantum advantage rather than optimizing the ration \(\rho=0.7172\); better score functions and more involved quantum operations may further improve the approximation ratio.↩︎

4. Under the certified rounding vector \(r^*\), recorded in Appendix 8, every literal is satisfied with probability at least \(0.27083\)↩︎

5. in the codes↩︎

6. The file↩︎

7. in codes↩︎