Exact quantum algorithms have advantage for almost all Boolean functions

Autor:	Ambainis, Andris, Gruska, Jozef, Zheng, Shenggen
Rok vydání:	2014
Předmět:	Computer Science - Computational Complexity Quantum Physics 81P68 03D15
Druh dokumentu:	Working Paper
Popis:	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. Comment: 17 pages. Accepted to Quantum information & Computation
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1404.1684 Zobrazit plný text záznamu View this record from Arxiv