Abstract 1 Introduction 2 Preliminaries 3 The QSETH framework 4 When certain properties are not P/poly-compression-oblivious References Appendix A Proofs of Claim 40 and Claim 41

Fine-Grained Complexity via Quantum Natural Proofs

Yanlin Chen University of Maryland (QuICS), College Park, MD, USA    Yilei Chen Shanghai Qi Zhi Institute, Tsinghua University, Beijing, China    Rajendra Kumar Indian Institute of Technology Delhi, New Delhi, India    Subhasree Patro Eindhoven University of Technology, The Netherlands    Florian Speelman University of Amsterdam and QuSoft, The Netherlands
Abstract

Buhrman, Patro, and Speelman [11] presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be “compression oblivious” can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as parity and majority are compression oblivious for certain circuit class Λ if subexponentially secure quantum pseudorandom functions exist in Λ, answering an open question in [11].

Keywords and phrases:
Fine-grained complexity, Quantum natural proofs, QSETH, Pseudorandom functions
Category:
RANDOM
Funding:
Yanlin Chen: Acknowledges the support from a QuICS Hartree Postdoctoral Fellowship.
Yilei Chen: Supported by Tsinghua University startup funding, and Shanghai Qi Zhi Institute Innovation Program SQZ202405.
Rajendra Kumar: Supported by the Chandrukha New Faculty Fellowship from IIT Delhi and the Prime Minister Early Career Research Grant from the Anusandhan National Research Foundation (ANRF).
Subhasree Patro: Acknowledges the support from the Dutch Ministry of Education, Culture, and Science through Gravitation project “Challenges in Cyber Security - 024.006.037” for this work.
Florian Speelman: Supported by the Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of the Quantum Delta NL program, and the project Divide and Quantum “D&Q” NWA.1389.20.241 of the program “NWA-ORC”, which is partly funded by the Dutch Research Council (NWO).
Copyright and License:
[Uncaptioned image] © Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Quantum computation theory
Related Version:
Full Version: https://arxiv.org/pdf/2504.10363 [13]
Editors:
Mohit Singh and Tom Gur

1 Introduction

A well-studied problem in complexity theory is CNFSAT, the problem of whether a formula, input in conjunctive normal form, has a satisfying assignment. Not only is there no polynomial time known for CNFSAT, there is also no known algorithm that significantly improves over the brute-force method of checking all 2n assignments. Impagliazzo, Paturi and Zane in [23, 24] conjectured that determining whether an input CNF formula is satisfiable or not cannot be done in time O⁢(2n⁢(1−ε)) for any constant ε>0. They called it Strong Exponential-Time Hypothesis (SETH). As a consequence, SETH-based lower bounds were shown for many computational problems; for example, see [31, 8, 21].

Variants of classical SETH

Subsequent works also explored alternate directions in which the strong exponential-time hypothesis can be weakened and thereby made more plausible. For, e.g.,

  1. 1.

    The satisfiability problem is studied for other (more general) succinct representations of Boolean functions such as BPSAT or CircuitSAT - the problem of whether a polynomial-size branching program or a polynomial-size circuit has a satisfying assignment. Furthermore, respective hardness conjectures for these satisfiability problems, namely NCSETH and CircuitSETH (under the name “CircuitSAT form of SETH”) have also been discussed together with their implications [2, 30].

  2. 2.

    Another direction of study that has made SETH more plausible is by computing more complicated properties of the formula. For example, counting the number of satisfying assignments and computing whether the number of satisfying assignments is even or odd is captured by #⁢SETH and ⊕SETH, respectively; see [17] for example.

Unfortunately, neither SETH nor NCSETH or CircuitSETH, hold relative to quantum computation, as using Grover’s algorithm for unstructured search [19] it is possible to solve the respective satisfiability problems in O⁢(2n/2) time - leading to conjectured lower bounds of complexity Ω⁢(2n/2). While these lower bounds have interesting consequences (as shown by [1, 11]), in the quantum case, generalizing the properties to be computed (as suggested in Item 2) is a way to come up with variants of the hypothesis that enable stronger bounds: for many of such tasks it is likely that the quadratic quantum speedup, as given by Grover’s algorithm, no longer exists. In fact, motivated by this exact observation, Buhrman, Patro, and Speelman [11] 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 quantum analogues of SETH, ⊕SETH, #⁢SETH, NCSETH, ⊕NCSETH, etc., all under one umbrella conjecture.

The QSETH framework

Buhrman et al. consider the problem in which one is given a formula or a circuit representation of a Boolean function f:{0,1}n→{0,1} and is asked whether a property P:{0,1}2n→{0,1} on its truth table111Truth table of a formula/circuit ϕ on n variables, denoted by tt⁢(ϕ), is a 2n bit string derived in the following way tt(ϕ)=○a∈{0,1}nϕ(a); the symbol ∘ denotes concatenation. evaluates to 1. They conjectured that when the circuit representation is obfuscated enough (that is, the description of the circuit provides no advantages over treating the circuit as a black-box with query access to its truth table), then for most properties P (that are “compression oblivious” with respect to the representation), the time taken to compute P on the truth table of poly⁢(n)-sized circuits is lower bounded by 𝖰⁢(P), i.e., the 1/3-bounded error quantum query complexity of P, on all bit strings of length 2n.

Note that there are two requirements to using the QSETH framework. Firstly, the input formula or circuit must be “obfuscated enough” - as we already saw this translates to saying that knowing the description of the input must not help towards computing P any more than just having query access to the truth table of the input. The second requirement (which is the main topic of discussion of this paper) is that the property P itself must be “compression oblivious” - a notion introduced in [11] that we discuss next.

Compression-oblivious properties

Buhrman et al. defined this notion to capture properties whose query complexity on all strings is a lower bound for the time complexity to compute the property even for inputs that are “compressible” as a truth table of small formulas (or circuits). This notion is useful (to their framework) because if the formula (or circuit) is obfuscated enough then one can use the quantum query lower bound of such a property to conjecture a time lower bound of computing that property on a small formula (or circuit).222Here is an example to illustrate why obfuscation is important. Consider the OR property. The quantum query complexity of OR when restricted to truth tables of small CNF or DNF formulas defined on n input variables is Ω⁢(N) where N=2n - let us denote this statement by (⋆). Furthermore, the structure of CNF formulas are not known to help in computing OR more efficiently than O⁢(N). Therefore, we can use the same lower bound from (⋆) to conjecture the lower bound of Ω⁢(N) for CNFSAT in the quantum setting. However, DNF formulas are not obfuscated enough for OR as we can compute OR in poly⁢(n) time when input formulas are DNFs. This means we cannot use the query lower bound of N from (⋆) for the DNFs as we do in the case of CNF formulas. Therefore, before using their framework, one has to be convinced that the property is indeed compression-oblivious with respect to the circuit representation considered. They give various results to initiate the study of the set of compression-oblivious languages; see Section 2.3 in [11]. For example, they show the following.

  • ■

    For simple properties, such as OR,AND, they were able to prove that these are compression-oblivious for polynomial-size 𝖠𝖢20 circuits.

  • ■

    They gave an example of a property that is not compression oblivious for polynomial-sized circuits (or any smaller class of representations).333Consider the following property (Example 7 in [11]), defined on some string z∈{0,1}2n, which we view as the truth table of a formula or circuit: Plarge−c⁢(z)=parity⁢(z)∧[there exists no circuit C of size less than 2n/100 s.t. z=tt⁢(C)]. We use tt⁢(C) to denote the truth table of C. Because most strings are not a truth table of a small circuit, the query complexity of this property is close to the query complexity of parity, i.e., 𝖰⁢(Plarge−c)=Ω⁢(2n). Nevertheless, the property is always 0 when restricted to truth tables of small circuits, and therefore trivial to compute. Therefore, Plarge−c is not compression oblivious for polynomial-sized circuits (or any smaller class of representations).

  • ■

    For more complicated properties, such as parity or majority, they show that proving compression-obliviousness would separate 𝖯 from 𝖯𝖲𝖯𝖠𝖢𝖤; see Theorem 9 in [11]. Their result indicates that unconditionally proving compression-obliviousness for a complicated property is hard. One way around this would be to directly conjecture the compression-obliviousness of such properties, which was the choice of [11]. However, it would be desirable to put this on more solid ground.

One might ask – why is the notion of compression-oblivious properties useful for the QSETH framework when it is hard to prove results about this notion for many properties?

Towards answering this question, consider the ⊕QSETH hypothesis - implicitly stated and discussed in [11] and explicitly stated in [14, 12]. It says,

Conjecture 1 (Conjecture 8.9 in [12]).

For each constant δ>0, there exists c>0 such that there is no bounded-error quantum algorithm that solves ⊕CNFSAT (even restricted to formulas with at most c⋅n2 clauses) in O⁢(2n⁢(1−δ)) time.

