Query complexity of generalized Simon's problem

DOI10.1016/J.IC.2021.104790MaRDI QIDQ2051810zbMATH OpenOpenAlexFDO

Authors Zekun Ye, Yunqi Huang, Lvzhou Li, Yuyi Wang

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)

Recommendations

• Optimal separation in exact query complexities for Simon's problem
• Automata, Languages and Programming
• The quantum query complexity of the abelian hidden subgroup problem
• Tight bounds for Simon's algorithm
• Deterministic polynomial-time quantum algorithms for Simon's problem

Cites work

• A note on quantum related-key attacks
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Automata, Languages and Programming
• Breaking symmetric cryptosystems using quantum period finding
• 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
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 5076264 (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?)
• Optimal separation in exact query complexities for Simon's problem
• Quantum algorithm for a generalized hidden shift problem
• Quantum algorithms and the Fourier transform
• Quantum algorithms for Simon's problem over general groups
• Quantum computing
• Quantum lower bounds by polynomials
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Quantum Property Testing
• Rapid solution of problems by quantum computation
• Separations in query complexity using cheat sheets
• Superlinear advantage for exact quantum algorithms
• The hidden subgroup problem and permutation group theory
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The quantum query complexity of the hidden subgroup problem is polynomial

Cited in

(9)

• Optimal separation in exact query complexities for Simon's problem
• Deterministic algorithms for the hidden subgroup problem
• Tight bounds for Simon's algorithm
• Sample complexity of hidden subgroup problem
• Quantum and classical query complexities for generalized Simon's problem
• Automata, Languages and Programming
• Exact distributed quantum algorithm for generalized Simon's problem
• Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
• Derandomization of quantum algorithm for triangle finding

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

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