Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
Measuring and Controlling Bias for Some Bayesian Inferences and the Relation to Frequentist Criteria
Next Article in Special Issue
Integrable and Chaotic Systems Associated with Fractal Groups
Previous Article in Journal
Modeling Predictability of Traffic Counts at Signalised Intersections Using Hurst Exponent
Previous Article in Special Issue
Elliptic Solutions of Dynamical Lucas Sequences
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Entropy
Volume 23
Issue 2
10.3390/e23020189
entropy-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Partial Boolean Functions With Exact Quantum Query Complexity One

by
Guoliang Xu
1,2 and
Daowen Qiu
1,2,*
1
Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
2
Guangdong Key Laboratory of Information Security Technology, Sun Yat-sen University, Guangzhou 510006, China
*
Author to whom correspondence should be addressed.
Entropy 2021, 23(2), 189; https://doi.org/10.3390/e23020189
Submission received: 9 November 2020 / Revised: 27 January 2021 / Accepted: 28 January 2021 / Published: 3 February 2021
(This article belongs to the Special Issue Exploring the NP-Complexity of Nature: Critical Phenomena, Chaos, Fractals, Graphs, Boson Sampling, Quantum Computing and More)
Versions Notes

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, then F ( 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 input x ∈ D ⊆ { 0 , 1 } n that can only be accessed through a black box by querying some bit x i of the input, the quantum query model computes an n-bit partial Boolean function f : 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 ( > 1 2 ) 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 Q E ( f ) and the deterministic decision tree complexity D ( f ) [1], where D ( 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 with D = { 0 , 1 } n ), the first known quantum speed-up was Q E ( 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- ( 2 t ) 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 function f ( x ) = x 1 and the two-bit function x 1 ⊕ x 2 , 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, notations N , R , and C denote 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 input x = x 1 x 2 ⋯ x n ∈ D , the Hamming weight (number of 1s) of x is denoted by | x | . Given a real number set S, the notation max S denotes the maximum in S and the notation min S denotes the minimum in S. For any finite set S, the notation | S | denotes the number of elements in S. For a complex matrix A, A T is the transpose of the matrix A, and A † = ( A T ) * is the conjugate transpose of the matrix A. Obviously, A † = A T for 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 functions f : D → C , f : D → R and f : D → { 0 , 1 } . In general, these functions can be given by a 2 n -dimensional vector ( f ( 0 ) , f ( 1 ) , ⋯ , f ( x ) , ⋯ , f ( 2 n − 1 ) ) T whose entry f ( x ) is denoted by * for any undefined input x ∈ { 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 function f : 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 | = n 2 } ) .
In order to represent these functions, we need to use two monomials X S = ∏ i ∈ S x i and ( − 1 ) S · x = ∏ i ∈ S ( − 1 ) x i [1,20,30]. In particular, X Ø = ( − 1 ) Ø · x = 1 . And, the set { X S : 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 function p : R n → C can be written as Σ S α S X S 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 by deg ( p ) = max { | S | : α S ≠ 0 } . For any partial function f : D → C , a multilinear polynomial p ( x ) represents f if and only if p ( x ) = f ( x ) for all x ∈ D [1,32]. Unlike total functions f : { 0 , 1 } n → C , the multilinear representation of a partial (not total) function f : D → C is usually not unique. Naturally, the degree of a partial (or total) function f : D → C can be defined by deg ( f ) = min { deg ( p ) : p represents f } .
In the quantum query model, for every input x ∈ D , the quantum black box O x can be described as a unitary operator which is defined by
O x | i , j 〉 = ( − 1 ) x i | i , j 〉 , if i ∈ { 1 , 2 , ⋯ , n } , | 0 , j 〉 , if i = 0 .
Here, the integer number i ∈ { 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 U 0 , O x , U 1 , O x , ⋯ , O x , U t followed by a measurement, where t + 1 unitary operators U 0 , U 1 , ⋯ , U t 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 function f : D → { 0 , 1 } can be computed exactly by a 1-query quantum algorithm, if and only if there exist at least one non-negative solution z = ( z 0 , z 1 , z 2 , ⋯ , z n ) T of equations z 0 + z 1 + z 2 + ⋯ + z n =1 and F T ( a ⊕ b ) z = 0 for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } where the function vector F ( x ) = ( 1 , ( − 1 ) x 1 , ( − 1 ) x 2 , ⋯ , ( − 1 ) x n ) T for any x = x 1 x 2 ⋯ x n ∈ { 0 , 1 } n .
Proof. 
⇒ ) . Since the algorithm is exact, the quantum state U 1 O a U 0 | ψ 0 〉 for all a ∈ { x : f ( x ) = 0 } must be orthogonal to the quantum state U 1 O b U 0 | ψ 0 〉 for all b ∈ { x : f ( x ) = 1 } . Meanwhile, since the unitary operator U 1 preserves the inner product of any two complex vectors, the quantum state O a U 0 | ψ 0 〉 for all a ∈ { x : f ( x ) = 0 } must be orthogonal to the quantum state O b U 0 | ψ 0 〉 for all b ∈ { x : f ( x ) = 1 } . For any quantum state U 0 | ψ 0 〉 = ∑ i , j α i , j | i , j 〉 , note that
O a U 0 | ψ 0 〉 = ∑ j α 0 , j | 0 , j 〉 + ∑ i , j α i , j ( − 1 ) a i | i , j 〉
and the inner product
( O a U 0 | ψ 0 〉 ) † O b U 0 | ψ 0 〉 = ∑ j | α 0 , j | 2 + ∑ i , j ( − 1 ) a i ⊕ b i | α i , j | 2 = ( ∑ j | α 0 , j | 2 , ∑ j | α 1 , j | 2 , ⋯ , ∑ j | α n , j | 2 ) ( 1 , ( − 1 ) a 1 ⊕ b 1 , ⋯ , ( − 1 ) a n ⊕ b n ) T = ( z 0 , z 1 , ⋯ , z n ) F ( a ⊕ b ) = z T F ( a ⊕ b )
where the notation z i = ∑ j | α i , j | 2 for all i ∈ { 0 , 1 , 2 , ⋯ , n } is introduced in the last equality. Thus, there exists at least one non-negative solution z = ( z 0 , z 1 , z 2 , ⋯ , z n ) T of equations z 0 + z 1 + z 2 + ⋯ + z n = 1 and z T F ( a ⊕ b ) = 0 for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } .
⇐ ) . For a non-negative solution z = ( z 0 , z 1 , z 2 , ⋯ , z n ) T of equations z 0 + z 1 + z 2 + ⋯ + z n = 1 and z T F ( a ⊕ b ) = 0 for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } , if we set ∑ j | α i , j | 2 = z i for all i ∈ { 0 , 1 , 2 , ⋯ , n } in the state U 0 | ψ 0 〉 = ∑ i , j α i , j | i , j 〉 of an undetermined 1-query quantum algorithm, then the inner product
( U 1 O a U 0 | ψ 0 〉 ) † U 1 O b U 0 | ψ 0 〉 = 0
for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } . By Gram-Schmidt orthogonalization, we can find an orthonormal basis { U 1 O a U 0 | ψ 0 〉 : f ( a ) = 0 , a ∈ D } and an orthonormal basis { U 1 O b U 0 | ψ 0 〉 : f ( b ) = 1 , b ∈ D } , respectively. By the measurement consisting of the two orthonormal bases, the 1-query quantum algorithm (with the state U 0 | ψ 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 is n + 1 and the number of equations is 1 + | { a ⊕ b : f ( a ) = 0 , f ( b ) = 1 } | ≤ 2 n .
Considering the definition of the exact quantum query complexity, the task of proving Q E ( f ) = k must 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. For k = 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 function f : 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 is 1 + | { a ⊕ b : f ( a ) = 0 , f ( b ) = 1 } | which is an exponential number. Note that the number of variables in the linear system is n + 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 + 1 equations 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 } | − n equations can be ignored and things become quite easy.
(2)
If the exact quantum query complexity of an n-bit partial Boolean function f : 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 3 2 n − | 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 function f : 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 on n 2 + 1 bits.
For partial Boolean functions depending on all bits, the result is stated in the following.
Theorem 2.
For any n-bit partial Boolean function f : D → { 0 , 1 } depending on all n bits, f can be computed exactly by a 1-query quantum algorithm, if and only if f ( x ) = x 1 or 1 ⊕ x 1 with D = { 0 , 1 } , or f ( x ) = x 1 ⊕ x 2 or 1 ⊕ x 1 ⊕ x 2 with D ∈ { E ⊆ { 0 , 1 } 2 : | E | ∈ { 3 , 4 } } . □
Proof. 
⇒ ) . For any n-bit partial Boolean function f : D → { 0 , 1 } and k ∈ { 1 , 2 , ⋯ , n } , any multilinear polynomial representation of f can be written as
f ( x ) = x k q 1 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n ) + q 2 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n )
where q 1 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n ) and q 2 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n ) are two multilinear polynomials on variables x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n (i.e., not on the variable x k ). Let the input X k { k } be the same as the input X k except 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 ( X 1 , X 1 { 1 } ) , ( X 2 , X 2 { 2 } ) , ⋯ , ( X n , X n { n } ) such that 1 ⊕ f ( X k ) = f ( X k { k } ) ∈ { 0 , 1 } for all k ∈ { 1 , 2 , ⋯ , n } (In fact, for a certain k, if f ( X ) = f ( X { k } ) always hold for any X ∈ D , then the polynomial q 1 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n ) = 0 and f ( x ) = q 2 ( x 1 , x 2 , ⋯ , x k − 1 , x k + 1 , ⋯ , x n ) depends on at most n − 1 bits. This result contradicts the assumption that f depends on n bits).
By Theorem 1, there exists a non-negative vector z = ( z 0 , z 1 , z 2 , ⋯ , z n ) T such that the equations z 0 + z 1 + z 2 + ⋯ + z n =1 and
z T F ( X k ⊕ X k { k } ) = 0 = z 0 + ∑ i ≠ k z i − z k , k ∈ { 1 , 2 , ⋯ , n }
hold. Combining with z 0 + z 1 + z 2 + ⋯ + z n = 1 = z 0 + ∑ i ≠ k z i + z k , we have 2 z k = 1 for all k ∈ { 1 , 2 , ⋯ , n } which implies that n = 1 with z = ( 1 2 , 1 2 ) T or n = 2 with z = ( 0 , 1 2 , 1 2 ) T .
The case n = 1 is trivial, and f can be given by ( f ( 0 ) , f ( 1 ) ) = ( 0 , 1 ) or ( 1 , 0 ) . For the case n = 2 , the unique non-negative solution z = ( 0 , 1 2 , 1 2 ) T implies that
1 2 ( − 1 ) a 1 ⊕ b 1 + 1 2 ( − 1 ) a 2 ⊕ b 2 = 0
for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } . Then, a 1 ⊕ a 2 ≠ b 1 ⊕ b 2 for all a ∈ { x : f ( x ) = 0 } and b ∈ { x : f ( x ) = 1 } . This result implies that f ( x ) = x 1 ⊕ x 2 or 1 ⊕ x 1 ⊕ x 2 . Meanwhile, since f : 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 into n + 1 classes.
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 for n 2 , 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.
Let N ( n ) ( n ≥ 1 ) denote the number of all n-bit partial Boolean functions depending on n bits. Then, N ( n ) ≥ 2 × 3 2 n − n − 1 .
In contrast, the number of all n-bit total Boolean functions (investigated by Montanaro et al. [15]) is 2 2 n and the number of all n-bit symmetric partial Boolean functions (investigated by Qiu et al. [23,24]) is 3 n + 1 .
As a result, many n-bit partial Boolean functions depending on k ∈ { 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], if f : D → { 0 , 1 } can be computed by an exact 1-query quantum algorithm, then there exist degree-1 SOS complex representations of f and 1 − 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 function f : D → { 0 , 1 } , then there must exist degree-1 SOS complex (multilinear polynomials) representations of f and 1 − 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 vector F ( x ) = ( 1 , ( − 1 ) x 1 , ( − 1 ) x 2 , ⋯ , ( − 1 ) x n ) T . For an n-bit partial Boolean function f : D → { 0 , 1 } , if there exist two real ( 1 + n ) -dimensional column vector sets { a 1 , a 2 , ⋯ , a p } and { a p + 1 , a p + 2 , ⋯ , a p + q } such that the equations
f ( x ) = ∑ l = 1 p | a l T F ( x ) | 2 , x ∈ D , 1 − f ( x ) = ∑ l = p + 1 p + q | a l T F ( x ) | 2 , x ∈ D , ∑ l = p + 1 p + q | a l T F ( x ) | 2 = 1 − ∑ l = 1 p | a l T F ( x ) | 2 , x ∈ { 0 , 1 } n ,
hold, then the ( p + q ) × ( 1 + n ) complex coefficient matrix [ α f ] in the form of
[ α f ] = a 1 T ⋮ a p T a p + 1 T ⋮ a p + q T
is called a degree-1 SOS complex representation matrix of f and 1 − f . Here, every row vector a p T is the coefficient vector of the degree-1 Fourier polynomial a l T F ( x ) in Equation (9).
As we know, for the state U 1 O x U 0 | ψ 0 〉 = ∑ i , j ( ∑ S α i , j S ( − 1 ) S · x ) | i , j 〉 in a 1-query quantum algorithm, the amplitude ∑ S α i , j S ( − 1 ) S · x of any basis state | i , j 〉 is a polynomial of degree ≤ 1 . Therefore, ∑ S α i , j S ( − 1 ) S · x = ( α i , j Ø , α i , j { 1 } , α i , j { 2 } , ⋯ , α i , j { n } ) ( 1 , ( − 1 ) x 1 , ( − 1 ) x 2 , ⋯ , ( − 1 ) x n ) T . Then, the coefficient matrix α i , j S (here, the number pair i , j is the row index and the number set S the column index. In a 1-query quantum algorithm, the number pair i , j traverses all basis states and the set S traverses Ø , { 1 } , { 2 } , ⋯ , { n } ) with n + 1 columns in the form of
[ a Ø , a { 1 } , a { 2 } , ⋯ , a { n } ]
can be used to represent the state U 1 O x U 0 | ψ 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 U 1 O x U 0 | ψ 0 〉 = α i , j S F ( x ) holds (here, F ( x ) = ( 1 , ( − 1 ) x 1 , ( − 1 ) x 2 , ⋯ , ( − 1 ) x n ) T ). In order to distinguish the coefficient matrix of the state O x U 0 | ψ 0 〉 from the coefficient matrix of the state U 1 O x U 0 | ψ 0 〉 , the notation β i , j S denotes the coefficient matrix U 1 − 1 α i , j S of the state O x U 0 | ψ 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 function f : 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 and 1 − f such that
[ α f ] † [ α f ] = diag ( u 0 , u 1 , u 2 , ⋯ , u n ) .
Proof. 
⇒ ) . On one hand, the coefficient matrices of the states U 1 O x U 0 | ψ 0 〉 and O x U 0 | ψ 0 〉 are in the form of
α i , j S = [ a Ø , a { 1 } , a { 2 } , ⋯ , a { n } ]
and
β i , j S = U 1 − 1 α i , j S ,
respectively. On the other hand, for any quantum state
U 0 | ψ 0 〉 = ∑ j α 0 , j Ø | 0 , j 〉 + ∑ i ≠ 0 ∑ j α i , j Ø | i , j 〉 ,
the state
O x U 0 | ψ 0 〉 = ∑ j α 0 , j Ø | 0 , j 〉 + ∑ i ≠ 0 ∑ j α i , j Ø ( − 1 ) x i | i , j 〉 .
Thus, the coefficient matrix of the state O x U 0 | ψ 0 〉 is in the form of a block diagonal matrix
β i , j S = diag ( B 0 , B 1 , ⋯ , B n )
where the i-th block matrix
B i = α i , 0 Ø α i , 1 Ø ⋮ α i , j Ø ⋮
for every fixed i ∈ { 0 , 1 , 2 , ⋯ , n } . Thus, U 1 − 1 α i , j S = β i , j S = diag ( B 0 , B 1 , ⋯ , B n ) .
According to Lemma 2 and Definition 2, the coefficient matrix α i , j S of the state U 1 O x U 0 | ψ 0 〉 is an SOS complex representation matrix [ α f ] of the partial Boolean function f and 1 − f . Meanwhile, since all columns of any block-diagonal matrix diag ( B 0 , B 1 , ⋯ , B n ) are pairwise orthogonal and the unitary operator U 1 − 1 preserves 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 and 1 − f satisfying [ α f ] † [ α f ] = diag ( u 0 , u 1 , u 2 , ⋯ , u n ) , 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 B 0 , B 1 , ⋯ , B n satisfying | | B 0 | | = | | a Ø | | = u 0 and | | B i | | = | | a { i } | | = u i for all i ∈ { 1 , 2 , ⋯ , n } (for example, B i = ( u i , 0 , 0 , ⋯ ) T ). Since all columns of [ α f ] and diag ( B 0 , B 1 , ⋯ , B n ) are pairwise orthogonal, there always exists a unitary operator U 1 − 1 such that U 1 − 1 [ α f ] = diag ( B 0 , B 1 , ⋯ , B n ) .
As a result, the three states U 1 O x U 0 | ψ 0 〉 , O x U 0 | ψ 0 〉 and U 0 | ψ 0 〉 of an exact 1-query quantum algorithm computing f can be determined by [ α f ] , diag ( B 0 , B 1 , ⋯ , B n ) and
B 0 B 1 ⋮ B n ,
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 and 1 − 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- ( 2 t ) 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 Q E ( f ) = 1 to 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 vector P ( x ) = ( 1 , x 1 , x 2 , ⋯ , x n ) T where x = x 1 x 2 ⋯ x n ∈ { 0 , 1 } n . For any n-bit non-constant partial Boolean function f : 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 ) − ( 2 n + 2 − k ) ≤ 0
where all columns P ( x ) in the matrix ( ⋯ , P ( x ) , ⋯ ) f ( x ) = b traverse all legal inputs x ∈ D satisfying f ( x ) = b for b ∈ { 0 , 1 } .
In order to prove Theorem 4, the following lemma is necessary.
Lemma 3.
If an n-bit partial Boolean function f : 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 { i 1 } , a { i 2 } , ⋯ , a { i k } in the matrix [ α f ] where i 1 , i 2 , ⋯ , i k ∈ { 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 inputs x ∈ D satisfying f ( x ) = b where the vector function P ( x ) = ( 1 , x 1 , x 2 , ⋯ , x n ) 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 a 1 , a 2 , ⋯ , a p satisfying
f ( x ) = ∑ l = 1 p | a l T P ( x ) | 2 , ∀ x ∈ D .
Considering Equation (22) for x such that f ( x ) = 0 forces a l T P ( x ) = 0 . Thus, a l ⏊ P ( x ) for all P ( x ) with f ( x ) = 0 . Then, a l for any l is in the orthogonal complement of the space spanned by all P ( x ) with f ( x ) = 0 , we know the existence of the sequence (i.e., non-zero vectors a 1 , a 2 , ⋯ , a p ) requires 1 ≤ ( n + 1 ) − rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 0 ) ≤ n . Similarly, considering Equation (22) for x such that f ( x ) = 1 , we can get 1 ≤ ( 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 and 1 − f such that U 1 − 1 [ α f ] = diag ( B 0 , B 1 , ⋯ , B n ) . By Equation (10), we can see that
rank ( [ α f ] ) ≤ rank ( [ a 1 , ⋯ , a p ] ) + rank ( [ a p + 1 , ⋯ , a p + q ] ) .
Moreover,
rank ( [ a 1 , ⋯ , a p ] ) ≤ ( 1 + n ) − rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 0 )
and
rank ( [ a p + 1 , ⋯ , a p + q ] ) ≤ ( 1 + n ) − rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 1 )
can be obtained by considering Equation (22) for x such that f ( x ) = 0 and f ( 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 } | ( Lemma 3 ) = | { i ∈ { 0 , 1 , ⋯ , n } : ∥ B i ∥ ≠ 0 } | ( The unitary operator U 1 preserves Euclidean norm ) = rank ( diag ( B 0 , B 1 , ⋯ , B n ) ) ( The characterization of the block diagonal matrix ) = rank ( [ a Ø , a { 1 } , a { 2 } , ⋯ , a { n } ] ) ( The unitary operator U 1 preserves the rank ) = rank ( [ α f ] ) ≤ 2 ( 1 + n ) − ∑ b = 0 1 rank ( ( ⋯ , 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 that rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 0 ) = 1 and rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 1 ) = 3 . However, using Theorem 10 of Ref. [23], Q E ( 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 function F ( f ) : = rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 0 ) + rank ( ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 1 ) − ( 2 n + 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 N 1 ( 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 function P ( X k ) = ( 1 , X k , 1 , X k , 2 , ⋯ , X k , n ) T for a string X k = X k , 1 X k , 2 ⋯ X k , n ∈ { 0 , 1 } n . If n ≥ 2 , for any j ∈ { 1 , 2 , ⋯ , n + 1 } different linearly independent vectors P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X j ) , there exist at most T j ≤ 2 j − 1 − j other different vectors P ( X j + 1 ) , P ( X j + 2 ) , ⋯ , P ( X j + T j ) satisfying rank ( [ P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X j + T j ) ] ) = j .
By Theorem 4, the fifth result is the following.
Theorem 5.
Let N 1 ( 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. If n ≥ 3 and k ≥ 2 , then N 1 ( n , k ) ≤ n 2 2 2 n − 1 ( 1 + 2 2 − k ) + 2 n 2 .
Proof. 
Recall that all columns in the matrix ( ⋯ , P ( x ) , ⋯ ) f ( x ) = b traverse all legal inputs x ∈ D satisfying f ( x ) = b where the function vector P ( x ) = ( 1 , x 1 , x 2 , ⋯ , x n ) T . Let r 0 denote the rank of ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 0 and r 1 the rank of ( ⋯ , P ( x ) , ⋯ ) f ( x ) = 1 . According to Theorem 4, N 1 ( n , k ) is not bigger than the number of all n-bit partial Boolean functions satisfying r 0 + r 1 ≤ 2 n + 2 − k and 1 ≤ r 0 , r 1 ≤ n . For every fixed ( r 0 , r 1 ) , an n-bit partial Boolean function can be determined using the following two steps.
In the first step, we choose r 0 linearly independent vectors
P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X r 0 )
and r 1 linearly independent vectors
P ( Y 1 ) , P ( Y 2 ) , ⋯ , P ( Y r 1 )
for some X 1 , X 2 , ⋯ , X r 0 , Y 1 , Y 2 , ⋯ , Y r 1 ∈ { 0 , 1 } n , respectively. Here, r 0 linearly independent vectors P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X r 0 ) correspond to r 0 different inputs with function value 0, and r 1 linearly independent vectors P ( Y 1 ) , P ( Y 2 ) , ⋯ , P ( Y r 1 ) correspond to r 1 different inputs with function value 1. For every fixed ( r 0 , r 1 ) , the number of different selections (i.e., { P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X r 0 ) } and { P ( Y 1 ) , P ( Y 2 ) , ⋯ , P ( Y r 1 ) } ) is not bigger than
2 n r 0 2 n − r 0 r 1 ≤ 2 n ( r 0 + r 1 )
for all n ≥ 3 and k ≥ 2 .
In the second step, we add some other vectors P ( X r 0 + 1 ) , ⋯ and P ( Y r 1 + 1 ) , ⋯ to the sets { P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X r 0 ) } and { P ( Y 1 ) , P ( Y 2 ) , ⋯ , P ( Y r 1 ) } , respectively. Here, every newly added vector in the set { P ( X r 0 + 1 ) , ⋯ } should be represented linearly by the determined r 0 linearly independent vectors P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X r 0 ) and every newly added vector in the set { P ( Y r 1 + 1 ) , ⋯ } should be represented linearly by the determined r 1 linearly independent vectors P ( Y 1 ) , P ( Y 2 ) , ⋯ , P ( Y r 1 ) . After that, an n-bit partial Boolean function f is determined as follows. f ( x ) = 0 for x in the set { X 1 , X 2 , ⋯ , X r 0 , ⋯ } , f ( x ) = 1 for x in the set { Y 1 , Y 2 , ⋯ , Y r 1 , ⋯ } , and it is undefined for the rest cases. Using Equation (29) and Lemma 4, for every fixed ( r 0 , r 1 ) , there are at most
2 n ( r 0 + r 1 ) 2 ( 2 r 0 − 1 − r 0 ) 2 ( 2 r 1 − 1 − r 1 ) < 2 2 n 2 2 ( 2 n − 1 + 2 n + 1 − k ) = 2 2 n − 1 ( 1 + 2 2 − k ) + 2 n 2
partial Boolean functions with a pair of fixed r 0 and r 1 . Note that the number of different ( r 0 , r 1 ) is not bigger than n 2 . 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, 3 2 n is the number of all n-bit partial Boolean functions, as each n-bit partial Boolean function corresponds to a string f ( 0 ) f ( 1 ) ⋯ f ( 2 n − 1 ) ∈ { 0 , 1 , * } 2 n . In fact, the exact quantum query complexity of any n-bit partial Boolean function is in the set { 0 , 1 , 2 , ⋯ , n } , which implies that max { N j ( n , k ) : j , k ∈ { 0 , 1 , 2 , ⋯ , n } } ≥ 3 2 n ( n + 1 ) 2 . Here, the notation N j ( 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.
Fact 2 . 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 | = n 2 , 1 , | x | = 0 , n .
By Fact 2, the exact quantum query complexity of any partial Boolean function g defined by
g ( x ) = 0 or * , ∀ | x | = n 2 , 1 or * , | x | = 0 , n .
is also 1. The number of functions in this form is 3 × ( 2 n n 2 − 1 ) . Thus, for an even integer n, 3 × ( 2 n n 2 − 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 n e n ,
we have
n n 2 = n ! n 2 ! 2 ≈ 2 π n ( n e ) n 2 π n 2 n 2 e n 2 2 = 2 π n π n 2 n .
Thus, the trivial lower bound
3 × ( 2 n n 2 − 1 ) ≈ 3 × 2 2 π n π n 2 n .
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 ≤ 2 in 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 all k ∈ { 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

Not applicable.

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 function f : { 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 X k , X k { k } ∈ { 0 , 1 } n such that 1 ⊕ f ( X k ) = f ( X k { k } ) ∈ { 0 , 1 } . Here, X k { k } is the same as X k except 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 function f : { 0 , 1 } n → { 0 , 1 } depends on k bits, then we can always find out a sequence i 1 , i 2 , ⋯, i k such that f depends on the i 1 -bit, the i 2 -bit, ⋯ , and the i k -bit. Meanwhile, the unique multilinear polynomial representation of f is on the k variables (i.e., x i 1 , x i 2 , ⋯ , x i k ). 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 that N ( 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 function f : D → { 0 , 1 } ( D ⊆ { 0 , 1 } k ) depending on k bits (Note that D is not an empty set for k ≥ 1 ), we construct at least 3 2 k − 1 ( k + 1 ) -bit partial Boolean function g depending on k + 1 bits by f. In fact, for any fixed y = y 1 y 2 ⋯ y k ∈ D ⊆ { 0 , 1 } k , any ( k + 1 ) -bit partial Boolean function g defined by
g ( x 0 ) = f ( x ) , ∀ x ∈ D , g ( x 0 ) = * , ∀ x ∈ { 0 , 1 } k ∖ D , g ( x 1 ) = 1 ⊕ f ( y ) , x = y , g ( x 1 ) ∈ { 0 , 1 , * } , ∀ x ∈ { 0 , 1 } k ∖ { y }
is a ( k + 1 ) -bit partial Boolean function depending on ( k + 1 ) bits. For any k ≥ 1 , the last line in Equation (A1) implies that
N ( k + 1 ) N ( k ) ≥ 3 2 k − 1 .
Since N ( 1 ) = 2 (i.e., ( f ( 0 ) , f ( 1 ) ) = ( 0 , 1 ) and ( f ( 0 ) , f ( 1 ) ) = ( 1 , 0 ) ), we have
N ( n ) ≥ 2 ∏ k = 1 n − 1 3 2 k − 1 = 2 × 3 2 n − n − 1 .
The lemma has been proved. □

Appendix C. Proof of Lemma 3

Proof. 
Assume that there exist at most k − 1 non-zero vectors in all vectors a Ø , a { 1 } , a { 2 } , ⋯ , a { n } . Then, there exist at least n − k + 1 zero vectors a { i k } , a { i k + 1 } , ⋯ , a { i n } where i k , i k + 1 , ⋯ , i n ∈ { 1 , 2 , ⋯ , n } . Note that all entries a { i r } l in a { i r } are zeros for all l ∈ { 1 , 2 , ⋯ , p + q } and r ∈ { k , k + 1 , ⋯ , n } . Therefore,
f ( x ) = | f 1 ( x ) | 2 + ⋯ + | f p ( x ) | 2 = ∑ l = 1 p a Ø l + ∑ i ∈ { 1 , 2 , ⋯ , n } a { i } l ( − 1 ) x i 2 = ∑ l = 1 p a Ø l + ∑ r ∈ { 1 , 2 , ⋯ , k − 1 } a { i r } l ( − 1 ) x i r 2 .
Obviously, the number of variables in this representation of f is at most k − 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 + 1 and every fixed input X r = X r , 1 X r , 2 ⋯ X r , n ∈ { 0 , 1 } n where r ∈ { 1 , 2 , ⋯ , j , k } , let P ( X k ) = s 1 P ( X 1 ) + s 2 P ( X 2 ) + ⋯ + s j P ( X j ) which is a linear system of equations on j undetermined variables s 1 , s 2 , ⋯ , s j . Note that this linear system of equations
∑ r = 1 j s r = 1 , ∑ r = 1 j s r X r , i = X k , i , i ∈ { 1 , 2 , ⋯ , n } .
consists of n + 1 equations. Since vectors P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X j ) is a base, the rank of the matrix ( P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X j ) ) is j. In other word, for all rows of the matrix ( P ( X 1 ) , P ( X 2 ) , ⋯ , P ( X j ) ), we can find out a base which consists of j row vectors. After that, the augmented matrix of the linear system Equation (A5)
1 1 ⋯ 1 1 X 1 , 1 X 2 , 1 ⋯ X j , 1 X k , 1 X 1 , 2 X 2 , 2 ⋯ X j , 2 X k , 2 ⋮ ⋮ ⋮ ⋮ X 1 , n X 2 , n ⋯ X j , n X k , n
can be transformed into
1 1 ⋯ 1 1 X 1 , i 1 X 2 , i 1 ⋯ X j , i 1 X k , i 1 X 1 , i 2 X 2 , i 2 ⋯ X j , i 2 X k , i 2 ⋮ ⋮ ⋮ ⋮ X 1 , i j − 1 X 2 , i j − 1 ⋯ X j , i j − 1 X k , i j − 1 0 0 ⋯ 0 X k , i j ′ 0 0 ⋯ 0 X k , i j + 1 ′ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 X k , i n ′
where { i 1 , i 2 , ⋯ , i n } = { 1 , 2 , ⋯ , n } . According to the solution theory of linear system of equations, if any of X k , i j ′ , X k , i j + 1 ′ , ⋯ , and X k , i n ′ is non-zero, then there exists no solution of the linear system Equation (A5) and the vector P ( X k ) is not what we want. Otherwise, we can always get a solution
s 1 s 2 s 3 ⋮ s j = 1 1 ⋯ 1 X 1 , i 1 X 2 , i 1 ⋯ X j , i 1 X 1 , i 2 X 2 , i 2 ⋯ X j , i 2 ⋮ ⋮ ⋮ X 1 , i j − 1 X 2 , i j − 1 ⋯ X j , i j − 1 − 1 1 X k , i 1 X k , i 2 ⋮ X k , i j − 1 .
As a result, for every X k , i 1 X k , i 2 ⋯ X k , i j − 1 ∈ { 0 , 1 } j − 1 , we either can get a unique string X k = X k , 1 X k , 2 ⋯ X k , n ∈ { 0 , 1 } n satisfying X k , i j ′ = X k , i j + 1 ′ = ⋯ = X k , i n ′ = 0 in Equation (A7) or can not get a string X r , 1 X r , 2 ⋯ X r , n ∈ { 0 , 1 } n satisfying X k , i j ′ = X k , i j + 1 ′ = ⋯ = X k , i n ′ = 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. [Google Scholar] [CrossRef] [Green Version]
  2. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. Quantum lower bounds by polynomials. J. ACM 2001, 48, 778–797. [Google Scholar] [CrossRef]
  3. Ambainis, A. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. 2002, 64, 750–767. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar] [CrossRef] [Green Version]
  5. Hyer, P.; Špalek, R. Lower Bounds on Quantum Query Complexity. Bull. Eur. Assoc. Theor. Comput. Sci. 2005, 87, 78–103. [Google Scholar]
  6. Nielson, M.A.; Chuang, I.L. Quantum Computation and Quantum Information, 10th ed.; Cambridge University Press: Cambridge, MA, USA, 2012. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  9. Deutsch, D. Quantum theory, the Church-Turing Principle and the universal quantum computer. Proc. R. Soc. London Ser. A 1985, 400, 97–117. [Google Scholar]
  10. Deutsch, D.; Jozsa, R. Rapid solution of problems by quantum computation. Proc. R. Soc. London Ser. A 1992, 439, 553–558. [Google Scholar]
  11. Harrow, A.W.; Hassidim, A.; Lloyd, S. Quantum Algorithm for Linear Systems of Equations. Phys. Rev. Lett. 2009, 103, 150502. [Google Scholar] [CrossRef]
  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. [Google Scholar]
  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. [Google Scholar]
  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. [Google Scholar]
  15. Montanaro, A.; Jozsa, R.; Mitchison, G. On exact quantum query complexity. Algorithmica 2015, 71, 775–796. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar]
  17. Qiu, D.W.; Zheng, S.G. Generalized Deutsch-Jozsa problem and the optimal quantum algorithm. Phys. Rev. A 2018, 97, 062331. [Google Scholar] [CrossRef]
  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. [Google Scholar]
  20. Montanaro, A.; Nishimura, H.; Raymond, R. Unbounded error quantum query complexity. Theor. Comput. Sci. 2011, 412, 4619–4628. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar] [CrossRef]
  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. [Google Scholar]
  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). [CrossRef] [Green Version]
  28. Chen, W.J.; Ye, Z.K.; Li, L.Z. Characterization of exact one-query quantum algorithms. Phys. Rev. A 2020, 101, 022325. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar] [CrossRef] [Green Version]
  32. Nisan, N.; Szegedy, M. On the degree of Boolean functions as real polynomials. Comput. Complex. 1994, 4, 301–313. [Google Scholar] [CrossRef]
  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. [Google Scholar] [CrossRef]
  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. [Google Scholar]
  35. Powers, V.; Wörmann, T. An algorithm for sums of squares of real polynomials. J. Pure. Appl. Algebra 1998, 127, 99–104. [Google Scholar] [CrossRef] [Green Version]
  36. Lasserre, J.B. A sum of squares approximation of nonnegative polynomials. SIAM J. Optimiz. 2006, 16, 751–765. [Google Scholar] [CrossRef] [Green Version]
  37. Lasserre, J.B. Sufficient conditions for a real polynomial to be a sum of squares. Arch. Math. 2006, 89, 390–398. [Google Scholar] [CrossRef] [Green Version]
  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. [Google Scholar] [CrossRef] [Green Version]
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Xu, G.; Qiu, D. Partial Boolean Functions With Exact Quantum Query Complexity One. Entropy 2021, 23, 189. https://doi.org/10.3390/e23020189

AMA Style

Xu G, Qiu D. Partial Boolean Functions With Exact Quantum Query Complexity One. Entropy. 2021; 23(2):189. https://doi.org/10.3390/e23020189

Chicago/Turabian Style

Xu, Guoliang, and Daowen Qiu. 2021. "Partial Boolean Functions With Exact Quantum Query Complexity One" Entropy 23, no. 2: 189. https://doi.org/10.3390/e23020189

APA Style

Xu, G., & Qiu, D. (2021). Partial Boolean Functions With Exact Quantum Query Complexity One. Entropy, 23(2), 189. https://doi.org/10.3390/e23020189

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop