Quantum Query Complexity of Boolean Functions with Small On-Sets

DOI10.1007/978-3-540-92182-0_79MaRDI QIDQ3597889zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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

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)