Research team designed an optimal quantum algorithm for the MOD function and characterized its exact quantum query complexity, proving a conjecture. They also proposed a quantum algorithm for the EXACT function, characterizing its complexity.

It has demonstrated the powerful ability of a quantum computer to perform certain computational tasks more efficiently than a classical computer. Thus, to show quantum advantages is a key problem in the field of quantum computation. The query complexity model is a computational model that describes the power and limitations of algorithms in solving problems in a query-based setting. As a result, the query complexity model is a helpful tool to compare the ability of quantum and classical computation. Furthermore, quantum advantages can be shown by comparing exact quantum query complexity and deterministic query complexity for solving certain problems without any error.

Symmetric functions are functions that are invariant under permutations of their inputs, which have a wide range of applications in various fields of computer science, such as coding theory and cryptography. Currently, there are only several symmetric functions whose exact quantum query complexities are fully characterized. Therefore, there are still many problems worth exploring in this field. For instance, some symmetric functions have been widely studied, but the exact quantum query complexity is not fully characterized, including MOD and EXACT functions.

To address this challenge, a research team led by Penghui YAO published their new research in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team designs an optimal quantum query algorithm to compute MOD function exactly and thus provides a tight characterization of its exact quantum query complexity, which settles a previous conjecture. Based on this algorithm, it is shown that a broad class of symmetric functions is not evasive in the quantum model, i.e., there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size. Moreover, the team proposes a quantum algorithm that utilizes the minimum number of queries to compute EXACT function and thus characterizes its exact quantum query complexity in some specific scenarios.

For the future direction, an interesting challenge is to give a full characterization of the exact quantum query complexity of more symmetric functions.

DOI: 10.1007/s11704-024-3770-4