Constant and Balanced Functions

algorithmsReading-focused

11 min read

Constant and Balanced Functions

What "constant" and "balanced" really mean, how many balanced functions exist, and why a classical algorithm needs more than half the domain in the worst case.

Suggested before this lesson

Oracles and Black-Box Functions

The last lesson built oracles for specific functions. This one is about the two categories Deutsch-Jozsa's whole premise rests on, made precise, before you see the algorithm that tells them apart in a single query.

The Definitions

For $f:\{0,1\}^n \to \{0,1\}$ :

$f$ is constant if $f(x)$ is the same value for every input $x$ : either $f(x)=0$ always, or $f(x)=1$ always.
$f$ is balanced if $f(x)=0$ for exactly half of all $2^n$ inputs and $f(x)=1$ for the other half.

Notice these two categories don't cover every possible $f$ . Take $f(x_0,x_1) = x_0 \wedge x_1$ (AND): it outputs 1 only for input $11$ , one out of four inputs, 25%, neither all-same nor half-and-half. AND is neither constant nor balanced. Deutsch-Jozsa's algorithm only works because it's handed a promise that rules functions like this out ahead of time: "trust me, this $f$ is one or the other." Without that promise, a single query couldn't distinguish the cases; the promise is doing real work, not just narrating flavor text.

How Many of Each Are There?

Out of all $2^{2^n}$ possible boolean functions on $n$ bits (each of the $2^n$ inputs independently maps to 0 or 1), only 2 are constant (all-0 or all-1), no matter how large $n$ gets. Balanced functions are far more common: there are $\binom{2^n}{2^{n-1}}$ of them, choosing which half of the $2^n$ inputs get mapped to 1. For $n=2$ that's $\binom{4}{2}=6$ ; for $n=3$ it's already $\binom{8}{4}=70$ . Almost every function on more than a handful of bits is neither, but within the constant-or-balanced promise, balanced functions vastly outnumber constant ones.

The Classical Worst Case

Suppose you're checking $f$ by querying inputs one at a time and comparing outputs, with no quantum tricks. Query $2^{n-1}$ inputs and every single one comes back $0$ . Are you done? No: an adversary choosing $f$ 's truth table to make your life hard can still make the unqueried half all $1$ s, which is a perfectly valid balanced function consistent with everything you've seen so far, or leave them all $0$ too, giving a constant function equally consistent with what you've seen. Only the $\left(2^{n-1}+1\right)^{\text{th}}$ query breaks the tie: however it comes back, you can now rule one case out for certain. So the classical worst case is $2^{n-1}+1$ queries, more than half the entire domain, and there's no cleverer classical strategy that beats this bound: it's a hard information-theoretic floor, not a limitation of any one algorithm.

Deutsch-Jozsa (next lesson) answers this with one query, period, regardless of $n$ . That gap, $2^{n-1}+1$ vs. $1$ , only grows as $n$ grows, which is why this is presented as a "speedup" rather than just "a faster trick."

A Second Balanced Oracle

The last lesson's XOR oracle used both input qubits. Balanced functions don't have to use every input: $f(x_0,x_1,x_2) = x_0 \oplus x_2$ (ignoring $x_1$ entirely) is still balanced, exactly half of the 8 inputs give 0. The oracle just skips the CX for the input it doesn't depend on:

U_{f}

for

f (x_{0}, x_{1}, x_{2}) = x_{0} \oplus x_{2}

Set input qubits 0 and 2, then watch qubit 3 (the ancilla) in the Exact State table: it tracks

x_0 \oplus x_2

exactly, completely independent of whatever qubit 1 is set to.

Circuit

Step through the circuit: after gate 2 of 2

3 / 3

Exact State

Basis state	Re	Probability
$∣0000 ⟩$	1.000	100.0%
$∣0001 ⟩$	0	0.0%
$∣0010 ⟩$	0	0.0%
$∣0011 ⟩$	0	0.0%
$∣0100 ⟩$	0	0.0%
$∣0101 ⟩$	0	0.0%
$∣0110 ⟩$	0	0.0%
$∣0111 ⟩$	0	0.0%
$∣1000 ⟩$	0	0.0%
$∣1001 ⟩$	0	0.0%
$∣1010 ⟩$	0	0.0%
$∣1011 ⟩$	0	0.0%
$∣1100 ⟩$	0	0.0%
$∣1101 ⟩$	0	0.0%
$∣1110 ⟩$	0	0.0%
$∣1111 ⟩$	0	0.0%

Exercise

Build the oracle for

f(x_0, x_1, x_2) = x_0 \oplus x_2

on a 4-qubit circuit (qubits 0-2 are inputs, qubit 3 is the ancilla):

CX

from qubit 0 into qubit 3, then

CX

from qubit 2 into qubit 3. Qubit 1 isn't used by this

f

, so it gets no gate at all.

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

f(x_0, x_1) = x_0 \wedge x_1

(

f=1

only when both inputs are 1). Is this constant, balanced, or neither?

Constant

Balanced

Neither: only 1 of the 4 inputs (11) gives

