Article ID Journal Published Year Pages File Type
6874651 Journal of Computer and System Sciences 2018 11 Pages PDF
Abstract
Simon's problem is one of the most important problems demonstrating the power of quantum computers. In this paper, we propose another exact quantum algorithm for solving Simon's problem with O(n) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simon's algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simon's problem can be solved by a classical deterministic algorithm with O(2n) queries (as we are aware, there were no classical deterministic algorithms for solving Simon's problem with O(2n) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simon's problem: Θ(n) versus Θ(2n).
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,