Partial Boolean Functions With Exact Quantum Query Complexity One

Abstract

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, thenF(f)is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.

1. Introduction

In the field of theoretical computer science, computational complexity aims to measure “how much" computation is necessary and sufficient to finish some certain computational tasks. In classical computation, a simplest model of computation is the decision tree (For more details, we can refer to the survey paper [1]). Correspondingly, the quantum query model (quantum black box model, or quantum decision tree model) is a generalization of the decision tree model in quantum computation [1,2,3,4,5]. Most of famous quantum algorithms are captured by the quantum query model [6], such as Shor’s factoring algorithm [7], Grover’s unstructured search algorithm [8], and so on [9,10,11]. The quantum query model can be investigated in the exact setting and the bounded-error setting [1]. Given an inputx∈D⊆^{0,1}nthat can only be accessed through a black box by querying some bit_xiof the input, the quantum query model computes an n-bit partial Boolean functionf:D→{0,1} exactly (or with bounded-error) [1]. An exact quantum algorithm must always output the correct function value for all legal inputs [1]. If a quantum algorithm outputs the function value with a probability greater than a constant (>12 ) for all legal inputs, then the quantum algorithm is said to compute the function with bounded error. In the quantum query model, we care the quantum query complexity that is the decision tree complexity for the quantum model [1,2,3]. Roughly speaking, the exact (or bounded-error) quantum query complexity of a Boolean function denotes the number of queries of an optimal quantum decision tree that computes the Boolean function exactly (or with bounded-error) [1].

In quantum computation, the hope is to find out many problems whose computational complexity in quantum computer is less than the computational complexity in classical computer, i.e., finding out many problems that have the quantum advantage. For a function f, quantum advantage can be investigated by comparing the exact quantum query complexity_QE(f)and the deterministic decision tree complexityD(f) [1], whereD(f) denotes the minimum number of queries used by any classical deterministic algorithm. Over the past decade, there have been many results on the quantum query model [12,13,14,15,16,17,18,19,20]. In particular, Ambainis et al. [14] proved that exact quantum algorithms have advantage for almost all Boolean functions in 2015. For total Boolean functions (i.e., partial Boolean functions withD=^{0,1}n), the first known quantum speed-up was_QE(f)=O(D^(f)0.8675…) by Ambainis [13], and then Ambainis et al. [21] presented a better separation with a quadratic gap between the exact quantum query complexity and the deterministic decision tree complexity, up to polylogarithmic factors.

For any partial Boolean function, the best separation is still achieved by Deutsch-Jozsa algorithm [10,17]. And, some main related results are as follows. In 2007, Montanaro [22] considered a problem of exact oracle identification with a single quantum query. In 2015, Montanaro et al. [15] investigated all small total Boolean functions up to four bits and symmetric total Boolean functions up to six bits. In 2016, Qiu et al. [17,23] generalized Deutsch-Jozsa problem and gave its optimal exact quantum query algorithm, and in particular, Qiu et al. [23,24] presented all symmetric partial Boolean functions (it is a special class of partial Boolean functions) with exact quantum query complexity 1, and proved that any symmetric partial Boolean function f can be computed exactly by a 1-query quantum algorithm if and only if f can be computed by the Deutsch-Jozsa algorithm [10]. In the same year, Aaronson et al. [25] showed an equivalence between 1-query quantum algorithms and bounded quadratic polynomials in the bounded-error setting. Also in the same year, Grillo et al. [26] investigated partial Boolean functions which are computed exactly with t queries. However, the result in [26] (i.e., Theorem 5) for any numerical procedure is difficult to use as an analytic tool. In 2017, Arunachalam et al. [27] proved a characterization of t-query quantum algorithms in terms of the unit ball of a space of degree-(2t) polynomials. Using the same method as the proof of Theorem 11 given by Qiu et al. [23,24], Chen et al. [28] showed that the total Boolean functions with exact quantum query complexity 1 are the one-bit functionf(x)=_x1and the two-bit function_x1⊕_x2 , and Mukherjee et al. [29] noticed that this result of [28] is the same as a result by Montanaro et al. [15].

As above, the exact 1-query quantum model for all partial Boolean functions is expected to be investigated further. On one hand, similar to Refs. [23,24,25,26,27], establishing an equivalence between quantum query algorithms and some other theories will inspire more new algorithms and related results on the complexity theory. On the other hand, with the development of quantum computer, the problems solved by 1-query quantum algorithms may be the first to be used widely in the future, as the 1-query quantum algorithm costs the least unitary operators. Specifically, we investigate the following two problems.

• The partial Boolean functions can be regarded as a generalization of the total Boolean functions. Actually, Deutsch’s algorithm [9] computes a two-bit partial (also total) Boolean function using one query. Both the extension of Deutsch’s problem (computed by Deutsch-Jozsa algorithm [10]) and a generalized Deutsch-Jozsa problem in Ref. [17] are described by even n-bit partial (not total) Boolean functions. Naturally, what is the characterization of partial Boolean functions with exact quantum query complexity 1?

• In the field of quantum computation, it is a fundamental and interesting subject to evaluate the computational power of the 1-query quantum model, and is also critical for discovering quantum advantage. Specifically, the number of partial Boolean functions with exact quantum query complexity 1 shows the power and advantage of the exact 1-query quantum model. So, how many partial Boolean functions can be computed exactly by 1-query quantum algorithms?

The rest of the paper is organized as follows. In Section 2, we introduce some basis notations and the related knowledge. Then, we state and prove the first characterization and a related result in Section 3. Next, we state and prove the second characterization and two related results in Section 4. Finally, the conclusion is presented in Section 5. For the sake of brevity and readability, all proofs of lemmas in this paper are showed in Appendix A, Appendix B, Appendix C and Appendix D.

2. Preliminaries

In this section, we introduce some basic notations and recall some basic knowledge of partial Boolean functions and the exact quantum query model. For the details, we can refer to Refs. [1,6,20,23,30,31].

As usual, notationsN,R, andCdenote the sets of natural numbers, real numbers, and complex numbers, respectively. In particular, we will always use the notation D (or promised set) to denote a subset of^{0,1}n. For any inputx=_{x1 x2}⋯_xn∈D, the Hamming weight (number of 1s) of x is denoted by|x|. Given a real number set S, the notationmaxSdenotes the maximum in S and the notationminSdenotes the minimum in S. For any finite set S, the notation|S|denotes the number of elements in S. For a complex matrix A,^ATis the transpose of the matrix A, and^A†=^(AT)*is the conjugate transpose of the matrix A. Obviously,^A†=^ATfor any real matrix A. Furthermore, the notation|a⟩is usually used to denote a quantum state which is a unit vector in a Hilbert space and labeled by the notation a. In particular,^{⟨a|=(|a⟩)†}is a row vector.

In this paper, we mainly concern partial functionsf:D→C,f:D→Randf:D→{0,1}. In general, these functions can be given by a²ⁿ-dimensional vector(f(0),f(1),⋯,f(x),⋯,f(²ⁿ−1)^)Twhose entryf(x)is denoted by * for any undefined inputx∈^{0,1}n∖D . For example, the Boolean function f computed by Deutsch’s algorithm [9] can be given by(f(00),f(01),f(10),f(11))=(1,0,0,1). Sometimes, we also use a two-tuple({x:f(x)=0},{y:f(y)=1})to give a certain partial Boolean functionf:D→{0,1} . For example, the even n-bit partial Boolean function f computed by Deutsch-Jozsa algorithm [10] can be given by({x∈^{0,1}n:|x|=0,n},{y∈^{0,1}n:|y|=n2}).

