Characterization of exact two-query quantum algorithms

Quantum query model is a crucial model for quantum computing, where one query to some input variable of a Boolean function f defined on { 0, 1 } n returns the variable value. The exact query complexity, denoted as Q E ( f ), is defined to be the minimum number of queries required to determine the function value. An important problem in this area is to give a succinct characterization of a k-query exact quantum algorithm for an arbitrary k. To date, the cases k = 1 and k = n are already solved and the case k = 2 remains unknown. Our result is that there are 27 nondegenerate Boolean functions up to isomorphism with Q E ( f ) being two, among which only two functions can be solved by a 2-query classical algorithm. The input bit number n of the above 27 functions ranges from 2 to 6, where the case n ≤ 3 is already proved and the case n = 4 is already found by numerically solving semidefinite programming, which is a complete characterization of quantum query algorithm. Assuming the correctness of the numerical result for n = 4, we prove that there are four functions in the case n = 5, one in the case n = 6 and none in the case n ≥ 7. We further show that the 25 functions for which quantum algorithm has advantage over classical algorithm contain essentially only four different structures.

Authors

• Shaoliang Ye
• Wei Yang
• Liusheng Huang

Keywords

• Exact query algorithm
• Quantum query complexity
• Boolean function