A Boolean function f on n bits is given as a truth table truth of length 2^n: truth[x] is f(x), with x the input read as a binary number. Its bit oracle U_f acts on n+1 qubits, the input register (qubits 0 to n-1) followed by the target (qubit n, the last):
Bit order: qubit 0 is the leftmost bit, so |x, y\rangle is index 2 * x + y; in 3 qubits |011\rangle is index 3. H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.
The lab runs this circuit:
- start in |0\dots0\rangle|1\rangle (all input qubits 0, target 1);
- apply H to every one of the n+1 qubits;
- apply U_f once;
- apply H to each input qubit (qubits 0 to n-1, not the target);
- measure the input register.
Write dj_zero_prob(truth) that returns the probability that all n input qubits read 0 (whatever the target reads). Any f may come in, not only constant or balanced ones. Press Run with plot(range(9), [dj_zero_prob([1] * k + [0] * (8 - k)) for k in range(9)], kind="bar") to see how the probability depends on the number of inputs with f(x) = 1.
Examples
Input: truth = [0, 0]
Output: 1.0
Input: truth = [0, 1, 1, 1]
Output: 0.25
Input: truth = [0, 1, 1, 0]
Output: 0.0
Constraints
- answers are compared with a tolerance of
1e-6
Goals
- Simulate the Deutsch-Jozsa circuit for any Boolean function, promised or not
- Compute the probability that the input register reads all zeros
- Relate that probability to how unevenly f takes the values 0 and 1