One can go about refuting this conjecture in two (immediate) ways.

  1. 1.

    Either one could use the description of the input formulas to help deduce parity of the truth table corresponding to this formula (which would mean that the CNF formula is not obfuscated enough and one could use the structure of the formula towards computing parity more efficiently), or

  2. 2.

    One could use the fact that the set of truth tables on which parity is to be computed is “not too big” (as the number of polynomial length formulas are not too many) and potentially use this information to speed up the computation quantumly.

While both approaches seem like good starting points, the likelihood of Item 1 not working out is probably for the same reason why ⊕SETH is not refuted yet. Which brings us to Item 2. There is a stark contrast between the possible speedups that quantum can offer over classical computation. For example, there exists a quantum query algorithm that can compute any property in O~⁢(N) many queries, when the input is promised to be the N-length truth table of a small formula [4, 5, 25]; such an algorithm is impossible in the classical setting. Although efficient in the number of queries, the algorithm itself is not time efficient. But the existence of this algorithm (in contrast to the lack of one in the classical setting) does alert us that query complexity cannot naively be used to lower bound time complexity in our setting, without taking care. (The results of the current work will indicate that such a fast algorithm is unlikely to refute ⊕QSETH via Item 2.)

As pointed out by Buhrman et al. [11], the proof barrier does not allow one to (easily) prove compression-obliviousness of properties such as parity or majority. It is therefore natural to ask if there are other reasons why certain properties, say parity for example, should be compression oblivious. The authors leave the following open question:

“What complexity-theoretic assumptions are needed to show that, e.g., the parity property, is compression oblivious?”

It is precisely this question we answer in this paper. While our answer doesn’t give us a way around conjecturing the compression obliviousness of these properties, it gives strong evidence supporting the conjecture and the use of the QSETH framework.

1.1 Main idea: arguing compression obliviousness via quantum natural proofs

Following is the answer to the question asked earlier.

Theorem 2 (Informal restatement of Theorem 34).

The properties parity and majority are compression oblivious for a circuit class 𝖬 unless there are no quantum-secure 𝖬-constructible PRFs (of a particular type).444For us, the logical statements “A implies B”, “if A then B” and “¬A unless B” are all equivalent.

In fact, we conclude the same for a larger class of properties (which includes parity and majority). The details are mentioned in the statement of Theorem 34.

1.1.1 Natural proofs by Razborov and Rudich

To prove our results, we use the notion of natural proofs introduced by Razborov and Rudich [28]. Consider a Boolean function defined on other Boolean functions, or equivalently defined on their truth tables. Razborov and Rudich called a property (of Boolean functions) natural if it satisfies certain “constructivity” and “largeness” conditions. Roughly speaking, for their proof, the constructivity condition requires that the property is decidable in poly⁢(n) time when the 2n-sized truth table of an n-input Boolean function is given as input. The largeness condition requires that the property holds for a sufficiently large fraction of the set of all Boolean functions. Moreover, they say a property is useful against a complexity class Λ if every sequence of Boolean functions having the property (infinitely often) defines a language outside of Λ. A natural proof is a proof that establishes that a certain language lies outside of Λ. This can be formally defined as (following the notation of Chow [16]),

Definition 3 (Υ-natural property with density δ, Definition 3 in [16]).

Let Υ be a complexity class and let δ≔(δn)n∈ℕ denote a sequence of positive real numbers. A property D≔(Dn)n∈ℕ is Υ-natural with density δ≔(δn)n∈ℕ if the following statements hold:

  1. 1.

    largeness: ∃n′,∀n>n′, |Dn|≥22n⋅δn, and

  2. 2.

    constructivity: the problem of determining whether a Boolean function fn∈Dn, when given as input the truth table of fn on n variables, is decidable in Υ.

Note that the largeness is captured by the density function (δn)n∈ℕ and constructivity is captured by the complexity class Υ. Additionally, this Υ-natural property is useful against a complexity class Λ if the following statement is satisfied.

Definition 4 (Useful property, Definition 4 in [16]).

Let Λ denote a complexity class. A property D≔(Dn) is useful against complexity class Λ if ∀(fn), we have (fn)∉Λ whenever (fn) is a sequence of Boolean functions satisfying fn∈Dn for infinitely many n.

Using these definitions, Razborov and Rudich prove the following.

Theorem 5 (Main theorem of Razborov and Rudich as stated in [16]).

If there exists a 2kε-hard pseudorandom generator in 𝖲𝖨𝖹𝖤⁢(kc), then there is no 𝖯/poly-constructible natural property with density 1/2nd that is useful against the complexity class 𝖲𝖨𝖹𝖤⁢(ne) whenever e>1+c⁢d/ε.

Broadly speaking, their proof idea is to use the algorithm that computes the 𝖯/poly-natural property of density (δn=12nd) that is useful against 𝖲𝖨𝖹𝖤⁢(ne) (if such a property exists) as a distinguisher to distinguish truth tables of functions with poly⁢(n)-size circuits from truth tables of truly random functions. As this algorithm computes a natural property of density (δn), this means the distinguisher (which is the algorithm itself) can now distinguish a δn fraction of truly random functions. As δn here is quite large (for all n), this translates to a statistical test with a significant advantage to distinguish pseudorandom functions from truly random (n-input) functions. This in turn breaks the assumption about the existence of pseudorandom generators.

1.1.2 Technical overview

We use techniques similar to those of Razborov and Rudich to relate compression obliviousness of parity (and majority) with the existence of quantum-secure pseudorandom functions. We divide our contributions into two broad categories: a part that uses natural proofs, and a part that uses techniques from Fourier analysis of Boolean functions.

Part 1: quantum natural proofs

We use the term quantum natural proofs to mean that the proof relies on natural properties computable within a complexity class that captures quantum computation; equivalently, Υ in Definition 3 is a quantum complexity class. In our case, it is sufficient to consider Υ to be BQTIME⁢(linear). Let P=(Pn)n∈ℕ be the property whose compression obliviousness, with respect to 𝖬, we want to study. Additionally, suppose that P satisfies the following two conditions.

  • ■

    The property P is computable in DTIME⁢(N); where N is the length of the input.

  • ■

    For all S⊆{0,1}N of size |S|≥2N⁢(1−1N2), the 𝖰⁢(Pn|S), i.e., the quantum query complexity to compute P on strings in set S, is Ω⁢(N).

We can show that P has to be compression oblivious with respect to 𝖬 unless a type of quantum secure pseudorandom functions doesn’t exist.

Towards contradiction, let us assume that P is not compression oblivious for 𝖬. This means there exists a quantum algorithm that computes P on truth tables of functions corresponding to 𝖬 in N1−α time for some constant α>0. Let 𝒜 denote this algorithm. Without loss of generality, let us assume 𝒜 is a 1/10-bounded-error quantum algorithm. Let ℬ denote the algorithm that computes P in DTIME⁢(N) as promised earlier. Using 𝒜 and ℬ, we now construct an algorithm 𝒟 that, on all inputs z, does the following:

  1. 1.

    Run 𝒜 on z for M=O⁢(1) many times and note the outputs.

  2. 2.

    Run ℬ on z once.

  3. 3.

    ACCEPT if over M runs of 𝒜 on input z the number of times 𝒜⁢(z)=ℬ⁢(z) is at most 810⋅M, otherwise REJECT. (We need the success probability of 𝒟 to be at least 2/3 therefore choosing M=O⁢(1) suffices.)

Let z be a Boolean string of length N=2n. Let Dn denote the set of N-bit strings that 𝒟 accepts with at least 2/3 success probability. It is easy to see that 𝒟 rejects strings for which 𝒜 correctly computes P (i.e., with success probability 9/10). Recall that, correctness of 𝒜 is only promised for strings that are truth tables of functions having poly⁢(n)-size circuits. There is no guarantee on how 𝒜 behaves outside of this promise. But, we do know that P has a quantum query complexity of Ω⁢(N) on all sets of size at least 2N⁢(1−1N2). As 𝒜 is a strictly-sublinear time algorithm (hence, also a strictly-sublinear query algorithm), it can at best correctly compute P on at most 2N⁢(1−1N2) many strings outside of its promise. This, by construction, means 𝒟 accepts at least 2NN2 many strings of length N and therefore Dn will contain these strings (or alternatively these functions). Now it is easy to see that 𝒟 computes a natural property (Dn)n∈ℕ, of density (δn=122⁢n)n∈ℕ, in 2⋅2n quantum time. Moreover, this property (Dn)n∈ℕ is useful against complexity class 𝖬.

Once we have the natural property which is useful against 𝖬, we run a similar argument as done by Razborov and Rudich. As the algorithm 𝒟 computes (Dn), it can distinguish truth tables of functions with small circuits (i.e., circuits of polylog⁢(n)-depth and poly⁢(n)-size or simply poly⁢(n)-size) from truth tables of truly random functions with 122⁢n advantage. But many believe that it is not possible to have quantum adversaries that are bounded by 2⋅2n time and distinguish pseudorandom functions constructible in 𝖬 with 122⁢n advantage. Then it must be the case that P is compression oblivious for 𝖬.

Part 2: Fourier analysis of Boolean functions

As discussed above, our impossibility results hold for properties that are computable in DTIME⁢(linear) and that have high quantum query complexity even when the computation is restricted to strings from sets of size 2N⁢(1−1N2). Both parity and majority can be computed in DTIME⁢(linear). Moreover, using techniques from Fourier analysis, we are able to show that parity and majority also require Ω⁢(N) many quantum queries on sets of size 2N⁢(1−1N2). Therefore, proving Theorem 2.

1.2 Related work

  • ■

    Chen et al. in [14] use the QSETH framework to conjecture quantum time lower bounds for variants of CNFSAT such as ⊕CNFSAT and #⁢CNFSAT, etc and show lower bounds for several computational problems, such as variants of lattice problems, set-cover, hitting-set, etc., as implications.

  • ■

    Arunachalam et al. in [7] also discuss the notion of quantum natural properties but they do so to relate learning algorithms and circuit lower bounds. As one of the results, they show that containment of the Minimum Circuit Size Problem (MCSP) in BQP implies new circuit lower bounds. This type of result was later extended by [15] to show that a few (more) quantum complexity classes can be separated if the Minimum Quantum Circuit Size Problem (MQCSP) is in BQP. Despite the overlap in topic, both of these works turn out to be complementary to the current work. We use the notion of quantum natural properties to strengthen Buhrman et al.’s QSETH framework by grounding assumptions in cryptography.

  • ■

    Contrary to Razborov and Rudich’s impossibility result, Chow [16] proves the existence of a natural proof useful to imply circuit lower bounds as a consequence of the Exponential-Time Hypothesis (ETH).

1.3 Discussion and open questions

In agreement with [11], we also believe that the notion of compression-oblivious properties is of independent interest. (See the blog post by Aviad Rubinstein also expressing interest [29].)

  • ■

    There may be other connections with topics in meta-complexity theory (as the one we witness in this paper) or say, connections with obfuscation as suspected by Aviad Rubinstein [29] or connections with Kolmogorov complexity (as suggested by Harry Buhrman).

  • ■

    Note that our results cannot be extended to show parity and majority are compression oblivious for 𝖠𝖢𝟢 circuits. This is because 𝖠𝖢𝟢-constructible pseudorandom functions are not secure against 2polylog⁢(n)-time adversaries [26]. Therefore, extending this result to parity or majority for AC20-QSETH, i.e. CNF or DNF input, would be another step towards grounding the (necessary) assumption that such properties are compression oblivious.

  • ■

    It is also worthwhile to study compression obliviousness of properties that don’t meet the criteria discussed in our paper. There might be properties for which one may be able to construct natural proofs of slightly worse densities potentially implying some other complexity theoretic results as shown in [16].

On the other front, our proof technique also allows us to, in a rather black-box way, check if a particular property is likely to be compression-oblivious. One could plausibly extend our results to a larger set of functions that have a similar structure, e.g., a natural candidate would be to show an equivalent statement for symmetric functions with non-negligible mass on high-degree Fourier coefficients. It is very likely that there are in fact many properties of the type we discuss in this paper; one could use techniques similar to ones used in [3] to formally estimate the number of such properties.

1.4 Structure of the paper

In Section 2, we present useful definitions and notations. In Section 3, we formally define the QSETH framework. Our definitions omit an ambiguity from its original version presented in [11]. In Section 4, we prove our main result - the complexity-theoretic evidence for compression obliviousness of parity and majority. A few proofs useful for this section are moved to Appendix A. Additionally, in [13, Appendix A] in the full version of this paper, we reprove some of the earlier results about compression-oblivious properties that were given in [11]; we do this to convince the readers of the correctness of our proposed definition of the QSETH framework.

2 Preliminaries

Most of the definitions and notions presented in this section are taken from [6], and we restate them here for completeness and ease of reading.

2.1 Uniform models of computation

Definition 6 (Function and language recognition).

Let f:{0,1}∗→{0,1} be a Boolean function. The language corresponding to f is the set of strings Lf on which f evaluates to 1, i.e., ∀x∈{0,1}∗,

x∈Lf⇔f⁢(x)=1.

Additionally, we say a Turing machine M decides a language Lf if for all x∈{0,1}∗, whenever M is initialized to the start configuration on input x, the machine M halts with f⁢(x) written on its output tape.

Definition 7 (DTIME, Definition 1.12 in [6]).

Let T:ℕ→ℕ be a function. A language L is in DTIME⁢(T⁢(n)) if there exists a Turing machine M, and there exists a constant c, such that ∀n,∀x∈{0,1}n, M on input x runs in c⋅T⁢(n) steps and decides L.

Definition 8 (BQTIME, adapting Definition 10.9 in [6]).

Let f:{0,1}∗→{0,1} and T:ℕ→ℕ be a function. We say f is computable in quantum T⁢(n)-time, or (equivalently) say Lf∈BQTIME⁢(T⁢(n)), if there is a classical polynomial-time Turing machine that, for every n∈ℕ, on input (1n,1T⁢(n)) outputs the descriptions of a T⁢(n)-size quantum circuit,555A few clarifications. ■ A description of a T-size quantum circuit F≔(F1,…,FT) is an ordered sequence of T elements, where ∀i∈[T] each element Fi=(Gi,wi) specifies a quantum elementary gate Gi∈{CNOT}∪{set of all 1-qubit operations} and the label(s) of the wire(s) wi on which gate Gi will be applied. ■ The action “applying an elementary quantum operation Fi=(Gi,wi)” means applying the elementary gate Gi on wire specified by location(s) wi. ■ The size of the quantum circuit, on the other hand, is the number of elements in its description. let us denote it by F≔(F1,…,FT⁢(n)), such that for every x∈{0,1}n, the output of the following process is f⁢(x) with probability at least 2/3:

  1. 1.

    Initialize an m-qubit quantum state |x⟩⁢|0m−n⟩, where m≤T⁢(n).

  2. 2.

    Apply one after the other T⁢(n) elementary quantum operations F1,…,FT⁢(n) to the state.666See Footnote 5.

  3. 3.

    Measure the last qubit in the computational basis and output the measurement outcome.

A language Lf corresponding to a Boolean function f:{0,1}∗→{0,1} is in BQP if there exists a polynomial p such that f is computable in quantum p⁢(n)-time, or equivalently, Lf∈BQTIME⁢(p⁢(n)).

2.2 Non-uniform model of computation - Boolean circuits and circuit families

Definition 9 (Boolean circuits, Definition 6.1 in [6]).

For every n∈ℕ, an n-input, single-output Boolean circuit is a directed acyclic graph with n sources (i.e., vertices with no incoming edges but could have an unbounded number of outgoing edges) and one sink (i.e., vertex with no outgoing edges); let us denote the sink vertex by s. All non-source vertices are called gates and are labeled with one of ∧, ∨ or ¬ (the logical operations AND, OR and NOT, respectively). The vertices labeled with ∧ and ∨ have fan-in equal to 2 and those labeled with ¬ gate have fan-in 1. The source vertices are labeled with indices i∈[n]. We use label⁢(v) to denote the label of a vertex v. The circuit-size of 𝖢, denoted by |𝖢|, is the total number of vertices in it.

If 𝖢 is a Boolean circuit and x∈{0,1}n is some input, then the output of 𝖢 on x, denoted by 𝖢⁢(x), is defined in the natural way. More formally, for every vertex v of 𝖢 we define a val⁢(v) as follows: if label⁢(v)=i then val⁢(v)=xi and otherwise val⁢(v) is defined recursively by applying the logical operation of v labeled by label⁢(v) on the values of vertices connected to v. The output 𝖢⁢(x) is the value of the sink vertex val⁢(s).

In any situation, if we require that the Boolean circuits are only allowed to have ∧ and ∨ gates with fan-in 2, as opposed to these gates having unbounded fan-in, then we explicitly mention it.

Definition 10 (Circuit family and language recognition, Definition 6.2 in [6]).

Let T:ℕ→ℕ be a function. A T⁢(n)-size circuit family is a sequence {Cn}n∈ℕ of Boolean circuits where for every n, Cn has n inputs and a single output and its circuit size |Cn|≤T⁢(n).

Definition 11 (SIZE).

Let T:ℕ→ℕ be a function. We say a language L∈𝖲𝖨𝖹𝖤⁢(T) if there exists a T⁢(n)-size circuit family {Cn}n∈ℕ such that ∀n, Cn consists of ∧ and ∨ gates with fan-in 2 and ¬ gates of fan-in 1 and, moreover, ∀x∈{0,1}n,x∈L⇔Cn⁢(x)=1.

Definition 12 (Complexity class).

A complexity class is a set of languages.

Definition 13 (Circuit family corresponding to a language).

Let L be a language (as in Definition 6). We say a family of circuits {Cn}n∈ℕ corresponds to language L, if ∀n, ∀x∈{0,1}n, we have x∈L⇔Cn⁢(x)=1.

