# QSETH strikes again: finer quantum lower bounds for lattice problem, strong
simulation, hitting set problem, and more

Yanlin Chen Centrum Wiskunde and Informatica (QuSoft<EMAIL_ADDRESS>Yilei Chen
Tsinghua University<EMAIL_ADDRESS>Rajendra Kumar Weizmann Institute
of Science<EMAIL_ADDRESS>Subhasree Patro Utrecht University and Centrum
Wiskunde and Informatica (QuSoft<EMAIL_ADDRESS>Florian Speelman
University of Amsterdam and QuSoft<EMAIL_ADDRESS>
###### Abstract

While seemingly undesirable, it is not a surprising fact that there are
certain problems for which quantum computers offer no computational advantage
over their respective classical counterparts. Moreover, there are problems for
which there is no ‘useful’ computational advantage possible with the current
quantum hardware [BMN+21]. This situation however can be beneficial if we
_don’t want_ quantum computers to solve certain problems fast - say problems
relevant to post-quantum cryptography. In such a situation, we would like to
have evidence that it is difficult to solve those problems on quantum
computers; _but what is their exact complexity?_

To do so one has to prove lower bounds, but proving unconditional time lower
bounds has never been easy. As a result, resorting to conditional lower bounds
has been quite popular in the classical community and is gaining momentum in
the quantum community. In this paper, by the use of the QSETH framework
[Buhrman-Patro-Speelman 2021], we are able to understand the quantum
complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or
counting-CNFSAT, and also are able to comment on the non-trivial complexity of
approximate-#CNFSAT; both of these have interesting implications about the
complexity of (variations of) lattice problems, strong simulation and hitting
set problem, and more.

In the process, we explore the QSETH framework in greater detail than was
(required and) discussed in the original paper, thus also serving as a useful
guide on how to effectively use the QSETH framework.

###### Contents

  1. 1 Introduction
  2. 2 Lower bounds for variants of CNFSAT using $\textsc{AC}^{0}_{2}$-QSETH
    1. 2.1 Quantum complexity of CNFSAT
    2. 2.2 Quantum complexity of #CNFSAT, $\oplus$CNFSAT, $\\#_{q}$CNFSAT and maj-CNFSAT
    3. 2.3 Quantum complexity of $\Delta$-add-#CNFSAT
    4. 2.4 Quantum complexity of $\gamma$-#CNFSAT and other related problems
    5. 2.5 Quantum complexity of $\\#$k-SAT and other related problems
  3. 3 Quantum strong simulation of quantum circuits
  4. 4 Quantum lower bound for lattice counting and q-count problems
  5. 5 Hardness of Counting/Parity of OV, Hitting Set, and Set-Cover
  6. 6 Discussions and open questions
  7. A Quantum upper bounds for strong simulation
  8. B Proof of Theorem 4.11

##  1 Introduction

A popular classical hardness conjecture known as the Strong Exponential Time-
Hypothesis (SETH) says determining whether an input CNF formula is satisfiable
or not cannot be done in time $O(2^{n(1-\varepsilon)})$ for any constant
$\varepsilon>0$ [IP01, IPZ01]. Several fine-grained lower bounds based on SETH
were shown ever since; see [Vas15, Wil18] for a summary of many such results.
Some of the SETH-hard problems are building blocks for fine-grained
cryptography [BRSV17, LLW19]. Following the introduction to SETH, hardness
assumptions for variations of CNFSAT, for e.g., $\oplus$SETH (conjecturing
complexity of parity CNFSAT, output of the parity of satisfying assignments to
input CNF formula), $\\#$SETH (conjectures complexity of counting CNFSAT,
output the count of the satisfying assignments), were also proposed and
several other fine-grained lower bounds based on these variants of SETH were
given [CDL+16].

When considering quantum computation the SETH conjecture is no longer true, as
one can, using Grover’s algorithm for unstructured search [Gro96], solve the
CNFSAT problem in $O(2^{\frac{n}{2}}\cdot\mathrm{poly}(n))$ time. However,
conjectures such as $\\#$SETH or $\oplus$SETH are likely to still hold in the
quantum setting because a Grover-like quantum speedup is not witnessed when
the task is to compute the total number of satisfying assignments or to
compute the parity of the total number of satisfying assignments. This
situation can in some cases be exploited to give better quantum lower bounds
than one would get from the conjectured quantum lower bound for the vanilla
CNFSAT problem. This makes it at least as relevant (if not more) to study
variants of CNFSAT and their implications in the quantum setting, as has been
done classically. In fact, motivated by this exact observation, Buhrman,
Patro, and Speelman [BPS21] introduced a framework of Quantum Strong
Exponential-Time Hypotheses (QSETH) as quantum analogues to SETH, with a
striking feature that allows one to ‘technically’ unify conjectures such as
quantum analogues of $\oplus$SETH, $\\#$SETH, maj-SETH, etc. under one
_umbrella_ conjecture.

In this paper, we use the QSETH framework to ‘generate’ natural variations of
QSETH such as $\oplus$QSETH, $\\#$QSETH, maj-QSETH, etc., which otherwise (in
our opinion) would already be acceptable standalone conjectures in the quantum
setting, and study some of their interesting implications. Additionally, we
also use the QSETH framework in proving _non-trivial_ quantum lower bounds for
approximately counting the number of satisfying assignments to CNF formulas, a
problem whose complexity has been of interest in the classical setting [DL21];
we study its quantum implications. See Section 2 for details. Proof of this
result follows from a more detailed exploration of the QSETH framework than
what was required in the original paper. Thus, as another contribution of this
paper, we present a useful guide on how to effectively use the QSETH
framework.

#### The QSETH framework

In their framework, Buhrman et al. consider the problem in which one is given
formula or circuit representation of a Boolean function
$f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
is asked whether a property $P\mathrel{\mathop{\mathchar
58\relax}}\mathcal{D}\subseteq\\{0,1\\}^{2^{n}}\rightarrow\\{0,1\\}$ on the
truth table111Truth table of a formula $\phi$ on $n$ variables, denoted by
$tt(\phi)$, is a $2^{n}$ bit string derived in the following way
$tt(\phi)=\bigcirc_{a\in\\{0,1\\}^{n}}\phi(a)$; the symbol $\circ$ denotes
concatenation. of this formula evaluates to $1$. They conjectured that when
the circuit representation is obfuscated enough then for most properties $P$
(that are compression-oblivious properties as we will see in Definition 1.1),
the time taken to compute $P$ on the truth table of $\mathrm{poly}(n)$-sized
circuits is lower bounded by $Q(P)$, i.e. the $1/3$-bounded error quantum
query complexity of $P$, on all bit strings of length $2^{n}$.

It is not hard to see that such a conjecture cannot be true for _all_
properties. In principle, one can construct properties for which the above
statement would not hold. For instance, consider a property $P$ that is
trivial on truth tables of small formulas (i.e., $\mathrm{poly}(n)$ size) but
complicated on formulas of longer length. These kinds of properties are likely
to have very high quantum query complexity, but in reality, it will be trivial
to compute such a $P$ on formulas of $\mathrm{poly}(n)$ size. In order to
prevent such scenarios the authors in [BPS21] introduce the notion of
compression-oblivious properties which they believe encompasses most of the
naturally occurring properties. See Sections 2.2 and 2.3 of their paper for a
detailed discussion on this topic. To give a bit of intuition, first consider
the set of truth tables corresponding to the set of $\mathrm{poly}(n)$ size
formulas on $n$ variables and consider the set of all the $2^{n}$ bit strings.
Compression-oblivious properties are those properties for which one cannot
save in computational time to compute them on a string from the former set in
comparison to computing the same property on strings from the latter set. More
formally,

######  Definition 1.1 (Compression Oblivious Properties [BPS21]).

Let $\Gamma$ denote a class of representation such as poly-sized depth-2
circuits or poly-sized circuits of a more complex class. Then _compression
oblivious_ properties corresponding to the class $\Gamma$, denoted by
$\mathcal{CO}(\Gamma)$, are the set of (partial or total) properties such that
time taken to compute $P$ on the truth table of the input circuit from
$\Gamma$ is at least the quantum query complexity of $P$ on all strings, i.e.
$\Omega(Q(P)^{1-\alpha})$ for all constants $\alpha>0$.

With that, they conjecture the following.

######  Conjecture 1.2 (QSETH framework [BPS21]).

For each class of representations such as poly-sized depth-2 circuits or poly-
sized circuits of a more complex class, let us denote by $\Gamma$, for all
compression oblivious properties $P$ of class $\Gamma$, given a circuit
$C\in\Gamma$ the time taken to compute $P$ on the truth table of $C$ is at
least $\Omega(Q(P)^{1-\alpha})$ for all constants $\alpha>0$.

It is good to note that the QSETH framework allows us to consider formulas of
complicated classes, however, taking $\Gamma$ as the class of all poly-sized
CNF or DNF formulas suffices for the results presented in this paper.
Therefore, using $\textsc{AC}^{0}_{2}$ to denote the class of all poly-sized
CNF and DNF formulas, we define $\textsc{AC}^{0}_{2}$-QSETH as the following
conjecture and use this as the main conjecture of our paper.

######  Conjecture 1.3 ($\textsc{AC}^{0}_{2}$-QSETH).

For all compression oblivious properties
$P\in\mathcal{CO}(\textsc{AC}^{0}_{2})$, given a circuit
$C\in\textsc{AC}^{0}_{2}$ the time taken to compute $P$ on the truth table of
$C$ is at least $\Omega(Q(P)^{1-\alpha})$ for all constants $\alpha>0$.

One can now _almost_ directly use $\textsc{AC}^{0}_{2}$-QSETH instead of the
general QSETH framework to understand the hardness of computing certain
properties on truth tables of CNF formulas. The emphasis on almost is because
of the following two reasons: firstly, there are certain properties that might
be easy on CNF formulas and hard on DNF formulas which one has to formally
verify, and secondly, one needs to ensure that the property we are interested
in is compression oblivious. Moreover, for properties defined on $N$ bit
strings that can be computed in $\mathrm{polylog}(N)$ space and have quantum
query complexity $\widetilde{\omega}(\sqrt{N})$ it is not easy to show that
they are compression oblivious, as doing so would separate P from PSPACE; see
Theorem 9 in [BPS21] for more details. This means even for natural properties
such as count or parity one cannot easily check if they are compression
oblivious. In such situations, we resort to conjecturing that the property is
compression oblivious. See Figure 1 for a step-by-step guide on how we use the
QSETH framework in a plug-and-play fashion.

In comparison to the original QSETH paper where the framework was introduced
and applied to a more complex class of formulas,222The authors in [BPS21]
extensively used QSETH framework for branching programs or equivalently NC
circuits to show non-trivial lower bounds for edit distance and longest common
subsequence problems. this paper instead serves as a guide to using QSETH for
the lowest level of formulas, i.e., poly-sized CNF and DNF formulas, in a more
elaborate fashion.

Problem | Variants | Quantum lower bound | Reference
---|---|---|---
CNFSAT | Vanilla | $2^{\frac{n}{2}-o(n)}$ | Corollary 2.1
Parity | $2^{n-o(n)}$ | Corollary 2.7
Majority | $2^{n-o(n)}$ | Corollary 2.8
Strict Majority | $2^{n-o(n)}$ | Corollary 2.8
| Count | $2^{n-o(n)}$ | Theorem 2.6
| $\text{Count}_{q}$ | $2^{n-o(n)}$ | Corollary 2.10
|  $\Delta$-Additive error | $\left(\sqrt{\frac{2^{n}}{\Delta}}+\frac{\sqrt{\hat{h}(2^{n}-\hat{h})}}{\Delta}\right)^{1-o(1)}$ | Theorem 2.15
|  $\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Theorem 2.21
$k$-SAT $k=\Theta(\log(n))$ | Vanilla | $2^{\frac{n}{2}-o(n)}$ |  Section 4, [ACL+20]
Parity | $2^{n-o(n)}$ | Corollary 2.24
| Count | $2^{n-o(n)}$ | Corollary 2.24
| $\text{Count}_{q}$ | $2^{n-o(n)}$ | Corollary 2.24
|  $\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Corollary 2.25
Table 1: Overview of conditional lower bounds for variants of CNFSAT and $k$-SAT. The variable $\hat{h}$ in the above table is an arbitrary natural number satisfying $\gamma\hat{h}\geq 1$. The multiplicative approximation factor $\gamma$ is between $2^{-n}$ to $1$, and the additive approximate factor $\Delta$ is between $2^{-1}$ to $2^{n}$. Problem | Variants | Quantum lower bound | Reference
---|---|---|---
Strong Simulation | Exact (with $n$ bits precision) | $2^{n-o(n)}$ | Theorem 3.2
Exact (with $2$ bits precision) | $2^{n-o(n)}$ | Corollary 3.3
|  $\Delta$-Additive error | $\left(\sqrt{\frac{1}{\Delta}}+\frac{\sqrt{\hat{h}(2^{n}-\hat{h})}}{2^{n}\Delta}\right)^{1-o(1)}$ | Corollary 3.5
|  $\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Theorem 3.7
CVPp for $p\notin 2\mathbb{Z}$ |  | $2^{\frac{n}{2}-o(n)}$ | Section 4
Lattice Counting (for non-even norm) | Vanilla | $2^{n-o(n)}$ | Corollary 4.7
$\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Corollary 4.8
|  $q$-count | $2^{n-o(n)}$ | Corollary 4.10
Orthogonal Vectors | Vanilla | $n^{1-o(1)}$ | [ACL+20, BPS21]
Parity | $n^{2-o(1)}$ | Corollary 5.7
| Count | $n^{2-o(1)}$ | Corollary 5.7
|  $\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{n^{2}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Corollary 5.7
Hitting Set | Vanilla | $2^{\frac{n}{2}-o(n)}$ | Corollary 5.4
Parity | $2^{n-o(n)}$ | Corollary 5.4
| Count | $2^{n-o(n)}$ | Corollary 5.4
|  $\gamma$-Multiplicative factor | $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-o(1)}$ | Corollary 5.4
$\oplus$Set Cover |  | $2^{n-o(n)}$ | Corollary 5.9
Table 2: Overview of lower bounds based on $\textsc{AC}^{0}_{2}$-QSETH. The
variable $\hat{h}$ in the above table is an arbitrary natural number
satisfying $\gamma\hat{h}\geq 1$. The multiplicative approximation factor
$\gamma$ is between $2^{-n}$ to $1$, while the additive approximate factor
$\Delta$ is between $2^{-n-1}$ to $1$.

#### Summary and technical overview

  * •

We zoom into Buhrman et al.’s QSETH framework at the lowest-level formula
class, i.e., the class of polynomial-size CNFs and DNFs, and use it to study
the quantum complexity of variations of CNFSAT problems. The QSETH framework
is quite general which also makes it not entirely trivial to use it thus, we
present a useful guide on how to effectively use the
$\textsc{AC}^{0}_{2}$-QSETH conjecture, for e.g., what lemmas need to be
proved and what assumptions are needed to be made in order to understand the
quantum complexity of CNFSAT and its variants; see Figure 1.

  * •

We can categorise the several variants of CNFSAT in two ways. First
classification can be done by the width of the CNF formulas, i.e., $k$-CNFs
versus CNFs of unbounded clause length; second, by the property of the truth
table one needs to compute. See the summary of all the variants and their
respective quantum time lower bounds in Table 1 and see below for the overview
of the techniques used.

    * –

To prove the quantum time lower bounds for the property variants of CNFSAT
problem we invoke $\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3). But,
$\textsc{AC}^{0}_{2}$-QSETH conjectures the hardness of properties on a set of
CNF and DNF formulas. For properties like count, parity, majority, etc., it
easily follows from De Morgan’s laws that these properties are equally hard on
both CNF and DNF formulas. However, such arguments no longer hold when the
properties are approximate variants of count for which we give nontrivial
proofs; see Sections 2.3 and 2.4.

    * –

Additionally, we also use $\textsc{AC}^{0}_{2}$-QSETH to understand quantum
complexity of $k$-SAT and its property variants. As a first step we study the
classical reduction from CNFSAT to $k$-SAT given by [CIP06] and observe that
the $2^{\frac{n}{2}}$ quantum lower bound for k-SAT, for $k=\Theta(\log n)$,
follows from the quantum lower bound of CNFSAT. Moreover, we make an important
observation that this reduction by [CIP06] is count-preserving333Should not be
mistaken to be parsimonious, see Section 2.5 for details. and can be used to
conclude lower bounds for other counting variants of $k$-SAT. See Table 1 for
the summary of these bounds.

  * •

Having (somewhat) understood the complexities of the above-mentioned variants
of CNFSAT, we then prove conditional quantum time lower bounds for lattice
problem, strong simulation, orthogonal vectors, set cover, hitting set
problem, and their respective variants; see Table 2.

    * –

The quantum $2^{\frac{n}{2}}$ time lower bound we present for $\text{CVP}_{p}$
(for $p\notin 2\mathbb{Z}$) follows from a reduction from $k$-SAT to
$\text{CVP}_{p}$ by [BGS17, ABGS21] and from the hardness result of $k$-SAT we
present. Though such a result would also trivially follow by using Aaronson et
al.’s version of QSETH, we stress that our hardness result of $k$-SAT is based
on basic-QSETH which is a more believable conjecture.444If basic-QSETH from
Buhrman et al.’s framework is false then Aaronson et al’s QSETH is also false,
but the implication in the other direction is not obvious.

    * –