In order to represent these functions, we need to use two monomials_XS=_{∏i∈S xi}and^(−1)S·x=_∏i∈S ^(−1)_xi [1,20,30]. In particular,_XØ=^(−1)Ø·x=1. And, the set{_XS:S⊆{1,2,⋯,n}}is usually called the polynomial basis and the set{^(−1)S·x:S⊆{1,2,⋯,n}} is usually called Fourier basis [1,20,30]. If a functionp:^Rn→Ccan be written as_{ΣS αS XS}for some complex numbers_αS , then the function p is called a multilinear polynomial [1]. Meanwhile, the degree of the multilinear polynomial p is defined bydeg(p)=max{|S|:_αS≠0}. For any partial functionf:D→C, a multilinear polynomialp(x)represents f if and only ifp(x)=f(x)for allx∈D [1,32]. Unlike total functionsf:^{0,1}n→C, the multilinear representation of a partial (not total) functionf:D→Cis usually not unique. Naturally, the degree of a partial (or total) functionf:D→Ccan be defined bydeg(f)=min{deg(p):prepresentsf}.

In the quantum query model, for every inputx∈D, the quantum black box_Oxcan be described as a unitary operator which is defined by

_Ox|i,j⟩=^(−1)_xi |i,j⟩,ifi∈{1,2,⋯,n},|0,j⟩,ifi=0.

Here, the integer numberi∈{0,1,2,⋯,n}is the query-part and the label j is the auxiliary space. As a result, a t-query quantum algorithm can be determined by an initial state|_ψ0⟩and a sequence of unitary transformations_U0,_Ox,_U1,_Ox,⋯,_Ox,_Utfollowed by a measurement, wheret+1unitary operators_U0,_U1,⋯,_Ut are independent of the input [1,6].

3. The First Characterization This section introduces and proves the first characterization and a related result. 3.1. A Characterization by the Linear System of Equations

Inspired by proofs of Theorem 8 in Ref. [23], the first characterization is presented in the following. In fact, the characterization can also be got by Theorem 5 in [26].

Theorem 1.

An n-bit non-constant partial Boolean functionf:D→{0,1}can be computed exactly by a 1-query quantum algorithm, if and only if there exist at least one non-negative solutionz=(_z0,_z1,_z2,⋯,_zn ^)Tof equations_z0+_z1+_z2+⋯+_zn=1 and^FT(a⊕b)z=0for alla∈{x:f(x)=0}andb∈{x:f(x)=1}where the function vectorF(x)=^{(1,(−1)_x1 ,(−1)_x2 ,⋯,(−1)_xn )T}for anyx=_{x1 x2}⋯_xn∈^{0,1}n.

Proof.

⇒). Since the algorithm is exact, the quantum state_{U1 Oa U0}|_ψ0⟩for alla∈{x:f(x)=0}must be orthogonal to the quantum state_{U1 Ob U0}|_ψ0⟩for allb∈{x:f(x)=1}. Meanwhile, since the unitary operator_U1preserves the inner product of any two complex vectors, the quantum state_{Oa U0}|_ψ0⟩for alla∈{x:f(x)=0}must be orthogonal to the quantum state_{Ob U0}|_ψ0⟩for allb∈{x:f(x)=1}. For any quantum state_U0|_ψ0⟩=_{∑i,j αi,j}|i,j⟩,note that

_{Oa U0}|_ψ0⟩=∑j_α0,j|0,j⟩+∑i,j_αi,j ^(−1)_ai |i,j⟩

and the inner product

(_{Oa U0}|_ψ0⟩^)† _{Ob U0}|_ψ0⟩=∑j|_α0,j ^|2+∑i,j^{(−1)_ai⊕_bi |_αi,j|2}=(∑j|_α0,j ^|2,∑j|_α1,j ^|2,⋯,∑j|_αn,j^|2)^{(1,(−1)_a1⊕_b1,⋯,(−1)_an⊕_bn)T}=(_z0,_z1,⋯,_zn)F(a⊕b)=^zTF(a⊕b)

where the notation_zi=_∑j ^|_αi,j|2for alli∈{0,1,2,⋯,n}is introduced in the last equality. Thus, there exists at least one non-negative solutionz=(_z0,_z1,_z2,⋯,_zn ^)Tof equations_z0+_z1+_z2+⋯+_zn= 1 and^zTF(a⊕b)=0for alla∈{x:f(x)=0}andb∈{x:f(x)=1}.

⇐). For a non-negative solutionz=(_z0,_z1,_z2,⋯,_zn ^)Tof equations_z0+_z1+_z2+⋯+_zn= 1 and^zTF(a⊕b)=0for alla∈{x:f(x)=0}andb∈{x:f(x)=1}, if we set_∑j ^|_αi,j|2=_zifor alli∈{0,1,2,⋯,n}in the state_U0|_ψ0⟩=_{∑i,j αi,j}|i,j⟩of an undetermined 1-query quantum algorithm, then the inner product

(_{U1 Oa U0}|_ψ0⟩^)† _{U1 Ob U0}|_ψ0⟩=0

for alla∈{x:f(x)=0}andb∈{x:f(x)=1}. By Gram-Schmidt orthogonalization, we can find an orthonormal basis{_{U1 Oa U0}|_ψ0⟩:f(a)=0,a∈D}and an orthonormal basis{_{U1 Ob U0}|_ψ0⟩:f(b)=1,b∈D}, respectively. By the measurement consisting of the two orthonormal bases, the 1-query quantum algorithm (with the state_U0|_ψ0⟩=_{∑i,j αi,j}|i,j⟩) computes f exactly. Thus, Theorem 1 has been proved. □

Discussions on Theorem 1

Theorem 1 transforms the problem of deciding the partial Boolean function with exact quantum query complexity 1 into the problem of solving a linear system of equations. Specifically, the number of variables in the linear system isn+1and the number of equations is1+|{a⊕b:f(a)=0,f(b)=1}|≤²ⁿ.

Considering the definition of the exact quantum query complexity, the task of proving_QE(f)=kmust be finished by presenting an exact k-query quantum algorithm. For a small n, presenting an optimal exact quantum query algorithm is still quite hard in some cases. Fork=1, Theorem 1 transforms this task to the problem of solving a linear system which is a computable task. For any non-constant n-bit partial Boolean functionf:D→{0,1}, if|D|is not big, then this task can be done efficiently in a classical computer. This is the most important contribution of Theorem 1.

In fact, Theorem 1 is also a practical tool in some cases. In the worst case, the number of equations in the linear system is1+|{a⊕b:f(a)=0,f(b)=1}|which is an exponential number. Note that the number of variables in the linear system isn+1. So, the following two results can be got.

(1)

