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

DOI10.1007/S00037-016-0139-6zbMATH Open1353.68094arXiv0908.2468OpenAlexW2467963819MaRDI QIDQ347109FDOQ347109

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)

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).

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

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

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)

Cites Work

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

Cited In (7)

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

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)