Additionally, we also discuss the quantum complexity of the lattice counting
problem (for non-even norm). We present a reduction, using a similar idea of
[BGS17], from $\\#k$-SAT to the lattice counting problem and we show a $2^{n}$
time quantum lower bound for the latter when $k=\Theta(\log n)$. As mentioned
earlier, we get a $2^{n}$ time quantum lower bound for $\\#k$-SAT, when
$k=\Theta(\log n)$, using $\textsc{AC}^{0}_{2}$-QSETH.

    * –

As another application to the bounds we get from the property variants of
CNFSAT we look at the strong simulation problem. It was already established by
[CHM21, VDN10] that strong simulation of quantum circuit is a #P-hard problem
but in this work we give exact lower bounds for the same. Additionally, using
the lower bounds of approximate counts of CNFSAT we are able to shed light on
how hard it is to quantumly solve the strong simulation problem with additive
and multiplicative error approximation.

    * –

Last but not least, we are also able to use the lower bounds for the property
variants of CNFSAT to give interesting lower bounds for orthogonal vectors,
hitting set problem and their respective variants. See Section 5 for more
details.

#### Related work

Our paper is a follow-up work to the original QSETH paper by [BPS21]; also the
list of problems for which we show lower bounds does not overlap with the
problems studied in [BPS21]. A basic version of QSETH was also introduced by
Aaronson et al. [ACL+20] where they primarily used it to study the quantum
complexity of closest pair and bichromatic pair problems; they also discuss
the complexity of the (vanilla version of) orthogonal vector problem. Prior to
this work, a quantum hitting set conjecture was proposed and its implications
were discussed in Schoneveld’s bachelor thesis [Sch22] but their definition of
hitting set is different from ours. In our work, we observe that the
parsimonious reduction from CNFSAT to hitting set (Definition 5.1) given by
[CDL+16] is easily quantizable, using which we get a QSETH-based lower bound.

#### Structure of our paper

In Section 2, we discuss the quantum complexity of variants of CNFSAT
problems, for e.g. #CNFSAT, $\oplus$CNFSAT, $\gamma$-#CNFSAT, etc.,
conditional on $\textsc{AC}^{0}_{2}$-QSETH. The broad idea to show the
hardness results of these variants is quite similar; the _several_ lemmas only
account for the properties being different. Using results from Section 2, we
show quantum time lower bounds for strong simulation problem in Section 3,
lattice problems in Section 4, and orthogonal vectors, hitting set and set
cover in Section 5. We conclude with open questions and future directions in
Section 6. The appendix section of this paper contains proofs of theorems that
are long to state or lemmas of observational nature.

StartFor a given property P show the quantum time complexity of P-CNFSATInvoke
$\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) Easy to show
$\textsc{P}\in\mathcal{CO}(\textsc{AC}_{2}^{0})$? See Theorem 9 in [BPS21].
Conjecture compression obliviousness of PProve it Is
$\textsc{P}\in\mathcal{CO}(\textsc{AC}_{2}^{0})$ (provably or in conjecture)?
Cannot use $\textsc{AC}^{0}_{2}$-QSETH for PCompute the bounded error quantum
query complexity of P, i.e. $Q_{\varepsilon}(\textsc{P})$ with
$\varepsilon=\frac{1}{3}$Quantum time lower bound for computing P on CNF and
DNF is $\Omega((Q_{\varepsilon}(\textsc{P}))^{1-\alpha})$ for all $\alpha>0$
Are CNFs at least harder in comparison to DNFs for computing P Cannot comment
on hardness of P-CNFSATComplexity of P-CNFSAT is
$\Omega((Q_{\varepsilon}(\textsc{P}))^{1-\alpha})$ for all $\alpha>0$, under
$\textsc{AC}^{0}_{2}$-QSETHEndYesNoNoYesNoYes

Figure 1: Step-by-step guide on how to use the QSETH framework in a plug-n-
play manner to show hardness results for P-CNFSAT. Here P can be any (partial
or total) Boolean property.

##  2 Lower bounds for variants of CNFSAT using $\textsc{AC}^{0}_{2}$-QSETH

We will now define several variants of CNFSAT problem and using
$\textsc{AC}^{0}_{2}$-QSETH understand the quantum complexity of all of them.
The consequences of these hardness results, some of which follow immediately
and the rest with some work, will be discussed in Sections 3, 4 and 5. We
begin with some common variants of CNFSAT problem which are also very well
studied classically [CDL+16]; we do this in Section 2.2. And, proceed with
some less popular variants (Sections 2.3, 2.4 and 2.5) but with interesting
consequences (presented in Sections 3, 4 and 5).

###  2.1 Quantum complexity of CNFSAT

We first restate the quantum hardness of CNFSAT before delving into showing
hardness results for its other variants. Interestingly, for the property
$\textsc{OR}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow\\{0,1\\}$, where for
$x\in\\{0,1\\}^{2^{n}}$ we define $\textsc{OR}(x)=1$ if $|x|\geq 1$ and
$\textsc{OR}(x)=0$ whenever $|x|=0$, we can explicitly prove that
$\textsc{OR}{}\in\mathcal{CO}(AC_{2}^{0})$ in the following way: The
adversarial set $\\{x\mathrel{\mathop{\mathchar
58\relax}}x\in\\{0,1\\}^{2^{n}}\text{ and }|x|\in\\{0,1\\}\\}$ gives the tight
query bound for the property OR are truth tables of functions that can be
represented by $O(n)$ sized CNF formulas. Namely, these are given by the
formulas that accept a single possible input, which can be constructed by
using $n$ clauses that each contain a single variable or its negation. Also,
note that computing OR on truth tables of DNF formulas of $\mathrm{poly}(n)$
length can be computed in $\mathrm{poly}(n)$ time. Hence, using
$\textsc{AC}^{0}_{2}$-QSETH we can recover the following Basic-QSETH
conjecture.

######  Corollary 2.1 (Basic-QSETH [BPS21]).

If $\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) is true then there is no
bounded error quantum algorithm that solves CNFSAT on $n$ variables and $m$
clauses in $O\left(2^{\frac{n(1-\delta)}{2}}m^{O(1)}\right)$ time, for any
$\delta>0$.

###  2.2 Quantum complexity of #CNFSAT, $\oplus$CNFSAT, $\\#_{q}$CNFSAT and
maj-CNFSAT

######  Definition 2.2.

Some popular variants of CNFSAT.

  1. 1.

#CNFSAT: Given a CNF formula $\phi$ on $n$ input variables, output $t$ where
$t=|\\{x\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{n}\text{ and
}\phi(x)=1\\}|$ is the number of satisfying assignments to $\phi$.

  2. 2.

$\oplus$CNFSAT: Given a CNF formula $\phi$ on $n$ input variables, output $t$
where $t=|\\{x\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{n}\text{ and
}\phi(x)=1\\}|\mod 2$ is the parity of the number of satisfying assignments to
$\phi$.

  3. 3.

$\\#_{q}$CNFSAT: Given a CNF formula $\phi$ on $n$ input variables and an
integer $q\in[2^{n}]\setminus\\{1\\}$, output $t$ where
$t=|\\{x\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{n}\text{ and
}\phi(x)=1\\}|\mod q$ is the $q$-count of the number of satisfying assignments
to $\phi$.

  4. 4.

maj-CNFSAT: Given a CNF formula $\phi$ on $n$ input variables, output if
majority of the assignments satisfy $\phi$, i.e., if
$t=|\\{x\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{n}\text{ and
}\phi(x)=1\\}|$ output $1$ if $t\geq 2^{n-1}$ else output $0$.

  5. 5.

st-maj-CNFSAT: Given a CNF formula $\phi$ on $n$ input variables, output if a
strict majority of the assignments satisfy $\phi$, i.e., if
$t=|\\{x\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{n}\text{ and
}\phi(x)=1\\}|$ output $1$ if $t>2^{n-1}$ else output $0$.

We now define the Boolean properties corresponding to items in Definition 2.2
for completeness.555Note that the QSETH framework though is defined on
properties with Boolean outcomes it can be used for non-Boolean properties
like count or $\gamma$-count as we can instead consider the threshold versions
of these properties which are Boolean. In fact, we will soon see the inner
working of all our hardness results actually rely on Boolean properties.

######  Definition 2.3.

Some popular properties defined on Boolean bit strings.

  1. 1.

count: Let $\textsc{count}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow[N]\cup\\{0\\}$ be a non-Boolean function
such that $\textsc{count}{}(x)=|\\{i\mathrel{\mathop{\mathchar
58\relax}}x\in\\{0,1\\}^{N}\text{ and }x_{i}=1\\}|$.

  2. 2.

parity: Let $\textsc{parity}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ be a Boolean function with
$\textsc{parity}{}(x)=|\\{i\mathrel{\mathop{\mathchar
58\relax}}x\in\\{0,1\\}^{N}\text{ and }x_{i}=1\\}|\mod 2$.

  3. 3.

$\textsc{count}_{q}$: Let $q$ be an integer and let
$\textsc{count}_{q}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow[q-1]\cup\\{0\\}$ be a non-Boolean function
with $\textsc{count}_{q}(x)=|\\{i\mathrel{\mathop{\mathchar
58\relax}}x\in\\{0,1\\}^{N}\text{ and }x_{i}=1\\}|\mod q$.

  4. 4.

majority: Let $\textsc{majority}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ be a Boolean function with

$\textsc{majority}{}(x)=\begin{cases}1&\text{ if }t\geq\frac{N}{2},\\\
0&\text{otherwise;}\end{cases}$

here $t=|\\{i\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{N}\text{ and
}x_{i}=1\\}|$.

  5. And, there is also the following function almost similar to majority.

  6. 5.

st-majority: Let $\text{st}\textsc{-majority}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ be a Boolean function with

$\text{st}\textsc{-majority}{}(x)=\begin{cases}1&\text{ if }t>\frac{N}{2},\\\
0&\text{otherwise;}\end{cases}$

here $t=|\\{i\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{N}\text{ and
}x_{i}=1\\}|$.

######  Theorem 2.4 (Implicit in [BBC+01]).

The bounded error quantum query complexity for count, parity, majority and st-
majority on inputs of $N$ bit Boolean strings is $\Omega(N)$.

###### Proof.

There is a seminal result by [BBC+01] where they show that the bounded-error
quantum query complexity of a (total) Boolean function
$f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$,
denoted by $Q(f)$ is lower bounded by the degree of a minimum-degree
polynomial $p$ that approximates $f$ on all $X\in\\{0,1\\}^{N}$, i.e.,
$|p(X)-f(X)|\leq 1/3$; let us denote this degree by $\widetilde{deg}(f)$.
Another important result by Paturi [Pat92] showed that if $f$ is a non-
constant, symmetric666A symmetric Boolean function
$f\mathrel{\mathop{\mathchar 58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$
implies $f(X)=f(Y)$ for all $X,Y$ whenever $|X|=|Y|$. and a total Boolean
function on $\\{0,1\\}^{N}$ then
$\widetilde{deg}(f)=\Theta(\sqrt{N(N-\Gamma(f))})$ where
$\Gamma(f)=\min\\{|2k-N+1|\mathrel{\mathop{\mathchar 58\relax}}f_{k}\neq
f_{k+1}\text{ and }0\leq k\leq N-1\\}$ and $f_{k}=f(X)$ for $|X|=k$.

Using the above two results we can show the following:

  1. 1.

$\Gamma(\textsc{parity})=0$ for odd $N$ and $\Gamma(\textsc{parity})=1$
whenever $N$ is even. Either ways
$Q(\textsc{parity})=\Omega(\Gamma(f))=\Omega(N)$.

  2. 2.

Similar to the above item
$\Gamma(\textsc{majority})=\Gamma(\text{st}\textsc{-majority})=0$ for odd $N$
and $\Gamma(\textsc{majority})=\Gamma(\text{st}\textsc{-majority})=1$
otherwise. Hence, $Q(\textsc{majority})=\Omega(N)$ and
$Q(\text{st}\textsc{-majority})=\Omega(N)$.

  3. 3.

Any of these above three properties can be computed from count. Hence, the
quantum query lower bound for count is also $Q(\textsc{count})=\Omega(N)$.

∎

As we don’t yet know how to prove compression-obliviousness of complicated
properties (Theorem 9 in [BPS21]) we instead conjecture that count, parity,
majority and st-majority are compression oblivious for poly-sized CNF and DNF
formulas.

######  Conjecture 2.5.

Let $\textsc{AC}^{0}_{2}$ denote the class of $\mathrm{poly}(n)$ sized CNF and
DNF formulas on $n$ input variables then the following properties

  1. 1.

$\textsc{count}{}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow[2^{n}]\cup\\{0\\}$,

  2. 2.

$\textsc{parity}{}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow\\{0,1\\}$,

  3. 3.

$\textsc{count}_{q}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow[q-1]\cup\\{0\\}$,

  4. 4.

$\textsc{majority}{}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow\\{0,1\\}$, and

  5. 5.

$\text{st}\textsc{-majority}{}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{2^{n}}\rightarrow\\{0,1\\}$

stated in Definition 2.3 are in $\mathcal{CO}(\textsc{AC}^{0}_{2})$.

We can now invoke $\textsc{AC}^{0}_{2}$-QSETH (as mentioned in Conjecture 1.3)
to prove the quantum hardness for #CNFSAT, $\oplus$CNFSAT, maj-CNFSAT and st-
maj-CNFSAT.

######  Theorem 2.6 (#QSETH).

There is no bounded error quantum algorithm that solves #CNFSAT on $n$
variables and $m$ clauses in $O(2^{n(1-\delta)}m^{O(1)})$ time for any
$\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) is false or
$\textsc{count}\notin\mathcal{CO}(\textsc{AC}^{0}_{2})$ (i.e., Item 1 of
Conjecture 2.5 is false).

###### Proof.

By way of contradiction let us assume that there exists a bounded-error
quantum algorithm $\mathcal{A}$ that solves #CNFSAT on $n$ variables and $m$
clauses in $O(2^{n(1-\delta)}m^{O(1)})$ time for some $\delta>0$. Then given a
circuit $C\in\textsc{AC}^{0}_{2}$ we do one of the following:

  * •

if $C$ is a poly-sized CNF formula then we use the algorithm $\mathcal{A}$ to
compute the number of satisfying assignments to $C$ in
$O(2^{n(1-\delta)}m^{O(1)})$ time. Or,

  * •

if $C$ is a poly-sized DNF formula then we first construct the negation of
$C$, let us denote by $\neg C$, in $\mathrm{poly}(n)$ time; using De Morgan’s
law we can see that the resulting formula $\neg C$ will be a
$\mathrm{poly}(n)$ CNF formula. Using $\mathcal{A}$ we can now compute the
number of satisfying assignments $t$ to $\neg C$ in
$O(2^{n(1-\delta)}m^{O(1)})$ time. The number of satisfying assignments to $C$
would be then $2^{n}-t$.

The existence of an algorithm such as $\mathcal{A}$ would imply that
$\textsc{AC}^{0}_{2}$-QSETH is false. Hence, proved. ∎

Using similar arguments as in the proof of Theorem 2.6 we can conclude the
following statements.

######  Corollary 2.7 ($\oplus$QSETH).

There is no bounded error quantum algorithm that solves $\oplus$CNFSAT on $n$
variables and $m$ clauses in $O(2^{n(1-\delta)}m^{O(1)})$ time for any
constant $\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) is
false or $\textsc{parity}{}\notin\mathcal{CO}(\textsc{AC}^{0}_{2})$ (i.e.,
Item 2 of Conjecture 2.5 is false).

######  Corollary 2.8 (Majority QSETH).

There are no bounded-error quantum algorithms that solve

  1. 1.

maj-CNFSAT on $n$ variables and $m$ clauses in $O(2^{n(1-\delta)}m^{O(1)})$
time, or

  2. 2.

st-maj-CNFSAT on $n$ variables and $m$ clauses in $O(2^{n(1-\delta)}m^{O(1)})$
time,

any constant $\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH is false or
$\textsc{majority}\notin\mathcal{CO}(\textsc{AC}^{0}_{2})$ (i.e., Item 4 of
Conjecture 2.5 is false).

We can extend the above-mentioned arguments to compute the total number of
assignments in $\mathbb{F}_{q}$ for any $q\geq 2$ as well. To understand the
complexity of $\\#_{q}$CNFSAT (Definition 2.2) we first need to understand the
quantum query complexity of $\textsc{count}_{q}{}$.

######  Lemma 2.9.

Let $2<q\leq\frac{N}{2}$ be an integer and let
$\textsc{count}_{q}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow[q-1]$ be a function such that for any
$x\in\\{0,1\\}^{N}$ the $\textsc{count}_{q}(x)=\textsc{count}(x)\mod q$. Then
$Q(\textsc{count}_{q})=\Omega(\sqrt{N(N-2q+1)})$.

###### Proof.

Let $\textsc{dec-count}_{q}$ be a decision version of the $\textsc{count}_{q}$
defined for all $x\in\\{0,1\\}^{N}$ as

$\textsc{dec-count}_{q}(x)=\begin{cases}1,\text{ if
}\textsc{count}_{q}(x)=q-1,\\\ 0,\text{ otherwise}.\end{cases}$ (1)

Beals et al. showed that the bounded error quantum query complexity of any
Boolean function is lower bounded by the approximate degree of that function
[BBC+01]. When the function is non-constant and symmetric then one can use
Paturi’s theorem to characterise the approximate degree of that function
[Pat92]. It is easy to see that $\textsc{dec-count}_{q}$ is a non-constant
symmetric function. Combining both these results we get that $Q(\textsc{dec-
count}_{q})=\Omega(\sqrt{N(N-\eta(\textsc{dec-count}_{q}))})$; we compute the
value of $\eta(\textsc{dec-count}_{q})$ in the next paragraph.

