Evaluation of exact quantum query complexities by semidefinite programming

Abstract

One of the difficult tasks in quantum computation is inventing efficient exact quantum algorithms, which are the quantum algorithms that output the correct answer with certainty on any input. We improve and generalize the semidefinite programming (SDP) method of Montanaro et al. (Algorithmica 71:775-796, 2015) in order to evaluate exact quantum query complexities of partial functions. We present a more systematical approach to achieve the inspired result by Montanaro et al. for the function EXACT24, which is the Boolean function of 4 bits that output only when 2 of the input bits are equal to 1. The same approach also allows us to reduce the size of the ancilla space used by the algorithms that evaluate symmetric functions like EXACT36. We employ the generalized SDP to verify the complexities of the earliest and best known quantum algorithms in the literature, namely, Deutsch-Jozsa and Grover algorithms for a small number of input bits. We utilized the method to solve the weight decision problem of bit strings with lengths up to 10 bits and observed that the generalized SDP gives better exact quantum query complexities than the known methods. Finally, we test the method on some selected functions and demonstrate that they all exhibit quantum speedup.