A note on the quantum query complexity of permutation symmetric functions

DOI10.4230/LIPICS.ITCS.2019.19MaRDI QIDQ5090392zbMATH OpenFDO

Authors André Chailloux

Publication date 18 July 2022

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

zbMATH Keywords

quantum query complexitypermutation symmetric functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Quantum Queries on Permutations with a Promise
• Quantum queries on permutations
• Quantum query complexity of almost all functions with fixed on-set size
• The structure of promises in quantum speedups
• On exact quantum query complexity

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Quantum lower bound for the collision problem with small range
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems
• Rapid solution of problems by quantum computation
• Strengths and Weaknesses of Quantum Computing
• The need for structure in quantum speedups

Cited in

(4)

• On the fine-grained query complexity of symmetric functions
• On the fine-grained query complexity of symmetric functions
• Symmetries, graph properties, and quantum speedups
• Quantum and classical communication complexity of permutation-invariant functions

This page was built for publication: A note on the quantum query complexity of permutation symmetric functions

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