For any symmetric Boolean function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ the quantity $\eta(f)$ is defined
as $\eta(f)=\min_{k}\\{|2k-N+1|\\}$ such that $f_{k}\neq f_{k+1}$ and
$f_{k}=f(x)$ for $|x|=k$ with $1\leq k\leq N-1$. It is easy to see that
$\textsc{dec-count}_{q}(x)=1$ only for $x$ with hamming weight $|x|=rq-1$
where $r$ is an integer and $\textsc{dec-count}_{q}(x)=0$ elsewhere. Let
$r^{\prime}$ be the integer such that
$r^{\prime}q-1\leq\frac{N}{2}\leq(r^{\prime}+1)q-1$ then the $k$ minimising
$\eta(\textsc{dec-count}_{q})$ is either $r^{\prime}q-1$ or
$(r^{\prime}+1)q-1$. With a back-of-the-envelope-calculation we can see that
$\eta(\textsc{dec-count}_{q})\leq 2q-1$ which in turn implies that
$N-\eta(\textsc{dec-count}_{q})\geq N-2q+1$. Therefore, $Q(\textsc{dec-
count}_{q})=\Omega(\sqrt{N(N-2q+1)})$.

As one can compute $\textsc{dec-count}_{q}$ using an algorithm that computes
$\textsc{count}_{q}{}$, we therefore have
$Q(\textsc{count}_{q}{})=\Omega(\sqrt{N(N-2q+1)})$. ∎

Using Conjectures 1.3 and 2.5 we can now conclude the following.

######  Corollary 2.10 ($\\#_{q}$QSETH).

Let $2<q\leq 2^{n-1}$. There is no bounded error quantum algorithm that solves
$\\#_{q}$CNFSAT on $n$ variables and $m$ clauses in
$O\left(\left(\sqrt{2^{n}(2^{n}-2q+1)}\right)^{1-\delta}m^{O(1)}\right)$ time
for any constant $\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH (Conjecture
1.3) is false or $\textsc{count}_{q}\notin\mathcal{CO}(\textsc{AC}^{0}_{2})$
(i.e., Item 3 of Conjecture 2.5 is false).

###  2.3 Quantum complexity of $\Delta$-add-#CNFSAT

Instead of the exact number of satisfying assignments to a formula, one might
be interested in its additive error approximation. Towards that, we define the
$\Delta$-add-#CNFSAT as follows.

######  Definition 2.11 ($\Delta$-add-#CNFSAT).

Given an input a CNFSAT formula on $n$ Boolean variables and $m$ clauses. The
problem is to output an additive error approximation of the total number of
satisfying assignments, i.e., an integer $d$ such that $|d-d^{\prime}|<\Delta$
where $d^{\prime}$ is the number of assignments to these $n$ variables that
satisfy the given formula and $\Delta\in[1,2^{n})$.

This problem (Definition 2.11) can be viewed as computing the following
property on the truth table of the given formula.

######  Definition 2.12 ($\Delta\textsc{-add-count}$).

Given a Boolean string $x\in\\{0,1\\}^{N}$, the $\Delta\textsc{-add-count}(x)$
is an integer such that $|\Delta\textsc{-add-count}(x)-|x||<\Delta$ where
$|x|=|\\{i\mathrel{\mathop{\mathchar 58\relax}}x\in\\{0,1\\}^{N}\text{ and
}x_{i}=1\\}|$ and $\Delta\in[1,N)$.

The bounded-error quantum query complexity for computing $\Delta\textsc{-add-
count}$ was studied in [NW99]. They showed the following result.

######  Theorem 2.13 (Theorem 1.11 in [NW99]).

Any quantum algorithm computing $\Delta\textsc{-add-count}(x)$ for an
$x\in\\{0,1\\}^{N}$ and $\Delta\in[1,N)$ (Definition 2.12) requires to make
$\Omega\left(\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{t(N-t)}}{\Delta}\right)$
quantum queries to $x$ where $t=|x|$.

For values of $\Delta=o(\sqrt{t})$ we are unable to prove the compression-
obliviousness of this property. Hence, we make the following conjecture.

######  Conjecture 2.14.

Let $\textsc{AC}^{0}_{2}$ denote the class of $\mathrm{poly}(n)$ size CNF and
DNF formulas on $n$ input variables the property $\Delta\textsc{-add-count}$
is compression oblivious corresponding to $\textsc{AC}^{0}_{2}$, i.e.
$\Delta\textsc{-add-count}\in\mathcal{CO}(\textsc{AC}^{0}_{2})$.

One can now establish the time lower bound for computing the
$\Delta\textsc{-add-count}$ on $\mathrm{poly}(n)$ sized CNF and DNF formulas.
However, this doesn’t automatically imply the same lower bound for the case
when there are only CNF formulas to consider. Fortunately,
$\Delta\textsc{-add-count}$ is defined in such a way that computing this
property is equally hard for both CNF and DNF formulas. More precisely, the
following statement holds.

######  Theorem 2.15 ($\Delta$-add-#QSETH).

Let $n$ be an integer and let $\Delta\in[\frac{1}{2},2^{n})$. Conditional on
$\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) and Conjecture 2.14, there is no
bounded error quantum algorithm that solves $\Delta$-add-#CNFSAT on CNF
formulas with $n$ variables and $m=\mathrm{poly}(n)$ clauses in
$O\left(\left(\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{t(N-t)}}{\Delta}\right)^{1-\alpha}m^{O(1)}\right)$
time for any constant $\alpha>0$.

###### Proof.

By way of contradiction let’s assume that there is an algorithm $\mathcal{A}$
such that given a CNF formula it can compute the $\Delta\textsc{-add-count}$
on its truth table in
$O\left(\left(\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{t(N-t)}}{\Delta}\right)^{1-\beta}m^{O(1)}\right)$
time for some constant $\beta>0$.

Then, given a $\mathrm{poly}(n)$ sized DNF formula on $n$ variables and $m$
clauses, let us denote that by $\phi$, we can run Algorithm $\mathcal{A}$ on
$\neg\phi$ and use its output which is a $\Delta$ additive error approximation
of the number of satisfying assignments to $\neg\phi$ to compute a $\Delta$
additive error approximation of the number of satisfying assignments to
$\phi$.

Let us denote the number of satisfying assignments of $\neg\phi$ by
$d^{\prime}$ and the output of Algorithm $\mathcal{A}$ by $d$. This means we
have $|d-d^{\prime}|<\Delta$. We claim that $2^{n}-d$ will be a $\Delta$
additive error approximation of $2^{n}-d^{\prime}$, which is the number of
satisfying assignments of $\phi$;
$|(2^{n}-d)-(2^{n}-d^{\prime})|=|d^{\prime}-d|<\Delta$.

Therefore, a
$O\left(\left(\sqrt{\frac{N}{\Delta}}+\frac{\sqrt{t(N-t)}}{\Delta}\right)^{1-\beta}m^{O(1)}\right)$
time (for some constant $\beta>0$) algorithm for computing
$\Delta\textsc{-add-count}$ on truth table of CNF formulas also implies the
same run time for computing $\Delta\textsc{-add-count}$ on truth table of DNF
formulas; this violates the combination of $\textsc{AC}^{0}_{2}$-QSETH and
Conjecture 2.14. Hence, proved. ∎

###  2.4 Quantum complexity of $\gamma$-#CNFSAT and other related problems

One other approximation of the count of satisfying assignments is the
multiplicative factor approximation, defined as follows.

######  Definition 2.16 ($\gamma$-#CNFSAT).

Let $\gamma\in(0,1)$. The $\gamma$-#CNFSAT is defined as follows. The input is
a CNFSAT formula on $n$ Boolean variables and $m$ clauses. The problem is to
output an integer $d$ such that $(1-\gamma)d^{\prime}<d<(1+\gamma)d^{\prime}$
where $d^{\prime}$ is the number of assignments to these $n$ variables that
satisfy the given formula.777The same results hold if the approximation is
defined with the equalities, i.e., $(1-\gamma)d^{\prime}\leq
d\leq(1+\gamma)d^{\prime}$. An additional observation under this changed
definition of $\gamma$-#CNFSAT is as follows. Given a CNF formula as input,
the algorithm for $\gamma$-#CNFSAT outputs $0$ only when there is no
satisfying assignment to that formula. Hence, one can decide satisfiability of
a given CNF formula using the algorithm for $\gamma$-#CNFSAT. Therefore, the
same lower bound from Basic-QSETH carries for this changed definition of
$\gamma$-#CNFSAT.

The expression $(1-\gamma)d^{\prime}<d<(1+\gamma)d^{\prime}$, which is same as
$(d^{\prime}-\gamma d^{\prime})<d<(d^{\prime}+\gamma d^{\prime})$, can be
categorised into the following two cases.

  * •

Case 1 is when $\gamma d^{\prime}\leq 1$: in this regime, the algorithm
solving $\gamma$-#CNFSAT is expected to return the value $d^{\prime}$ which is
the _exact_ count of the number of solutions to the CNFSAT problem and from
Theorem 2.6 we know that there is no $O^{*}(2^{n(1-\varepsilon)})$ time
algorithm, for any constant $\varepsilon>0$, that can compute the exact number
of solutions to input CNF formula; this is a tight lower bound.

  * •

Case 2 is when $\gamma d^{\prime}>1$: in this regime, the algorithm solving
$\gamma$-#CNFSAT is expected to return value $d$ which is the _$\gamma$
-approximate relative count_ of the number of solutions to the CNFSAT problem.
Using $\textsc{AC}^{0}_{2}$-QSETH we are able to prove a lower bound for
$\gamma$-#CNFSAT that accounts for the approximation factor $\gamma$ also when
$\gamma d^{\prime}>1$. We use the rest of this section towards proving this
result.

In order to understand the hardness of $\gamma$-#CNFSAT we will first try to
understand how hard it is to compute the following property on poly-sized CNF
and DNF formulas. Let $f_{\ell,\ell^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{D}\rightarrow\\{0,1\\}$ with
$\mathcal{D}\subset\\{0,1\\}^{N}$ be a partial function defined as follows

$f_{\ell,\ell^{\prime}}=\begin{cases}1,\text{ if }|x|=\ell,\\\ 0,\text{ if
}|x|=\ell^{\prime}.\end{cases}$

Nayak and Wu in [NW99] analysed the minimum degree of any polynomial
approximating $f_{\ell,\ell^{\prime}}$ and by invoking the Beals et al. result
[BBC+01] gave a lower bound on the quantum query complexity of
$f_{\ell,\ell^{\prime}}$ as mentioned in the following statement.

######  Corollary 2.17 (Rephrasing Corollary 1.2 in [NW99]).

Let $f_{\ell,\ell^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{D}\rightarrow\\{0,1\\}$ where
$\mathcal{D}\subset\\{0,1\\}^{N}$ and

$f_{\ell,\ell^{\prime}}=\begin{cases}1,\text{ if }|x|=\ell,\\\ 0,\text{ if
}|x|=\ell^{\prime}.\end{cases}$

Let $\Delta_{\ell}=|\ell-\ell^{\prime}|$ and let
$p\in\\{\ell,\ell^{\prime}\\}$ such that $|\frac{N}{2}-p|$ is maximized. Then
the bounded error quantum query complexity of $f_{\ell,\ell^{\prime}}$ is
$\Omega\left(\sqrt{\frac{N}{\Delta_{\ell}}}+\frac{\sqrt{p(N-p)}}{\Delta_{\ell}}\right)$.

Using $\textsc{AC}^{0}_{2}$-QSETH we will now show that for a choice of
$\ell,\ell^{\prime}$ computing $f_{\ell,\ell^{\prime}}$ on truth tables of CNF
formulas of $\mathrm{poly}(n)$ size requires
$\Omega\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)$
time where $\Delta_{\ell}=|\ell-\ell^{\prime}|$ and
$p\in\\{\ell,\ell^{\prime}\\}$ that maximises $|2^{n-1}-p|$. The only caveat
(as also witnessed several times earlier) is that we cannot prove the
compression obliviousness of $f_{\ell,\ell^{\prime}}$ hence we state and use
the following conjecture.

######  Conjecture 2.18.

Let $\textsc{AC}^{0}_{2}$ denote the class of $\mathrm{poly}(n)$ size CNF and
DNF formulas on $n$ input variables then for any pair of integers
$\ell\in[2^{n}]\cup\\{0\\}$ and $\ell^{\prime}\in[2^{n}]\cup\\{0\\}$ the
property $f_{\ell,\ell^{\prime}}$ is compression oblivious corresponding to
$\textsc{AC}^{0}_{2}$, i.e.
$f_{\ell,\ell^{\prime}}\in\mathcal{CO}(\textsc{AC}^{0}_{2})$.888Note that,
there are some values of $\ell,\ell^{\prime}$ for which
$f_{\ell,\ell^{\prime}}$ will be provably compression oblivious, for e.g.,
$\ell=1$ and $\ell^{\prime}=0$ would capture the OR property which is
compression oblivious; see Section 2.1.

We can now prove the following.

######  Lemma 2.19.

Let $n$ be an integer and let $\ell\in[2^{n}]\cup\\{0\\}$ and
$\ell^{\prime}\in[2^{n}]\cup\\{0\\}$. Then conditional on Conjecture 2.18 and
$\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) then at least one of the
following is true.

  * •

There is no bounded error quantum algorithm that can compute
$f_{\ell,\ell^{\prime}}$ on the truth table of $\mathrm{poly}(n)$ size CNF
formulas defined on $n$ variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any constant $\delta>0$.

  * •

There is no bounded error quantum algorithm that can compute
$f_{N-\ell,N-\ell^{\prime}}$ on the truth table of $\mathrm{poly}(n)$ size CNF
formulas defined on $n$ variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any constant $\delta>0$.

Here $\Delta_{\ell}=|\ell-\ell^{\prime}|$ and $p\in\\{\ell,\ell^{\prime}\\}$
is such that $|2^{n-1}-p|$ is maximized.

###### Proof.

Let $N$ be an integer that we will fix later and let
$f^{\prime}_{\ell,\ell^{\prime}}\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ be defined as follows

$f^{\prime}_{\ell,\ell^{\prime}}=\begin{cases}1,\text{ if }|x|=N-\ell,\\\
0,\text{ if }|x|=N-\ell^{\prime}.\end{cases}$

It is not hard to see $f^{\prime}_{\ell,\ell^{\prime}}$ is the same as
function $f_{N-\ell,N-\ell^{\prime}}$. Fortunately, both the functions
$f_{N-\ell,N-\ell^{\prime}}$ and $f_{\ell,\ell^{\prime}}$ have the same value
of $\Delta_{\ell}$ and $h$ where $h=p(N-p)$. Therefore the bounded error
quantum query complexity of $f^{\prime}_{\ell,\ell^{\prime}}$ is
$\Omega\left(\sqrt{\frac{N}{\Delta_{\ell}}}+\frac{\sqrt{p(N-p)}}{\Delta_{\ell}}\right)$
where $\Delta_{\ell}=|\ell-\ell^{\prime}|$ and $p\in\\{\ell,\ell^{\prime}\\}$
such that $|\frac{N}{2}-p|$ is maximised; same as the bounded error quantum
query complexity of $f_{\ell,\ell^{\prime}}$ as mentioned in Corollary 2.17.

Moreover, as $f^{\prime}_{\ell,\ell^{\prime}}$ is the same function
$f_{N-\ell,N-\ell^{\prime}}$ it is therefore clear from Conjecture 2.18 that
$f^{\prime}_{\ell,\ell^{\prime}}\in\mathcal{CO}(\textsc{AC}^{0}_{2})$ which
means there is no bounded error quantum algorithm that can compute
$f^{\prime}_{\ell,\ell^{\prime}}$ or $f_{\ell,\ell^{\prime}}$ on truth tables
of $\mathrm{poly}(n)$ size CNF or DNF formulas defined on $n$ input variables
in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any constant $\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH is false.
We will now show that conditional on $\textsc{AC}^{0}_{2}$-QSETH this result
holds even when we restrict ourselves to only $\mathrm{poly}(n)$ sized CNF
formulas.

Having introduced $f^{\prime}_{\ell,\ell^{\prime}}$ we will now prove Lemma
2.19 using the following propositions.

  * •

Proposition A There is no bounded error quantum algorithm that can compute
$f_{\ell,\ell^{\prime}}$ on truth table of CNF formulas defined on $n$
variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any $\delta>0$.

  * •

Proposition B There is no bounded error quantum algorithm that can compute
$f_{\ell,\ell^{\prime}}$ on truth table of DNF formulas defined on $n$
variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any $\delta>0$.

  * •

Proposition C There is no bounded error quantum algorithm that can compute
$f^{\prime}_{\ell,\ell^{\prime}}$ on truth table of CNF formulas defined on
$n$ variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any $\delta>0$.

  * •

Proposition D There is no bounded error quantum algorithm that can compute
$f^{\prime}_{\ell,\ell^{\prime}}$ on truth table of DNF formulas defined on
$n$ variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any $\delta>0$.

Conditional on Conjecture 2.18 and $\textsc{AC}^{0}_{2}$-QSETH the following
statements hold.

  * •

Claim 1 At least one of the propositions A or B is true.

  * •

Claim 2 At least one of the propositions C or D is true.

  * •

