Quantum and classical query complexities for generalized Simon's problem

DOI10.1016/j.tcs.2022.05.025OpenAlexW2945149578MaRDI QIDQ2672650

Jiawei Tan, Guangya Cai, Zhenggang Wu, Hao Li, Dao Wen Qiu

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dimensional reductionquantum computingexact query complexitygeneralized Simon's problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Zero sum subsequences and hidden subgroups ⋮ Deterministic algorithms for the hidden subgroup problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal separation in exact query complexities for Simon's problem
• Deterministic polynomial-time quantum algorithms for Simon's problem
• Complexity measures and decision tree complexity: a survey.
• The quantum query complexity of the abelian hidden subgroup problem
• Quantum algorithms for Simon's problem over nonabelian groups
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Quantum lower bounds by polynomials
• Automata, Languages and Programming

This page was built for publication: Quantum and classical query complexities for generalized Simon's problem