Quantum Query Complexity of Boolean Functions with Small On-Sets

DOI10.1007/978-3-540-92182-0_79MaRDI QIDQ3597889zbMATHOpenAlexDBLPWikidataFDO

Authors Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, S. Yamasita, Andris Ambainis, Kazuo Iwama

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_79

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Recommendations

• Quantum query complexity of almost all functions with fixed on-set size
• SOFSEM 2005: Theory and Practice of Computer Science
• Optimal quantum query bounds for almost all Boolean functions
• A lower bound on the quantum query complexity of read-once functions
• How low can approximate degree and quantum query complexity be for total Boolean functions?

Cited in

(10)

• The quantum query complexity of \(\mathrm{AC}^0\)
• Symmetries, graph properties, and quantum speedups
• Query complexity of matroids
• SOFSEM 2005: Theory and Practice of Computer Science
• Quantum query complexity of almost all functions with fixed on-set size
• Optimal quantum query bounds for almost all Boolean functions
• Average-case quantum query complexity
• A lower bound on the quantum query complexity of read-once functions
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)

This page was built for publication: Quantum Query Complexity of Boolean Functions with Small On-Sets

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