Given any n-bit partial Boolean function f, if some equations (By basic linear algebra,n+1equations are enough in the best case) lead to an empty (non-negative real) solution of the linear system, then by Theorem 1 these equations are enough to prove that the exact quantum query complexity of f is bigger than 1. Thus, for the best case, other|{a⊕b:f(a)=0,f(b)=1}|−nequations can be ignored and things become quite easy.

(2)

If the exact quantum query complexity of an n-bit partial Boolean functionf:D→{0,1}is bigger than 1, then the exact quantum query complexity of any n-bit partial Boolean function g defined by

g(x)=f(x),∀x∈D,g(x)∈{0,1,*},otherwise

is also bigger than 1. The number of partial Boolean functions in this form is^32n−|D|which is also an exponential number.

3.2. Partial Boolean Functions Depending on All Bits This subsection considers a special class of all partial Boolean functions using Theorem 1.

First, we introduce the following definition [14,31] (A background of this definition is introduced briefly in Appendix A).

Definition 1.

[14,31]. An n-bit partial Boolean functionf:D→{0,1}is said to depend on k (≤n) bits, if k is the minimum number of variables in all multilinear polynomials representing f.

By Definition 1, the two-bit total Boolean function computed by Deutsch’s algorithm [9] depends on two bits, and, for even n, the n-bit partial Boolean function computed by Deutsch-Jozsa algorithm [10] depends onn2+1bits.

For partial Boolean functions depending on all bits, the result is stated in the following.

Theorem 2.

For any n-bit partial Boolean functionf:D→{0,1}depending on all n bits, f can be computed exactly by a 1-query quantum algorithm, if and only iff(x)=_x1or1⊕_x1withD={0,1}, orf(x)=_x1⊕_x2or1⊕_x1⊕_x2withD∈{E⊆^{0,1}2:|E|∈{3,4}}. □

Proof.

⇒). For any n-bit partial Boolean functionf:D→{0,1}andk∈{1,2,⋯,n}, any multilinear polynomial representation of f can be written as

f(x)=_{xk q1}(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)+_q2(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)

where_q1(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)and_q2(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)are two multilinear polynomials on variables_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn(i.e., not on the variable_xk). Let the input_Xk{k}be the same as the input_Xkexcept for the k-th bit being flipped. With an argument, if f depends on n bits (By Definition 1, this means that the number of variables in all multilinear polynomials representing f is at least n), then there must exist at least n input pairs(_X1,_X1{1}),(_X2,_X2{2}),⋯,(_Xn,_Xn{n})such that1⊕f(_Xk)=f(_Xk{k})∈{0,1}for allk∈{1,2,⋯,n}(In fact, for a certain k, iff(X)=f(^X{k})always hold for anyX∈D, then the polynomial_q1(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)=0andf(x)=_q2(_x1,_x2,⋯,_xk−1,_xk+1,⋯,_xn)depends on at mostn−1bits. This result contradicts the assumption that f depends on n bits).

By Theorem 1, there exists a non-negative vectorz=(_z0,_z1,_z2,⋯,_zn ^)Tsuch that the equations_z0+_z1+_z2+⋯+_zn=1 and

^zTF(_Xk⊕_Xk{k})=0=_z0+∑i≠k_zi−_zk,k∈{1,2,⋯,n}

hold. Combining with_z0+_z1+_z2+⋯+_zn=1=_z0+_{∑i≠k zi}+_zk, we have2_zk=1for allk∈{1,2,⋯,n}which implies thatn=1withz=^(12,12)Torn=2withz=^(0,12,12)T.

The casen=1is trivial, and f can be given by(f(0),f(1))=(0,1)or(1,0). For the casen=2, the unique non-negative solutionz=^(0,12,12)Timplies that

12^{(−1)_a1⊕_b1}+12^{(−1)_a2⊕_b2}=0

for alla∈{x:f(x)=0}andb∈{x:f(x)=1}. Then,_a1⊕_a2≠_b1⊕_b2for alla∈{x:f(x)=0}andb∈{x:f(x)=1}. This result implies thatf(x)=_x1⊕_x2or1⊕_x1⊕_x2. Meanwhile, sincef:D→{0,1}is a two-bit partial Boolean function depending on two bits,|D|∈{3,4}.

⇐). This direction is trivial. Thus, Theorem 2 has been proved. □

Discussions on Theorem 2

Since there are many partial Boolean functions with exact quantum query complexity 1, it is necessary to divide them into some classes. In 2015, Montanaro et al. [15] investigated all small total Boolean functions up to four bits and symmetric total Boolean functions up to six bits. In 2016, Qiu et al. [23,24] studied all symmetric partial Boolean functions and remained others open. By Definition 1, it is natural to divide all n-bit partial Boolean functions inton+1classes.

For all n-bit partial Boolean functions depending on 1 and 2 bits, the problem is trivial. For n-bit partial Boolean functions depending on n bits, the result is put into Theorem 2. By a trivial (not direct) argument, the statement that a partial Boolean function f depends on all n bits is consistent with previous definition. This is a key hint in the proof. Intuitively, this implication seems obvious. However, since the implication does not hold forn2, we remark that a proof is necessary.

Theorem 2 clarifies all partial Boolean functions that depend on all bits and can be computed exactly by a 1-query quantum algorithm. Observing the unique multilinear polynomial of any total Boolean function, any n-bit total Boolean function depending on k(≤n) bits can be identified with a k-bit total Boolean function depending on k bits. Therefore, Theorem 2 generalizes the result on total Boolean functions [15] to partial Boolean functions. Surprisingly, the number of all n-bit partial Boolean functions depending on n bits is quite big. This fact is implied by the following lemma.

Lemma 1.

LetN(n)(n≥1)denote the number of all n-bit partial Boolean functions depending on n bits. Then,N(n)≥2×^32n−n−1.

In contrast, the number of all n-bit total Boolean functions (investigated by Montanaro et al. [15]) is²²ⁿ and the number of all n-bit symmetric partial Boolean functions (investigated by Qiu et al. [23,24]) is³ⁿ⁺¹.

As a result, many n-bit partial Boolean functions depending onk∈{3,⋯,n−1}bits is sitll unclear. This motivate us to investigate partial Boolean functions further.

4. The Second Characterization This section introduces and proves the second characterization and two related results. 4.1. A Characterization by the Sum-of-Squares Representation

Following the discussions of Lemma 7 and Theorem 17 in [1], iff:D→{0,1}can be computed by an exact 1-query quantum algorithm, then there exist degree-1 SOS complex representations of f and1−f. Thus, this subsection introduces and proves a characterization using the SOS representation.

First, the following lemma follows the discussions of Lemma 7 and Theorem 17 in [1]. This lemma is proved and also used in our recent paper [33].

Lemma 2.

[1]. If there exists an exact 1-query quantum algorithm computing an n-bit partial Boolean functionf:D→{0,1}, then there must exist degree-1 SOS complex (multilinear polynomials) representations of f and1−f.

In order to give the second characterization, we introduce the following definition. This definition is also used in [33]. More related definitions can be seen in Refs. [34,35,36,37,38,39].

Definition 2.

[34,35,36,37,38,39]. Let the function vectorF(x)=^{(1,(−1)_x1 ,(−1)_x2 ,⋯,(−1)_xn )T}. For an n-bit partial Boolean functionf:D→{0,1}, if there exist two real(1+n)-dimensional column vector sets{_a1,_a2,⋯,_ap}and{_ap+1,_ap+2,⋯,_ap+q}such that the equations

