Search

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 ( 2 n ) queries (as we are aware, there were no classical deterministic algorithms for solving Simon's problem with O ( 2 n ) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simon's problem: Θ ( n ) versus Θ ( 2 n ) . [ABSTRACT FROM AUTHOR]

Abstract: Simon, in his FOCS’94 paper, was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon’s problem from the point of view of quantum query complexity and give here a first non-trivial lower bound on the query complexity of a hidden subgroup problem, namely Simon’s problem. More generally, we give a lower bound which is optimal up to a constant factor for any abelian group. [Copyright &y& Elsevier]

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP (p , n , k) , is a natural extension of Simon's problem: Given a function f : Z p n → X where X is a finite set and the promise that for any x , y ∈ Z p n , f (x) = f (y) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k < n , the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O (n − k). However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , p n − k }) values and any classical nonadaptive deterministic algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , k ⋅ p n − k }) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O (max ⁡ { k , k ⋅ p n − k }) on the classical deterministic query complexity of GSP (p , n , k) , by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem. [ABSTRACT FROM AUTHOR]