Quantum lower bounds for the Goldreich-Levin problem

DOI10.1016/j.ipl.2005.01.016zbMath1184.68261OpenAlexW2095275555MaRDI QIDQ1045938

Shigeru Yamashita, Richard Cleve, Kazuo Iwama, Raymond H. Putra, Mark R. A. Adcock

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

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

Related Items (2)

Quantum algorithms for the Goldreich-Levin learning problem ⋮ Quantum learning of concentrated Boolean functions

Cites Work

• One way functions and pseudorandom generators
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing
• Unnamed Item
• Unnamed Item
• Unnamed Item

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