f(x)=∑l=1p^|_alTF(x)|2,x∈D,1−f(x)=∑l=p+1p+q^|_alTF(x)|2,x∈D,∑l=p+1p+q|_alT ^F(x)|2=1−∑l=1p^|_alTF(x)|2,x∈^{0,1}n,

hold, then the(p+q)×(1+n)complex coefficient matrix[_αf]in the form of

[_αf]=_a1T⋮_apTap+1T⋮_ap+qT

is called a degree-1 SOS complex representation matrix of f and1−f. Here, every row vector_apTis the coefficient vector of the degree-1 Fourier polynomial_alTF(x) in Equation (9).

As we know, for the state_{U1 Ox U0}|_ψ0⟩=_∑i,j(_{∑S αi,jS} ^(−1)S·x)|i,j⟩in a 1-query quantum algorithm, the amplitude_{∑S αi,jS} ^(−1)S·xof any basis state|i,j⟩is a polynomial of degree≤1. Therefore,_{∑S αi,jS} ^(−1)S·x=(_αi,jØ,_αi,j{1},_αi,j{2},⋯,_αi,j{n})^{(1,(−1)_x1 ,(−1)_x2 ,⋯,(−1)_xn )T}. Then, the coefficient matrix_αi,jS(here, the number pairi,jis the row index and the number set S the column index. In a 1-query quantum algorithm, the number pairi,jtraverses all basis states and the set S traversesØ,{1},{2},⋯,{n}) withn+1columns in the form of

[_aØ,_a{1},_a{2},⋯,_a{n}]

can be used to represent the state_{U1 Ox U0}|_ψ0⟩. Without loss of generality, assume that the basis states in a 1-query quantum algorithm are the computational basis{|0⟩,|1⟩,|2⟩,⋯}. Next, the equation_{U1 Ox U0}|_ψ0⟩=_αi,jSF(x)holds (here,F(x)=^{(1,(−1)_x1 ,(−1)_x2 ,⋯,(−1)_xn )T}). In order to distinguish the coefficient matrix of the state_{Ox U0}|_ψ0⟩from the coefficient matrix of the state_{U1 Ox U0}|_ψ0⟩, the notation_βi,jSdenotes the coefficient matrix_U1−1αi,jSof the state_{Ox U0}|_ψ0⟩.

By Definition 2 and the coefficient matrix, the second characterization is presented in the following.

Theorem 3.

Any n-bit non-constant partial Boolean functionf:D→{0,1}can be computed exactly by a 1-query quantum algorithm, if and only if there exists a degree-1 SOS complex representation matrix[_αf]of f and1−fsuch that

^[_αf]†[_αf]=diag(_u0,_u1,_u2,⋯,_un).

Proof.

⇒). On one hand, the coefficient matrices of the states_{U1 Ox U0}|_ψ0⟩and_{Ox U0}|_ψ0⟩are in the form of

_αi,jS=[_aØ,_a{1},_a{2},⋯,_a{n}]

and

_βi,jS=_U1−1αi,jS,

respectively. On the other hand, for any quantum state

_U0|_ψ0⟩=∑j_α0,jØ|0,j⟩+∑i≠0∑j_αi,jØ|i,j⟩,

the state

_{Ox U0}|_ψ0⟩=∑j_α0,jØ|0,j⟩+∑i≠0∑j_αi,jØ ^(−1)_xi |i,j⟩.

Thus, the coefficient matrix of the state_{Ox U0}|_ψ0⟩is in the form of a block diagonal matrix

_βi,jS=diag(_B0,_B1,⋯,_Bn)

where the i-th block matrix

_Bi=_{αi,0Øαi,1Ø}⋮_αi,jØ⋮

for every fixedi∈{0,1,2,⋯,n}. Thus,_U1−1αi,jS=_βi,jS=diag(_B0,_B1,⋯,_Bn).

According to Lemma 2 and Definition 2, the coefficient matrix_αi,jSof the state_{U1 Ox U0}|_ψ0⟩is an SOS complex representation matrix[_αf]of the partial Boolean function f and1−f. Meanwhile, since all columns of any block-diagonal matrixdiag(_B0,_B1,⋯,_Bn)are pairwise orthogonal and the unitary operator_U1−1preserves the inner product of any two complex vectors, all columns of the matrix[_αf] are also pairwise orthogonal. Thus, Equation (12) holds.

⇐). For a degree-1 SOS complex representation matrix[_αf]of f and1−fsatisfying^[_αf]†[_αf]=diag(_u0,_u1,_u2,⋯,_un), all columns of the matrix[_αf]=[_aØ,_a{1},_a{2},⋯,_a{n}]are pairwise orthogonal. Note that we can always get a sequence of proper vectors_B0,_B1,⋯,_Bnsatisfying||_B0||=||_aØ||=_u0and||_Bi||=||_a{i}||=_uifor alli∈{1,2,⋯,n}(for example,_Bi=^{(_ui,0,0,⋯)T}). Since all columns of[_αf]anddiag(_B0,_B1,⋯,_Bn)are pairwise orthogonal, there always exists a unitary operator_U1−1such that_U1−1[_αf]=diag(_B0,_B1,⋯,_Bn).

As a result, the three states_{U1 Ox U0}|_ψ0⟩,_{Ox U0}|_ψ0⟩and_U0|_ψ0⟩of an exact 1-query quantum algorithm computing f can be determined by[_αf],diag(_B0,_B1,⋯,_Bn)and

_B0B1⋮_Bn,

respectively. Thus, Theorem 3 has been proved. □

Discussions on Theorem 3

In order to use Theorem 3, we need to find a pair of SOS real representations of f and1−f first, and then transform it into a proper SOS complex representation matrix. Since it is feasible to get a pair of SOS real representations for very small (partial) Boolean functions [34,35,36,37,38,39], Theorem 3 can be tested on very small partial Boolean functions.

To some extent, Theorem 3 provides a different style for the characterization of partial Boolean function with exact quantum query complexity 1. On one hand, similar to Ref. [25] (showed an equivalence between 1-query quantum algorithms and bounded quadratic polynomials in the bounded-error setting) and [27] (proved a characterization of t-query quantum algorithms in terms of the unit ball of a space of degree-(2t)polynomials), Theorem 3 shows an equivalence between the sum-of-squares polynomial representations and the exact 1-query quantum algorithm. In fact, Theorem 3 transforms the problem of proving_QE(f)=1to the problem of solving a system of multivariate quadratic equations which is a difficult problem in practical applications. On the other hand, combining Theorem 3 with Theorem 1, we can see that the problem of solving the system of multivariate quadratic equations in Theorem 3 can be reduced to the problem of solving the linear system of equations in Theorem 1. This result is a quantum-inspired result which is an interesting application of the quantum theory.

4.2. Partial Boolean Functions Depending on k Bits This subsection considers partial Boolean functions depending on k bits. Inspired by Theorem 3, we get the following result.

Theorem 4.

Let the function vectorP(x)=^{(1,_x1,_x2,⋯,_xn)T}wherex=_{x1 x2}⋯_xn∈^{0,1}n. For any n-bit non-constant partial Boolean functionf:D→{0,1}, if f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then

