On Deciding Whether a Boolean Function is Constant or Not

DOI10.1142/S0219749903000115MaRDI QIDQ4819267zbMATH OpenFDO

Authors Luca Marinatto, F. Benatti

Publication date 24 September 2004

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0304073

zbMATH Keywords

Boolean functionsOraclesDeutsch-Josza algorithm

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: We study the probability of making an error if, by querying an oracle a fixed number of times, we declare constant a randomly chosen n-bit Boolean function. We compare the classical and the quantum case, and we determine for how many oracle-queries k and for how many bits n one querying procedure is more efficient than the other.

Recommendations

• Publication:3474690
• scientific article; zbMATH DE number 4012691
• scientific article; zbMATH DE number 1051018
• scientific article; zbMATH DE number 2154574
• On the non-linearity of Boolean functions
• Sur la non-linéarité des fonctions booléennes
• On complexity of a particular Boolean functions class
• scientific article; zbMATH DE number 2127869
• On the independence of Boolean functions

Cites work

• Rapid solution of problems by quantum computation

Cited in

(1)

• Recognizing the presence of a growing unessential argument of Boolean functions

This page was built for publication: On Deciding Whether a Boolean Function is Constant or Not

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4819267)