Query complexity of generalized Simon's problem

DOI10.1016/j.ic.2021.104790OpenAlexW3197138950MaRDI QIDQ2051810

Yunqi Huang, Zekun Ye, Yuyi Wang, Lvzhou Li

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

group theoryquantum computingquery complexitySimon's problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Sample complexity of hidden subgroup problem ⋮ Deterministic algorithms for the hidden subgroup problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on quantum related-key attacks
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• 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 hidden subgroup problem is polynomial
• Superlinear Advantage for Exact Quantum Algorithms
• Breaking Symmetric Cryptosystems Using Quantum Period Finding
• Quantum Property Testing
• Rapid solution of problems by quantum computation
• Quantum algorithms and the Fourier transform
• Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
• Separations in Query Complexity Based on Pointer Functions
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Separations in query complexity using cheat sheets
• Quantum lower bounds by polynomials
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Automata, Languages and Programming
• Quantum computing

This page was built for publication: Query complexity of generalized Simon's problem