rank(_{(⋯,P(x),⋯)f(x)=0}),rank(_{(⋯,P(x),⋯)f(x)=1})∈{1,2,⋯,n}

and

rank(_{(⋯,P(x),⋯)f(x)=0})+rank(_{(⋯,P(x),⋯)f(x)=1})−(2n+2−k)≤0

where all columnsP(x)in the matrix_{(⋯,P(x),⋯)f(x)=b}traverse all legal inputsx∈Dsatisfyingf(x)=bforb∈{0,1}.

In order to prove Theorem 4, the following lemma is necessary.

Lemma 3.

If an n-bit partial Boolean functionf:D→{0,1}depends on k (≤n) bits and there exists a degree-1 SOS complex representation of f, then there exist at least k non-zero columns_a{i1},_a{i2},⋯,_a{ik}in the matrix[_αf]where_i1,_i2,⋯,_ik∈{1,2,⋯,n}.

Then, Theorem 4 can be proved in the following.

Proof.

Recall that all columns of the matrix_{(⋯,P(x),⋯)f(x)=b}traverse all legal inputsx∈Dsatisfyingf(x)=bwhere the vector functionP(x)=^{(1,_x1,_x2,⋯,_xn)T}. Note that the size of the matrix_{(⋯,P(x),⋯)f(x)=b}is(n+1)×|{x:f(x)=b}|.

On one hand, for a non-constant n-bit partial Boolean function f, if there exists a degree-1 SOS complex representation, then there exists a sequence of(n+1)-dimensional non-zero vectors_a1,_a2,⋯,_apsatisfying

f(x)=∑l=1p^|_alTP(x)|2,∀x∈D.

Considering Equation (22) for x such thatf(x)=0forces_alTP(x)=0. Thus,_al⏊P(x)for allP(x)withf(x)=0. Then,_alfor any l is in the orthogonal complement of the space spanned by allP(x)withf(x)=0, we know the existence of the sequence (i.e., non-zero vectors_a1,_a2,⋯,_ap) requires1≤(n+1)−rank(_{(⋯,P(x),⋯)f(x)=0})≤n. Similarly, considering Equation (22) for x such thatf(x)=1, we can get1≤(n+1)−rank(_{(⋯,P(x),⋯)f(x)=1})≤n . Thus, Equation (20) holds.

On the other hand, by Theorem 3, for an n-bit partial Boolean function f with exact quantum query complexity 1, there exists an SOS complex representations matrix[_aØ,_a{1},_a{2},⋯,_a{n}]=[_αf]of f and1−fsuch that_U1−1[_αf]=diag(_B0,_B1,⋯,_Bn). By Equation (10), we can see that

rank([_αf])≤rank([_a1,⋯,_ap])+rank([_ap+1,⋯,_ap+q]).

Moreover,

rank([_a1,⋯,_ap])≤(1+n)−rank(_{(⋯,P(x),⋯)f(x)=0})

and

rank([_ap+1,⋯,_ap+q])≤(1+n)−rank(_{(⋯,P(x),⋯)f(x)=1})

can be obtained by considering Equation (22) for x such thatf(x)=0andf(x)=1, respectively. Using the property (i.e., preserving Euclidean norm and the rank) of the unitary matrix and Lemma 3,

k≤|{i∈{0,1,⋯,n}:_a{i}≠0}|(Lemma3)=|{i∈{0,1,⋯,n}:∥_Bi∥≠0}|(Theunitaryoperator_U1preservesEuclideannorm)=rank(diag(_B0,_B1,⋯,_Bn))(Thecharacterizationoftheblockdiagonalmatrix)=rank([_aØ,_a{1},_a{2},⋯,_a{n}])(Theunitaryoperator_U1preservestherank)=rank([_αf])≤2(1+n)−∑b=01rank(_{(⋯,P(x),⋯)f(x)=b}).(Equations(23)–(25))

Thus, Theorem 4 has been proved. □

Discussions on Theorem 4

The inverse direction of Theorem 4 is not always hold. For example, a three-bit partial Boolean function f given by the two-tuple({x∈^{0,1}3:|x|=0},{y∈^{0,1}3:|y|=1}). Here, it is not difficult to know thatrank(_{(⋯,P(x),⋯)f(x)=0})=1andrank(_{(⋯,P(x),⋯)f(x)=1})=3 . However, using Theorem 10 of Ref. [23],_QE(f)≥2.

Theorem 4 gives a necessary condition on the case that an n-bit partial Boolean function depends on k bits and can be computed exactly by a 1-query quantum algorithm. That is, the functionF(f):=rank(_{(⋯,P(x),⋯)f(x)=0})+rank(_{(⋯,P(x),⋯)f(x)=1})−(2n+2−k)must be negative.

Compared with Theorem 1, Theorem 4 provides an approximate method on deciding the exact quantum query complexity of a partial Boolean function. Most importantly, the method in Theorem 4 is more efficient than Theorem 1. In order to construct the linear system in Theorem 1, we should observe at most|{a:f(a)=0}||{b:f(b)=1}|equations. In contrast, we only observe at most|{a:f(a)=0}|+|{b:f(b)=1}|inputs in Theorem 4. From this point, Theorem 4 is more efficient than Theorem 1. Note that the result in Theorem 4 is one-side exact. That is, if the exact quantum query complexity of a partial Boolean function f is bigger than 1 by Theorem 4, then the result is exact.

4.3. Estimating the Number of Partial Boolean Functions Depending on k Bits

In this subsection, let us evaluate the number_N1(n,k)of n-bit partial Boolean functions which depend on k bits and can be computed exactly by a 1-query quantum algorithm.

As a preparation, the following lemma is necessary.

Lemma 4.

Let the vector functionP(_Xk)=^{(1,_Xk,1,_Xk,2,⋯,_Xk,n)T}for a string_Xk=_{Xk,1 Xk,2}⋯_Xk,n∈^{0,1}n. Ifn≥2, for any j∈{1,2,⋯,n+1}different linearly independent vectorsP(_X1),P(_X2),⋯,P(_Xj), there exist at most_Tj≤^2j−1−jother different vectorsP(_Xj+1),P(_Xj+2),⋯,P(_Xj+Tj)satisfyingrank([P(_X1),P(_X2),⋯,P(_Xj+Tj)])=j.

By Theorem 4, the fifth result is the following.

Theorem 5.

Let_N1(n,k)be the number of all n-bit partial Boolean functions which depend on k bits and can be computed exactly by a 1-query quantum algorithm. Ifn≥3andk≥2, then_N1(n,k)≤^{n2 22n−1(1+22−k)+2n2}.

Proof.

Recall that all columns in the matrix_{(⋯,P(x),⋯)f(x)=b}traverse all legal inputsx∈Dsatisfyingf(x)=bwhere the function vectorP(x)=^{(1,_x1,_x2,⋯,_xn)T}. Let_r0denote the rank of_{(⋯,P(x),⋯)f(x)=0}and_r1the rank of_{(⋯,P(x),⋯)f(x)=1}. According to Theorem 4,_N1(n,k)is not bigger than the number of all n-bit partial Boolean functions satisfying_r0+_r1≤2n+2−kand1≤_r0,_r1≤n. For every fixed(_r0,_r1), an n-bit partial Boolean function can be determined using the following two steps.

