A balanced Boolean function is one that has an equal number of output values of 0 and 1 for all possible combinations of its input variables. In other words, for a Boolean function with \( n \) input variables, there are \( 2^n \) possible input combinations. A balanced Boolean function will produce a 1 for exactly half of these combinations and a 0 for the other half.
Articles by others on the same topic
A Boolean function on a finite nonempty domain is balanced when it is zero on exactly half the inputs and one on the other half. For a one-bit domain, the balanced functions are and , while the remaining two functions are constant functions. The Deutsch algorithm distinguishes these two classes with one Boolean quantum oracle query in the absence of noise.