Definition 14 (𝖯/poly, Definition 6.5 in [6]).

𝖯/poly is the class of languages that are decidable by polynomial-sized circuit families, or equivalently, 𝖯/poly=∪c,d𝖲𝖨𝖹𝖤⁢(c⋅nd)=∪c,d𝖲𝖨𝖹𝖤c,d.

Definition 15 (𝖠𝖢20, Adapting Definition 6.25 in [6]).

A language L is in 𝖠𝖢20 if there exists a polynomial p:ℕ→ℕ and there exists a p⁢(n)-size circuit family {Cn}n∈ℕ corresponding to L where ∀n, circuit Cn uses ¬, ∧ and ∨ gates, with latter two allowed to have unbounded fan-in, and has depth at most 2.

Definition 16 (𝖳𝗒𝗉𝖾−𝖮 complexity class).

We say a complexity class is of 𝖳𝗒𝗉𝖾−𝖮 if it is any of the following complexity classes:

  1. 1.

    For every d∈ℕ and k∈ℕ, we include the class 𝖠𝖢d,k0; we say a language L∈𝖠𝖢d,k0 if there exists a family of Boolean circuits {Cn}n∈ℕ corresponding to L such that ∀n, Cn uses ¬, ∧ and ∨ gates, with latter two allowed to have unbounded fan-in, and has depth at most d and circuit size |Cn|≤nk.

  2. 2.

    For every d∈ℕ and k∈ℕ, we include the class 𝖭𝖢d,k; we say a language L∈𝖭𝖢d,k if there exists a family of Boolean circuits {Cn}n∈ℕ corresponding to L such that ∀n, Cn has depth at most logd⁡n and circuit size |Cn|≤nk.

  3. 3.

    For every d∈ℕ and k∈ℕ, we include the class 𝖲𝖨𝖹𝖤d,k; we say a language L∈𝖲𝖨𝖹𝖤d,k if there exists a family of Boolean circuits {Cn}n∈ℕ corresponding to L such that ∀n, Cn has circuit size |Cn|≤d⋅nk.

2.3 Truth tables of circuits, languages and a few other useful notations

A truth table is binary string capturing the outputs of a Boolean function. If a function is defined on n binary inputs then its corresponding truth table is a Boolean string in {0,1}2n. The notion of a truth table can also be extended to capture the membership of strings in a language by fixing the length of the strings. We formally define these notions as follows.

Definition 17 (Truth tables).

For any n∈ℕ, let fn:{0,1}n→{0,1} be a Boolean function. Then the truth table of fn, denoted by tt⁢(fn), is a 2n-length binary string constructed in the following way:

tt(fn)=○a∈{0,1}nfn(a).

Here fn⁢(a) denotes the output fn on input a. And for the concatenation, the strings a∈{0,1}n are taken in lexicographic order.

For a language L⊆{0,1}∗ the notion of truth table is as follows: for any n∈ℕ, the truth table of L at n, denoted by tt⁢(L,n), is a 2n-length binary vector that can be obtained by concatenating the outputs ba≔[a∈L] for all a∈{0,1}n taken in lexicographic order.

Other useful notations

Let n be an integer. Let fn:{0,1}n→{0,1} be a Boolean function on n input variables.

  • ■

    We use Fn to denote the set of all Boolean functions defined on n input variables; We represent Fn={tt⁢(fn)∣fn⁢ is a Boolean function on ⁢n⁢ variables} as the set of truth tables of all functions fn:{0,1}n→{0,1}, implying Fn={0,1}2n and |Fn|=22n. We also use N=2n.

  • ■

    We overload the notation of tt⁢(⋅) on sets of Boolean functions to denote the following: if S is a set of Boolean functions on n variables then tt⁢(S)={tt⁢(fn)∣fn∈S}.

  • ■

    Let Λ be a complexity class. Let L∈Λ. Furthermore, let fn:0,1n→{0,1} be a Boolean function such that tt⁢(fn)=tt⁢(L,n) then we say fn is a sub-element of Λ.

  • ■

    We sometimes also overload the notation of tt⁢(⋅) on complexity classes to denote the following: if Λ is a complexity class then tt⁢(Λ,n)={tt⁢(fn)∣fn⁢ sub-element in ⁢Λ} or equivalently tt⁢(Λ,n)={tt⁢(L,n)∣L∈Λ}. Furthermore, we use tt⁢(Λ)=⋃n∈ℕtt⁢(Λ,n).

3 The QSETH framework

3.1 Definitions

Definition 18 (Property).

A Boolean property (or just property) is a sequence P≔(Pn)n∈ℕ where each Pn is a set of Boolean functions defined on n variables.

Alternatively, one can view Pn as a set of 2n-length Boolean strings that are truth tables of functions fn∈Pn, or equivalently view it as a function Pn:{0,1}2n→{0,1} such that Pn⁢(tt⁢(fn))=1 if and only if fn∈Pn; see Definition 17 for the definition of a truth table. Also note that it is possible for a property P to be partial. In such a case, for every n, there could be some functions fn for which we don’t care whether or not they belong to Pn.777For example, both the properties PPedit and PPlcs considered in [11] are partial.

Quantum query complexity of P

The (bounded-error) quantum query complexity is defined only in a non-uniform setting; therefore, we define this notion for Pn for every n∈ℕ. A quantum query algorithm ℬ for Pn:{0,1}2n→{0,1}, on an input x∈{0,1}2n begins in a fixed initial state |ψ0⟩, applies a sequence of unitaries U0,Ox,U1,Ox,…,UT, and performs a measurement whose outcome is denoted by z. Here, the initial state |ψ0⟩ and the unitaries U0,U1,…,UT are independent of the input x. The unitary Ox represents the “query” operation, and maps |i⟩⁢|b⟩ to |i⟩⁢|b+xi⁢ mod ⁢2⟩ for all i∈[2n]−1. We say that ℬ is a 1/3-bounded-error algorithm computing Pn if for all x in the domain of Pn, the success probability of outputting z=Pn⁢(x) is at least 2/3. Let cost(ℬ) denote the number of queries ℬ makes to Ox throughout the algorithm. The 1/3-bounded-error quantum query complexity of Pn, denoted by 𝖰1/3⁢(Pn), is defined as 𝖰1/3⁢(Pn)=min⁡{cost⁢(ℬ):ℬ⁢ computes Pn⁢ with error probability ≤1/3}.888Note that if parity≔(parityn)n∈ℕ is the property we are considering, under our definition of parityn the value of 𝖰⁢(parityn) is equal to Ω⁢(2n) and not Ω⁢(n). For the property OR≔(ORn)n∈ℕ then Q⁢(ORn)=Ω⁢(2n2).

Algorithms computing a property P in black-/white-box setting

We say a (bounded-error quantum) algorithm 𝒜 computes a property P (as in Definition 18) in the black-box setting if for all n∈ℕ, for all fn given its truth table as input, i.e., a 2n-length Boolean string, 𝒜 makes (quantum) queries to this input and (with success probability at least 2/3) determines whether or not fn∈Pn. An algorithm computing P in the white-box setting gets a circuit description of fn, which is possibly a more succinct description of fn’s truth table, and the algorithm has to determine whether or not fn∈Pn. We emphasize that, in both the black-/white-box setting, we care about the time that algorithm 𝒜 takes when deciding whether or not fn∈Pn.

We now present the definition of compression-oblivious properties. In simple terms, these are the properties whose quantum query complexity is a lower bound for the time complexity to compute the property even for inputs that are “compressible” as a truth table of small formulas (or circuits). Formally,

Definition 19 (Γd,k-compression-oblivious properties).

Let d,k∈ℕ. Let Γd,k denote a 𝖳𝗒𝗉𝖾−𝖮 complexity class as stated in Definition 16 parameterized by d and k. We say a property P is Γd,k-compression-oblivious, denoted by P∈𝒞⁢𝒪⁢(Γd,k), if for every constant δ>0, for every quantum algorithm 𝒜 that computes P in the black-box setting, ∀n′∈ℕ,∃n≥n′ and ∃ a set L={L1,L2,…}⊆Γd,k of “hard languages”, such that ∀ circuit families {Cn′′1}n′′∈ℕ corresponding to L1, ∀ circuit families {Cn′′2}n′′∈ℕ corresponding to L2, …, the algorithm 𝒜 uses at least 𝖰1/3⁢(Pn)1−δ quantum time on at least one of the inputs in {Cni}i∈[|L|].999While the idea of compression-oblivious properties can be easily expressed informally, describing the notion formally requires discussing intricate details to bridge the connections between uniform (e.g., algorithm 𝒜 computing P) and non-uniform models of computations (e.g., query complexity 𝖰⁢(Pn)).

Definition 20 (compression-oblivious properties w.r.t. 𝖠𝖢20, 𝖭𝖢, 𝖯/poly).