In the first step, we choose_r0linearly independent vectors

P(_X1),P(_X2),⋯,P(_Xr0 )

and_r1linearly independent vectors

P(_Y1),P(_Y2),⋯,P(_Yr1 )

for some_X1,_X2,⋯,_Xr0 ,_Y1,_Y2,⋯,_Yr1 ∈^{0,1}n, respectively. Here,_r0linearly independent vectorsP(_X1),P(_X2),⋯,P(_Xr0 )correspond to_r0different inputs with function value 0, and_r1linearly independent vectorsP(_Y1),P(_Y2),⋯,P(_Yr1 )correspond to_r1different inputs with function value 1. For every fixed(_r0,_r1), the number of different selections (i.e.,{P(_X1),P(_X2),⋯,P(_Xr0 )}and{P(_Y1),P(_Y2),⋯,P(_Yr1 )}) is not bigger than

²ⁿ _r0²ⁿ−_r0r1≤^2n(_r0+_r1)

for alln≥3andk≥2.

In the second step, we add some other vectorsP(_Xr0+1),⋯ andP(_Yr1+1),⋯ to the sets{P(_X1),P(_X2),⋯,P(_Xr0 )}and{P(_Y1),P(_Y2),⋯,P(_Yr1 )}, respectively. Here, every newly added vector in the set{P(_Xr0+1),⋯}should be represented linearly by the determined_r0linearly independent vectorsP(_X1),P(_X2),⋯,P(_Xr0 )and every newly added vector in the set{P(_Yr1+1),⋯}should be represented linearly by the determined_r1linearly independent vectorsP(_Y1),P(_Y2),⋯,P(_Yr1 ). After that, an n-bit partial Boolean function f is determined as follows.f(x)=0for x in the set{_X1,_X2,⋯,_Xr0 ,⋯},f(x)=1for x in the set{_Y1,_Y2,⋯,_Yr1 ,⋯} , and it is undefined for the rest cases. Using Equation (29) and Lemma 4, for every fixed(_r0,_r1), there are at most

^{2n(_r0+_r1) 2(2_r0−1−_r0) 2(2_r1−1−_r1)}<^{22n2 2(2n−1+2n+1−k)}=^{22n−1(1+22−k)+2n2}

partial Boolean functions with a pair of fixed_r0and_r1. Note that the number of different(_r0,_r1)is not bigger thanⁿ². Thus, Theorem 5 has been proved. □

Discussions on Theorem 5

The most important contribution of Theorem 5 is to give an estimate on the number of partial Boolean functions with exact quantum 1-query complexity. This is the first non-trivial upper bound on this problem. In contrast,³²ⁿ is the number of all n-bit partial Boolean functions, as each n-bit partial Boolean function corresponds to a stringf(0)f(1)⋯f(²ⁿ−1)∈^{0,1,*}2n . In fact, the exact quantum query complexity of any n-bit partial Boolean function is in the set{0,1,2,⋯,n}, which implies thatmax{_Nj(n,k):j,k∈{0,1,2,⋯,n}}≥^{32n (n+1)2}. Here, the notation_Nj(n,k)is used to denote the number of n-bit partial Boolean functions which depend on k bits and can be computed exactly by a j-query quantum algorithm. Thus, all n-bit partial Boolean functions with exact quantum query complexity 1 only make up a very tiny proportion of all n-bit partial Boolean functions.

Furthermore, corresponding to Fact 1 in Ref. [23], the following Fact 2 is also applicable to all partial Boolean functions, as a common 1-query quantum algorithm computes the two partial Boolean functions.

Fact2.For any two partial Boolean functions f and g satisfying{x:g(x)=0}⊆{x:f(x)=0}and{y:g(y)=1}⊆{y:f(y)=1}, if f can be computed exactly by a 1-query quantum algorithm, then g can also be computed exactly by this 1-query quantum algorithm.

As we know, the partial Boolean function computed by Deutsch-Jozsa algorithm can be written as

f(x)=0,∀|x|=n2,1,|x|=0,n.

By Fact 2, the exact quantum query complexity of any partial Boolean function g defined by

g(x)=0or*,∀|x|=n2,1or*,|x|=0,n.

is also 1. The number of functions in this form is3×(²ⁿⁿ²−1). Thus, for an even integer n,3×(²ⁿⁿ²−1)is a trivial lower bound on the number of n-bit partial Boolean functions with exact quantum query complexity 1. In general, given an n-bit partial Boolean function with exact quantum query complexity 1, we can find out trivially at least(^{2|{a:f(a)=0}|}−1)×(^{2|{b:f(b)=0}|}−1)different partial Boolean functions with exact quantum query complexity 1. By Stirling’s approximation

n!≈2πn^nen,

we have

nn2=n!^n2!2≈2πn^{(ne)n2πn2n2en22}=2πnπn²ⁿ.

Thus, the trivial lower bound

3×(²ⁿⁿ²−1)≈3×^22πnπn2n.

Finally, the gap between the upper bound and the lower bound comes from the following two aspects. The first aspect is that the upper bound is obtained from a necessary condition (i.e., Theorem 4) and an approximate counting argument. The second aspect is that there exist many unknown partial Boolean functions with exact quantum query complexity 1. 5. Conclusions

Motivated by this issue of exact 1-query quantum model [9,10,15,22,23,24], in this paper, we have investigated the power and advantage of the exact 1-query quantum model for partial Boolean functions. Specifically, we have contributed two sufficient and necessary conditions for characterizing n-bit partial Boolean functions with exact quantum query complexity 1, and one necessary condition for characterizing n-bit partial Boolean functions that depend on k(k≤n)bits and can be computed exactly by a 1-query quantum algorithm. Using these characterizations, we have clarified all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm (in fact,n≤2in this case, i.e. Theorem 2). Also, we have proved that the number of all n-bit partial Boolean functions with exact quantum query complexity 1 is quite small. As a result, the following two problems are worthy of further consideration.

• Find all (or some) non-trivial n-bit partial Boolean functions with exact quantum query complexity 1. This is an interesting problem for the following two aspects. On one hand, the upper bound (given by Theorem 5) of the actual number of partial Boolean functions in this class is quite big. On the other hand, known non-trivial n-bit partial Boolean functions in this class are still fairly rare [9,10,15,22,23,24].

• How many n-bit partial Boolean functions can be computed exactly (or with bounded-error) by k-query quantum algorithms for allk∈{2,3,⋯,n} ? The solution of this problem is a quantitative evaluation of the advantage of the k-query quantum model. In contrast, the result of Ambainis et al. [14] is a qualitative evaluation of the advantage of the quantum query model.

Author Contributions

Conceptualization, G.X. and D.Q.; formal analysis, G.X. and D.Q.; investigation, G.X. and D.Q.; writing-original draft preparation, G.X. and D.Q.; visualization, G.X. and D.Q.; supervision, D.Q.; funding acquisition, D.Q. All authors have read and agreed to the published version of the manuscript.

Funding

