Quantum query complexity of almost all functions with fixed on-set size

DOI10.1007/S00037-016-0139-6MaRDI QIDQ347109zbMATHOpenAlexFDO

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

Publication date 30 November 2016

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.2468

zbMATH Keywords

Boolean functionson-set sizequantum query complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).

Recommendations

• Quantum Query Complexity of Boolean Functions with Small On-Sets
• Optimal quantum query bounds for almost all Boolean functions
• SOFSEM 2005: Theory and Practice of Computer Science
• The quantum query complexity of \(\mathrm{AC}^0\)
• A lower bound on the quantum query complexity of read-once functions

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• A note on quantum black-box complexity of almost all Boolean functions
• An optimal quantum algorithm for the oracle identification problem
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• CREW PRAM<scp>s</scp> and Decision Trees
• Classification by polynomial surfaces
• Complexity measures and decision tree complexity: a survey.
• How Many Copies are Needed for State Discrimination?
• Improved algorithms for quantum identification of Boolean oracles
• Information theory and the complexity of boolean functions
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• Optimal quantum query bounds for almost all Boolean functions
• Quantum lower bounds by polynomials
• Quantum query complexity of almost all functions with fixed on-set size
• STACS 2004
• Unbounded-Error Quantum Query Complexity

Cited in

(7)

• The quantum query complexity of \(\mathrm{AC}^0\)
• Query complexity of Boolean functions on the middle slice of the cube
• Learning bounds for quantum circuits in the agnostic setting
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• Quantum query complexity of almost all functions with fixed on-set size
• Optimal quantum query bounds for almost all Boolean functions
• The quantum setting with randomized queries for continuous problems

This page was built for publication: Quantum query complexity of almost all functions with fixed on-set size

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