Claim 3 At least one of the propositions A or C is true; by way of
contradiction let us assume that both propositions A and C are false, this
means there exist algorithms $\mathcal{A},\mathcal{A}^{\prime}$ that for an
$\alpha>0$ and $\alpha^{\prime}>0$ compute $f_{\ell,\ell^{\prime}}$ and
$f^{\prime}_{\ell,\ell^{\prime}}$ on the truth table of $\mathrm{poly}(n)$
size CNF formulas defined on $n$ input variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\alpha}\right)$
time and in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\alpha^{\prime}}\right)$
time, respectively. Moreover, if propositions A and C are false then from
Claims 1 and 2 we can deduce that both B and D must be true which means there
is no quantum algorithm that can compute $f_{\ell,\ell^{\prime}}$ or
$f^{\prime}_{\ell,\ell^{\prime}}$ on the truth table of $\mathrm{poly}(n)$
size DNF formulas on $n$ input variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any $\delta>0$. However, given a DNF formula $\phi$ as an input to
compute $f_{\ell,\ell^{\prime}}$ on its truth table one can instead compute
$f^{\prime}_{\ell,\ell^{\prime}}$ on the negation of $\phi$, let us denote by
$\neg\phi$, using algorithm $\mathcal{A}^{\prime}$ on $\neg\phi$ in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{p(2^{n}-p)}}{\Delta_{\ell}}\right)^{1-\alpha^{\prime}}\right)$
time which is a contradiction. This means at least one of the two propositions
A or C must be true which is exactly the statement of Lemma 2.19.

∎

It is then not hard to see that for the values when $\ell+\ell^{\prime}=N$ the
following result holds.

######  Corollary 2.20.

Let $n$ be an integer and let $\ell\in[2^{n}]\cup\\{0\\}$ and
$\ell^{\prime}\in[2^{n}]\cup\\{0\\}$ such that $\ell+\ell^{\prime}=2^{n}$.
Then there is no bounded error quantum algorithm that can compute
$f_{\ell,\ell^{\prime}}$ on the truth table of $\mathrm{poly}(n)$ size CNF
formulas defined on $n$ variables in
$O^{*}\left(\left(\sqrt{\frac{2^{n}}{\Delta_{\ell}}}+\frac{\sqrt{\ell\ell^{\prime}}}{\Delta_{\ell}}\right)^{1-\delta}\right)$
time for any constant $\delta>0$ unless $\textsc{AC}^{0}_{2}$-QSETH or
Conjecture 2.18 is false; here $\Delta_{\ell}=|\ell-\ell^{\prime}|$.

Inspired by arguments used in the proof of Theorem 1.13 in [NW99], we will now
use Corollary 2.20 to prove the following result. Our result holds for
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$; this range of $\gamma$
suffices for our reductions presented in the later sections.

######  Theorem 2.21 ($\gamma$-#QSETH).

Let $n$ be an integer and let
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$. Conditional on
$\textsc{AC}^{0}_{2}$-QSETH and Conjecture 2.18, there is no bounded error
quantum algorithm that solves $\gamma$-#CNFSAT on $n$ variables and
$m=\mathrm{poly}(n)$ clauses

  1. 1.

in
$O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-\delta}m^{O(1)}\right)$
time, for any constant $\delta>0$, whenever $\gamma\hat{h}>1$, and

  2. 2.

in $O(2^{n(1-\delta)}m^{O(1)})$ time, for any constant $\delta>0$, whenever
$\gamma\hat{h}\leq 1$.

Here $\hat{h}$ denotes the number of satisfying assignments to the input CNF
formula.

We prove the first part of Theorem 2.21 in the following way and use the
result from Theorem 2.6 for the second part. Given a value of
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$ we will fix values of
$\ell\in[2^{n}]\cup\\{0\\}$ and $\ell^{\prime}\in[2^{n}]\cup\\{0\\}$ such that
we are able to compute $f_{\ell,\ell^{\prime}}$ on truth table of an input CNF
formulas on $n$ variables and $m$ clauses using the algorithm that solves
$\gamma$-#CNFSAT. Hence, showing a lower bound on $\gamma$-#CNFSAT using the
lower bound result from Corollary 2.20.

###### Proof.

Let $N=2^{n}$ and let $\gamma\in\left[\frac{1}{N},\frac{1}{2}\right)$. Let
$\ell=\frac{N}{2}+\lceil{\gamma t}\rceil=\left\lceil{\frac{N}{2}+\gamma
t}\right\rceil$ and $\ell^{\prime}=\frac{N}{2}-\lceil{\gamma
t}\rceil=\left\lfloor{\frac{N}{2}-\gamma t}\right\rfloor$; here $t\in[N]$ is a
value that we will fix later but in any case, we have $1\leq\lceil{\gamma
t}\rceil<\frac{N}{2}$. With that, we are ensured that
$\gamma\ell>\frac{1}{2}$. We also make sure to choose values
$\ell,\ell^{\prime}$ in such a way that $\gamma\ell^{\prime}=\Omega(1)$.
Clearly, $\ell+\ell^{\prime}=N$ and
$\Delta_{\ell}=|\ell-\ell^{\prime}|=2\lceil{\gamma t}\rceil$ therefore by
invoking the result from Corollary 2.20 we can say that for these values of
$\ell,\ell^{\prime}$ there is no bounded error quantum algorithm that can
solve $f_{\ell,\ell^{\prime}}$ on truth table of CNF formulas in
$O\left(\left(\sqrt{\frac{N}{\lceil{\gamma
t}\rceil}}+\frac{\sqrt{\ell(N-\ell)}}{\lceil{\gamma
t}\rceil}\right)^{1-\delta}m^{O(1)}\right)$ time, for any $\delta>0$; let us
denote this claim by (*).

Let $\mathcal{A}$ be an algorithm that computes $\gamma$-#CNFSAT to the
relative error approximation $\gamma$, i.e., Algorithm $\mathcal{A}$ returns a
value $h$ such that $(1-\gamma)\hat{h}<h<(1+\gamma)\hat{h}$ where $\hat{h}$ is
the actual number of satisfying assignments of the input CNF formula. Given
$\ell=\frac{N}{2}+\lceil{\gamma t}\rceil$ and
$\ell^{\prime}=\frac{N}{2}-\lceil{\gamma t}\rceil$ there are values of
$t\in[N]$ such that we will be able to distinguish whether the number of
satisfying assignments to a formula is $\ell$ or $\ell^{\prime}$ using
Algorithm $\mathcal{A}$. As $\ell>\ell^{\prime}$ in our setup, we want $t$
such that $\ell^{\prime}(1+\gamma)<\ell(1-\gamma)$; it is then necessary that
$\gamma N<2\lceil{\gamma t}\rceil$; let us denote this as Condition 1.

Now we set the values of $\ell$ and $\ell^{\prime}$. Given a value of
$\gamma\in\left[\frac{1}{N},\frac{1}{2}\right)$ set
$\ell=\left\lceil{\frac{N}{2(1-\gamma)}}\right\rceil$ and set
$\ell^{\prime}=N-\ell$; this means
$\frac{N}{2(1-\gamma)}\leq\ell<\frac{N}{2(1-\gamma)}+1$ and
$\frac{N(1-2\gamma)}{2(1-\gamma)}-1<\ell^{\prime}\leq\frac{N(1-2\gamma)}{2(1-\gamma)}$
and $\frac{\gamma N}{(1-\gamma)}\leq|\ell-\ell^{\prime}|<\frac{\gamma
N}{(1-\gamma)}+2$ therefore
$2\gamma\ell-2\gamma\leq|\ell-\ell^{\prime}|<2\gamma\ell+2$.999To view the
calculations in a less cumbersome way one can use the fact that asymptotically
$\ell=\frac{N}{2(1-\gamma)}$, $\ell^{\prime}=\frac{N(1-2\gamma)}{2(1-\gamma)}$
and $|\ell-\ell^{\prime}|=\frac{\gamma N}{(1-\gamma)}=2\gamma\ell$. We know
from claim (*) that all algorithms that (for these values of
$\ell,\ell^{\prime}$) compute $f_{\ell,\ell^{\prime}}$ on CNF formulas require
$\Omega(L^{1-\delta})$ time for all $\delta>0$ where
$L=\frac{1}{\gamma}\sqrt{\frac{N-\ell}{\ell+1}}=\Omega\left(\frac{1}{\gamma}\sqrt{\frac{N-\ell}{\ell}}\right)$.
Moreover, $\ell^{\prime}$ when expressed in terms of $\ell$ and $\gamma$ is as
follows $(\ell-1)(1-2\gamma)-1<\ell^{\prime}\leq\ell(1-2\gamma)$. Therefore,
we can see that
$L=\Omega\left(\frac{1}{\gamma}\sqrt{\frac{N-\ell}{\ell}}\right)=\Omega\left(\frac{1-2\gamma}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}}\right)=\Omega\left(\frac{1}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}}\right)$;
the last equality holds because
$\frac{1-2\gamma}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}}>c_{0}\cdot\frac{1}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}}$
where $c_{0}$ is some constant strictly less than $1$.101010Note that we need
$c_{0}<1$ which means this would require that
$\gamma\in[\frac{1}{N},\frac{1-c_{0}}{2})$ instead of the range
$\gamma\in[\frac{1}{N},\frac{1}{2})$ that we considered earlier.

It is also easy to see that if $\ell=\lceil{\frac{N}{2(1-\gamma)}}\rceil$ were
to be expressed as $\frac{N}{2}+\lceil{\gamma t}\rceil$ then for that value of
$t$ we have $\lceil{\gamma
t}\rceil\geq\frac{N\gamma}{2(1-\gamma)}>\frac{N\gamma}{2}$ which satisfies
Condition 1 implying that this is in the case where we can use Algorithm
$\mathcal{A}$ to distinguish whether the number of satisfying assignments to a
formula is $\ell$ or $\ell^{\prime}$. Hence given a CNF formula as input, we
will be able to now use Algorithm $\mathcal{A}$ to distinguish whether the
number of satisfying assignments is $\ell$ or $\ell^{\prime}$. Let
$T=\frac{1}{\gamma}\sqrt{\frac{N-\ell}{\ell}}+\frac{1}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}}=O(\frac{1}{\gamma}\sqrt{\frac{N-\ell^{\prime}}{\ell^{\prime}}})$
because $\ell^{\prime}<\ell$. If Algorithm $\mathcal{A}$ can solve the
$\gamma$-#CNFSAT on an input CNF that has $\hat{h}$ number of satisfying
assignments in
$O((\frac{1}{\gamma}\sqrt{\frac{N-\hat{h}}{\hat{h}}})^{1-\delta}m^{O(1)})$
time, for some constant $\delta>0$, then we are essentially computing
$f_{\ell,\ell^{\prime}}$ in $O(T^{1-\delta}m^{O(1)})$ time, which is a
contradiction to claim (*); hence the first part of the statement of Theorem
2.21 proved.

Proof of the second part of this theorem follows from Theorem 2.6 as the
regime $\gamma\hat{h}\leq 1$ translates to exactly counting the number of
satisfying assignments.

∎

###  2.5 Quantum complexity of $\\#$k-SAT and other related problems

While $\textsc{AC}^{0}_{2}$-QSETH can be used to comment on the quantum
hardness of several properties on truth tables of CNF formulas, it however
doesn’t immediately allow for making similar hardness assumptions for bounded
width $k$-CNF formulas. In fact, one has to be extremely careful while making
such general hardness assumptions in the case of bounded width CNF formulas,
such a thing can be witnessed in [AW21]. However, sometimes reductions from
CNF-SAT to lattice problems [BGS17], require that the width of the input
formulas gets encoded exponentially as the dimension of the vector of the
lattice problems, which is undesirable when $k$ approaches $n$, which however
is tolerable for smaller $k$. Hence, we would like to say something
interesting about hardness #$k$-SAT or $\oplus k$-SAT say when $k=\Theta(\log
n)$. Turns out that we can do so by basing the hardness on #QSETH.

To do so, we use the randomised classical algorithm by Rainer Schuler [Sch05]
that solves CNF-SAT on $n$ variables, $m$ clauses in
$O(\mathrm{poly}(n)2^{n(1-1/(1+\log m))})$ expected time. This algorithm can
be viewed as a Turing reduction from SAT with bounded clause density to SAT
with bounded clause width, which was analyzed in [CIP06], a result that we
directly use.

Algorithm 1 $\text{ReduceWidth}_{k}{(\psi)}$

1:CNF formula $\psi$

2:if $\psi$ has no clause of width $>k$ then

3: output $\psi$

4:else

5: let $C^{\prime}=\\{l_{1},\ldots,l_{k^{\prime}}\\}$ be a clause of $\psi$ of
width $k^{\prime}>k$

6: $C=\\{l_{1},\ldots,l_{k}\\}$

7: $\psi_{0}\leftarrow\psi-\\{C^{\prime}\\}\cup\\{C\\}$

8: $\psi_{1}\leftarrow\psi\land\lnot l_{1}\land\lnot
l_{2}\land\cdots\land\lnot l_{k}$

9: $\psi_{1}\leftarrow$ Remove variables corresponding to literals
$l_{1},\ldots,l_{k}$ from $\psi_{1}$ by setting $l_{1}=0,\ldots,l_{k}=0$

10: $\text{ReduceWidth}_{k}{(\psi_{0})}$

11: $\text{ReduceWidth}_{k}{(\psi_{1})}$

Algorithm 1, the $\text{ReduceWidth}_{k}$ subroutine takes an input a CNF
formula, say $\psi$, of width greater than $k$ and then outputs a list of
$k$-CNF formulas $\psi_{i}$ where the solutions of the input formula is the
union of the solutions of the output formulas, i.e.,
$\text{sol}(\psi)=\cup_{i}\text{sol}(\psi_{i})$ where $\text{sol}(\phi)$
denotes the set of satisfying assignments to a formula $\phi$. In fact, it is
not hard to see that the count of the number of satisfying assignments also is
preserved, i.e., $|\text{sol}(\psi)|=\sum_{i}|\text{sol}(\psi_{i})|$.

######  Lemma 2.22 (Implicit from Section 3.2 in [CIP06]).

Algorithm 1 takes as input a CNF formula $\psi$ on $n$ input variables, $m$
clauses, and is of width strictly greater than $k$ and outputs a number of
$k$-CNF formulas $\psi_{i}$ each defined on at most $n$ input variables and at
most $m$ clauses such that
$|\text{sol}(\psi)|=\sum_{i}|\text{sol}(\psi_{i})|$.

###### Proof.

Let $\psi=C^{\prime}_{1}\land C^{\prime}_{2}\land\cdots\land C^{\prime}_{m}$
be the input CNF formula to Algorithm 1. The algorithm finds the first clause
$C^{\prime}_{i}$ that has its width $k^{\prime}>k$. Let
$C^{\prime}_{i}=(l_{1}\lor l_{2}\lor\dots\lor l_{k^{\prime}})$ and
$C_{i}=(l_{1}\lor l_{2}\lor\dots\lor l_{k})$. The algorithm then constructs
two formulas $\psi_{0}=\psi-\\{C^{\prime}_{i}\\}\cup\\{C_{i}\\}$ and
$\psi_{1}=\psi\land\lnot l_{1}\land\lnot l_{2}\land\cdots\land\lnot l_{k}$.
Then recursively calls the subroutine on $\psi_{0}$ and $\psi_{1}$. We now
claim the following.

######  Claim 2.23.

$\text{sol}(\psi_{0})\cap\text{sol}(\psi_{1})=\emptyset$ and
$\text{sol}(\psi)=\text{sol}(\psi_{0})\cup\text{sol}(\psi_{1})$, i.e.,
$\text{sol}(\psi)=\text{sol}(\psi_{0})\sqcup\text{sol}(\psi_{1})$.

###### Proof.

Let $x\in\text{sol}(\psi_{0})$ and then the clause
$C_{i}(x)=(l_{1}(x)\lor\cdots\lor l_{k}(x))$ should evaluate to 1. Which means
$\lnot(l_{1}(x)\lor\cdots\lor l_{k}(x))=0$, which using De Morgan’s laws
implies $(\lnot l_{1}(x)\land\cdots\land\lnot l_{k}(x))=0$, which means that
$\psi_{1}(x)=\psi(x)\land\lnot l_{1}(x)\land\cdots\land\lnot l_{k}(x)=0$.
Similar argument can be used to show that if $x\in\text{sol}(\psi_{1})$ then
$x\notin\text{sol}(\psi_{0})$. Therefore,
$\text{sol}(\psi_{0})\cap\text{sol}(\psi_{1})=\emptyset$.

What remains to show is
$\text{sol}(\psi)=\text{sol}(\psi_{0})\cup\text{sol}(\psi_{1})$.

  * •

If $x\in\text{sol}(\psi_{0})$ then $C_{i}(x)=1$ which implies
$C^{\prime}_{i}(x)=1$, therefore $x\in\text{sol}(\psi)$. If
$x\in\text{sol}(\psi_{1})$ then $\psi_{1}(x)=1$, but
$\psi_{1}(x)=\psi(x)\land\lnot l_{1}(x)\land\lnot
l_{2}(x)\land\cdots\land\lnot l_{k}(x)$ which means $\psi(x)=1$ as well.
Therefore, if $x\in\text{sol}(\psi_{0})\cup\text{sol}(\psi_{1})$ then
$x\in\text{sol}(\psi)$.

  * •

If $x\in\text{sol}(\psi)$ then $\psi(x)=1$ which means $C^{\prime}_{i}(x)=1$.
However, $C^{\prime}_{i}(x)=(l_{1}(x)\lor\cdots\lor
l_{k}(x))\lor(l_{k+1}(x)\lor\cdots\lor l_{k}^{\prime}(x))$. Which means either
$(l_{1}(x)\lor\cdots\lor l_{k}(x))=C_{i}(x)=1$ or $(l_{k+1}(x)\lor\cdots\lor
l_{k}^{\prime}(x))=1$ or both evaluate to 1. If $C_{i}(x)=1$ then
$\psi_{0}(x)=1$ which would mean $x\in\text{sol}(\psi_{0})$. If $C_{i}(x)=0$
then $\psi_{1}(x)=\psi(x)\land(\lnot C_{i}(x))=1$ which means
$x\in\text{sol}(\psi_{1})$.

