Exact quantum algorithms have advantage for almost all Boolean functions

• Autoři: AMBAINIS Andris; GRUSKA Jozef; ZHENG Shenggen
• Rok publikování: 2015
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Quantum Information & Computation
• Fakulta / Pracoviště MU: Fakulta informatiky
• www: http://www.rintonpress.com/journals/qiconline.html#v15n56
• Obor: Informatika
• Klíčová slova: Quantum computing; Quantum query complexity; Boolean function; Symmetric Boolean function; Monotone Boolean function; Read-once Boolean functio n
• 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 ANDn is the only n-bit Boolean function, up to isomorphism, that requires n queries.

Související projekty

• Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci