A note on quantum black-box complexity of almost all Boolean functions

DOI10.1016/S0020-0190(99)00079-4zbMath0999.68065OpenAlexW2004840485MaRDI QIDQ1606953

Andris Ambainis

Publication date: 25 July 2002

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00079-4

zbMATH Keywords

Boolean functions

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Quantum query complexity of almost all functions with fixed on-set size ⋮ Unbounded-error quantum query complexity ⋮ Extremal properties of polynomial threshold functions ⋮ Quantum certificate complexity ⋮ Unnamed Item ⋮ Complexity measures and decision tree complexity: a survey.

This page was built for publication: A note on quantum black-box complexity of almost all Boolean functions