Optimal Separation in Exact Query Complexities for Simon's Problem

Guangya Cai, Daowen Qiu

Simon's problem is one of the most important problems demonstrating the power of quantum computers, which achieves a large separation between quantum and classical query complexiti…