Therefore, $\text{sol}(\psi)=\text{sol}(\psi_{0})\sqcup\text{sol}(\psi_{1})$.
∎

Using the statement of Claim 2.23 we conclude that
$\text{sol}(\psi)=\sqcup_{i}\text{sol}(\psi_{i})$, consequently implying that
$|\text{sol}(\psi)|=\sum_{i}|\text{sol}(\psi_{i})|$. ∎

Using Lemma 2.22 from this paper and Lemma 5 in [CIP06] we will now show the
hardness of $k$-SAT and its popular counting variants when $k=\Theta(\log n)$.

######  Corollary 2.24.

Conditional on $\textsc{AC}^{0}_{2}$-QSETH (Conjecture 1.3) and Conjecture
2.5, there are no bounded error quantum algorithms that for $k=\Theta(\log n)$
solve

  1. 1.

$k$-SAT in $O(2^{sn/2})$ time,

  2. 2.

$\\#$$k$-SAT in $O(2^{sn})$ time,

  3. 3.

$\oplus$$k$-SAT in $O(2^{sn})$ time,

  4. 4.

$\oplus_{q}$$k$-SAT in $O(2^{sn})$ time,

for any constant $s<1$, respectively.

###### Proof.

Consider the $\text{ReduceWidth}_{k}$ algorithm. Let $p$ be some path of
length $t$ in the tree $T$ of recursive calls to Algorithm 1. Let $\psi_{g}$
be the output formula of width $k$ on the path $p$. Let $l,r$ be the number of
left, right turns respectively on path $p$. Every left branch in the path
reduces the width of exactly 1 clause to $k$, therefore $l\leq m$. One the
other hand, with additional $\mathrm{poly}(n,m)$ time every right branch of
path $p$ reduces the number of variables by $k$, therefore $r\leq n/k$.
Therefore number of paths in tree $T$ with $r$ right branches is at most
$m+r\choose r$.

Now suppose there is an algorithm $S$ that solves #$k$-SAT in $2^{ns}$ for
some $s<1$ for all $k=\Theta(\log n)$. We can use the same arguments from
Lemma 5 in [CIP06] to show that this algorithm $S$ together with the
$\text{ReduceWidth}_{k}$ subroutine we can solve #CNF-SAT (ignoring
$\mathrm{poly}(n)$ factors) in time at most

$\displaystyle\sum_{r=0}^{n/k}{m+r\choose r}2^{s(n-rk)}$ $\displaystyle\leq$
$\displaystyle\sum_{r=0}^{n/k}{m+\frac{n}{k}\choose r}2^{s(n-rk)}$
$\displaystyle=$ $\displaystyle 2^{sn}\sum_{r=0}^{n/k}{m+\frac{n}{k}\choose
r}\frac{1}{2^{srk}}$ $\displaystyle\leq$ $\displaystyle
2^{sn}(1+\frac{1}{2^{sk}})^{m+\frac{n}{k}}$ $\displaystyle\leq$ $\displaystyle
2^{sn}e^{\frac{1}{2^{sk}}(m+\frac{n}{k})}\hskip 50.00008pt\text{since
}(1+x)\leq e^{x}$ $\displaystyle\leq$ $\displaystyle
2^{sn+\frac{4m}{2^{sk}}}\hskip 75.0001pt\text{since we can assume that
}m\geq\frac{n}{k}.$

For every $s<1$ and $m=\mathrm{poly}(n)$ there is a setting of $k=c\log n$ for
a constant $c(s,m)$ such that $s+\frac{4m}{n2^{sk}}<1$. Therefore, a $2^{ns}$
(for some $s<1$) algorithm for #$k$-SAT for $k=\Theta(\log n)$ would refute
#-QSETH (Theorem 2.6). The same arguments hold for k-SAT or $\oplus$k-SAT as
well. ∎

Note that, we _cannot_ extend the same arguments for the majority or st-
majority or additive error approximation of count. However, these arguments
extend to the multiplicative factor approximation of the count.

######  Corollary 2.25.

Let $n$ be an integer and let
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$. Conditional on
$\gamma$-#QSETH, there is no bounded error quantum algorithm that for
$k=\Theta(\log n)$ solves $\gamma$-#$k$-SAT on $n$ variables and
$m=\mathrm{poly}(n)$ clauses

  1. 1.

in
$O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-\delta}m^{O(1)}\right)$
time, for any constant $\delta>0$, whenever $\gamma\hat{h}>1$, and

  2. 2.

in $O(2^{n(1-\delta)}m^{O(1)})$ time, for any constant $\delta>0$, whenever
$\gamma\hat{h}\leq 1$.

Here $\hat{h}$ denotes the number of satisfying assignments to the input k-CNF
formula.

##  3 Quantum strong simulation of quantum circuits

We use the phrase _strong simulation problem_ to mean strong simulation of
_quantum_ circuits which is defined as follows.111111Note that, this is
different from _weak simulation_ problem; a weak simulation _samples_ from
probability distribution $p(x)=|\bra{0^{n}}C\ket{x}|^{2}$.

######  Definition 3.1 (The strong simulation problem).

Given a quantum circuit $C$ on $n$ qubits, a _strong simulation_ of $C$
computes the value of $|\bra{x}C\ket{0^{n}}|$, up to a desired bits of
precision, for some specified $x\in\\{0,1\\}^{n}$.121212Though in some papers
the strong simulation problem requires that we output $\bra{x}C\ket{0^{n}}$
instead of $|\bra{x}C\ket{0^{n}}|$, we use this definition because it is more
comparable to the definition of the weak simulation problem. Also, the lower
bound we present holds for either of these definitions.

For a quantum circuit $C$, computing $|\bra{x}C\ket{0^{n}}|$ exactly, to a
precision of $n$ bits, is #P-hard [CHM21, VDN10]. This means even a _quantum_
computer will likely require exponential time to strongly simulate another
quantum circuit. In this section, we prove a more _precise_ quantum time bound
for strongly simulating quantum circuits, both exactly and approximately; in
the approximate case, we present complexity results for both multiplicative
factor and additive error approximation. Our results extend the results by
[HNS20] in two directions: firstly, we give explicit (conditional) bounds
proving that it is hard to strongly simulate quantum circuits using _quantum_
computers as well. Secondly, we also address the open question posed by
[HNS20] on the (conditional) hardness of strong simulation up to accuracy
$O(2^{-n/2})$, however, our results are based on a hardness assumption
different from SETH or Basic QSETH.

The results presented in this section are based on two main components.
Firstly, on the observation that the reduction from CNFSAT to the strong
simulation problem given (in Theorem 3) by [HNS20] encodes the count of the
number of satisfying assignments; this fact allows us to use the same
reduction to reduce other variants of CNFSAT, such as #CNFSAT or
$\oplus$CNFSAT, to the strong simulation problem, moreover, the same reduction
also allows us to reduce $\gamma$-#CNFSAT and $\Delta$-add-#CNFSAT to
analogous variants of the strong simulation problem, respectively. As the
second main component, we use the quantum hardness of these variants of CNFSAT
problem discussed in Section 2.

We will first state the result of the exact quantum time complexity of the
strong simulation problem and then use that result to later show how hard it
is for a quantum computer to strongly simulate a quantum circuit with an
additive error or a multiplicative factor approximation.

$n$$n$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}H}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}X}$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}C^{\prime\prime}_{\phi}}$

Figure 2: The circuit $C_{\phi}$.

######  Theorem 3.2.

There is no constant $\alpha>0$ such that one can solve the strong simulation
problem (Definition 3.1) up to a precision of $n$ bits for an $s$-size circuit
on $n$ qubits in $2^{n(1-\alpha)}s^{O(1)}$ time, unless #QSETH (Theorem 2.6)
is false.

The proof is identical to the proof of Theorem 3 by [HNS20] which we restate
here for ease of reading.

###### Proof.

Let $\phi$ be a CNF formula on $n$ input variables and $m=\mathrm{poly}(n)$
clauses. Let $C^{\prime}_{\phi}$ denote the _reversible_ classical circuit,
using TOFFOLI, CNOT and NOT gates, that _tidily_ computes $\phi(x)$ for all
$x\in\\{0,1\\}^{n}$.131313A classical circuit $C\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n+w(n)+1}\rightarrow\\{0,1\\}^{n+w(n)+1}$ _reversibly and
tidily computes_ a function $f\mathrel{\mathop{\mathchar
58\relax}}\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ if the following statements are
true.  1. Circuit $C$ reversibly computes $f$ if $C$ consists of reversible
gates, such as $\\{\text{TOFFOLI, CNOT, NOT}\\}$, and $\forall
x\in\\{0,1\\}^{n},\exists
W(x)\in\\{0,1\\}^{w(n)},C(x,0^{w(n)},b)=(x,W(x),b\oplus f(x)).$ (2) 2. Circuit
$C$ tidily computes $f$ if $\forall x\in\\{0,1\\}^{n},\forall
b\in\\{0,1\\},C(x,0^{w(n)},b)=(x,0^{w(n)},b\oplus f(x)).$ (3) One can
construct circuit $C^{\prime}_{\phi}$ of width $k$ with $n\leq k\leq
n+2(\lceil{\log n}\rceil+\lceil{\log m}\rceil)$ and size $s\leq 8\times
3^{\lceil{\log n}\rceil+\lceil{\log m}\rceil}$ with sublinear space and
polynomial time overhead; see Section 4.1 of [HNS20]. Let
$C^{\prime\prime}_{\phi}$ denote the quantum analogue of the classical
reversible circuit $C^{\prime}_{\phi}$, i.e., for the gates in
$C^{\prime}_{\phi}$, TOFFOLI and CNOT remain unchanged and NOT gate is
replaced by $X$ gate; therefore, the width and size of
$C^{\prime\prime}_{\phi}$ remains $k$ and $s$, respectively.

Clearly, $C^{\prime\prime}_{\phi}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{H}\rightarrow\mathcal{H}$ where $\mathcal{H}$ denotes a
$2^{k}$ dimensional Hilbert space. Then, it is not hard to see that
$C^{\prime\prime}_{\phi}\ket{x}\ket{0^{k-n}}=\ket{x}\ket{\phi(x)}\ket{0^{k-1-n}}$.
Let $C_{\phi}$ denote the quantum circuit in Figure 2; width of this circuit
is still $k$ and size is $O(s)$. With a bit of calculation, it can be shown
that $\bra{0^{k}}C_{\phi}\ket{0^{k}}$ encodes the fraction of satisfying
assignments to formula $\phi$.

This means if there exists a constant $\alpha>0$ such that _strong quantum
simulation_ of circuit $C_{\phi}$ on basis state $\ket{x}$ with $x=0^{k}$ can
be computed in $T=2^{k(1-\alpha)}s^{O(1)}$ time up to $k$ bits of precision,
then essentially this would reveal the count of the number of satisfying
assignments formula $\phi$ in time $T$. Plugging in the values of $k\leq
n+2(\lceil{\log n}\rceil+\lceil{\log m}\rceil)$ and $s\leq 8\times
3^{\lceil{\log n}\rceil+\lceil{\log m}\rceil}=\mathrm{poly}(n)$ we get $T\leq
2^{n(1-\alpha)}n^{O(1)}$ time; this would refute #QSETH (Theorem 2.6). Hence,
proving the statement of Theorem 3.2. ∎

The following corollary also gives the same lower bound for $2$-bits of
precision but by using a different hardness assumption (which is Majority
QSETH) addressing an open question by [HNS20].141414We must admit, this answer
might not be an interesting enough answer to the open question by [HNS20]
because same observation can also be made in the classical setting by basing
the hardness assumption on _Majority SETH_. However, we still think it is an
observation worthwhile to mention.,151515Additionally, one needs to be careful
about the definition of Majority SETH: mostly about what definition of
Majority is being used because if the formulas under consideration are k-SAT
formulas then Majority can be computed in polynomial time but Strict Majority
still seems to require exponential time on k-SAT [AW21]. Hence, one way to
circumvent that would be to define SETH also on CNF formulas of unbounded
width, which is exactly how QSETH is defined.

######  Corollary 3.3.

There is no $2^{n(1-\alpha)}s^{O(1)}$ time quantum algorithm, for any constant
$\alpha>0$, that can solve the strong simulation problem (Definition 3.1) up
to $2$ bits of precision for an $s$-size circuit on $n$ qubits, unless
Majority QSETH (Part 1 of Corollary 2.8) is false.

One can also try to solve the strong simulation problem with additive error
approximation with the following definition.

######  Definition 3.4.

($\Delta^{\prime}$ additive error strong simulation) Given a quantum circuit
$C$ on $n$ qubits, output with $\Delta^{\prime}\in[\frac{1}{2^{n+1}},1)$
additive error the value $d^{\prime}=|\bra{0^{n}}C\ket{x}|$ for some specified
$x\in\\{0,1\\}^{n}$, i.e., output a value $d$ such that
$|d-d^{\prime}|<\Delta^{\prime}$.

Using the reduction mentioned in Theorem 3.2 and the conjectured hardness of
$\Delta$-add-#CNFSAT problem we can prove the following.161616Note that, the
value of $k$ in relation to $n$ is such that $2^{k}=\widetilde{O}(2^{n})$;
here $k$ refers to the $k$ used in the proof of Theorem 3.2.

######  Corollary 3.5.

Conditional on $\Delta$-add-#QSETH (Theorem 2.15), there is no bounded error
quantum algorithm that can solve the strong simulation problem of an $s$-sized
circuit $C$ on $n$ qubits to
$\Delta^{\prime}=\frac{\Delta}{2^{n}}\in[\frac{1}{2^{n+1}},1)$ additive error
approximation in
$\widetilde{O}\left(\left(\sqrt{\frac{2^{n}}{\Delta}}+\frac{\sqrt{\hat{h}(2^{n}-\hat{h})}}{\Delta}\right)^{1-\alpha}s^{O(1)}\right)$
time for any constant $\alpha>0$, for a specified $x\in\\{0,1\\}^{n}$, upto
$n$ bits of precision; here $\hat{h}=\bra{0^{n}}C\ket{x}\cdot 2^{n}$.

It is beneficial to note that, we only get (at best) a $\mathrm{poly}(n)$ time
quantum lower bound for the strong simulation problem when
$\Delta^{\prime}=\frac{\Delta}{2^{n}}=O(1)$. Fortunately, this lower bound
matches the $\mathrm{poly}(n)$ time quantum upper bound for the strong
simulation problem when $\Delta^{\prime}=O(1)$, see Appendix A in the appendix
for details. In fact, for some values of $\hat{h}$ our lower bounds are also
tight in terms of $\Delta^{\prime}$; this reassures us of our proposed
conjectures.

Additionally, we are also able to show strong simulation results with
multiplicative error whose definition is as follows.

######  Definition 3.6.

(Multiplicative $\gamma$-approximate strong simulation) Given a quantum
circuit $C$ on $n$ qubits, output with $\gamma$ multiplicative error the value
$d^{\prime}=|\bra{0^{n}}C\ket{x}|$ for some specified $x\in\\{0,1\\}^{n}$,
i.e., output a value $d$ such that
$(1-\gamma)d^{\prime}<d<(1+\gamma)d^{\prime}$.

The exact arguments in the proof of Theorem 3.2 can be used to prove the
following statement.

######  Theorem 3.7.

Conditional on $\gamma$-#QSETH (Theorem 2.21), there is no bounded-error
quantum algorithm that can solve the strong simulation problem to
multiplicative error approximation (Definition 3.6) of an input circuit $C$ on
$n$ qubits with error parameter $\gamma\in[\frac{1}{2^{n}},\frac{1}{2})$ in

  1. 1.

in
$O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-\delta}s^{O(1)}\right)$
time, for any constant $\delta>0$, whenever $\gamma\hat{h}\geq 1$, and

  2. 2.

in $O(2^{n(1-\delta)}s^{O(1)})$ time, for any constant $\delta>0$, whenever
$\gamma\hat{h}<1$.

Here $\hat{h}=\bra{0^{n}}C\ket{x}$ for a specific $x\in\\{0,1\\}^{n}$ and $s$
denotes the size of circuit $C$.

###### Proof.

Let $\mathcal{A}$ denote an algorithm that for a given $s$-sized quantum
circuit $C$ on $k$ qubits and a given $x\in\\{0,1\\}^{k}$ computes
$\bra{0^{k}}C\ket{x}$ with $\gamma$ multiplicative error approximation for a
$\gamma\in[\frac{1}{2^{k}},\frac{1}{2})$ in time

  1. 1.

in
$O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{k}-\hat{h}}{\hat{h}}}\right)^{1-\delta}s^{O(1)}\right)$
time, for a constant $\delta>0$, whenever $\gamma\hat{h}\geq 1$, and

  2. 2.

in $O(2^{k(1-\delta^{\prime})}s^{O(1)})$ time, for a constant
$\delta^{\prime}>0$, whenever $\gamma\hat{h}<1$;

here $\hat{h}=\bra{0^{k}}C\ket{x}\cdot 2^{n}$.

