scientific article; zbMATH DE number 7651029

DOI10.4230/LIPICS.TQC.2020.2MaRDI QIDQ5874384zbMATH OpenFDO

Authors Nikhil S. Mande, Justin Thaler, Shuchen Zhu

Publication date 7 February 2023

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

zbMATH Keywords

\(k\)-distinctnessapproximate degreedual polynomialsquantum query complexity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Recommendations

• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Algorithmic polynomials
• Algorithmic Polynomials
• Quantum adversary lower bound for element distinctness with small range

Cited in

(11)

• Improved lower bounds on k‐independence
• Improving upper bounds for the distinguishing index
• Approximate Degree in Classical and Quantum Computing
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Multidimensional quantum walks
• A direct reduction from the polynomial to the adversary method
• An exponential separation between quantum query complexity and the polynomial degree
• The approximate degree of DNF and CNF formulas
• Multidimensional quantum walks, with application to k-distinctness
• Quantum property testing in sparse directed graphs

This page was built for publication:

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