A Boolean function f on n bits is given as a truth table truth of length 2^n: truth[x] is f(x), where x is the input read as a binary number. Its bit oracle U_f acts on n+1 qubits, an input register (qubits 0 to n-1) followed by one target qubit (qubit n, the last):
Bit order: qubit 0 is the leftmost bit, so the basis state |x, y\rangle is index 2 * x + y, and in 3 qubits |011\rangle is index 3.
The register starts in the state psi (a list of 2^n amplitudes, qubit 0 leftmost) and the target in one of
The whole input is the product state |\psi\rangle\otimes|\text{target}\rangle (2^{n+1} amplitudes, amplitude 2 * x + y equal to psi[x] times the target's amplitude y). For these two targets, the output of U_f is again a product: the target comes out in the state it went in, and the register comes out in some state |\varphi\rangle.
Write kickback(psi, truth, target) that returns |\varphi\rangle, a list of 2^n amplitudes. Any global phase is accepted: [-0.6, -0.8] is the same state as [0.6, 0.8].
Examples
Input: psi = [0.6, 0.8], truth = [0, 1], target = "-"
Output: [0.6, -0.8]
Input: psi = [0.6, 0.8], truth = [0, 1], target = "+"
Output: [0.6, 0.8]
Input: psi = [0.5, 0.5, 0.5, 0.5], truth = [1, 0, 0, 1], target = "-"
Output: [-0.5, 0.5, 0.5, -0.5]
Constraints
len(psi) == len(truth);psiis normalised; amplitudes are compared with a tolerance of1e-6
Goals
- Run the bit oracle on a register whose target qubit is |+> or |->
- Read the input register's state back out of a product state
- See that a target in |-> turns the bit oracle into a phase oracle on the register