Optimal separation in exact query complexities for Simon's problem

DOI10.1016/J.JCSS.2018.05.001zbMATH Open1398.68173arXiv1610.01920OpenAlexW2964102687MaRDI QIDQ1672002FDOQ1672002

Guangya Cai, Daowen Qiu

Publication date: 7 September 2018

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

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}}}).

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

Recommendations

• Query complexity of generalized Simon's problem
• scientific article; zbMATH DE number 7564429
• 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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Power of Quantum Computation
• Title not available (Why is that?)
• Rapid solution of problems by quantum computation
• Complexity measures and decision tree complexity: a survey.
• Title not available (Why is that?)
• Quantum lower bounds by polynomials
• On exact quantum query complexity
• Separations in Query Complexity Based on Pointer Functions
• The quantum query complexity of the abelian hidden subgroup problem
• Deterministic polynomial-time quantum algorithms for Simon's problem
• Forrelation
• Superlinear advantage for exact quantum algorithms

Cited In (12)

• 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
• Distributed Grover's algorithm
• Quantum and classical query complexities for generalized Simon's problem
• 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)