We say a property P:{0,1}∗→{0,1} is

  1. 1.

    P∈𝒞⁢𝒪⁢(𝖠𝖢20) if d=2 and ∃k∈ℕ such that P∈𝒞⁢𝒪⁢(𝖠𝖢d,k0),

  2. 2.

    P∈𝒞⁢𝒪⁢(𝖠𝖢𝟢) if ∃d∈ℕ,∃k∈ℕ such that P∈𝒞⁢𝒪⁢(𝖠𝖢d,k0),

  3. 3.

    P∈𝒞⁢𝒪⁢(𝖭𝖢) if ∃d∈ℕ,∃k∈ℕ such that P∈𝒞⁢𝒪⁢(𝖭𝖢d,k), and

  4. 4.

    P∈𝒞⁢𝒪⁢(𝖯/poly) if ∃d∈ℕ,∃k∈ℕ such that P∈𝒞⁢𝒪⁢(𝖲𝖨𝖹𝖤d,k).

The original definition of compression-oblivious properties, as presented in Section 2.2 of [11], does not clearly enforce a unique ordering of the quantifiers, which can potentially lead to undesirable consequences. Hence, we make the effort of presenting a more formal definition of Γ-compression-oblivious properties in Definitions 19 and 20 (with the approval of the authors [11]).

Having formally defined Γ-compression-oblivious properties for all Γ∈{𝖠𝖢20,𝖠𝖢𝟢,𝖭𝖢,𝖯/poly} we now state the Γ-QSETH conjecture. Earlier in this section, we discussed the difference between computing a Boolean property in a black-box setting versus computing the same property in a white-box setting. The compression-oblivious properties are those properties for which its corresponding quantum query complexity lower bounds the time complexity in the black-box setting. For such properties, Buhrman et al. conjectured that the time complexity of computing these properties in the white-box setting is as bad as it is in the black-box setting. This assumes that the succinct description of the Boolean functions doesn’t help in computing the properties more efficiently. (This is similar to the Black-Box Hypothesis (BBH) stated in [22].) More formally,

Conjecture 21 (Γ-QSETH, a more formal presentation of Conjecture 5 in [11]).

Let Γ∈{𝖠𝖢20,𝖠𝖢𝟢,𝖭𝖢,𝖯/poly} be a complexity class (as in Definition 12). Let P be a Γ-compression-oblivious property. The Γ-QSETH conjecture states that ∃d,∃k∈ℕ, such that for every constant δ>0, for every quantum algorithm 𝒜 that computes P in the white-box setting, ∀n′∈ℕ,∃n≥n′, ∃ a set L={L1,L2,…}⊆Γd,k, ∀ circuit families {Cn′′1}n′′∈ℕ corresponding to L1, ∀ circuit families {Cn′′2}n′′∈ℕ corresponding to L2, …, the algorithm 𝒜 uses at least 𝖰1/3⁢(Pn)1−δ quantum time on at least one of the inputs in {Cni}i∈[|L|]. Note that Γd,k is a 𝖳𝗒𝗉𝖾−𝖮 complexity class corresponding to Γ.

3.2 Relevance

Note that a basic version of the QSETH conjecture and its implications has already been discussed in complementary works [1, 11], and other variants of QSETH are discussed more recently in [14] and in Chen’s PhD thesis [12]. For example,

Conjecture 22 (Basic-QSETH, Conjecture 8.3 in [12]).

For each constant δ>0, there exists c>0 such that there is no bounded-error quantum algorithm that solves CNFSAT (even restricted to formulas with at most c⁢n2 many clauses) in O⁢(2n⁢(1−δ)2) time.

Conjecture 23 (⊕QSETH, Conjecture 8.9 in [12]).

For each constant δ>0, there exists c>0 such that there is no bounded-error quantum algorithm that solves ⊕CNFSAT (even restricted to formulas with at most c⁢n2 many clauses) in O⁢(2n⁢(1−δ)) time.

