Exact quantum algorithms have advantage for almost all Boolean functions

Abstract

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.

arXiv comment17 pages. Accepted to Quantum information & Computation

References in corpus (9)

• Quantum Algorithms Revisited
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• A Limit on the Speed of Quantum Computation in Determining Parity
• Superiority of exact quantum automata for promise problems
• On the state complexity of semi-quantum finite automata
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Exact quantum query complexity of EXACT and THRESHOLD
• Potential of quantum finite automata with exact acceptance
• From Quantum Query Complexity to State Complexity

Cited by in corpus (2)

• Potential of quantum finite automata with exact acceptance
• Quantum Query as a State Decomposition