A Boolean function f on n bits cannot be a gate as it is, because a gate must be reversible and f usually is not. The standard fix is the bit oracle U_f on n+1 qubits: qubits 0 to n-1 hold the input x (the input register) and qubit n, the last one, is the target y. On basis states
where \oplus is XOR: the target flips exactly when f(x) = 1, and the input register is left as it was. On any other state U_f acts linearly, so each amplitude simply moves to its new basis state.
Bit order: basis state |b_0 b_1 \dots b_n\rangle has index int("b0b1...bn", 2), and qubit 0 is the leftmost bit. So |x, y\rangle, with x read as an n-bit number, is index 2 * x + y. In 3 qubits (n = 2), |01, 1\rangle is |011\rangle, index 3.
The function arrives as a truth table truth of length 2^n: truth[x] is f(x) (0 or 1), where x is the input register read as a binary number, qubit 0 leftmost.
Write bit_oracle(state, truth) that returns the state after U_f, a list of 2^{n+1} amplitudes. Any global phase is accepted: [1j, 0, 0, 0] is the same state as [1, 0, 0, 0].
Examples
Input: state = [0, 0, 1, 0], truth = [0, 1]
Output: [0, 0, 0, 1]
Explanation: n = 1. The state is |1, 0>, and f(1) = 1 flips the target: |1, 1>.
Input: state = [0.5, 0, 0.5, 0, 0.5, 0, 0.5, 0], truth = [0, 1, 1, 0]
Output: [0.5, 0, 0, 0.5, 0, 0.5, 0.5, 0]
Input: state = [0, 0, 0.6, 0, 0, 0.8j, 0, 0], truth = [0, 1, 0, 0]
Output: [0, 0, 0, 0.6, 0, 0.8j, 0, 0]
Explanation: index 2 is |01, 0> and f(01) = 1, so it moves to |01, 1>, index 3.
Index 5 is |10, 1> and f(10) = 0, so it stays.
Constraints
len(state) == 2 * len(truth); the state is normalised; amplitudes are compared with a tolerance of1e-6
Goals
- Apply the bit oracle |x, y> -> |x, y XOR f(x)> to a state as a permutation of amplitudes
- Locate the input register and the target qubit inside a basis index