Optimal separation in exact query complexities for Simon's problem

DOI10.1016/J.JCSS.2018.05.001MaRDI QIDQ1672002zbMATH OpenOpenAlexFDO

Authors Guangya Cai, Daowen Qiu

Publication date 7 September 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01920

zbMATH Keywords

quantum computingexact query complexitySimon's problem

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: 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 complexities. However, Simon's discussion on his problem was limited to bounded-error setting, which means his algorithm can not always get the correct answer. Exact quantum algorithms for Simon's problem have also been proposed, which deterministically solve the problem with O(n) queries. Also the quantum lower bound Omega(n) for Simon's problem is known. Although these algorithms are either complicated or specialized, their results give an O(n) versus Omega(sqrt{2^{n}}) separation in exact query complexities for Simon's problem (Omega(sqrt{2^{n}}) is the lower bound for classical probabilistic algorithms), but it has not been proved whether this separation is optimal. 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(sqrt{2^{n}}) queries (as we are aware, there were no classical deterministic algorithms for solving Simon's problem with O(sqrt{2^{n}}) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simon's problem: Theta({n}) versus Theta({sqrt{2^{n}}}).

Recommendations

• Query complexity of generalized Simon's problem
• Optimal separation and strong direct sum for randomized query complexity
• Tight bounds for Simon's algorithm
• Separation between deterministic and randomized query complexity
• Nearly optimal separations between communication (or query) complexity and partitions
• An Optimal Separation of Randomized and Quantum Query Complexity
• An optimal separation of randomized and Quantum query complexity
• A quasipolynomial-time algorithm for the quantum separability problem
• Towards better separation between deterministic and randomized query complexity
• Revisiting separation: algorithms and complexity

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Complexity measures and decision tree complexity: a survey.
• Deterministic polynomial-time quantum algorithms for Simon's problem
• Forrelation: a problem that optimally separates quantum from classical computing
• On exact quantum query complexity
• On the Power of Quantum Computation
• Quantum lower bounds by polynomials
• Rapid solution of problems by quantum computation
• Superlinear advantage for exact quantum algorithms
• The quantum query complexity of the abelian hidden subgroup problem

Cited in

(13)

• Revisiting Deutsch-Jozsa algorithm
• Deterministic algorithms for the hidden subgroup problem
• Sample complexity of hidden subgroup problem
• Complete analysis of Simon's quantum algorithm with additional collisions
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems
• Zero sum subsequences and hidden subgroups
• Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
• Quantum and classical query complexities for generalized Simon's problem
• Distributed Grover's algorithm
• Automata, Languages and Programming
• Query complexity of generalized Simon's problem
• An exact quantum algorithm for a restricted subtraction game
• Exact distributed quantum algorithm for generalized Simon's problem

This page was built for publication: Optimal separation in exact query complexities for Simon's problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1672002)