One Look at a Sealed Switch

A sealed switch hides one of the four functions from one bit to one bit:

Asking the switch classically, you would need both f(0) and f(1) to know whether f is constant (f(0)=f(1)) or balanced (f(0)\ne f(1)). You have the quantum version instead: its bit oracle on 2 qubits, with qubit 0 the input x and qubit 1 the target y,

Qubit 0 is the leftmost bit: |x, y\rangle is index 2 * x + y, so the state is a list of 4 amplitudes for |00\rangle, |01\rangle, |10\rangle, |11\rangle.

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 deutsch(box) that uses the box once and returns "constant" or "balanced". The tests call deutsch_test(deutsch, name, seed), which seals the function called name in a box (with the measurement draws fixed by seed) and returns your answer; your function never sees name. Try it with Run: print(deutsch_test(deutsch, "flip", 7)).

Examples

Input:  deutsch_test(deutsch, "copy", 4)
Output: "balanced"

Input:  deutsch_test(deutsch, "one", 2)
Output: "constant"

Input:  deutsch_test(deutsch, "flip", 6)
Output: "balanced"

Constraints

• one use of the box; the answer must be right for every one of the four functions, whatever the measurement draws

Goals

• Prepare the input state of Deutsch's algorithm and choose the gates after the oracle
• Decide whether a one-bit function is constant or balanced with a single oracle use