title: Characterization of exact one-query quantum algorithms (ii): for partial functions
authors: Zekun Ye Lvzhou Li
text: 
  	
  	lilvzh@mail.sysu.edu.cn.
  	
  	
  		^1 Institute of Computer Science Theory, School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China
  	
  
  	
  		^2 Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing (Sun Yat-sen University), Guangzhou  510006, China
  	
  	
  
  	
  	 The
   query model  (or black-box model) has attracted much attention  from the communities  of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum   algorithm that has  a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and  Grover algorithm  all show  a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. 101, 02232 (2020)) the problem: what
  functions can be computed by an exact one-query quantum algorithm?
   This problem has been addressed for  total Boolean functions but still open for partial Boolean functions. 
   Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions,  we construct some new functions that can be computed exactly by  one-query quantum  algorithms but have essential difference from the already known ones.	Note that before our work, the known functions that can be computed by exact one-query quantum  algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
   
  
  	Characterization of exact one-query quantum algorithms (ii): for partial functions 
      Zekun Ye^1, Lvzhou Li^1, 2, 
      August 27, 2020
  ===================================================================================
  
  
  
  	
  
  	
  	
  
  §  INTRODUCTION
  
  	
  	
  	
  	The  decision tree model  has been well studied in classical computing,  and focuses on problems such as the following: given a Boolean function f:{0,1}^n→{0,1},  how can we make  as few queries as possible  to the bits of x in order to output the value of  f(x)? Quantum analog, called the quantum query model, has also attracted much attention in recent years <cit.>. The implementation procedure of a quantum query model is  a  quantum query algorithm, which can be roughly described as follows:  it starts with a fixed state |ψ_0⟩, and then performs the sequence of operations U_0, O_x, U_1,  …, O_x,U_t, where U_i's are unitary operators that do not depend on the input x but the query O_x  does. This leads to the final state |ψ_x⟩=U_tO_xU_t-1⋯ U_1O_xU_0|ψ_o⟩. The result is obtained by measuring the final state  |ψ_x⟩.
  	
  	
  	The quantum query model can be discussed in two main settings: the exact setting and the bounded-error setting. A quantum query algorithm is said to compute a function f exactly, if its output equals f(x) with probability 1, for all inputs x. In this case, the algorithm is called an exact quantum algorithm. It is said to compute f with bounded error,  if its output equals f(x) with a  probability greater than a constant, for all inputs x. Roughly speaking, the query complexity of a function f  is the number of queries  that an  optimal (classical or quantum) algorithm should make in the worst case to compute f. The classical deterministic query complexity of  f is denoted by D(f), and the quantum query complexity in the  exact setting is denoted by Q_E(f). In this paper, we focus on quantum query algorithms in the exact setting  <cit.>, where quantum advantages were shown by comparing Q_E(f) and D(f). For total Boolean functions, Beals et al. <cit.> showed that exact quantum query algorithms can only achieve  polynomial speed-up over classical counterparts.  At the same time, Ambainis et al. <cit.> proved that exact quantum algorithms have advantages for almost all Boolean functions.  However, the biggest gap between Q_E(f) and D(f) is only a factor of 2 and is achieved by Deutsch algorithm for a long time. In 2013,  a breakthrough result  was obtained by Ambainis, showing   the first total Boolean function for which exact quantum algorithms have superlinear advantage over  classical deterministic algorithms <cit.>. Moveover, Ambainis  <cit.> improved this result and presented a nearly quadratic separation in 2016.
  	
   For partial functions (promise problems),  exponential separations between exact quantum and classical deterministic query complexity were obtained in several papers <cit.>. A typical example is  Deutsch-Jozsa algorithm <cit.>. In addition, some work showed an exponential separation between quantum and randomized query complexity in the bound-error setting, such as Simon algorithm <cit.> and Shor algorithm <cit.>.
   Recently, Childs and Wang <cit.> proved that there is at most polynomial quantum speedup for (partial) graph property problems in the adjacency matrix model. On the contrary, in the adjacency list model for bounded-degree graphs, they exhibited a promise problem that shows an exponential separation between the randomized and quantum query complexities. Moreover, a series of work showed that for partial Boolean functions on N variables, the quantum query complexity could be exponentially smaller (or even less) than the randomized query complexity. 
   Aaronson and Ambainis <cit.> proposed a promise problem called Forrelation and showed that this problem can be solved using 1 quantum query with bounded error, yet any randomized algorithm needs  Ω(√(N)) queries. They also showed that this separation is essentially optimal: any t-query quantum algorithm can be simulated by an O(N^1-1/2t)-query randomized algorithm. Tal <cit.> gave a O(1) vs. N^2/3-ϵ separation between the quantum and randomized query complexities of partial Boolean functions by a variant of k-fold Forrelation problem. Furthermore, for any positive integer k, Sherstov et al. <cit.> obtained a partial function on N bits that has bounded-error quantum query complexity at most ⌈ k/2 ⌉ and randomized query complexity Ω̃(N^1-1/k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis <cit.>.
  	
  
  Recently, characterization of one-query quantum algorithms (that can make only one query) has received some attention <cit.>.  Aarsonson et al. <cit.> and Arunachalam et al. <cit.> have presented a complete characterization of the Boolean functions that can be computed by a one-query quantum algorithm in the bounded-error setting,  but their results are not applicable to the exact case. 
  We  considered  the problem of what Boolean functions can be computed by exact one-query quantum algorithms, by  proving that  a total  Boolean function f:{0,1}^n →{0,1}  can be  computed by an exact one-query quantum algorithm if and only if f(x)=x_i_1 or f(x)=x_i_1⊕ x_i_2 (up to isomorphism) <cit.>. However, this does not hold for partial functions.   On the one hand, it has been known that any symmetric partial Boolean function f has Q_E(f) = 1 if and only if f can be computed by Deutsch-Jozsa algorithm <cit.>. On the other hand, it is unclear for the asymmetric partial functions. 
  
  
  
  
  All the above motivates us to consider the following question: what partial Boolean functions can be computed by an exact one-query quantum algorithm? We answer this question by giving some necessary and sufficient conditions.  Furthermore, by these conditions we obtain and discuss some new representative function examples that can be computed  by exact one-query quantum algorithms. These examples generalize the known function cases and fill a gap in the discussion of exact one-query asymmetric functions. Especially, some cases have essential difference from the known functions that can be computed by  Deutsch-Jozsa algorithm. Note that recently Xu and Qiu <cit.> have independently carried out an interesting work on the similar topic as in this paper.
   
   
  	
  The remainder of this paper is organized as follows. The query model and the problem we consider are given in Section <ref>. Some necessary and sufficient conditions are presented in Section <ref>. The construction and discussion of new functions are shown in Section <ref>. Finally, a conclusion is made in Section <ref> and some further problems are proposed.
  	
  
  
  § PRELIMINARIES
   
  	In this paper,  we consider  Boolean functions	f:{0,1}^n →{0,1}.  It is called a total function,  if it is defined for all x∈{0,1}^n. It is called a partial function, if it is defined on a subset D⊂{0,1}^n.  In the following, we first give an introduction about the query models, including both  classical and quantum cases, and then we describe  the problem  to be discussed.
  	
  
  	Given a Boolean function f:{0,1}^n →{0,1}, suppose x=x_1x_2...x_n ∈{0,1}^n is an input of f and we use x_i to denote its i-th bit. The goal of a query algorithm is to compute f(x), given queries to the bits of x.
  	
  	
  	
  	In the classical case, the process of querying  x is implemented by using the black box (called query oracle) shown in Figure <ref>. We want to compute f(x) by using the query oracle as few as possible. 	A classical deterministic algorithm for computing f  can be described by a decision tree. 
  	For example, suppose that we want to use a classical deterministic algorithm to compute  f(x)=x_1  (x_2 ∨ x_3).  Then  a decision tree T for that  is depicted  in Figure <ref>. 	Given an input x, the tree is evaluated as follows. It starts at the root. At each node, if it is a leaf, then  its label is output as the result for f(x); otherwise, it queries its label variable  x_i. If x_i = 0, then we recursively evaluate the left subtree. Otherwise, we recursively evaluate the right subtree. The query complexity of tree T denoted by D(T) is its depth, and we have D(T)=3 in this example. Given f, there exist different decision trees to compute it, and the query complexity of f, denoted by D(f), is defined as 
  D(f)=min_TD(T).
  	
  	
  	
  	
  	
  	
  	In the quantum case, we are able to query more than one bit each time due to quantum superposition. There are two equivalent query oracles: the bit flip oracle Ô_x defined by Ô_x|i,b⟩ = |i,b ⊕ x_i⟩ for i ∈{1,...,n}, b ∈{0,1}; the phase oracle O_x defined by O_x|i⟩ = (-1)^x_i|i⟩ for all i ∈{0,...,n}, where  x_0=0. In this paper, we use the phase oracle for convenience. A T-query quantum algorithm can be seen as a sequence of unitaries U_TO_xU_T-1O_x...O_xU_0, where U_i's are fixed unitaries and O_x depends on x. The process of computation is as follows:
  			
  		
     (1)  Start with an initial state |ψ_0⟩.
  		
  		
     (2) Perform the operators U_0, O_x, U_1, O_x...U_T in sequence, and then we obtain the state |ψ_x⟩=U_TO_xU_T-1O_x...U_0|ψ_0⟩.
  		
  		
     (3) Measure |ψ_x⟩ with a 0-1 positive operator-valued measurement  <cit.>. The measurement result
  		is regarded as the output of the algorithm.
  	
  	
  	
  	In the above,  we use r(x) to denote the measurement result of |ψ_x⟩. Let P[𝒜] denote the probability that event 𝒜 occurs.  If it satisfies:
  	
  	
      ∀ x , P[ r(x)=f(x) ]  ≥ 1-ϵ   ,
  
  	where ϵ < 1/2, then the quantum query algorithm is said to compute f(x) with bounded error ϵ. If it satisfies:
  	
      ∀ x, P[ r(x)=f(x) ]  =1,
   
  	then it is said to compute f(x) exactly, and the algorithm is called an exact quantum algorithm.
  	The exact quantum  query complexity of   f, denoted by Q_E(f), is the minimum number of queries that a quantum query algorithm needs to compute f.
  	The gap between D(f) and Q_E(f) is usually used to exhibit quantum advantages. 
  	
  	
  	
  	In this paper, we want to characterize those partial Boolean functions f that satisfy Q_E(f)=1. In other words, we consider this problem: what partial Boolean functions f can be computed by an exact one-query quantum algorithm?  
  	
  	
  	
  	
  
  § NECESSARY AND SUFFICIENT CONDITIONS
   
  	
  
  First, we give some notation. For x∈{0, 1}^n, we  always associate it with one bit x_0 = 0, and let  |x⟩ = ∑_i x_i|i⟩ be an n+1 dimension vector.
  Define x' by x'_i = (-1)^x_i for any i. For a non-negative diagonal matrix D, let |x_D⟩ = √(D)|x'⟩. If tr(D) = 1, then |x_D⟩ is a unit vector. 
  
     
      We given some necessary and sufficient conditions as follows.
  	
  	
  		
  		The following statements  are equivalent to each other:
  	
  	
    (a) f:{0,1}^n →{0,1} can be computed by an exact one-query quantum algorithm. 
  		
  	
    (b) There exist a set of non-negative coefficients {c_i} with ∑_i=0^n c_i = 1, such that f(x) ≠ f(y) implies ∑_i ∈ Sc_i = 1/2, where S = {i|x_i ≠ y_i}.
  
  	
    (c)  There exists a non-negative diagonal matrix D with tr(D) = 1, such that f(x) ≠ f(y) implies ⟨ x_D|y_D ⟩ = 0.
  
  	
    (d)  There exists a project operation P and a non-negative diagonal matrix D with tr(D) = 1, such that f(x) = ⟨ x_D |P| x_D ⟩.
  
  	
  
  	
  	
  	
  
  	
  	 (a)⇒ (b).
  	Suppose we have an exact one-query quantum algorithm. let |ψ_x⟩ = U_1 O_x U_0|ψ_0⟩. 
  	 Since the algorithm is allowed to use auxiliary space, we assume 
  	
      |ϕ_x⟩   = O_x U_0|ψ_0⟩
         = O_x ∑_i,jα_ij|i⟩|j⟩
         = ∑_i,jα_ij(-1)^x_i|i⟩|j⟩.
  
  	The assumption that f can be computed exactly implies that |ψ_x⟩ and |ψ_y⟩ can be perfectly distinguished. Thus, the two states are orthogonal, i.e., ⟨ψ_x|ψ_y⟩=0. Since unitary operators don't change the orthogonality between two states, equivalently, there is ⟨ϕ_x|ϕ_y⟩ = 0, which means 
  	
      ⟨ϕ_x|ϕ_y⟩   = ∑_ij|α_ij|^2(-1)^x_i ⊕ y_i
         = ∑_i ∉ S∑_j|α_ij|^2- ∑_i ∈ S∑_j |α_ij|^2 = 0.
  
  	And because ∑_ij |α_ij|^2 = 1, we have ∑_i ∈ S∑_j |α_ij|^2 = 1/2.  Now we construct the coefficients {c_i} in item (b). For i ∈{0,...,n}, let c_i =∑_j |α_ij|^2. Then we have
  
      ∑_i ∈ Sc_i =  ∑_i ∈ S∑_j |α_ij|^2 = 1/2.
  
  As a result, we get a set of feasible coefficients {c_i}.
  	
   (b)⇒ (c).	
  	We define diagonal matrix D by D_ii = c_i for any i. 
  	If f(x) ≠ f(y), then 
  
      ⟨ x_D |y_D⟩    = ⟨ x'|D|y'⟩
          =∑_i c_i x'_i y'_i 
      
         = ∑_i:x_i = y_ic_i- ∑_i:x_i ≠ y_ic_i
         = ∑_i ∉ Sc_i-∑_i ∈ Sc_i =0.
  
  
   (c)⇒ (d).
  	
  	By item (c), if f(x) ≠ f(y), then ⟨ x_D|y_D ⟩ =0. Let X = {|x_D⟩|f(x)=1}, Y = {|y_D⟩|f(y) = 0}. Then X  Y. Select an orthonormal basis {|v_i⟩} of  Span{X}. 
  	Let g(x)=∑_i⟨ v_i|x_D⟩^2. If f(x)=1, then |x_D⟩∈ Span{X}, thus we have g(x) =  |x_D ⟩^2= 1. If f(x)=0, then for any i, ⟨ v_i|x_D ⟩ = 0, thus g(x)=0. As a result, we have f(x)=g(x). 
  	Let P = ∑_i |v_i ⟩⟨ v_i|. 
  	Then 
  	
      f(x)    = g(x) = ∑_i⟨ v_i| x_D ⟩^2 
         = ∑_i ⟨ x_D |v_i⟩⟨ v_i| x_D⟩
         = ⟨ x_D|(∑_i|v_i⟩⟨ v_i|)| x_D⟩
         =⟨ x_D|P|x_D⟩.
  
  
  
  	
   (d)⇒ (a).
  	Suppose 
  	f(x) = ⟨ x_D|P|x_D ⟩. We give Algorithm <ref> to compute f as follows, which uses only one quantum query.
  
  		One can see that the probability of output 1 is ⟨ x_D|P| x_D ⟩ = f(x), and the probability of output 0 is 1-⟨ x_D|P|x_D⟩ = 1-f(x). Thus, the algorithm always outputs correct results.
  		
  
  
  
  
  
  
  
  
  
  
  
  
  In summary, statements (a)-(d) are equivalent to each other, which may offer a deeper insight into the problem of what Boolean functions can be computed by an exact one-query quantum algorithm. By Theorem <ref>, one-query function f satisfies f(x) =  ∑_i ⟨ v_i|x_D ⟩^2. 
  Since ⟨ v_i|x_D ⟩ = ⟨ v_i|√(D)|x' ⟩ and x_i' = (-1)^x_i = 2x_i-1, the degree of ⟨ v_i|x_D ⟩ is 1. Thus, the expression of f in statement (d) satisfies that deg(f) ≤ 2, which meets the conclusion from the polynomial method <cit.>. 
  
  
  
  
  
  
  
  
  
  
  § NEW REPRESENTATIVE FUNCTIONS WITH ONE QUANTUM QUERY
   
  
  
  
  
  
  
  
  
  	
  In the following, we call a function that can be computed by an exact one-query quantum algorithm as a one-query function for the sake of simplicity. Here we find some new one-query functions by Theorem <ref>. 
  These examples help us understand the power of exact one-query algorithm better. 
  To begin with, we list all known one-query functions (up to isomorphism) <cit.>, which can be computed by  Deusch-Josza algorithm: 
  
  i) Deusch-Josza function f_1:{0,1}^n →{0,1}: 
  
      f_1(x)=
      
      0,     |x|=n/2
      
      1,     |x| = 0  or  n
      .
  
  
  ii) Symmetric  function f_2:{0,1}^n →{0,1}: 
  
      f_2(x)=
      
      0,     |x|=c  (c ≥⌈ n/2 ⌉)
      
      1,     |x| = 0
      .
  
  
  Next, we construct some new functions inspired by Theorem <ref> as follows. It is easy to check these functions satisfy the statement (b) (see Table <ref>).
  
  iii) For any set of non-negative coefficients {c_i} satisfying ∑_i=0^n c_i = 1, there exists a quasi-symmetric function f_3:{0,1}^n →{0,1}: 
  
      f_3(x)=
      
      0,   x̂=1/2
      
      1,   x̂=0  or  1
      ,
  
  where x̂ = ∑_i=0^n c_i x_i.
  
  iv) Function f_4: {0,1}^4 →{0,1}: 
  
      f_4(x)=
      
      0,     x=0000,0011,1100,1111
      
      1,      x=0101,0110,1001,1010
      .
  
  
  v) Function f_5:{0,1}^4n→{0,1} as Table <ref>. 
  
  
    
  
  
  
  
  
  As mentioned earlier, a one-query function f has the expression: f(x) =  ∑_i ⟨ v_i|√(D)|x' ⟩^2. If a vector set {w_i} satisfies |v_i⟩ = √(D)|w_i⟩, then f(x) =  ∑_i ⟨ w_i|D|x' ⟩^2. Since D_ii = c_i for any i, we give the corresponding {c_i} and {w_i} for above functions as Table <ref>. For any above function and i, w_i is an n-bit Boolean string. By {c_i} and {w_i}, we can obtain D  and P  easily, and then use Algorithm <ref> to compute these functions.   
  
  
  
  
   §.§ Characteristics of new functions
  
  Different from the already known one-query functions, the new cases are generally asymmetric functions. In this way, our results fill a gap in the discussion of exact one-query asymmetric functions. Next, we describe the characteristics of these functions respectively. 
  
  i) Actually, f_1 and f_2 are both  instances of f_3. If c_0 = 0 and c_1 = … =c_n, then f_3 degenerates into f_1; if  c_0 ≠ 0 and c_1 = … =c_n, then f_3 degenerates into  f_2. Otherwise, f_3 is asymmetric. In this way, f_3 is a generalization of f_1 and f_2. It not only can represent all symmetric one-query functions, but also represents a broad class of asymmetric one-query functions.
  
  ii) Unlike previous functions, f_4 is the first function have the following property: any function f isomorphic to f_4 does not satisfy that f^-1(1) ⊆{x:|x|=0 or n}. It is also worth mentioning that f_4 and f_1 have the same domain when n=4.
  
  iii) 
  f_5 is the first proper example represented as the sum of square form: ∑_i ⟨ w_i|D|x' ⟩^2, whereas all previous examples can be represented as single square expressions: ⟨ w_1|D|x' ⟩^2 (see Table <ref>). 
  As a result, f_5 is more general and representative than previous cases in all one-query functions.
   
  
  	
  
  § CONCLUSION
   
  	In this paper we have presented several  necessary and sufficient conditions for partial Boolean functions being computed by exact one-query quantum algorithms. By these conditions, we have obtained  some new function examples which are asymmetric and have essential difference from the already known symmetric one-query functions.
  We hope our results are helpful for further discussion	of the power of exact k-query quantum algorithms. Figuring out this problem is useful for  understanding in depth quantum query algorithms and inspiring us to find more problems with quantum advantages.
  	
  	 
  
  	
  	unsrt
  	
  	30
  	
          
         
  		
  		Buhrman2002Complexity
  		H. Buhrman and R. de Wolf,  Theor. Comput. Sci. 288, 21 (2002).
  		 Chen2020Char
          W. Chen, Z. Ye and L. Li, Rhys. Rev. A 101, 02232 (2020).
  		Ambainis2013Superlinear
  		A. Ambainis, In Proceedings of the
  			forty-fifth annual ACM symposium on Theory of Computing (ACM, Palo Alto, USA, 2013), pp. 891-900.
  		
  		Ambainis2015Exact
  		A. Ambainis, J. Gruska and S. Zheng, Quantum Inf. Comput. 15, 435 (2015).
  		
  		Deutsch1992Rapid
  		D. Deutsch and R. Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992).
  		
  		Midrijanis2004Exact
  		G. Midrijanis, arXiv:quant-ph/0403168 (2004).
  		
  		Mihara2003Deterministic
  		T. Mihara and S. Sung, Comput. Complex. 12, 162 (2003).
  		
  		He2018Exact
  		X. He, X. Sun, G. Yang, and P. Yuan, arXiv:1801.05717 (2018).
  		
  		Montanaro2015On
  		A. Montanaro, R. Jozsa, and G. Mitchison, Algorithmica 71, 775 (2015).
  		
  		Ambainis2013Exact
  		A. Ambainis, J. Iraids and J. Smotrovs, In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (Guelph, Ontario, Canada, 2013), pp. 263-269.
  		
  		Ambainis2017Exact
  		A. Ambainis, J. Iraids and D. Nagaj, In  43rd International Conference on Current Trends in Theory and Practice of Computer Science (2017), pp. 243-255.
  	
  
  		
  		Cai2018Optimal
  		G. Cai and D. Qiu, J. Comput. Syst. Sci. 97, 83 (2018).
  		
  		Ambainis2016Superlinear
  		A. Ambainis, SIAM J. Comput. 45, 617 (2016).
  		
  		Cleve1998Quantum
  		R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, Proc. R. Soc. Lond. A  454, 339 (1998).
  		
  		Vasilieva2006Computing
  		A. Vasilieva and T. Mischenko-Slatenkova, arXiv:quant-ph/0607022 (2006).
  		
  		Aaronson2016separations
  		S. Aaronson, S. Ben-David and R. Kothari, In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (ACM, Cambridge, USA, 2016), pp. 863-876.
  		
  		Ambainis2017separations
  		A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha and J. Smotrovs, J. ACM 64, 1 (2017).
  		
  		Farhi1998alimit
  		E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Phys. Rev. Lett. 81, 5442 (1998).
  		
  		Hayes2002quantum
  		T. Hayes, S. Kutin and D. van Melkebeek, Algorithmica 34, 480 (2002).
  		
  		Mischenko2015quantum
  		T. Mischenko-Slatenkova, A. Vasilieva, I. Kucevalovs and R. Freivalds, In Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015 (Springer, Waterloo, Canada, 2015), pp. 177-184.
  		
  		
  		Braunstein2007exact
  		S. L. Braunstein, B. Choi, S. Ghosh, and S. Maitra, J. Phys. A 40, 8441 (2007).
  		
  		brassard1997exact
  		G. Brassard and P. Høyer, In Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997 (IEEE, Ramat-Gan, Israel, 1997), pp. 12-23.
  		
  		Qiu2018Generalized
  		D. Qiu and S. Zheng, Phys. Rev. A 97, 062331 (2018).
  		
  		Qiu2020Revisiting
  		D. Qiu and S. Zheng, Inf. Comput. 275, 104605 (2020). Also arXiv:1603.06505.
  		
  		beals2001quantum
  		R. Beals, H. Buhrman, R. Cleve,  M. Mosca and R. de Wolf, J. ACM 48, 778 (2001).
  		
  			
  		Simon1997On
  		D. R. Simon, SIAM J. Comput. 26, 1474 (1997).  
  		
  		Shor1994Discrete
  		P. W. Shor, In Proceedings of the 35th annual symposium on foundations of computer science (IEEE, Santa Fe, USA, 1994), pp. 124-134.
  	
  		
  		Childs2020Can
  	       A. M. Childs and D. Wang, arXiv:2001.10520 (2020).
  	       
  	   Aaronson2018Forrelation
  	       S. Aaronson and A. Ambainis, SIAM J. Comput. 47, 982 (2018).
  	       
  	   Tal2020Towards
  	       A. Tal, In Proceedings of the 61st annual symposium on foundations of computer science (2020). Also arXiv:1912.12561.
  		
         Sherstov2020An
          A. A. Sherstov, A. A. Storozhenko and P. Wu, arXiv:2008.10223 (2020).
  
  		
  		Aaronson2016Polynomials
  		S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis and J. Smotrovs, In Conference on Computational Complexity (LIPIcs, Tokyo, Japan, 2016), pp. 25:1-25:19. 
  		
  		Arunachalam2019Quantum
  		S. Arunachalam, J. Briet and C. Palazuelos, SIAM J. Comput. 48, 903 (2019).
  
          Xu2020Partial
  		G. Xu and D. Qiu, arXiv:2007.10924 (2020).
  		
  		Nielsen2002Quantum
  		M. A. Nielsen and I. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2002).
  		
  		
  		
  		
  		
  		
  
  	
  	
  