Math
One question, asked once
A black box computes f from n bits to one bit, and you may only ask it about inputs. To be certain whether f is constant or balanced can take half the table plus one call. Hadamard everything, ask ONCE with the answer as a sign, Hadamard everything again, and the all-zeros outcome settles it. The truth table here is clickable, so the promise can be broken by hand: for any table at all the answer comes up with probability (1 - 2k/N)². And when the table happens to be f(x) = s·x, the one call returns s itself.
What happens
A black box computes some function f from n bits to one bit. You are promised it is either constant or balanced - the same answer everywhere, or one answer on exactly half the inputs - and you must say which. Classically there is no shortcut: half the table can agree and the next entry still ruin it, so being certain costs N/2 + 1 calls. Nine of them at sixteen inputs, thirty-three at sixty-four. Now the quantum version, and it is three lines. Hadamard every qubit, so all N inputs are asked at once. Call the oracle - which answers not with a bit but with a SIGN, putting a minus on every input where f is one. Hadamard every qubit again. Measure. If all the qubits read zero, f was constant; anything else means balanced, and the whole thing took one call. What makes this module more than a demonstration is that the truth table above is clickable. Break the promise: turn one cell over and f is neither constant nor balanced, and the algorithm does not fail - it degrades by an amount you can write down. For ANY table whatever, the all-zeros outcome has probability (1 − 2k/N)² where k is how many ones the table has. Constant is k = 0 and gives one. Balanced is k = N/2 and gives exactly zero. One flipped cell at sixteen inputs gives 4/256, one run in sixty-four, and the panel says the number before you count it. That is what a promise inside an algorithm is worth, in figures. There is a second thing hiding here. When the table happens to be linear - f(x) = s·x mod 2 for some hidden string s - the same three steps do not merely answer yes or no: the outcome is s itself, with probability one, and every other outcome has probability exactly zero. That is Bernstein-Vazirani, and classically it costs n calls, one per bit of s. Ask it once, read the whole string. Underneath both facts is one formula: the amplitude of outcome y is the Walsh-Hadamard transform of (−1)^f, and the module computes it a second time straight from the truth table so the two can be held together.
Equations used in the module
Equations the three steps: H on every qubit; one oracle call as a sign, |x> -> (−1)^f(x) |x>; H on every qubit again amplitude of outcome y: (1/N) sum over x of (−1)^(f(x) + x·y) - the Walsh-Hadamard transform of (−1)^f P(all zeros) = (1 − 2k/N)² where k is how many ones the truth table has - EXACTLY, for any table at all constant (k = 0 or N): 1; balanced (k = N/2): 0; one cell of a balanced table flipped: 4/N² = 1/64 at N = 16 classical cost to be CERTAIN: N/2 + 1 calls (3, 5, 9, 17, 33 for n = 2…6) against 1 linear table f(x) = s·x mod 2 (Bernstein-Vazirani): the outcome IS s, probability 1, every other outcome exactly 0; classical cost n calls, one per bit f = 1 everywhere gives exactly the same probabilities as f = 0 everywhere - the difference is a global sign, and a global sign is not measurable counted, 2000 runs at n = 4: constant 2000 of 2000 on all zeros; hidden s = 11, 2000 of 2000 on 11; balanced 0 on all zeros; one cell flipped 30 (exact 31.25)