f=1

, not exactly half.

Both constant and balanced.

Check your understanding

For

n = 4

input bits (16 possible inputs), what's the classical worst-case number of queries needed to determine constant-vs-balanced with certainty?

9, one more than half of the 16 inputs.

16, every input.

The Definitions

For

f:\{0,1\}^n \to \{0,1\}

f

is constant if

f(x)

is the same value for every input

x

: either

f(x)=0

always, or

f(x)=1

always.

f

is balanced if

f(x)=0

for exactly half of all

2^n

inputs and

f(x)=1

for the other half.

Notice these two categories don't cover every possible

f

. Take

f(x_0,x_1) = x_0 \wedge x_1

(AND): it outputs 1 only for input

11

, one out of four inputs, 25%, neither all-same nor half-and-half. AND is neither constant nor balanced. Deutsch-Jozsa's algorithm only works because it's handed a promise that rules functions like this out ahead of time: "trust me, this

f

is one or the other." Without that promise, a single query couldn't distinguish the cases; the promise is doing real work, not just narrating flavor text.

How Many of Each Are There?

Out of all

2^{2^n}

possible boolean functions on

n

bits (each of the

2^n

inputs independently maps to 0 or 1), only 2 are constant (all-0 or all-1), no matter how large

n

gets. Balanced functions are far more common: there are

\binom{2^n}{2^{n-1}}

of them, choosing which half of the

2^n

inputs get mapped to 1. For

n=2

that's

\binom{4}{2}=6

; for

n=3

it's already

\binom{8}{4}=70

. Almost every function on more than a handful of bits is neither, but within the constant-or-balanced promise, balanced functions vastly outnumber constant ones.

The Classical Worst Case

Suppose you're checking

f

by querying inputs one at a time and comparing outputs, with no quantum tricks. Query

2^{n-1}

inputs and every single one comes back

0

. Are you done? No: an adversary choosing

f

's truth table to make your life hard can still make the unqueried half all

1

s, which is a perfectly valid balanced function consistent with everything you've seen so far, or leave them all

0

too, giving a constant function equally consistent with what you've seen. Only the

\left(2^{n-1}+1\right)^{\text{th}}

query breaks the tie: however it comes back, you can now rule one case out for certain. So the classical worst case is

2^{n-1}+1

queries, more than half the entire domain, and there's no cleverer classical strategy that beats this bound: it's a hard information-theoretic floor, not a limitation of any one algorithm.

Deutsch-Jozsa (next lesson) answers this with one query, period, regardless of

n

. That gap,

2^{n-1}+1

vs.

1

, only grows as

n

grows, which is why this is presented as a "speedup" rather than just "a faster trick."

A Second Balanced Oracle

The last lesson's XOR oracle used both input qubits. Balanced functions don't have to use every input:

f(x_0,x_1,x_2) = x_0 \oplus x_2

(ignoring

x_1

entirely) is still balanced, exactly half of the 8 inputs give 0. The oracle just skips the CX for the input it doesn't depend on:

Python

U_{f}

for

f (x_{0}, x_{1}, x_{2}) = x_{0} \oplus x_{2}

Set input qubits 0 and 2, then watch qubit 3 (the ancilla) in the Exact State table: it tracks

x_0 \oplus x_2

exactly, completely independent of whatever qubit 1 is set to.

Circuit

Step through the circuit: after gate 2 of 2

3 / 3

Exact State

Basis state	Re	Probability
$∣0000 ⟩$	1.000	100.0%
$∣0001 ⟩$	0	0.0%
$∣0010 ⟩$	0	0.0%
$∣0011 ⟩$	0	0.0%
$∣0100 ⟩$	0	0.0%
$∣0101 ⟩$	0	0.0%
$∣0110 ⟩$	0	0.0%
$∣0111 ⟩$	0	0.0%
$∣1000 ⟩$	0	0.0%
$∣1001 ⟩$	0	0.0%
$∣1010 ⟩$	0	0.0%
$∣1011 ⟩$	0	0.0%
$∣1100 ⟩$	0	0.0%
$∣1101 ⟩$	0	0.0%
$∣1110 ⟩$	0	0.0%
$∣1111 ⟩$	0	0.0%

Exercise

Build the oracle for

f(x_0, x_1, x_2) = x_0 \oplus x_2

on a 4-qubit circuit (qubits 0-2 are inputs, qubit 3 is the ancilla):

CX

from qubit 0 into qubit 3, then

CX

from qubit 2 into qubit 3. Qubit 1 isn't used by this

f

, so it gets no gate at all.

Python

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

f(x_0, x_1) = x_0 \wedge x_1

(

f=1

only when both inputs are 1). Is this constant, balanced, or neither?

Constant

Balanced

Neither: only 1 of the 4 inputs (11) gives

f=1

, not exactly half.

Both constant and balanced.

Check your understanding

For

n = 4

input bits (16 possible inputs), what's the classical worst-case number of queries needed to determine constant-vs-balanced with certainty?

9, one more than half of the 16 inputs.

16, every input.