Is This Wiring an Oracle?

A student hands in a circuit on n+1 qubits and claims it is the bit oracle of some Boolean function f on n bits: qubits 0 to n-1 are the input register x, qubit n (the last) is the target y, and the circuit should act on every basis state as

The circuit gates is a list applied from left to right, using three gates that send basis states to basis states:

• ("x", q) flips bit q;
• ("cx", c, t) flips bit t when bit c is 1;
• ("ccx", c1, c2, t) flips bit t when bits c1 and c2 are both 1.

Gates may also touch the target and may change the input register in the middle, as long as the end result has the form above. Bit order: qubit 0 is the leftmost bit, so in 3 qubits |011\rangle is index 3, and the basis state |x, y\rangle is index 2 * x + y.

Write read_wiring(n, gates) that returns the truth table of f, a list of 2^n values 0 or 1 where entry x is f(x) (x read as a binary number, qubit 0 leftmost), if the circuit is the bit oracle of some f. Return None if it is not: some basis state |x, y\rangle, for either value of y, does not end as |x, y\oplus f(x)\rangle for one common f.

Examples

Input:  n = 2, gates = [("ccx", 0, 1, 2)]
Output: [0, 0, 0, 1]
Explanation: f(x) = x0 AND x1.

Input:  n = 2, gates = [("x", 1), ("ccx", 0, 1, 2), ("x", 1)]
Output: [0, 0, 1, 0]
Explanation: f(x) = x0 AND NOT x1: only x = 10 (index 2) flips the target,
and the second X gate puts qubit 1 back.

Input:  n = 1, gates = [("cx", 1, 0)]
Output: None
Explanation: |0, 0> and |1, 0> are untouched, but |0, 1> becomes |1, 1>.

Constraints

• in every gate the qubits are distinct and lie in 0..n

Goals

• Run a circuit of X, CNOT and Toffoli gates on every basis state as bit operations
• Decide whether a circuit leaves the input register alone and only XORs a function into the target
• Read off the truth table of the function it computes