Revisiting Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm is essentially faster than any possible deterministic classical algorithm for solving a promise problem that is in fact a symmetric partial Boolean function, named as the Deutsch-Jozsa problem. The Deutsch-Jozsa problem can be equivalently described as a partial function D J n 0: { 0, 1 } n → { 0, 1 } defined as: D J n 0 ( x ) = 1 for | x | = n / 2, D J n 0 ( x ) = 0 for | x | = 0, n, and it is undefined for the remaining cases, where n is even, and | x | is the Hamming weight of x. The Deutsch-Jozsa algorithm needs only one query to compute D J n 0 but the classical deterministic algorithm requires n 2 + 1 queries to compute it in the worse case. We present all symmetric partial Boolean functions with degree 1 and 2; We prove the exact quantum query complexity of all symmetric partial Boolean functions with degree 1 and 2. We prove Deutsch-Jozsa algorithm can compute any symmetric partial Boolean function f with exact quantum 1-query complexity.

Authors

• Daowen Qiu
• Shenggen Zheng

Keywords

• Exact quantum query algorithms
• Deutsch-Jozsa problems
• Query complexity
• Symmetric Boolean functions
• Promise problems