Explicit relation between all lower bound techniques for quantum query complexity

DOI10.4230/LIPICS.STACS.2013.434MaRDI QIDQ2957904zbMATH OpenFDO

Authors Loïck Magnin, Jérémie Roland

Publication date 30 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2013.434

zbMATH Keywords

adversary methodlower boundpolynomial methodquantum computation

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• Explicit relation between all lower bound techniques for quantum query complexity
• Quantum lower bounds by quantum arguments
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Quantum lower bounds by quantum arguments
• A new quantum lower bound method, with an application to a strong direct product theorem for quantum search

Cited in

(5)

• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• Explicit relation between all lower bound techniques for quantum query complexity
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• A direct reduction from the polynomial to the adversary method
• Quantum lower bounds by sample-to-query lifting

This page was built for publication: Explicit relation between all lower bound techniques for quantum query complexity

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