Quantum and classical query complexities for generalized Simon's problem

Simon's problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simon's problem has been proved by Cai & Qiu. Generalized Simon's problem can be described as follows. Given a function f: { 0, 1 } n → { 0, 1 } m, with the property that there is some unknown hidden subgroup S such that f ( x ) = f ( y ) iff x ⊕ y ∈ S, for any x, y ∈ { 0, 1 } n, where | S | = 2 k for some 0 ≤ k ≤ n ( m ≥ n − k ). The goal of generalized Simon's problem is to find S. For the case of k = 1, it is Simon's problem exactly. In this paper, we propose an exact quantum algorithm with O ( n − k ) queries and an non-adaptive deterministic classical algorithm with O ( k 2 n − k ) queries for solving the generalized Simon's problem. Also, we prove that their lower bounds are Ω ( n − k ) and Ω ( k 2 n − k ), respectively. Therefore, we obtain a tight exact quantum query complexity Θ ( n − k ) and an almost tight non-adaptive classical deterministic query complexities Ω ( k 2 n − k ) ∼ O ( k 2 n − k ) for this problem.

Authors

• Zhenggang Wu
• Daowen Qiu
• Jiawei Tan Key Laboratory of Dependable Service Computing in Cyber Physical Society (Chongqing University), Ministry of Education, China School of Big Data and Software Engineering, Chongqing University, China
• Hao Li Shanghai Artificial Intelligence Laboratory & Northwestern Polytechnical University
• Guangya Cai

Keywords

• Quantum computing
• Exact query complexity
• Generalized Simon's problem
• Dimensional reduction