Optimal separation in exact query complexities for Simon's problem

作者：

Highlights：

• We propose another exact quantum algorithm for solving Simon's problem with O(n) queries.

• We show that Simon's problem can be solved by a classical deterministic algorithm with O(2n) queries.

• We obtain the optimal separation in exact query complexities for Simon's problem: Θ(n) versus Θ(2n).

摘要

•We propose another exact quantum algorithm for solving Simon's problem with O(n) queries.•We show that Simon's problem can be solved by a classical deterministic algorithm with O(2n) queries.•We obtain the optimal separation in exact query complexities for Simon's problem: Θ(n) versus Θ(2n).

论文关键词：Simon's problem,Exact query complexity,Quantum computing

论文评审过程：Received 4 December 2016, Revised 14 March 2018, Accepted 4 May 2018, Available online 4 June 2018, Version of Record 13 August 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.05.001