Then, given a CNF formula $\phi$ on $n$ input variables and $m$ clauses, one
can do the following to approximately count the number of satisfying
assignments to $\phi$: first use the $\mathrm{poly}(n)$ reduction as in the
proof of Theorem 3.2 to construct the quantum circuit $C_{\phi}$ of size
$s=\mathrm{poly}(n)$ and width $k\leq n+2(\lceil{\log n}\rceil+\lceil{\log
m}\rceil)$. Then run algorithm $\mathcal{A}$ on quantum circuit $C_{\phi}$ and
$x=0^{k}$ as inputs. The output would then be the $\gamma$ multiplicative
error approximation of the count of the number of satisfying assignments to
$\phi$. Depending on the value of $\gamma\cdot\hat{h}$, the run-time of this
entire process is either
$O\left(\mathrm{poly}(n)+\left(\frac{1}{\gamma}\sqrt{\frac{2^{k}-\hat{h}}{\hat{h}}}\right)^{1-\delta}s^{O(1)}\right)=O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{1-\delta}n^{O(1)}\right)$
for some constant $\delta>0$ or
$O(2^{k(1-\delta^{\prime})}s^{O(1)})=O(2^{n(1-\delta^{\prime})}n^{O(1)})$
time, for an constant $\delta^{\prime}>0$. Either way, violating the
$\gamma$-#QSETH (Theorem 2.21). ∎

##  4 Quantum lower bound for lattice counting and q-count problems

In this section, we would like to connect $k$-SAT to variants of lattice
problems and then use the QSETH lower bound we have in Section 2.5 to give
quantum fine-grained complexity for those lattice problems. For any set of $n$
linearly independent vectors
$\mathbf{B}=\\{\boldsymbol{b_{1}},\ldots,\boldsymbol{b_{n}}\\}$ from
$\operatorname{\mathbb{R}}^{d}$, the lattice $\operatorname{\mathcal{L}}$
generated by basis $\mathbf{B}$ is

$\operatorname{\mathcal{L}}(\mathbf{B})=\left\\{\sum\limits_{i=1}^{n}z_{i}\boldsymbol{b_{i}}\mathrel{\mathop{\mathchar
58\relax}}z_{i}\in\mathbb{Z}\right\\}.$

We call $n$ the rank of the lattice $\operatorname{\mathcal{L}}$ and $d$ the
dimension. The vectors
$\mathbf{B}=\\{\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n}\\}$ forms a basis
of the lattice. Given a basis $\operatorname{\mathbf{B}}$, we use
$\operatorname{\mathcal{L}}(\operatorname{\mathbf{B}})$ to denote the lattice
generated by $\operatorname{\mathbf{B}}$.

For $1\leq p<\infty$ the $\ell_{p}$-norm $\|\boldsymbol{x}\|_{p}$ of any
vector $\boldsymbol{x}\in\mathbb{R}^{d}$ is defined by

$\|\boldsymbol{x}\|_{p}\mathrel{\mathop{\mathchar
58\relax}}=\Big{(}\sum_{i=1}^{d}x_{i}^{p}\Big{)}^{1/p}\ .$

Additionally, the $\ell_{\infty}$ norm of such a vector $\boldsymbol{x}$ is
defined as
$\mathinner{\\!\left\lVert\boldsymbol{x}\right\rVert}_{\infty}\mathrel{\mathop{\mathchar
58\relax}}=\max_{i\in[d]}\mathinner{\\!\left\lvert x_{i}\right\rvert}$. The
$\ell_{p}$ unit ball $B^{d}_{p}\subset\mathbb{R}^{d}$ is defined by
$\\{\boldsymbol{x}\in\mathbb{R}^{d}\mid\|\boldsymbol{x}\|_{p}\leq 1\\}$.

Fine-grained complexity of lattice problems is quite widely studied in the
classical case [BGS17, ABGS21, AC21, AS18, BP20, BPT22]. Lots of variants of
lattice problems have been considered before, and the most well-studied one is
the closest vector problem (with respect to $\ell_{p}$ norm).

######  Definition 4.1.

For any $1\leq p\leq\infty$, the Closest Vector Problem CVPp is the search
problem defined as: The input is a basis
$\operatorname{\mathbf{B}}\in\operatorname{\mathbb{R}}^{d\times n}$ of the
lattice $\operatorname{\mathcal{L}}$ and a target vector $\boldsymbol{t}$. The
goal is to output a vector $\boldsymbol{v}\in\operatorname{\mathcal{L}}$ such
that
$\|\boldsymbol{v}-\boldsymbol{t}\|_{p}=\min\limits_{x\in\operatorname{\mathcal{L}}}\|\boldsymbol{x}-\boldsymbol{t}\|_{p}$.

CVPp is known to have a $2^{n}$ SETH lower bound for any $p\not\in
2\mathbb{Z}$ [BGS17, ABGS21], and for even $p$, there seems a barrier for
showing a fine-grained reduction from $k$-SAT to CVP [AK22]. Kannan gave a
$n^{\mathcal{O}(n)}$-time algorithm for solving CVPp for arbitrary $p\geq 1$
[Kan83], while the best-known algorithm for solving CVPp with noneven $p$ is
still $n^{cn}$ for some constant $c$. To get a conditional quantum lower bound
for CVPp for noneven $p$, given there is already a classical reduction from
$k$-SAT to CVPp using $2^{k}\cdot\mathrm{poly}(n)$ time (for noneven $p$)
[BGS17, ABGS21], either one can directly use the QSETH framework by Aaronson
et al. [ACL+20] to get a $2^{(0.5-\varepsilon)n}$ lower bound, or we can use
Corollary 2.24 to get the same lower bound in our QSETH framework.171717Basic
QSETH assumption is weaker than the QSETH assumption in Aaronson et al
[ACL+20], so our lower bound under basic QSETH assumption (Conjectures 1.3 and
2.1) will also imply a lower bound under their quantum SETH framework.

A natural question is invoked here: Can we have a $2^{(0.5+\varepsilon)n}$
quantum SETH lower bound for any (variants of) lattice problems? The answer is
yes by using the framework and the problems introduced in Section 2.5 and by
considering the counting variant of lattice problems. We begin by introducing
the (approximate) lattice counting problem and some other related problems as
follows:

######  Definition 4.2 (Lattice counting problem).

For all $\gamma\geq 0$ and $1\leq p\leq\infty$, the $\gamma$-approximate
Vector Counting Problem $\gamma$-VCPp is the counting problem defined as
follows: The input is a lattice a basis $\mathbf{B}\in\mathbb{R}^{d\times n}$
of lattice $\operatorname{\mathcal{L}}(\mathbf{B})$, target vector
$\boldsymbol{t}\in\mathbb{R}^{d}$, and radius $r\in\mathbb{R}_{+}$. The
problem is to output a value $C$ satisfying
$|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap r\cdot B^{d}_{p}|\leq
C\leq(1+\gamma)\cdot|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap r\cdot
B^{d}_{p}|$. If $\gamma=0$, we simply denote the problem as VCPp.

The (approximate) lattice counting problem was first introduced by Stephens-
Davidowitz as a promise problem [Ste16], and here we slightly modify the
definition to make it a counting problem. We also generalize the lattice
vector counting problem to the $q$-count problem, as follows.

######  Definition 4.3 (Lattice $q$-count problem).

For all $\gamma\geq 1$, $1\leq p\leq\infty$, and
$q\in[2^{n}]\setminus\\{1\\}$, the lattice $q$-count Problem $\\#_{q}$-VCPp is
the lattice q-count problem defined as follows: The input is a lattice a basis
$\mathbf{B}\in\mathbb{R}^{d\times n}$ of lattice
$\operatorname{\mathcal{L}}(\mathbf{B})$, target vector
$\boldsymbol{t}\in\mathbb{R}^{d}$, and radius $r\in\mathbb{R}_{+}$. The
problem is to output a value
$C=|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap r\cdot B^{d}_{p}|\mod q$.
If $q=2$, we simply denote the problem as $\oplus$VCPp.

One can consider the above two problems are the counting and the q-counting
version of CVPp, respectively. To connect these problems to the counting
$k$-SAT, we should first introduce the following geometric tool introduced by
Bennett, Golovnev, and Stephens-Davidowitz [BGS17].

######  Definition 4.4 (Isolating parallelepiped).

Let $k$ be an integer between $3$ and $n$. For all $1\leq p\leq\infty$, we say
that $V\in\mathbb{R}^{2^{k}\times k}$ and
$\boldsymbol{u}\in\mathbb{R}^{2^{n}}$ define a $(p,k)$-isolating
parallelepiped if $\|\boldsymbol{u}\|_{p}>1$ and
$\|V\boldsymbol{x}-\boldsymbol{u}\|_{p}$ = 1 for all
$\boldsymbol{x}\in\\{0,1\\}^{k}\setminus\\{0_{k}\\}$.

For the sake of completeness, we will explain how to connect a $k$-CNF formula
to an instance of VCP using the above object. The proof is very similar to the
proof of Theorem 3.2 of [BGS17].

######  Theorem 4.5.

Let $k$ be an integer between $3$ and $n$. Suppose we have a $(p,k)$-isolating
parallelepiped $(V,\boldsymbol{u})$ for some $p=p(n)\in[1,\infty)$ and can
make quantum queries to oracles $O_{V}\mathrel{\mathop{\mathchar
58\relax}}\ket{i}\ket{s}\ket{0}\rightarrow\ket{i}\ket{s}\ket{V_{is}}$ and
$O_{\boldsymbol{u}}\mathrel{\mathop{\mathchar
58\relax}}\ket{i}\ket{0}\rightarrow\ket{i}\ket{\boldsymbol{u}_{i}}$ for
$i\in[2^{k}]$ and $s\in[k]$. Then for every given input oracle
$O_{\Phi}\mathrel{\mathop{\mathchar
58\relax}}\ket{j}\ket{w}\ket{0}\rightarrow\ket{j}\ket{k}\ket{C_{w}(j)}$ of
k-CNF formula $\psi=C_{1}\land C_{2}\land\cdots\land C_{m}$ for $w\in[m]$ and
$j\in[n]$, one can output oracles $O_{\mathbf{B}}\mathrel{\mathop{\mathchar
58\relax}}\ket{h}\ket{j}\ket{0}\rightarrow\ket{h}\ket{j}\ket{\mathbf{B}_{j}(h)}$
of basis $\mathbf{B}\in\mathbb{R}^{(m\cdot 2^{k}+n)\times n}$ for each
$h\in[m\cdot 2^{k}+n]$ and $j\in[n]$,
$O_{\boldsymbol{t}}\mathrel{\mathop{\mathchar
58\relax}}\ket{h}\ket{0}\rightarrow\ket{h}\ket{t_{h}}$ of target vector
$\boldsymbol{t}\in\mathbb{R}^{m\cdot 2^{k}+n}$ for each $h\in[m\cdot
2^{k}+n]$, and radius $r$ such that
$|$sol($\psi)|=$VCP${}_{p}(\mathbf{B},\boldsymbol{t},r)$, using
$\mathrm{poly}(n,m)$ queries to $O_{V}$, $O^{\dagger}_{V}$,
$O_{\boldsymbol{u}}$, $O^{\dagger}_{\boldsymbol{u}}$, $O_{\Phi}$,
$O_{\Phi}^{\dagger}$, and elementary gates.

###### Proof.

Let $d=m\cdot 2^{k}+n$ and
$V=\\{\boldsymbol{v_{1}},\ldots,\boldsymbol{v_{k}}\\}$ with
$\boldsymbol{v_{s}}\in\mathbb{R}^{2^{k}}$ for every $s\in[k]$. The basis
$\mathbf{B}\in\mathbb{R}^{d\times n}$ and target vector
$\boldsymbol{t}\in\mathbb{R}^{d}$ in the output instance have the form:

$\displaystyle\mathbf{B}=\begin{pmatrix}\mathbf{B}_{1}\\\\[3.0pt]
\vdots\\\\[3.0pt] \mathbf{B}_{m}\\\\[3.0pt] 2\cdot m^{1/p}\cdot
I_{n}\\\\[3.0pt] \end{pmatrix},\hskip
14.22636pt\boldsymbol{t}=\begin{pmatrix}\boldsymbol{t}_{1}\\\\[3.0pt]
\vdots\\\\[3.0pt] \boldsymbol{t}_{m}\\\\[3.0pt]
m^{1/p}\cdot\mathbf{1}_{n}\\\\[3.0pt] \end{pmatrix},$

with blocks $\mathbf{B}_{w}\in\mathbb{R}^{2^{k}\times n}$ that correspond to
the clause $C_{w}=\vee_{s=1}^{k}\ell_{w,s}$ and
$\boldsymbol{t}_{w}\in\mathbb{R}^{2^{n}}$ for each $w\in[m]$. For each
$w\in[m]$ and $j\in[n]$, the $j$th column $(\mathbf{B}_{w})_{j}$ of block
$\mathbf{B}_{w}$ is

$\displaystyle(\mathbf{B}_{w})_{j}=\begin{cases}\boldsymbol{v_{w}},\text{ if
$x_{j}$ is the $w$th literal of clause $w$},\\\ -\boldsymbol{v_{w}},\text{ if
$\neg x_{j}$ is the $w$th literal of clause $w$,}\\\ 0_{2^{d}},\text{
otherwise,}\end{cases}$

and $\boldsymbol{t}_{w}=\boldsymbol{u}-\sum\limits_{s\in
N_{w}}\boldsymbol{v}_{s}$, where $N_{w}=\\{s\in[k]\mathrel{\mathop{\mathchar
58\relax}}\ell_{w,s}\text{ is negative}\\}$ is the set of the indices of
negative literals in $C_{w}$. Also set $r=(mn+m)^{1/p}$.

Define the equation unitary $U_{e}\mathrel{\mathop{\mathchar
58\relax}}\ket{a}\ket{b}\ket{0}\rightarrow\ket{a}\ket{b}\ket{\delta_{|a|,|b|}}$
for each $a,b\in[d]$, and the location indicator unitary as for each
$x_{1},\ldots,x_{n}\in\\{0,1\\},$

$U_{loc}\mathrel{\mathop{\mathchar
58\relax}}\ket{x_{1}}\ket{x_{2}}\ldots\ket{x_{n}}\ket{0}\rightarrow\begin{dcases}\ket{x_{1}}\ket{x_{2}}\ldots\ket{x_{n}}\ket{s},&\text{if
only $x_{s}=1$ and all others are }0,\\\
\ket{x_{1}}\ket{x_{2}}\ldots\ket{x_{n}}\ket{0},&\text{otherwise,}\end{dcases}$

which can both be implemented via $\mathrm{poly}(n)$ elementary gates up to
negligible error. Also, we define the sign literal indicator unitary as
follows: for each $w\in[m]$, $j\in[n]$,

$U_{s\ell}\mathrel{\mathop{\mathchar
58\relax}}\ket{w}\ket{j}\ket{0}\rightarrow\begin{dcases}\ket{w}\ket{j}\ket{s},&\text{if
$x_{j}$ is the $s$th literal of clause $C_{w}$},\\\
\ket{w}\ket{j}\ket{-s},&\text{if $\neg x_{j}$ is the $s$th literal of clause
$C_{w}$},\\\ \ket{w}\ket{j}\ket{0},&\text{otherwise,}\end{dcases}$

which can also be implemented by using $\mathrm{poly}(m,n)$ applications of
$O_{\Phi}$ and $\mathrm{poly}(m,n)$ many elementary gates.

We are now ready to show how to implement $O_{\mathbf{B}}$ and
$O_{\boldsymbol{t}}$. For input $\ket{h}\ket{j}\ket{0}\ket{0}\ket{0}\ket{0}$,
let $\ket{h}=\ket{h_{1}}\ket{h_{2}}$ where $h_{2}$ is the last $n$ bits of $h$
and $h_{1}$ is the remaining prefix. Then we first apply $U_{e}$ to the first,
third, and fifth registers to have
$\ket{h_{1}}\ket{h_{2}}\ket{j}\ket{0}\ket{\delta_{h_{1},0}}\ket{0}\ket{0}$.
After that, apply $U_{s\ell}$ to the first, third, and sixth registers, and
apply $O_{V}$ to the second, third, and seventh registers we get

$\ket{h_{1}}\ket{h_{2}}\ket{j}\ket{0}\ket{\delta_{h_{1},0}}\ket{s}\ket{V_{js}};$

note that $V_{js}=(\boldsymbol{v}_{s})_{j}$. Finally, adding another ancilla
register, we can store the value
$V_{js}\cdot\delta_{h_{1},0}+2m^{1/p}(1-\delta_{h_{1},0})\delta_{h-m\cdot
2^{k},j}$ in the last register. Uncomputing fourth to seventh registers, we
have

$\ket{h_{1}}\ket{h_{2}}\ket{j}\ket{V_{js}\cdot\delta_{h_{1},0}+2m^{1/p}(1-\delta_{h_{1},0})\delta_{h-m\cdot
2^{k},j}}=\ket{h}\ket{j}\ket{(\boldsymbol{v}_{s})_{j}\cdot\delta_{h_{1},0}+2m^{1/p}(1-\delta_{h_{1},0})\delta_{h-m\cdot
2^{k},j}},$

and
$(\boldsymbol{v}_{s})_{j}\cdot\delta_{h_{1},0}+2m^{1/p}(1-\delta_{h_{1},0})\delta_{h-m\cdot
2^{k},j}$ is exactly the coefficient of $\mathbf{B}_{j}(h)$. One can see we
only use $\mathrm{poly}(n,m)$ queries to $O_{V}$, $O^{\dagger}_{V}$,
$O_{\Phi}$, $O_{\Phi}^{\dagger}$ and elementary gates. We can also construct
$O_{\boldsymbol{t}}$ using a similar strategy, which can also be done using at
most $\mathrm{poly}(n,m)$ queries to $O_{V}$, $O^{\dagger}_{V}$, $O_{\Phi}$,
$O_{\Phi}^{\dagger}$, $O_{u}$, $O^{\dagger}_{u}$, and elementary gates.

To see the correctness, consider $\boldsymbol{y}\in\mathbb{Z}^{n}$. If
$\boldsymbol{y}\notin\\{0,1\\}^{n}$, then

