A sealed box hides a Boolean function f on n bits with a promise: f is either constant (the same value on all 2^n inputs) or balanced (1 on exactly half of the inputs and 0 on the other half). A classical tester may need many queries to be sure which; you get one use of the quantum oracle.
The box holds the bit oracle of f on n+1 qubits, the input register x (qubits 0 to n-1) followed by the target y (qubit n, the last):
Bit order: qubit 0 is the leftmost bit, so |x, y\rangle is index 2 * x + y, and a state of the box is a list of 2^{n+1} amplitudes; in 3 qubits |011\rangle is index 3.
box(state, gates) is a sealed piece of hardware. You hand it a state you have prepared (a list of amplitudes, normalised) and a list gates of gates to run afterwards, each ("h", q), ("x", q) or ("z", q) for H, X or Z on qubit q, applied from left to right (gates may be empty). The box applies its oracle once, then your gates, then measures every qubit and returns only the outcome, as a bit string with qubit 0 first (for example "01"). The measurement follows the Born rule, outcome i with probability |a_i|^2, using a random draw that is the same on every run. The box can be used once: a second call raises TooManyQueries. A state of the wrong length or not normalised, or an unknown gate, raises ValueError.
Write dj(box, n) that uses the box once and returns "constant" or "balanced". The tests call dj_test(dj, n, seed), which picks a hidden f that keeps the promise from seed, seals it in a box of n+1 qubits and returns your answer. Try it with Run: print(dj_test(dj, 4, 11)).
Examples
Input: dj_test(dj, 1, 3)
Output: "constant"
Input: dj_test(dj, 3, 16)
Output: "balanced"
Input: dj_test(dj, 4, 1)
Output: "constant"
Constraints
1 <= n <= 10; one use of the box; the answer must be right for every f that keeps the promise, whatever the measurement draws
Goals
- Prepare the Deutsch-Jozsa input state on n + 1 qubits
- Decide constant versus balanced from one measured outcome
- Use a sealed oracle exactly once