Quantum lower bounds for the Goldreich-Levin problem

DOI10.1016/J.IPL.2005.01.016MaRDI QIDQ1045938zbMATH OpenOpenAlexFDO

Authors Richard Cleve, Kazuo Iwama, S. Yamasita, Mark R. A. Adcock, Raymond H. Putra

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.01.016

zbMATH Keywords

computational complexitycryptographyquantum computing

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Quantum algorithms for the Goldreich-Levin learning problem
• scientific article; zbMATH DE number 2086396
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2086396 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Modern cryptography, probabilistic proofs and pseudo-randomness
• One way functions and pseudorandom generators
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing

Cited in

(6)

• Quantum learning of concentrated Boolean functions
• Quantum and classical tradeoffs
• Quantum algorithms for the Goldreich-Levin learning problem
• Query complexity of quantum biased oracles
• scientific article; zbMATH DE number 2086396 (Why is no real title available?)
• Quantum lower bounds by quantum arguments

This page was built for publication: Quantum lower bounds for the Goldreich-Levin problem

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