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.
Articles by others on the same topic
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.