This work is supported in part by the National Natural Science Foundation of China (Nos. 61572532, 61876195), the Natural Science Foundation of Guangdong Province of China (No. 2017B030311011).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Data available in a publicly accessible repository The data presented in this study are openly available in [repository name e.g., FigShare] at [doi], reference number [reference number].

Acknowledgments

The authors would like to thank the anonymous referees for important suggestions that help us improve the quality of the manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. The Background of Definition 1

First, the following definition is used widely for total Boolean functions (i.e.,D=^{0,1}n ) [14,28,31].

Definition 3.

[31]. Given an n-bit partial Boolean functionf:^{0,1}n→{0,1}, we say that f depends on the k-th (k∈{1,2,⋯,n}) bit if there exists a pair of inputs_Xk,_Xk{k}∈^{0,1}nsuch that1⊕f(_Xk)=f(_Xk{k})∈{0,1}. Here,_Xk{k}is the same as_Xkexcept for the k-th bit being flipped.

Based on Definition 3, the statements "f depends on k bits" and "f depends on all bits (or n bits )" is also used widely for total Boolean functions (i.e.,D=^{0,1}n). Clearly, if a total Boolean functionf:^{0,1}n→{0,1}depends on k bits, then we can always find out a sequence_i1,_i2, ⋯,_iksuch that f depends on the_i1-bit, the_i2-bit,⋯,and the_ik-bit. Meanwhile, the unique multilinear polynomial representation of f is on the k variables (i.e.,_xi1 ,_xi2 ,⋯,_xik ). However, for partial Boolean functions (i.e.,D≠^{0,1}n ), things become different. On one hand, the even n-bit partial Boolean function g computed by Deutsch-Jozsa algorithm [10] does not depend on any bit (using Definition 3). On the other hand, the partial Boolean function g is not a constant function. Thus, Definition 3 is not proper for many partial Boolean functions, while the statements "f depends on k bits" and "f depends on all bits (or n bits )" should also be reconsidered. This point motivates us to use Definition 1 in this paper. Specifically, in the case of total Boolean functions, Definition 1 is consistent with Definition 3.

Appendix B. Proof of Lemma 1

Proof.

Recall thatN(n)(n≥1)denotes the number of all n-bit partial Boolean functions depending on n bits. For any k-bit(k≥1)partial Boolean functionf:D→{0,1}(D⊆^{0,1}k) depending on k bits (Note that D is not an empty set fork≥1), we construct at least^32k-1(k+1)-bit partial Boolean function g depending onk+1bits by f. In fact, for any fixedy=_{y1 y2}⋯_yk∈D⊆^{0,1}k, any(k+1)-bit partial Boolean function g defined by

g(x0)=f(x),∀x∈D,g(x0)=*,∀x∈^{0,1}k∖D,g(x1)=1⊕f(y),x=y,g(x1)∈{0,1,*},∀x∈^{0,1}k∖{y}

is a(k+1)-bit partial Boolean function depending on(k+1)bits. For anyk≥1 , the last line in Equation (A1) implies that

N(k+1)N(k)≥^32k-1.

SinceN(1)=2(i.e.,(f(0),f(1))=(0,1)and(f(0),f(1))=(1,0)), we have

N(n)≥2∏k=1n-1^32k-1=2×^32n-n-1.

The lemma has been proved. □

Appendix C. Proof of Lemma 3

Proof.

Assume that there exist at mostk-1non-zero vectors in all vectors_aØ,_a{1},_a{2},⋯,_a{n}. Then, there exist at leastn-k+1zero vectors_a{ik},_a{ik+1},⋯,_a{in}where_ik,_ik+1,⋯,_in∈{1,2,⋯,n}. Note that all entries_a{ir}lin_a{ir}are zeros for alll∈{1,2,⋯,p+q}andr∈{k,k+1,⋯,n}. Therefore,

f(x)=|_f1 ^(x)|2+⋯+^|_fp(x)|2=∑l=1p^{_aØl+∑i∈{1,2,⋯,n}_a{i}l (-1)_xi 2}=∑l=1p^{_aØl+∑r∈{1,2,⋯,k-1}_a{ir}l (-1)_xir 2}.

Obviously, the number of variables in this representation of f is at mostk-1. Since f depends on k bits, this is a contradiction. Thus, the lemma has been proved. □

Appendix D. Proof of Lemma 4

Proof.

For every k≥j+1and every fixed input_Xr=_{Xr,1 Xr,2}⋯_Xr,n∈^{0,1}nwherer∈{1,2,⋯,j,k}, letP(_Xk)=_s1P(_X1)+_s2P(_X2)+ ⋯ +_sjP(_Xj)which is a linear system of equations on j undetermined variables_s1,_s2,⋯,_sj. Note that this linear system of equations

∑r=1j_sr=1,∑r=1j_{sr Xr,i}=_Xk,i,i∈{1,2,⋯,n}.

consists ofn+1equations. Since vectorsP(_X1),P(_X2),⋯,P(_Xj)is a base, the rank of the matrix (P(_X1),P(_X2),⋯,P(_Xj)) is j. In other word, for all rows of the matrix (P(_X1),P(_X2),⋯,P(_Xj) ), we can find out a base which consists of j row vectors. After that, the augmented matrix of the linear system Equation (A5)

11⋯11_X1,1X2,1⋯_{Xj,1Xk,1X1,2X2,2}⋯_Xj,2Xk,2⋮⋮⋮⋮_X1,nX2,n⋯_Xj,nXk,n

can be transformed into

11⋯11_X1,i1X2,i1⋯_{Xj,i1Xk,i1X1,i2X2,i2}⋯_Xj,i2Xk,i2⋮⋮⋮⋮_{X1,ij-1X2,ij-1}⋯_{Xj,ij-1Xk,ij-1}00⋯0_Xk,ij'00⋯0_Xk,ij+1'⋮⋮⋮⋮00⋯0_Xk,in'

where{_i1,_i2,⋯,_in}={1,2,⋯,n}. According to the solution theory of linear system of equations, if any of_Xk,ij',_Xk,ij+1',⋯,and_Xk,in' is non-zero, then there exists no solution of the linear system Equation (A5) and the vectorP(_Xk)is not what we want. Otherwise, we can always get a solution

_s1s2s3⋮_sj=^{11⋯1_X1,i1X2,i1⋯_{Xj,i1X1,i2X2,i2}⋯_Xj,i2⋮⋮⋮_{X1,ij-1X2,ij-1}⋯_Xj,ij-1-1}1_Xk,i1Xk,i2⋮_Xk,ij-1.

As a result, for every_{Xk,i1 Xk,i2}⋯_Xk,ij-1∈^{0,1}j-1, we either can get a unique string_Xk=_{Xk,1 Xk,2}⋯_Xk,n∈^{0,1}nsatisfying_Xk,ij'=_Xk,ij+1'= ⋯ =_Xk,in'=0 in Equation (A7) or can not get a string_{Xr,1 Xr,2}⋯_Xr,n∈^{0,1}nsatisfying_Xk,ij'=_Xk,ij+1'= ⋯ =_Xk,in'=0 in Equation (A7). The lemma has been proved. □

References

1. Buhrman, H.; de Wolf, R. Complexity measures and decision tree complexity: A survey. Theor. Comput. Sci. 2002, 288, 21-43.

2. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. Quantum lower bounds by polynomials. J. ACM 2001, 48, 778-797.

3. Ambainis, A. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 2002, 64, 750-767.

4. Childs, A.M.; Landahl, A.J.; Parrilo, P.A. Quantum algorithms for the ordered search problem via semidefinite programming. Phys. Rev. A 2007, 75, 032335.

5. Hyer, P.; Špalek, R. Lower Bounds on Quantum Query Complexity. Bull. Eur. Assoc. Theor. Comput. Sci. 2005, 87, 78-103.

6. Nielson, M.A.; Chuang, I.L. Quantum Computation and Quantum Information, 10th ed.; Cambridge University Press: Cambridge, MA, USA, 2012.

7. Shor, P.W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20-22 November 1994; Goldwasser, S., Ed.; IEEE Computer Society Press: Los Alamitos, CA, USA, 1994.

8. Grover, L.K. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, USA, 22-24 May 1996; ACM: New York, NY, USA, 1996.

9. Deutsch, D. Quantum theory, the Church-Turing Principle and the universal quantum computer. Proc. R. Soc. London Ser. A 1985, 400, 97-117.

10. Deutsch, D.; Jozsa, R. Rapid solution of problems by quantum computation. Proc. R. Soc. London Ser. A 1992, 439, 553-558.

11. Harrow, A.W.; Hassidim, A.; Lloyd, S. Quantum Algorithm for Linear Systems of Equations. Phys. Rev. Lett. 2009, 103, 150502.

12. Ambainis, A.; Iraids, J.; Smotrovs, J. Exact quantum query complexity of EXACT and THRESHOLD. In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, Guelph, ON, Canada, 21-23 May 2013; Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany, 2013.

13. Ambainis, A. Superlinear advantage for exact quantum algorithms. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA, 1-4 June 2013; ACM: New York, NY, USA, 2013.

14. Ambainis, A.; Gruska, J.; Zheng, S.G. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Inf. Comput. 2015, 15, 435-452.

15. Montanaro, A.; Jozsa, R.; Mitchison, G. On exact quantum query complexity. Algorithmica 2015, 71, 775-796.

16. Ambainis, A.; Iraids, J.; Nagaj, D. Exact Quantum Query Complexity of EXACTnk,l. In SOFSEM 2017: Theory and Practice of Computer Science, Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, 16-20 January 2017; Steffen, B., Baier, C., Eds.; Springer: Cham, Switzerland, 2017.

17. Qiu, D.W.; Zheng, S.G. Generalized Deutsch-Jozsa problem and the optimal quantum algorithm. Phys. Rev. A 2018, 97, 062331.

18. He, X.Y.; Sun, X.M.; Yang, G.; Yuan, P. Exact Quantum Query Complexity of Weight Decision Problems via Chebyshev Polynomials. Available online: https://arxiv.org/abs/1801.05717. (accessed on 22 December 2020).

19. Kaniewski, J.; Lee, T.; de Wolf, R. Query Complexity in Expectation. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 6-10 July 2015; Springer: Berlin, Germany, 2016.

20. Montanaro, A.; Nishimura, H.; Raymond, R. Unbounded error quantum query complexity. Theor. Comput. Sci. 2011, 412, 4619-4628.

21. Ambainis, A.; Balodis, K.; Belovs, A.; Lee, T.; Santha, M.; Smotrovs, J. Separations in query complexity based on pointer functions. In Proceedings of the 48th ACM Symposium on Theory of Computing, Cambridge, MA, USA, 19-21 June 2016; pp. 800-813. Available online: https://arxiv.org/abs/1506.04719 (accessed on 22 December 2020).

22. Montanaro, A. Structure, Randomness and Complexity in Quantum Computation. Available online: https://people.maths.bris.ac.uk/csxam/papers/thesis.pdf (accessed on 22 December 2020).

23. Qiu, D.W.; Zheng, S.G. Characterizations of Symmetrically Partial Boolean Functions with Exact Quantum Query Complexity. Available online: https://arxiv.org/abs/1603.06505 (accessed on 22 December 2020).

24. Qiu, D.W.; Zheng, S.G. Revisiting Deutsch-Jozsa Algorithm. Inform. Comput. 2020, 275, 104605.

25. Aaronson, S.; Ambainis, A.; Iraids, J.; Kokainis, M.; Smotrovs, J. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. In Proceedings of the 31st Conference on Computational Complexity, Tokyo, Japan, 29 May-1 June 2016; Raz, R., Ed.; Schloss Dagstuhl: Wadern, Germany, 2016.

26. Grillo, S.A.; Marquezino, F.L. Quantum query as a state decomposition. Theor. Comput. Sci. 2018, 736, 62-75. Available online: https://arxiv.org/abs/1602.07716 (accessed on 22 December 2020).

27. Arunachalam, S.; Briet, J.; Palazuelos, C. Quantum Query Algorithms Are Completely Bounded Forms. SIAM J. Comput. 2019, 48, 903-925. Available online: https://arXiv:1711.07285 (accessed on 22 December 2020).

28. Chen, W.J.; Ye, Z.K.; Li, L.Z. Characterization of exact one-query quantum algorithms. Phys. Rev. A 2020, 101, 022325.

29. Mukherjee, C.S.; Maitra, S. Classical-Quantum Separations in Certain Classes of Boolean Functions-Analysis Using the Parity Decision Trees. Available online: https://arxiv.org/abs/2004.12942 (accessed on 22 December 2020).

30. De Wolf, R. Nondeterministic quantum query and communication complexities. SIAM J. Comput. 2003, 32, 681-699.

31. Simon, H.U. A tight ω(log log n)-bound on the time for parallel RAM's to compute non-degenerated boolean functions. Inf. Control. 1982, 55, 102-107.

32. Nisan, N.; Szegedy, M. On the degree of Boolean functions as real polynomials. Comput. Complex. 1994, 4, 301-313.

33. Xu, G.L.; Qiu, D.W. From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm. Quantum Inf. Process 2021, 20, 33.

34. Lee, T.; Prakash, A.; de Wolf, R.; Yuen, H. On the sum-of-squares degree of symmetric quadratic functions. In Proceedings of the 31st Conference on Computational Complexity, Tokyo, Japan, 29 May-1 June 2016; Raz, R., Ed.; Schloss Dagstuhl: Wadern, Germany, 2016.

35. Powers, V.; Wörmann, T. An algorithm for sums of squares of real polynomials. J. Pure. Appl. Algebra 1998, 127, 99-104.

36. Lasserre, J.B. A sum of squares approximation of nonnegative polynomials. SIAM J. Optimiz. 2006, 16, 751-765.

37. Lasserre, J.B. Sufficient conditions for a real polynomial to be a sum of squares. Arch. Math. 2006, 89, 390-398.

38. Papachristodoulou, A.; Anderson, J.; Valmorbida, G.; Prajna, S.; Seiler, P.; Parrilo, P. SOSTOOLS Version 3.00 Sum of Squares Optimization Toolbox for MATLAB. Available online: https://arxiv.org/abs/1310.4716 (accessed on 22 December 2020).

39. Blekherman, G.; Gouveia, J.; Pfeiffer, J. Sums of squares on the hypercube. Math. Z. 2016, 284, 41-54.