A parity lock hides a secret bit string s = s_0 s_1 \dots s_{n-1}. For an input x of n bits it answers
where x_k is the bit of qubit k. Classically, each query reveals one bit of information, so finding s takes n queries. The lock also comes as a phase oracle on n qubits,
Bit order: qubit 0 is the leftmost bit, so |x_0x_1\dots x_{n-1}\rangle is index int("x0x1...", 2) and a state is a list of 2^n amplitudes; in 3 qubits |011\rangle is index 3. For example, with s = "110" and x = |011\rangle: f(x) = (1\cdot0 + 1\cdot1 + 0\cdot1) \bmod 2 = 1.
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 find_secret(box, n) that uses the box once and returns s as a string of n characters "0"/"1", s_0 first. The tests call bv_test(find_secret, n, seed), which picks a secret from seed (any of the 2^n strings, all zeros included), seals the phase oracle of f in a box of n qubits and returns your answer. Try it with Run: print(bv_test(find_secret, 6, 5)).
Examples
Input: bv_test(find_secret, 3, 7)
Output: "001"
Input: bv_test(find_secret, 4, 1)
Output: "1100"
Input: bv_test(find_secret, 5, 3)
Output: "00110"
Constraints
1 <= n <= 12; one use of the box; the answer must be right for every secret, whatever the measurement draws
Goals
- Recover a hidden n-bit string from one use of a phase oracle
- Connect the parity function s . x mod 2 with the sign pattern of the Hadamard transform
- Report the answer with qubit 0 as the leftmost character