Quantum Query Complexity of Boolean Functions with Small On-Sets

DOI10.1007/978-3-540-92182-0_79zbMATH Open1183.68291DBLPconf/isaac/AmbainisINNRTY08OpenAlexW1550265671WikidataQ56701651 ScholiaQ56701651MaRDI QIDQ3597889FDOQ3597889

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

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?

Mathematics Subject Classification ID

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

Cited In (8)

• Title not available (Why is that?)
• Query complexity of matroids
• A lower bound on the quantum query complexity of read-once functions
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• The quantum query complexity of \(\mathrm{AC}^0\)
• Symmetries, graph properties, and quantum speedups
• Average-case quantum query complexity
• 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)