Conjecture 24 (#⁢QSETH, Conjecture 8.8 in [12]).

For each constant δ>0, there exists c>0 such that there is no bounded-error quantum algorithm that solves #⁢CNFSAT (even restricted to formulas with at most c⁢n2 many clauses) in O⁢(2n⁢(1−δ)) time.

We are able to get these conjectures as a corollary to our QSETH framework. More precisely,

Corollary 25.

The 𝖠𝖢20-QSETH implies Conjecture 22. Additionally, if we assume that parity∈𝒞⁢𝒪⁢(𝖠𝖢20) then 𝖠𝖢20-QSETH implies Conjectures 23 and 24.

Proof.

The proof of OR∈𝒞⁢𝒪⁢(𝖠𝖢20) was first given in [11] (we also present the proof in the full version of this paper). Thereafter, setting d=2 and k=3 for 𝖠𝖢20-QSETH conjecture implies Conjectures 22, 23, and 24. ◀

Therefore, all the QSETH-based lower bounds presented in Chen’s PhD thesis [12] immediately follow from our QSETH framework.

4 When certain properties are not P/poly-compression-oblivious

In this section, we show that it is reasonable to conjecture that there exist d′,k′∈ℕ and d′′,k′′∈ℕ for which properties such as parity and majority are 𝖲𝖨𝖹𝖤d′,k′-compression-oblivious and 𝖲𝖨𝖹𝖤d′′,k′′-compression-oblivious, respectively. We do so by relating this conjecture to topics in circuit complexity and pseudorandomness. In fact, we are able to show similar consequences for properties that satisfy certain constraints. parity and majority happen to be such properties.

Following the notation about natural proofs from [28] and [16], we now define the following.

Definition 26 (Υ-natural property with density δ).

Let Υ be a complexity class (as in Definition 12) and let δ≔(δn)n∈ℕ denote a sequence of positive real numbers. A property D≔(Dn)n∈ℕ (as in Definition 18) is Υ-natural with density δ≔(δn)n∈ℕ if the following statements hold:

  1. 1.

    largeness: ∃n′,∀n>n′, |Dn|≥22n⋅δn, and

  2. 2.

    constructivity: the problem of determining whether a Boolean function fn∈Dn, when given as input the truth table of fn on n variables, is decidable in Υ, which in more formal terms translates to saying LD∈Υ where LD≔⋃n∈ℕ{tt⁢(fn)∣fn∈Dn}.

Definition 27 (Quasi-useful property, Definition 5 in [16]).
101010Note that Razborov and Rudich use the notion of useful property which is defined for infinitely many n. However, for our results the notion of quasi-useful property (defined for all sufficiently large n) makes more sense so we use this instead.

Let Λ denotes a complexity class. A property D≔(Dn), or equivalently the corresponding language LD≔⋃n∈ℕ{tt⁢(gn)∣gn∈Dn}, is quasi-useful against complexity class Λ if ∀(fn), we have (fn)∉Λ whenever (fn) is sequence of Boolean functions satisfying fn∈Dn for all sufficiently large n.

Our goal is to realize the chain of arguments as illustrated in Figure 1.

Figure 1: Chain of arguments presented in this section. We discuss the implications when a certain class of properties P are not Λ-compression-oblivious in links (A) and (B). In link (C) we show that majority and parity belong to this class of properties.
Realising link (A)

The proof idea is as follows. Let Λ=𝖲𝖨𝖹𝖤d,k. Our choice of d,k will be clear later. If parity∉𝒞⁢𝒪⁢(Λ) (or say majority∉𝒞⁢𝒪⁢(Λ) may be for another choice of d,k) then (from the definition of compression-oblivious properties) there exists a quantum algorithm that computes the parity (or majority) of truth tables of circuits C that are sub-elements of Λ in time sublinear in the size of the input tt⁢(C). Using this algorithm and the linear time deterministic algorithm to compute parity (or majority) on all strings of length |tt⁢(C)|, we will construct a BQTIME⁢(linear)-natural property that is quasi-useful against complexity class Λ. Interestingly enough, the idea also generalizes to other simple properties that satisfy certain requirements; we formalize that in the statement of Lemma 28.

Lemma 28.

Let d,k∈ℕ and Λ=𝖲𝖨𝖹𝖤d,k. If a property P:{0,1}∗→{0,1}, or alternatively denoted as (Pn)n∈ℕ (as in Definition 18), satisfies the following conditions:

  1. 1.

    P∉𝒞⁢𝒪⁢(Λ),

  2. 2.

    P on inputs of length N is computable in DTIME⁢(N), which more formally means LP≔⋃n∈ℕ{tt⁢(fn)∣fn∈Pn}∈DTIME⁢(N), and

  3. 3.

    ∀S⊆{0,1}N of size |S|≥2N⁢(1−1N2), any 1/3-bounded-error quantum query algorithm that computes Plog⁡N on each x∈S requires Ω⁢(N) queries,

then there exists a BQTIME⁢(2⋅N)-natural property (Dn) with density δn=1N2 and this natural property is quasi-useful against complexity class Λ.

Proof.

Let d,k∈ℕ and let Λ=𝖲𝖨𝖹𝖤d,k. From Definition 19 we say, P∉𝒞⁢𝒪⁢(Λ) if and only if ∃δ>0, ∃ algorithm 𝒜 computing property P such that ∃n′∈ℕ and ∀n≥n′, ∀L={L1,L2,…}⊆Λ, 𝒜 uses at most Q1/3⁢(Pn)1−δ quantum time on all inputs in {tt⁢(Li,n)}i∈[|L|].

Then, let n≥n′, let N=2n and let L be the largest subset of Λ, i.e., the set Λ itself, 𝒜 computes the property in at most Q1/3⁢(Pn)1−δ time for all binary strings in tt⁢(Λ)={tt⁢(Li,n)}i∈[|L|]. Furthermore, we have |tt⁢(Λ)|≤2d′⋅nk for some d′>d; this is because all the languages Li∈Λ which means for every Li there must exist a circuit family {Cni}n∈ℕ with |Cn|≤d⋅nk and the number of such circuits is at most 2d′⋅nk which means the number of unique 2n-length truth tables that Λ can hold is at most 2d′⋅nk. W.l.o.g., let us assume that 𝒜 computes P with success probability at least 9/10 (as we can boost the probability of success by running the 1/3-bounded-error algorithm 𝒜 and then take majority voting). For all n>n′, for all x∈tt⁢(Λ,n), the algorithm 𝒜 computes P⁢(x) in 𝖰1/10⁢(Plog⁡|x|)1−δ≤|x|1−δ time for some constant δ>0.

In addition, let ℬ denote a deterministic (quantum or classical) algorithm that computes P on all y∈{0,1}∗ in Θ⁢(|y|) time – upper and lower bound follow from Item 2 and Item 3 of the theorem statement, respectively. Using 𝒜 and ℬ we now construct Algorithm 𝒟 that on an input z∈{0,1}N does the following:

  1. 1.

    Run 𝒜 on z for M=O⁢(1) times and note the outputs.

  2. 2.

    Run ℬ on z once.

  3. 3.

    Accept if over M runs of 𝒜 on input z the number of times 𝒜⁢(z)=ℬ⁢(z) is at most 810⋅M, otherwise reject. We need the success probability of 𝒟 to be at least 2/3 therefore choosing M=O⁢(1) suffices.

Notice that Algorithm 𝒟 (with high probability) computes a property that is quasi-useful (Footnote 10) against complexity class Λ. This is true because ℬ⁢(z)=P⁢(z) for all z and whenever z∈tt⁢(Λ) the Pr⁢[𝒜⁢(z)=P⁢(z)]≥0.9, which means the outputs 𝒜⁢(z) and ℬ⁢(z) are equal more than 9/10 of the M times. Therefore, if z∈tt⁢(Λ) then 𝒟 rejects z.

What is left is to argue that Algorithm 𝒟 computes a BQTIME⁢(2⋅N)-natural property that satisfies both the largeness and contructivity conditions as mentioned in Definition 26. Let z∈Fn and let Dn={z∣|z|=2n⁢ and Algorithm ⁢𝒟⁢ accepts ⁢z}.

  • ■

    Algorithm 𝒟 on any z of size N=2n can in at most 2⋅N quantum time decide whether or not z∈Dn; hence satisfying the constructivity condition.

  • ■

    We argue about the largeness condition of |Dn|≥2N⋅δn for δn=1N2 in the following way. Consider the set Fn, i.e., the set of truth tables of all Boolean functions defined on n input variables. For a string z∈Fn, the algorithm 𝒟 rejects z only if Pr⁢[𝒜⁢(z)=P⁢(z)]>8/10. In other words, 𝒟 rejects z whenever z∈Fn∖Dn; see Figure 2. The runtime of Algorithm 𝒜 on N-length inputs is O⁢(N1−β) time (for a constant β>0), and we know from Item 3 in the statement of the theorem that 𝒜 cannot compute P correctly (with success probability greater than 2/3) on sets bigger than 2N⁢(1−1N2). Hence, |Fn∖Dn|≤2N⋅(1−1N2), which means |Dn|≥2NN2.

This concludes the proof of Lemma 28. ◀

Figure 2: A pictorial representation of the fraction of 2n-length strings that the algorithm 𝒟 accepts. Recall that Fn denotes the full set {0,1}2n; hence, |Fn|=22n. The set tt⁢(Λ,n) denotes the set of strings {tt⁢(L,n)∣L∈Λ}. Algorithm 𝒜 is guaranteed to accept all strings from tt⁢(Λ,n) with success probability at least 9/10 and no guarantee whatsoever on strings in Fn∖tt⁢(Λ,n). The set Dn denotes the set of 2n-length strings that Algorithm 𝒟 accepts.
Realising link (B)

We will now show the cryptographic implications when properties like parity and majority are not compression-oblivious. In link (A) we showed that, if either of these properties is not compression-oblivious with respect to complexity class Λ=𝖲𝖨𝖹𝖤d,k for some constants d,k∈ℕ, then we can construct a BQTIME⁢(2⋅2n)-natural property useful against Λ. Any quantum algorithm computing this natural property can now be used to distinguish pseudorandom functions constructible in Λ=𝖲𝖨𝖹𝖤d,k from truly random functions. However, such linear-time (linear in the length of the truth table of the functions) quantum distinguishers are not believed to exist. Therefore, it is plausible that a quantum algorithm computing this natural property in the specified time does not exist.

Let us recall the standard definition of pseudorandom functions [18].

Definition 29 (Keyspace).

Let K:ℕ→ℕ be a function. A key space 𝒦 generated by the function K is a set of sets defined as 𝒦={{0,1}K⁢(n)}n∈ℕ and we use 𝒦⁢(n) to denote the set {0,1}K⁢(n).

Note that, for our results, the function K is always chosen to be a polynomial.

Definition 30 (Pseudorandom functions (PRFs)).

A set F={fk:{0,1}n→{0,1}}n∈ℕ,k∈𝒦⁢(n), is called a family of pseudorandom functions with key space 𝒦 generated by function K if for all probabilistic polynomial time (p.p.t.) adversary A, there is a negligible function ε such that for all n∈ℕ,

|Prk⁡[Afk⁢(⋅)⁢(1n)=1]−Pr𝖳𝖱⁡[A𝖳𝖱⁢(⋅)⁢(1n)=1]|<η⁢(n),

where the probability is also over the random string used by A, 𝖳𝖱 denotes a truly random function from {0,1}n to {0,1}.

Sometimes we may strengthen or weaken the definition by letting the adversary’s running time be T⁢(n)-bounded, and letting the distinguishing probability to be less than some specific function η⁢(n). In this case, we call it a (K,T,η)-PRF. Additionally, if the family F, which can be interpreted as a families of circuits, corresponds to languages in Λ, then we call it as Λ-constructible (K,T,η)-PRFs.

Pseudorandom functions can also be defined against quantum adversaries making (classical or) quantum queries; see [32] for example. Formally stated as follows.

Definition 31 (Quantum-secure PRFs).

A set F={fk:{0,1}n→{0,1}}k∈𝒦⁢(n),n∈ℕ is called a family of quantum-secure pseudorandom functions with key space 𝒦 generated by a function K if for all polynomial time (polynomial in the length of its input) quantum adversary A making quantum queries, there is a negligible function ε such that for all n∈ℕ,

|Prk⁡[Afk⁢(⋅)⁢(1n)=1]−Pr𝖳𝖱⁡[A𝖳𝖱⁢(⋅)⁢(1n)=1]|<η⁢(n),

where the probability is also over the random string used by A, 𝖳𝖱 denotes a truly random function from {0,1}n to {0,1}.

Sometimes (just as we do for PRFs) we may strengthen or weaken the definition by letting the adversary’s running time be T⁢(n)-bounded, and letting the distinguishing probability governed by some other function η⁢(n). In this case, we denote them by (K,T,η)-quantum-secure-PRFs. Additionally, if the family F, which can be interpreted as a families of circuits, correspond to languages in Λ, then we call it as Λ-constructible (K,T,η)-quantum-secure-PRFs.

Using this notion of quantum-secure pseudorandom functions, we are able to prove the following.

Lemma 32.

Let d,k∈ℕ. If there exists a BQTIME⁢(2⋅2n)-natural property of density δn≥122⁢n that is quasi-useful against the complexity class Λ=𝖲𝖨𝖹𝖤d,k then there doesn’t exist any Λ-constructible (d⋅nk,2⋅2n,122⁢n)-quantum-secure-PRF; the size of the truth table of function fn is 2n.

Proof.

Let N=2n be the length of the truth table of functions on n variables. Let P be a BQTIME⁢(2⋅N)-natural property of density δn≥122⁢n that is quasi-useful against the complexity class 𝖲𝖨𝖹𝖤d,k. Let 𝒞 be the algorithm that computes this property P. Because 𝒞 computes P, for any (sufficiently large) value of n the following statements hold.

  • ■

    Algorithm 𝒞 rejects z whenever z is a string from tt⁢(𝖲𝖨𝖹𝖤d,k,n); this is because P is quasi-useful against 𝖲𝖨𝖹𝖤d,k.

  • ■

    There are at least 122⁢n⋅22n number of functions in Fn that 𝒞 accepts; this is because the P has density δn≥122⁢n.

  • ■

    Furthermore, 𝒞 runs in BQTIME⁢(2⋅2n).

Combining these observations we can see that

|Pr⁢[𝒞⁢(x)=1]−Pr⁢[𝒞⁢(y)=1]|≥122⁢n

when x is chosen at random from tt⁢(𝖲𝖨𝖹𝖤d,k,n) and y is chosen at random from Fn. This means 𝒞, despite being an algorithm running in BQTIME⁢(2⋅N) time, can distinguish 𝖲𝖨𝖹𝖤d,k-constructible pseudorandom functions from the set of all random functions. Hence, showing that 𝖲𝖨𝖹𝖤d,k-constructible (d⋅nk,2⋅2n,122⁢n)-quantum-secure-PRFs do not exist. ◀

We could also state our assumption about the existence of quantum-secure PRFs as a conjecture.

Conjecture 33.

There exists d,k∈ℕ for which 𝖲𝖨𝖹𝖤d,k-constructible (d⋅nk,2⋅2n,122⁢n)-quantum-secure-PRFs exist.

Using Lemma 28 and Lemma 32 we can now claim the following statement.

Theorem 34.

Let P:{0,1}∗→{0,1} be the Boolean property satisfying Items 2 and 3 stated in Lemma 28. Then property P∈𝒞⁢𝒪⁢(𝖯/poly) unless Conjecture 33 is false.

Proof.

If P∉𝒞⁢𝒪⁢(𝖯/poly) then ∀d,∀k∈ℕ we have P∉𝒞⁢𝒪⁢(𝖲𝖨𝖹𝖤d,k); see Definition 20. For every value of d,k we will then be able to construct a BQTIME⁢(2⋅2n)-natural property that will be quasi-useful against 𝖲𝖨𝖹𝖤d,k. This means for all values of d,k we will no longer have 𝖲𝖨𝖹𝖤d,k-constructible (d⋅nk,2⋅2n,122⁢n)-quantum-secure-PRFs. Hence, falsifying Conjecture 33. ◀

▶ Remark 35.

Although not explicitly used in this paper, we would also like to mention that under the assumption that the learning with errors (LWE) conjecture holds against quantum algorithms, there exist quantum-secure PRFs evaluatable by 𝖭𝖢2 circuits (𝖭𝖢1 if we assume the quantum hardness of RingLWE) [9]. This suggests that under the quantum hardness of LWE (resp. RingLWE), parity and majority are compression obliviousness with respect to the complexity class 𝖭𝖢2 (resp. 𝖭𝖢1).

▶ Remark 36 (Strengthening Conjecture 33 with OWFs).

First, recall the definition of one-way functions.

Definition 37 (One-way functions (OWFs)).

A function g:{0,1}∗→{0,1}∗ is called a (T,η)-one-way function if there is a polynomial p such that for all adversary A running in time T, for all n∈ℕ,

Prx←{0,1}p⁢(n)⁡[A⁢(1n,g⁢(x))=x′⁢ such that ⁢g⁢(x′)=g⁢(x)]<η⁢(n).

For example, when T=2n, we can set the length of the domain and range to be p⁢(n)=n2, therefore a T=2n adversary will not trivially break such an OWF.

It is known [20, 18] that (K,T,η)-PRF exists if (poly⁢(T),poly⁢(η))-one-way function exists. Furthermore, the same result holds against quantum adversaries even if the adversary for the PRF is allowed to make superposition queries [32]. Therefore, we can say that (2n,2−ω⁢(n))−PRF against quantum adversaries exists as long as (poly⁢(2n),poly⁢(2−ω⁢(n)))-one-way function against quantum adversaries exists. Therefore, the following conjecture implies Conjecture 33.

Conjecture 38.

Quantum secure (poly⁢(2n),poly⁢(2−ω⁢(n)))-one-way functions exist.

Realising implication (C)

Earlier in this section we discussed that the arguments presented work for properties that satisfy Items 1, 2, and 3 in the statement of Lemma 28. For properties like parity or majority it is trivial to see that they admit a linear time (quantum and classical) deterministic algorithm. However, it is not immediately clear if the query complexity of computing these properties is “high” on sets S⊂Fn that are not the full set Fn but still are relatively “large”. Using techniques from Fourier analysis of Boolean properties, we can show that this is indeed the case with parity and majority. In fact, we are able to say something more. More precisely, we show that the following statement holds.

Lemma 39.

Let N be an integer and let S∈{0,1}N be a subset of size s≥2N⁢(1−1N2). Let P:{0,1}N→{−1,1} be a Boolean property with Q⁢(P)=Ω⁢(N) and the N-degree Fourier coefficient |P^⁢([N])|≥12⁢N.111111Note that we use these constants so that Lemma 39 can be almost directly used for parity and majority. However, one can modify these constants to accommodate other properties as well. Then every quantum algorithm that, with error probability ε≤12⋅N2, computes P on each x∈S uses Ω⁢(N) queries.

Proof.

Suppose there exists a T-query algorithm, let us denote by 𝒜S, to compute property P on all x∈S with worst-case error probability ε≤12⋅N2. W.l.o.g, we can assume that the output of 𝒜S is in {−1,1}. Let R⁢(x) denote the probability that 𝒜S outputs −1; then we can immediately see that ∀x∈S,

(1−2⁢R⁢(x))⋅P⁢(x)≥(1−2⁢ε). (1)

We will now estimate the degree of the polynomial R⁢(x). Observe that deg⁢(R⁢(x))=deg⁢(1−2⁢R⁢(x)). Let Q⁢(x)=(1−2⁢R⁢(x)) and let ε′=(1−2⁢ε). Let the Fourier expansions of Q⁢(x)=∑B⊆[N] Q^⁢(B)⁢χB⁢(x) and P⁢(x)=∑B⊆[N] P^⁢(B)⁢χB⁢(x), respectively.

Towards a contradiction, suppose that deg⁢(Q⁢(x))<N then Q^⁢([N])=0, which implies

(∑B∈2[N]Q^⁢(B)⋅P^⁢(B))2 =(1)⁢(∑B∈2[N]∖[N]Q^⁢(B)⋅P^⁢(B))2
≤(2)⁢(∑B∈2[N]∖[N]Q^⁢(B)2)⋅(∑B∈2[N]∖[N]P^⁢(B)2)
≤(3)⁢1−12⁢N;

(1) using the assumption that Q^⁢([N])=0, (2) is argued using Cauchy-Schwarz inequality and (3) comes by using Parseval’s theorem (on Boolean output and bounded functions). However, from Equation 1 we have that ∀x∈S,Q⁢(x)⋅P⁢(x)≥ε′ which means

(∑B∈2[N]Q^⁢(B)⋅P^⁢(B))2 =(12N⁢∑x∈{0,1}NQ⁢(x)⋅P⁢(x))2
=12N⁢(∑x∈SQ⁢(x)⋅P⁢(x)+∑x∈{0,1}N∖SQ⁢(x)⋅P⁢(x))2
≥(ε′⋅|S|2N+12N⁢∑x∈{0,1}N∖SQ⁢(x)⋅P⁢(x))2
≥(ε′⋅|S|2N−2N−|S|2N)2
≥((1−1N2)⋅|S|2N−2N−|S|2N)2
≥(1−3N2)2
>1−6N2,

leading to a contradiction; therefore, deg⁢(Q⁢(x))=deg⁢(R⁢(x))=N; using polynomial method [10] this implies T=Ω⁢(N). ◀

Having stated Lemma 39 we can now immediately prove similar query lower bounds for parity and a variant of majority as their N-degree Fourier coefficients are 1 and at least 2π⁢N, respectively [27]. Moreover, this kind of result can be extended to show similar lower bounds for all Boolean properties P that have a non-negligible Fourier-mass of high degree coefficients. In fact, for parity we can show that similar lower bounds hold even on smaller sets as well. Also, we can prove such query lower bounds for majority and st-majority. More precisely,

Claim 40 (see Lemma 43 in Appendix A for proof).

Let S∈{0,1}N be a subset of size s≥0.8⋅2N. Every quantum algorithm that, with success probability at least ≥2/3, computes parity on each x∈S uses Ω⁢(N) queries.

and,

Claim 41 (see Lemma 48 in Appendix A for proof).

Let S∈{0,1}N be a subset of size s≥2N⁢(1−12⋅N2). Every quantum algorithm that, with success probability (1−ε)≥(1−12⋅N2), computes majority (st-majority) on each x∈S uses Ω⁢(N) queries.

The result proved in Lemma 28 when combined with the results stated in Claims 40 and 41 along with Theorem 34 lead us to the following result.

Corollary 42.

Let Λ=𝖯/poly be the complexity class. The properties parity∈𝒞⁢𝒪⁢(Λ), majority∈𝒞⁢𝒪⁢(Λ) and st-majority∈𝒞⁢𝒪⁢(Λ) unless Conjecture 33 is false.

References

  • [1] 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 für Informatik. doi:10.4230/LIPIcs.CCC.2020.16.
  • [2] Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 375–388. ACM, 2016. doi:10.1145/2897518.2897653.
  • [3] Andris Ambainis. A note on quantum black-box complexity of almost all boolean functions. Inf. Process. Lett., 71(1):5–7, 1999. doi:10.1016/S0020-0190(99)00079-4.
  • [4] Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita. Quantum identification of boolean oracles. In Volker Diekert and Michel Habib, editors, STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, volume 2996 of Lecture Notes in Computer Science, pages 105–116. Springer, 2004. doi:10.1007/978-3-540-24749-4_10.
  • [5] Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, and Shigeru Yamashita. Improved algorithms for quantum identification of boolean oracles. Theor. Comput. Sci., 378(1):41–53, 2007. doi:10.1016/J.TCS.2006.12.013.
  • [6] Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  • [7] Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 562–573. IEEE, 2021. doi:10.1109/FOCS52979.2021.00062.
  • [8] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51–58. ACM, 2015. doi:10.1145/2746539.2746612.
  • [9] Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 719–737. Springer, 2012. doi:10.1007/978-3-642-29011-4_42.
  • [10] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. doi:10.1145/502090.502097.
  • [11] 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. doi:10.4230/LIPIcs.STACS.2021.19.
  • [12] Yanlin Chen. On Quantum Algorithms and Limitations for Convex Optimization and Lattice Problems. PhD thesis, University of Amsterdam, 2024.
  • [13] Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman. Fine-grained complexity via quantum natural proofs. arXiv:2504.10363, 2025. doi:10.48550/arXiv.2504.10363.
  • [14] Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman. QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More. In Alina Ene and Eshan Chattopadhyay, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:24, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.6.
  • [15] Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.47.
  • [16] Timothy Y. Chow. Almost-natural proofs. Journal of Computer and System Sciences, 77(4):728–737, 2011. doi:10.1016/J.JCSS.2010.06.017.
  • [17] 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. doi:10.1145/2925416.
  • [18] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792–807, 1986. doi:10.1145/6490.6503.
  • [19] 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. doi:10.1145/237814.237866.
  • [20] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. doi:10.1137/S0097539793244708.
  • [21] Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. IEEE Transactions on Information Theory, 66(9):5585–5600, 2020. doi:10.1109/TIT.2020.3004427.
  • [22] Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does looking inside a circuit help? In 42nd International Symposium on Mathematical Foundations of Computer Science, volume 83 of LIPIcs, pages 1:1–1:13, 2017. doi:10.4230/LIPIcs.MFCS.2017.1.
  • [23] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.
  • [24] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.
  • [25] Robin Kothari. An optimal quantum algorithm for the oracle identification problem. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 482–493. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014. doi:10.4230/LIPIcs.STACS.2014.482.
  • [26] Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of ACM, 40(3):607–620, 1993. doi:10.1145/174130.174138.
  • [27] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2021. arXiv:2105.10386. arXiv:2105.10386.
  • [28] Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24–35, 1997. doi:10.1006/JCSS.1997.1494.
  • [29] Aviad Rubinstein. Quantum DNA sequencing & the ultimate hardness hypothesis. Blog post, 2019. URL: https://theorydish.blog/2019/12/09/quantum-dna-sequencing-the-ultimate-hardness-hypothesis/.
  • [30] R. Ryan Williams. Self-improvement for circuit-analysis problems. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1374–1385. ACM, 2024. doi:10.1145/3618260.3649723.
  • [31] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357–365, 2005. doi:10.1016/J.TCS.2005.09.023.
  • [32] Mark Zhandry. How to construct quantum random functions. In FOCS, pages 679–687. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.37.

Appendix A Proofs of Claim 40 and Claim 41

Lemma 43.

Let S∈{0,1}N be a subset of size s≥0.8⋅2N. Every quantum algorithm that, with success probability at least ≥2/3, computes parity on each x∈S uses Ω⁢(N) queries.

Proof.

Suppose there exists a T-query bounded-error quantum algorithm 𝒜S to compute parity on each x∈S with worst-case error probability ≤1/3. Here, without loss of generality, we assume the output of 𝒜S is ∈{−1,1}, where 1 means odd parity and −1 means even parity. Let P⁢(x) be the polynomial that represents 𝒜S’s probability of outputting −1 on input x. Since 𝒜S has worst-case error probability at most 1/3 on each x∈S, we can immediately see (1−2⁢P⁢(x))⋅(−1)|x|≥1/3 for every x∈S, where |x| denotes the Hamming weight of x.

Observe that deg⁢(P⁢(x))=deg⁢(1−2⁢P⁢(x)) and 𝔼x∈{0,1}N⁢[(1−2⁢P⁢(x))⁢(−1)|x|] is the Fourier coefficient of the degree-N term of (1−2⁢P⁢(x)). We obtain
𝔼x∈{0,1}N⁢[(1−2⁢P⁢(x))⁢(−1)|x|]= 12N⁢(∑x∈S[(1−2⁢P⁢(x))⁢(−1)|x|]+∑x∈{0,1}N∖S[(1−2⁢P⁢(x))⁢(−1)|x|]) ≥ 12N⋅(s/3−(2N−s))>0,

implying that deg⁢(P⁢(x))≥N. Then by polynomial method [10], 131313By the polynomial method we know if the amplitudes of the final state are degree-N polynomials of x then we need to make at least T≥N/2 queries. we immediately obtain T≥N/2. ◀

Lemma 44 (Theorem 5.19 in [27]).

Let N be an odd integer and let odd-majority:{0,1}N→{0,1} be defined as

odd-majority⁢(x)={1,if ⁢|x|>N2,0,otherwise,

where |x|=|{i∣i∈[N]⁢ and ⁢xi=1}|. If the Fourier expansion of odd-majority is

odd-majority⁢(x)=∑B⊆{0,1}Nodd-maj^⁢(B)⁢χB⁢(x),

where χB⁢(x)=(−1)x.B, then odd-maj^⁢(B)=0 whenever |B|==0mod2 and for |B|=N we have

odd-maj^⁢(B)2=44N⁢(N−1N−12)2≥6π⁢(3⁢N−1)>2π⁢N.
Lemma 45.

Let N be an odd integer and let S∈{0,1}N be a subset of size s≥2N⁢(1−1N2). Every quantum algorithm that, with error probability ε≤12⋅N2, computes odd-majority on each x∈S uses Ω⁢(N) queries.

Proof.

The absolute value of the N-degree Fourier coefficient for odd-majority is at least 2π⁢N using Lemma 39 gives us the required proof. ◀

Lemma 46.

Let N be an even integer and let S∈{0,1}N be a subset of size s≥2N⁢(1−12⋅N2). Every quantum algorithm that, with error probability ε≤12⋅N2, computes majority on each x∈S uses Ω⁢(N) queries.

We embed the odd-majority into the majority and then argue lower bound for majority for sets of size at least 2N⁢(1−12⋅N2) using the result obtained in Lemma 45.

Proof.

Towards contradiction, let us assume that there is a set B⊆{0,1}N of size b≥2N⁢(1−12⋅N2) that uses at most N0.999 queries to compute majority on all strings y∈B. The set B={B0○0}⊔{B1○1} can be viewed as two disjoint sets of strings ending with 0 and 1, respectively. Clearly |B1|≤2N−1 and by our assumption we have |B|≥2N⁢(1−12⁢N˙2), therefore, |B0|=|B|−|B1|≥2N⁢(12−12⋅N2). Set S′=B0. The set S′ is a subset of strings of N′-length strings where N′=N−1 and moreover N′ is odd. Therefore, in terms of N′ we have |B0|≥2N′+1⁢(12−12⋅(N′+1)2)=2N′−2N′22⋅(N′+1)2>2N′⁢(1−1N′2). As S′=B0, computing majority on strings in B0○0 (or equivalently S′○0) would be equivalent to computing odd-majority on N′-length strings in S′ of size |S′|≥2N′⁢(1−1N′2). But we know from Lemma 45 a sublinear query algorithm is not possible for these set sizes. Hence, proved. ◀

We can give query lower bound for st-majority by just setting S′=B1 and running the same arguments mentioned in the proof of Lemma 46. Giving the following result for st-majority.

Lemma 47.

Let N be an even integer and let S∈{0,1}N be a subset of size s≥2N⁢(1−12⋅N2). Every quantum algorithm that, with error probability ε≤12⋅N2, computes st-majority on each x∈S uses Ω⁢(N) queries.

When N is odd, all the three definitions of majority, st-majority and odd-majority are equivalent. Therefore, combining Lemmas 45, 46, and 47 we get the following.

Lemma 48.

Let S∈{0,1}N be a subset of size s≥2N⁢(1−12⋅N2). Every quantum algorithm that, with success probability (1−ε)≥(1−12⋅N2), computes majority (st-majority) on each x∈S uses Ω⁢(N) queries.