Exact quantum algorithms have advantage for almost all Boolean functions

AMBAINIS, Andris, Jozef GRUSKA and Shenggen ZHENG. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Information & Computation. 2015, vol. 15, 5-6, p. 435-452. ISSN 1533-7146.

Basic information

• Original name: Exact quantum algorithms have advantage for almost all Boolean functions
• Authors: AMBAINIS, Andris (428 Latvia), Jozef GRUSKA (703 Slovakia, belonging to the institution) and Shenggen ZHENG (156 China, guarantor, belonging to the institution).
• Edition: Quantum Information & Computation, 2015, 1533-7146.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 1.328
• RIV identification code: RIV/00216224:14330/15:00084458
• Organization unit: Faculty of Informatics
• UT WoS: 000358188600005
• Keywords in English: Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n
• Tags: International impact, Reviewed

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 ANDn is the only n-bit Boolean function, up to isomorphism, that requires n queries.

Links

• EE2.3.30.0009, research and development project: Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci