6533b86dfe1ef96bd12c94fd

RESEARCH PRODUCT

Exact quantum algorithms have advantage for almost all Boolean functions

Jozef GruskaAndris AmbainisShenggen Zheng

subject

FOS: Computer and information sciencesNuclear and High Energy Physics81P68 03D15Parity functionBoolean circuitGeneral Physics and AstronomyFOS: Physical sciencesBoolean algebras canonically definedComputational Complexity (cs.CC)Theoretical Computer ScienceCombinatoricsBoolean expressionBoolean functionMathematical PhysicsComputer Science::DatabasesMathematicsDiscrete mathematicsSymmetric Boolean functionQuantum PhysicsProduct termComputer Science::Information RetrievalStatistical and Nonlinear PhysicsComputer Science - Computational ComplexityComputational Theory and MathematicsMaximum satisfiability problemQuantum Physics (quant-ph)

description

It has been proved that almost all $n$-bit Boolean functions have exact classical query complexity $n$. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all $n$-bit Boolean functions can be computed by an exact quantum algorithm with less than $n$ queries. More exactly, we prove that ${AND}_n$ is the only $n$-bit Boolean function, up to isomorphism, that requires $n$ queries.

yearjournalcountryeditionlanguage
2014-04-07
https://dx.doi.org/10.48550/arxiv.1404.1684