Optimal separation in exact query complexities for Simon's problem

DOI10.1016/j.jcss.2018.05.001zbMath1398.68173arXiv1610.01920OpenAlexW2964102687MaRDI QIDQ1672002

Guangya Cai, Dao Wen 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 computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (9)

Sample complexity of hidden subgroup problem ⋮ Quantum and classical query complexities for generalized Simon's problem ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ An exact quantum algorithm for a restricted subtraction game ⋮ Zero sum subsequences and hidden subgroups ⋮ Distributed Grover's algorithm ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Query complexity of generalized Simon's problem ⋮ Deterministic algorithms for the hidden subgroup problem

Cites Work

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

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