$\|\mathbf{B}\boldsymbol{y}-\boldsymbol{t}\|^{p}_{p}\geq\|2m^{1/p}I_{n}\boldsymbol{y}-m^{1/p}\mathbf{1}_{n}\|^{p}_{p}\geq
m(n+2).$

On the other hand, if $\boldsymbol{y}\in\\{0,1\\}^{n}$, then for each
$\mathbf{B}_{w}$

$\displaystyle\|\mathbf{B}_{w}\boldsymbol{y}-\boldsymbol{t}\|^{p}_{p}$
$\displaystyle=\|\sum\limits_{s\in
P_{w}}\boldsymbol{y}_{ind({\ell_{w,s}})}\cdot\boldsymbol{v}_{s}-\sum\limits_{s\in
N_{w}}\boldsymbol{y}_{ind({\ell_{w,s}})}\cdot\boldsymbol{v}_{s}-(u-\sum\limits_{s\in
N_{w}}\boldsymbol{y}_{ind({\ell_{w,s}})}\cdot\boldsymbol{v}_{s})\|^{p}_{p}$
$\displaystyle=\|\sum\limits_{s\in
P_{w}}\boldsymbol{y}_{ind({\ell_{w,s}})}\cdot\boldsymbol{v}_{s}+\sum\limits_{s\in
N_{w}}(1-\boldsymbol{y}_{ind({\ell_{w,s}})})\cdot\boldsymbol{v}_{s}-u\|^{p}_{p}$
$\displaystyle=\|\sum\limits_{s\in
S_{w}(\boldsymbol{y})}\boldsymbol{v}_{s}-u\|^{p}_{p},$

where ${{ind({\ell_{w,s}})}}$ is the index of the variable underlying
$\ell_{w,s}$, $P_{w}=\\{s\in[k]\mathrel{\mathop{\mathchar
58\relax}}\ell_{w,s}\text{ is positive}\\}$ is the set of the indices of
positive literals in $C_{w}$, and $S_{w}(\boldsymbol{y})=\\{s\in
P_{w}\mathrel{\mathop{\mathchar
58\relax}}\boldsymbol{y}_{ind(\ell_{w,s})}=1\\}\cup\\{s\in
N_{w}\mathrel{\mathop{\mathchar
58\relax}}\boldsymbol{y}_{ind(\ell_{w,s})}=0\\}$ is the indices of literals in
$C_{w}$ satisfied by $\boldsymbol{y}$. Because $(V,\boldsymbol{u})$ is a
$(p,k)$-isolating parallelepiped, if $|S_{w}(\boldsymbol{y})|\neq 0$, then
$\|\sum\limits_{s\in
S_{w}(\boldsymbol{y})}\boldsymbol{v}_{s}-\boldsymbol{u}\|^{p}_{p}=1$, and it
will be greater than $1$ otherwise. Also, $|S_{w}(\boldsymbol{y})|\neq 0$ if
and only if $C_{w}$ is satisfied. Therefore, we have that for every satisfying
assignment $\boldsymbol{y}$,

$\|\mathbf{B}\boldsymbol{y}-\boldsymbol{t}\|^{p}_{p}=\sum\limits_{k=1}^{m}\|\mathbf{B}_{k}\boldsymbol{y}-\boldsymbol{t}\|^{p}_{p}+mn=m+mn,$

and for all other unsatisfying assignments $\boldsymbol{y}^{\prime}$,
$\|\mathbf{B}\boldsymbol{y^{\prime}}-\boldsymbol{t}\|^{p}_{p}>m+mn$. As a
result, every satisfying assignment of $\psi=C_{1}\land C_{2}\land\cdots\land
C_{m}$ is the lattice points of lattice
$\operatorname{\mathcal{L}}(\mathbf{B})$ with distance $r=(mn+m)^{1/p}$ to the
target vector $t$, which implies the answer of counting-SAT with input $\psi$
is equal to VCP${}_{p}(\mathbf{B},\boldsymbol{t},r)$. ∎

The theorem above shows how we can connect the counting $k$-SAT problem to the
vector counting problem given access to a $(p,k)$-isolating parallelepiped.
However, it is not always the case that we can compute such an isolating
parallelepiped efficiently. Nevertheless, Aggarwal, Bennett, Golovnev, and
Stephens-Davidowitz [BGS17, ABGS21] also showed the existence of isolating
parallelepiped for some $p,k$ and provided an efficient algorithm for
computing them.

######  Theorem 4.6 ([ABGS21]).

For $k\in\mathbb{Z}_{+}$ and computable $p=p(n)\in[1,\infty)$ if $p$ satisfies
either (1) $p\notin 2\mathbb{Z}$ or (2) $p\geq k$, there exists a
$(p,k)$-isolating parallelepiped $V\in\mathbb{R}^{2^{k}\times k}$,
$\boldsymbol{u}\in\mathbb{R}^{2^{k}}$and it is computable in time
$\mathrm{poly}(2^{k})$.

Therefore, by choosing $k=\Theta(\log n)$ and combining Corollary 2.24 and
Theorems 4.5 and 4.6, we can directly show a $2^{n}$ QSETH lower bound for
VCPp for all non-even $p$. Also, a similar idea works for the q-count and
approximate counting of CNF-SAT: for any CNF-SAT formula $\psi$, using
Algorithm 1 and Lemma 2.22, we can output a number of $k$-CNF formula
$\psi_{1}\ldots,\psi_{N}$ such that
$|\text{sol}(\psi)|=\sum_{i\in[N]}|\text{sol}(\psi_{i})|$. Once we have an
algorithm that solves $\gamma\\#$-$k$-SAT ($\\#_{q}$-$k$-SAT), we can use it
to compute $\gamma$-$\\#k$-SAT$(\psi_{i})$ ($\\#_{q}$-$k$-SAT$(\psi_{i})$) for
all $i\in[N]$, and then by adding the outputs together, we can therefore get a
valid solution to $\gamma$-$\\#$CNFSAT ($\\#_{q}$CNFSAT) with input $\psi$. By
a similar argument of the proof of Corollary 2.24, we know $N$ is bounded by
$2^{o(n)}$. Combining the above arguments with Theorem 4.5, we have following
corollaries.

######  Corollary 4.7.

Let $p\in[1,\infty)\setminus 2\mathbb{Z}$. There is no bounded error quantum
time algorithm that solves VCPp in $O(2^{sn})$ time for a constant $s<1$
unless #QSETH conjecture is false.

######  Corollary 4.8.

Let $\gamma\in[\frac{1}{2^{n}},\frac{1}{2})$, $\hat{h}\in[2^{n}]$, and
$p\in[1,\infty)\setminus 2\mathbb{Z}$. There is no bounded error quantum time
algorithm that solves $\gamma$-VCPp,

  1. 1.

in
$O\left(\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-\hat{h}}{\hat{h}}}\right)^{s}\right)$
time, for any constant $s<1$, whenever $\gamma\hat{h}>1$, and

  2. 2.

in $O(2^{sn})$ time, for any constant $s<1$, whenever $\gamma\hat{h}\leq 1$

unless $\gamma$-#QSETH conjecture is false.

######  Corollary 4.9.

Let $p\in[1,\infty)\setminus 2\mathbb{Z}$. There is no bounded error quantum
time algorithm that solves $\oplus$VCPp in $O(2^{sn})$ time for a constant
$s<1$ unless $\oplus$QSETH conjecture is false.

######  Corollary 4.10.

Let $p\in[1,\infty)\setminus 2\mathbb{Z}$ and $q\in[2^{n}]\setminus\\{1,2\\}$.
There is no bounded error quantum time algorithm that solves $\\#_{q}$VCPp in
$O(2^{sn})$ time for a constant $s<1$ unless #qQSETH conjecture is false.

The following theorem also shows how to connect the approximate vector
counting problem to the closest vector problem. The connection was already
built up in Theorem 3.5 of [Ste16], while we can easily give a quadratic
saving for the number of calls to CVPp oracle by using some basic quantum
tricks if quantum queries are allowed. We include the proof in Appendix B for
completeness.

######  Theorem 4.11.

Let $f(n)\geq 20$ be an efficiently computable function and $p\in[1,\infty)$.
One can solve $f(n)^{-1}$-VCPp using $\mathcal{O}(f^{2})$ quantum queries to
CVPp.

Note that the QSETH lower bound for $f^{-1}$-VCPp depends on $f$. Therefore if
one can show a reduction from $f^{-1}$-VCPp to CVPp using $f^{c}$ for some
constant $c<1$, then it will end up with a better QSETH lower bound for CVPp.

##  5 Hardness of Counting/Parity of OV, Hitting Set, and Set-Cover

In this section, we will discuss the consequences of Corollary 2.24 and
Theorem 2.21 on some well-motivated problems: Orthogonal Vectors, Hitting Set
and Set Cover. Following are the definitions of Hitting Set and its variants.

######  Definition 5.1 (Hitting Set).

For any integers $n,m>0$, the Hitting Set problem is defined as follows: The
input is a collection $\Sigma=(S_{1},\cdots,S_{m})$, where $S_{i}\subset V$
and integer $t>0$, the goal is to output a subset $S^{\prime}\subset V$ such
that $|S^{\prime}|\leq t$ and $\forall i\in[m],|S^{\prime}\cap S_{i}|>0$.

######  Definition 5.2 (Variants of Hitting Set).

For any integers $n,m>0$ and
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$, the input is a collection
$\Sigma=(S_{1},\cdots,S_{m})$, where $S_{i}\subset V$ and integer $t>0$.

  1. 1.

In Count Hitting Set problem, the goal is to output $|S^{\prime}\subset
V\mathrel{\mathop{\mathchar 58\relax}}\left|S^{\prime}|\leq t,\forall
i\in[m],|S^{\prime}\cap S_{i}|>0\right|$.

  2. 2.

In Parity Hitting Set problem, the goal is to output $|S^{\prime}\subset
V\mathrel{\mathop{\mathchar 58\relax}}\left|S^{\prime}|\leq t,\forall
i\in[m],|S^{\prime}\cap S_{i}|>0\right|\mod 2$.

  3. 3.

In Majority Hitting Set, the goal is to output $1$ if $|S^{\prime}\subset
V\mathrel{\mathop{\mathchar 58\relax}}\left|S^{\prime}|\leq t,\forall
i\in[m],|S^{\prime}\cap S_{i}|>0\right|>2^{n-1}$, otherwise output $0$.

  4. 4.

In $\gamma$ approximation of count Hitting Set, the goal is to output an
integer $d$ such that $(1-\gamma)d^{\prime}<d<(1+\gamma)d^{\prime}$ where
$d^{\prime}=|S^{\prime}\subset V\mathrel{\mathop{\mathchar
58\relax}}\left|S^{\prime}|\leq t,\forall i\in[m],|S^{\prime}\cap
S_{i}|>0\right|$.

In [CDL+16], Cygan et al. showed a Parsimonious reduction between CNF-SAT and
Hitting Set. By Parsimonious reduction, we mean a transformation from a
problem to another problem that preserves the number of solutions.

######  Theorem 5.3 (Theorem 3.4 in [CDL+16]).

For any sufficiently large integer $n>0$ and constant $\varepsilon>0$, there
exists a polynomial time Parsimonious reduction from CNF-SAT on $n$ variables
to Hitting Set on $n(1+\varepsilon)$ size universal set.

We get the following corollary.

######  Corollary 5.4.

For any sufficiently large integer $n>0$, constant $\delta>0$ and
$\gamma\in\left[\frac{1}{2^{n}},\frac{1}{2}\right)$, there is no bounded error
quantum algorithm

  1. 1.

in $2^{\frac{n}{2}(1-\delta)}$ time for Hitting Set unless basic-QSETH
(Corollary 2.1) is false.

  2. 2.

in $2^{n(1-\delta)}$ time for Count Hitting Set unless #QSETH(Theorem 2.6) is
false.

  3. 3.

in $2^{n(1-\delta)}$ time for Parity Hitting Set unless
$\oplus$QSETH(Corollary 2.7) is false.

  4. 4.

in $2^{n(1-\delta)}$ time for Majority Hitting Set unless Majority-
QSETH(Corollary 2.8) is false.

  5. 5.

in $\left(\frac{1}{\gamma}\sqrt{\frac{2^{n}-h}{h}}\right)^{1-\delta}$ time for
$\gamma$ approximation of count Hitting Set unless $\gamma$-#QSETH (as in
Theorem 2.21) is false. Here h denote the number of hitting sets to the input
instance.

We use our results form Section 2 to show fine-grained hardness of problems in
complexity class P. More specifically, we study Orthogonal Vectors problem and
its variants defined as follows.

######  Definition 5.5 (Orthogonal Vectors (OV)).

For any integers $d,n>0$, the Orthogonal Vectors (OV) problem is defined as
follows: The input is two lists A and B, each consists of $n$ vectors from
$\\{0,1\\}^{d}$. The goal is to find vectors $a\in A,b\in B$ for which
$\langle a,b\rangle=0$.

######  Definition 5.6 (Variants of OV).

For any integers $d,n>0$ and
$\gamma\in\left[\frac{1}{n^{2}},\frac{1}{2}\right)$, the input is two lists A
and B, each consists of $n$ vectors from $\\{0,1\\}^{d}$.

  1. 1.

In Count OV problem, the goal is to output $|(a,b)\mathrel{\mathop{\mathchar
58\relax}}a\in A,b\in B,\langle a,b\rangle=0|$ i.e. number of pairs (a,b) for
which $a\in A,b\in B$ and $\langle a,b\rangle=0$.

  2. 2.

In Parity OV problem, the goal is to output $|(a,b)\mathrel{\mathop{\mathchar
58\relax}}a\in A,b\in B,\langle a,b\rangle=0|\mod 2$.

  3. 3.

In Majority OV, the goal is to output $1$ if $|(a,b)\mathrel{\mathop{\mathchar
58\relax}}a\in A,b\in B,\langle a,b\rangle=0|>n^{2}/2$, otherwise output $0$.

  4. 4.

In $\gamma$ approximation of count OV, the goal is to output an integer $d$
such that $(1-\gamma)d^{\prime}<d<(1+\gamma)d^{\prime}$ where
$d^{\prime}=|(a,b)\mathrel{\mathop{\mathchar 58\relax}}a\in A,b\in B,\langle
a,b\rangle=0|$.

Orthogonal Vectors (OV) is an important computational problem that lies in
complexity class P. It turns out to be one of the central problem to show
fine-grained hardness of problems in P [Vas15, ABDN18]. Williams showed a
reduction from a reduction from CNF-SAT to OV [Wil05]. We observe that
Williams’s reductions is Parsimonious. Therefore we also get fine-grained
hardness of counting versions of OV. In [BPS21], authors showed
$O(n)$-hardness for OV under basic QSETH assumption.

######  Corollary 5.7.

For any sufficiently large integer $n>0$,
$\gamma\in\left[\frac{1}{n^{2}},\frac{1}{2}\right)$ and any constant
$\delta>0$, there is no bounded error quantum algorithm

  1. 1.

in $n^{2-\delta}$ time for Count OV unless #QSETH (Theorem 2.6) is false.

  2. 2.

in $n^{2-\delta}$ time for Parity OV unless $\oplus$QSETH (Corollary 2.7) is
false.

  3. 3.

in $n^{2-\delta}$ time for Majority OV unless Majority-QSETH (Corollary 2.8)
is false.

  4. 4.

in $\left(\frac{1}{\gamma}\sqrt{\frac{n^{2}-h}{h}}\right)^{1-\delta}$ time for
$\gamma$ approximation of count OV unless $\gamma$-#QSETH (Theorem 2.21)
conjecture is false. Here h denote the number of hitting sets to the input
instance.

We also show fine-grained hardness of parity Set-Cover defined as follows.

######  Definition 5.8 (parity Set-Cover).

For any integers $n,m>0$, the parity Set-Cover problem is defined as follows:
The input is a collection $\Sigma=(S_{1},\cdots,S_{m})$, where $S_{i}\subset
V$ and integer $t>0$, the goal is to output
$\left|\\{\mathcal{F}\subset\Sigma\mathrel{\mathop{\mathchar
58\relax}}\bigcup_{S\in\mathcal{F}}S=V,|\mathcal{F}|\leq t\\}\right|\mod 2$.

In [CDL+16], Cygan et al. showed an efficient reduction from parity Hitting
Set to parity Set Cover. We get the following corollary:

######  Corollary 5.9.

For any sufficiently large integer $n>0$ and $t>0$, parity Set-Cover on a
universal set of size $n$ is $2^{n}$ hard unless $\oplus$QSETH (Corollary 2.7)
is false.

It’s a big open to get an efficient fine-grained reduction from Hitting Set or
CNF-SAT to Set-Cover. Note that Hitting Set and Set Cover are dual problems of
each other but this reduction does not say anything interesting about the
fine-grained hardness of Set-Cover.

##  6 Discussions and open questions

We believe that this paper opens up the possibility of concluding quantum time
lower bounds for many other problems, both for other variants of CNFSAT and
also for problems that are not immediately related to CNFSAT. While this is a
natural broad future direction to explore, we also mention the following few
directions for future work which are more contextual to this paper.

  * •

One of the motivations to use $\textsc{AC}^{0}_{2}$-QSETH in this paper is so
that we can ‘tie’ certain conjectures, that would have otherwise been
standalone conjectures, to one main conjecture. But in the process, we
conjecture compression obliviousness of several properties. It would be nice
if we could also have an ‘umbrella’ conjecture that allows one to establish
compression obliviousness of several properties. For e.g., it would be nice if
we could show that compression obliviousness of a natural property like count
or parity implies compression obliviousness of say $\Delta\textsc{-add-
count}$.

  * •

It will be interesting to see if it is possible to use the QSETH framework (or
the $\textsc{AC}^{0}_{2}$-QSETH conjecture) to give a single exponential lower
bound for CVP in Euclidean norm ($\text{CVP}_{2}$).

## References

  * [ABDN18] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof.  More consequences of falsifying seth and the orthogonal vectors conjecture.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 253–266, 2018.
  * [ABGS21] Divesh Aggarwal, Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz.  Fine-grained hardness of CVP(P) - everything that we can prove (and nothing else).  In SODA, pages 1816–1835. SIAM, 2021.
  * [AC21] Divesh Aggarwal and Eldon Chung.  A note on the concrete hardness of the shortest independent vector in lattices.  Inf. Process. Lett., 167:106065, 2021.
  * [ACL+20] Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang.  On the quantum complexity of closest pair and related problems.  In Proceedings of the 35th Computational Complexity Conference, CCC ’20, Dagstuhl, DEU, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [AK22] Divesh Aggarwal and Rajendra Kumar.  Why we couldn’t prove SETH hardness of the closest vector problem for even norms, and of the subset sum problem!  CoRR, abs/2211.04385, 2022.
  * [AS18] Divesh Aggarwal and Noah Stephens-Davidowitz.  (gap/s)eth hardness of SVP.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 228–238. ACM, 2018.
  * [AW21] Shyan Akmal and R. Ryan Williams.  MAJORITY-3SAT (and related problems) in polynomial time.  CoRR, abs/2107.02748, 2021.
  * [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  J. ACM, 48(4):778–797, 2001.
  * [BGS17] Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz.  On the quantitative hardness of CVP.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 13–24. IEEE Computer Society, 2017.
  * [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation, 2002.
  * [BMN+21] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven.  Focus beyond quadratic speedups for error-corrected quantum advantage.  PRX Quantum, 2:010103, Mar 2021.
  * [BP20] Huck Bennett and Chris Peikert.  Hardness of bounded distance decoding on lattices in $\mathscr{l}$${}_{\mbox{p}}$ norms.  In 35th Computational Complexity Conference, CCC, volume 169 of LIPIcs, pages 36:1–36:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [BPS21] Harry Buhrman, Subhasree Patro, and Florian Speelman.  A Framework of Quantum Strong Exponential-Time Hypotheses.  In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [BPT22] Huck Bennett, Chris Peikert, and Yi Tang.  Improved hardness of BDD and SVP under gap-(s)eth.  In 13th Innovations in Theoretical Computer Science Conference, ITCS, volume 215 of LIPIcs, pages 19:1–19:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [BRSV17] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan.  Average-case fine-grained hardness.  In STOC, pages 483–496. ACM, 2017.
  * [CDL+16] Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström.  On problems as hard as cnf-sat.  ACM Transactions on Algorithms (TALG), 12(3):1–24, 2016.
  * [CHM21] Jordan S. Cotler, Hsin-Yuan Huang, and Jarrod R. McClean.  Revisiting dequantization and quantum advantage in learning tasks.  ArXiv, abs/2112.00811, 2021.
  * [CIP06] C. Calabro, R. Impagliazzo, and R. Paturi.  A duality between clause width and clause density for sat.  In 21st Annual IEEE Conference on Computational Complexity (CCC’06), pages 7 pp.–260, 2006.
  * [DL21] Holger Dell and John Lapinskas.  Fine-grained reductions from approximate counting to decision.  ACM Trans. Comput. Theory, 13(2):8:1–8:24, 2021.
  * [Gro96] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [HNS20] Cupjin Huang, Michael Newman, and Mario Szegedy.  Explicit lower bounds on strong quantum simulation.  IEEE Transactions on Information Theory, 66(9):5585–5600, 2020\.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.
  * [Kan83] Ravi Kannan.  Improved algorithms for integer programming and related lattice problems.  In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pages 193–206, 1983.
  * [LLW19] Rio LaVigne, Andrea Lincoln, and Virginia Vassilevska Williams.  Public-key cryptography in the fine-grained setting.  In CRYPTO (3), volume 11694 of Lecture Notes in Computer Science, pages 605–635. Springer, 2019.
  * [NW99] Ashwin Nayak and Felix Wu.  The quantum query complexity of approximating the median and related statistics.  In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 384–393. ACM, 1999.
  * [Pat92] Ramamohan Paturi.  On the degree of polynomials that approximate symmetric boolean functions (preliminary version).  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, pages 468–474, New York, NY, USA, 1992. Association for Computing Machinery.
  * [Sch05] Rainer Schuler.  An algorithm for the satisfiability problem of formulas in conjunctive normal form.  J. Algorithms, 54(1):40–44, jan 2005.
  * [Sch22] Daan Schoneveld.  Quantum fine-grained complexity: Hitting-set and related problems.  Bachelors thesis, Universiteit van Amsterdam, 2022.
  * [Ste16] Noah Stephens-Davidowitz.  Discrete gaussian sampling reduces to cvp and svp.  In SODA, 2016.
  * [Vas15] Virginia Vassilevska Williams.  Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk).  In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015\.
  * [VDN10] Maarten Van Den Nes.  Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond.  Quantum Info. Comput., 10(3):258–271, mar 2010.
  * [Wil05] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.
  * [Wil18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447–3487. World Scientific, 2018.

##  Appendix A Quantum upper bounds for strong simulation

In order to solve the $\Delta^{\prime}$ additive error strong simulation
problem we will be using the amplitude estimation algorithm given by [BHMT02]
as a subroutine.

######  Theorem A.1 (Implicit in Theorem 12 by [BHMT02]).

Given a natural number $M$ and access to an $(n+1)$-qubit unitary $U$
satisfying

$U\ket{0^{n}}\ket{0}=\sqrt{a}\cdot
e^{i\theta_{1}}\ket{\phi_{1}}\ket{1}+\sqrt{1-a}\cdot
e^{i\theta_{2}}\ket{\phi_{0}}\ket{0},$

where $\ket{\phi_{0}}$ and $\ket{\phi_{1}}$ are arbitrary $n$-qubit states,
$\theta_{1},\theta_{2}\in[0,2\pi]$ and $0<a<1$, there exists a quantum
algorithm that uses $O(M)$ applications of $U$ and $U^{\dagger}$ and
$\widetilde{O}(M)$ elementary gates, and outputs a state $\ket{\Lambda}$ such
that after measuring that state, with probability $\geq 9/10$, the first
register $\lambda$ of the outcome satisfies

$|\sqrt{a}-\lambda|\leq\frac{100\pi}{M}.$

######  Theorem A.2.

Let $n\in\mathbb{N}$. There is a
$O(\mathrm{poly}(n)\frac{1}{\Delta^{\prime}})$ time quantum algorithm for
solving the $\Delta^{\prime}$ additive error strong simulation of Definition
3.4.

###### Proof.

Let $C$ and $x$ denote the input, a quantum circuit on $n$ input variables of
size $\mathrm{poly}(n)$ and $x\in\\{0,1\\}^{n}$ be basis state, respectively.
The task is to estimate the value of $|\bra{x}C\ket{0^{n}}|$ with
$\Delta^{\prime}\in[\frac{1}{2^{n+1}},1)$ additive error approximation.

Let $\ket{\psi}=C\ket{0^{n}}=\sum_{i\in\\{0,1\\}^{n}}\alpha_{i}\ket{i}$ and
$\forall i,\alpha_{i}\in\mathbb{C}$. Let $U^{\prime}$ denote the unitary
$U^{\prime}\mathrel{\mathop{\mathchar
58\relax}}\ket{i}\ket{x}\ket{b}\rightarrow\ket{i}\ket{x}\ket{b\oplus(i=x)}$
for some $i,x\in\\{0,1\\}^{n}$ and $b\in\\{0,1\\}$. It is easy to verify that
combining $C$ and $U^{\prime}$ we can construct a unitary $U$ on $2n+1$ qubits
such that

$U\ket{0^{2n}}\ket{0}=\alpha_{x}\ket{x}\ket{x}\ket{1}+\sum_{i\neq
x}\alpha_{i}\ket{i}\ket{x}\ket{0},$

and $|\alpha_{x}|=|\bra{x}C\ket{0^{n}}|$. Using the _amplitude estimation_
algorithm from Theorem A.1 we can now estimate $|\bra{x}C\ket{0^{n}}|$ to an
additive error of $\Delta^{\prime}$ in
$O(\mathrm{poly}(n)\frac{1}{\Delta^{\prime}})$ time. ∎

##  Appendix B Proof of Theorem 4.11

To prove Theorem 4.11, we first introduce the following theorem.

######  Theorem B.1 ([Ste16], modified Theorem 3.2).

Let ${\mathbf{B}}$ be a basis of a lattice
$\operatorname{\mathcal{L}}({\mathbf{B}})$ and $Q$ be a prime number. Consider
the sparsification process: input any two vectors
$\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}_{Q}^{n}$, the sparsification
process $Spar(\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c})$ outputs a basis
$\mathbf{B}_{Q,\boldsymbol{z}}$ of the sublattice
$\operatorname{\mathcal{L}}_{\boldsymbol{z}}\subset\operatorname{\mathcal{L}}=\\{\boldsymbol{u}\in\operatorname{\mathcal{L}}\mathrel{\mathop{\mathchar
58\relax}}\langle{\boldsymbol{z}},{{\mathbf{B}}^{-1}\boldsymbol{u}}\rangle=0\mod
Q\\}$ and
$\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}={\mathbf{B}}\boldsymbol{c}$.
Then for every $\boldsymbol{t}\in\mathbb{R}^{n}$,
$\boldsymbol{x}\in\operatorname{\mathcal{L}}$ with
$N=|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap\|\boldsymbol{x}-\boldsymbol{t}\|\cdot
B^{n}_{p}|\leq Q$, and $CVP_{p}$ oracle, we have

$\frac{1}{Q}-\frac{N}{Q^{2}}-\frac{N}{Q^{n-1}}\leq\Pr\limits_{\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}_{Q}^{n}}[CVP_{p}(\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}},\operatorname{\mathcal{L}}_{\boldsymbol{z}})=\boldsymbol{x}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}]\leq\frac{1}{Q}+\frac{1}{Q^{n}},$

and in particular,

$\frac{N}{Q}-\frac{N^{2}}{Q^{2}}-\frac{N^{2}}{Q^{n-1}}\leq\Pr\limits_{\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}_{Q}^{n}}[\min\limits_{\boldsymbol{u}\in\operatorname{\mathcal{L}}_{z}}\|(\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}-\boldsymbol{u}\|_{p})\leq\|\boldsymbol{x}-\boldsymbol{t}\|_{p}]\leq\frac{N}{Q}+\frac{N}{Q^{n}}.$

Define $U_{Spar}\mathrel{\mathop{\mathchar
58\relax}}\ket{\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c}}\ket{0}\ket{0}\rightarrow\ket{\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c}}\ket{\mathbf{B}_{Q,\boldsymbol{z}}}\ket{\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}}$,
where
$\mathbf{B}_{Q,\boldsymbol{z}},{\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}}$
are the output of $Spar(\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c})$. Since
given CVPp oracle and a basis $\mathbf{B}$, the sparsification process can be
efficiently done according to the construction, we can also implement the
unitary $U_{Spar}$ efficiently. Then we are ready to show the proof of Theorem
4.11.

Before we enter the proof of Theorem 4.11, we would like to introduce the
promised version of lattice vector counting problem as follows:

######  Definition B.2 (Gap-VCP).

For all $\gamma\geq 0$ and $1\leq p\leq\infty$, the problem
$\gamma$-approximate gap Vector Counting Problem $\gamma$-Gap-VCPp is a
promise problem defined as follows: The input is a lattice a basis
$\mathbf{B}\in\mathbb{R}^{d\times n}$ of lattice
$\operatorname{\mathcal{L}}(\mathbf{B})$, target vector
$\boldsymbol{t}\in\mathbb{R}^{d}$, radius $r\in\mathbb{R}_{+}$, and $N\geq 1$.
It is a No instance if $|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap
r\cdot B^{d}_{p}|\leq N$ and a Yes instance if
$N>(1+\gamma)\cdot|(\operatorname{\mathcal{L}}-\boldsymbol{t})\cap r\cdot
B^{d}_{p}|$.

One can easily see if we can solve $\gamma$-Gap-VCPp, then by using
$\mathrm{poly}(n)$ calls of it we can solve $\gamma$-VCPp. As a result, it
suffices to show how to reduce $\gamma$-Gap-VCPp to CVPp in the following
proof.

###### Proof of Theorem 4.11.

Choose a prime $Q=\Theta(fN)$ and let $O_{CVP}$ be the quantum CVPp oracle.
First we prepare the superposition state
$\frac{1}{Q^{n/2}}\sum\limits_{\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}^{n}_{Q}}\ket{\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c}}\ket{0}\ket{\boldsymbol{t}}\ket{0}\ket{0}$,
apply $U_{Spar}$ on the first six registers, and apply $O_{CVP_{p}}$ on the
fifth, sixth, seventh registers, and then apply subtraction unitary
$U_{sub}\mathrel{\mathop{\mathchar
58\relax}}\ket{\boldsymbol{a}}\ket{\boldsymbol{b}}\ket{0}\rightarrow\ket{\boldsymbol{a}}\ket{\boldsymbol{b}}\ket{\|\boldsymbol{a}-\boldsymbol{b}\|_{p}}$
on the last three registers, we get

$\frac{1}{Q^{n/2}}\sum\limits_{\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}^{n}_{Q}}\ket{\mathbf{B},Q,\boldsymbol{z},\boldsymbol{c}}\ket{\mathbf{B}_{Q,\boldsymbol{z}}}\ket{\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}}\ket{CVP_{p}(\mathbf{B}_{Q,\boldsymbol{z}},\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}})}\ket{\|\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}-CVP_{p}(\mathbf{B}_{Q,\boldsymbol{z}},\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}))\|_{p}}.$

Let
$r_{\boldsymbol{z},\boldsymbol{c}}=\|\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}-CVP_{p}(\mathbf{B}_{Q,\boldsymbol{z}},\boldsymbol{t}+\boldsymbol{w}_{\boldsymbol{z},\boldsymbol{c}}))\|_{p}$
and umcompute the first seven registers, we get

$\frac{1}{Q^{n/2}}\sum\limits_{\boldsymbol{z},\boldsymbol{c}\in\mathbb{Z}_{Q}^{n}}\ket{r_{\boldsymbol{z},\boldsymbol{c}}},$

add another ancilla $\ket{0}$ at the end of the above state, and then apply
$r$-threshold gate

$U_{r}\mathrel{\mathop{\mathchar
58\relax}}\ket{R}\ket{0}\rightarrow\begin{cases}\ket{R}\ket{1}\text{ if }R\leq
r\\\ \ket{R}\ket{0}\text{ otherwise, }\end{cases}$

on it, we get

$\frac{1}{Q^{n/2}}\big{(}\sum\limits_{\begin{subarray}{c}r_{\boldsymbol{z},\boldsymbol{c}}\leq
r\end{subarray}}\ket{r_{\boldsymbol{z},\boldsymbol{c}}}\ket{1}+\sum\limits_{\begin{subarray}{c}r_{\boldsymbol{z},\boldsymbol{c},}\end{subarray}>r}\ket{r_{\boldsymbol{z},\boldsymbol{c}}}\ket{0}\big{)}=\sqrt{a}\ket{\phi_{1}}\ket{1}+\sqrt{1-a}\ket{\phi_{0}}\ket{0},$

where $a=|\\{(\boldsymbol{z},\boldsymbol{c})\mathrel{\mathop{\mathchar
58\relax}}r_{\boldsymbol{z},\boldsymbol{c}}\leq
r\\}|/Q^{n}=\Pr\limits_{\boldsymbol{z},\boldsymbol{c},\in\mathbb{Z}^{n}_{Q}}[r_{\boldsymbol{z},\boldsymbol{c}}\leq
r]$. Note that by Theorem B.1, if
$|\operatorname{\mathcal{L}}\cap(rB^{n}_{p}+\boldsymbol{t})|\leq N$, then

$\Pr\limits_{\boldsymbol{z},\boldsymbol{c},\in\mathbb{Z}^{n}_{Q}}[r_{\boldsymbol{z},\boldsymbol{c}}\leq
r]\leq\frac{N}{Q}+\frac{N}{Q^{n}},$

and if $|\operatorname{\mathcal{L}}\cap(rB^{n}_{p}+\boldsymbol{t})|\geq\gamma
N$, then

$\Pr\limits_{z,c,\in\mathbb{Z}^{n}_{Q}}[r_{\boldsymbol{z},\boldsymbol{c}}\leq
r]\geq\frac{\gamma
N}{Q}-\frac{\gamma^{2}N^{2}}{Q^{2}}-\frac{\gamma^{2}N^{2}}{Q^{n-1}}.$

Observing that $\frac{\gamma
N}{Q}-\frac{\gamma^{2}N^{2}}{Q^{2}}-\frac{\gamma^{2}N^{2}}{Q^{n-1}}-(\frac{N}{Q}+\frac{N}{Q^{n}})=\Theta(f^{-1}(n)N/Q)$,
we know that to distinguish the above two cases, it suffices to learn
$a=\Pr\limits_{\boldsymbol{z},\boldsymbol{c},\in\mathbb{Z}^{n}_{Q}}[r_{\boldsymbol{z},\boldsymbol{c}}\leq
r]$ with additive error $\Theta(f^{-1}(n)N/Q)$. Therefore, by using Theorem
A.1, we can solve $\gamma$-Gap-VCPp with $\gamma=f^{-1}(n)$ using
$\mathcal{O}(fQ/N)$ queries to $O_{CVP_{p}}$. Because $Q=\Theta(fN)$, we
finish the proof. ∎