Given a $|W_8\rangle$, perform a CCCZ using stabilizer operations

Question

I know it's possible to perform a CCZ operation using only stabilizer operations (Cliffords + Pauli measurements + classical feedback) by consuming a $|CCZ\rangle$ state, and that a $|W_4\rangle$ state can be turned into a $|CCZ\rangle$ state, so I can perform a CCZ using a $|W_4\rangle$. But I've been struggling to find the smallest $|W_n\rangle$ state that can perform a CCCZ deterministically. Initially I thought $|W_8\rangle$ would work, since I can turn it into a $|CCCZ\rangle$ state, but then when I teleport through it I end up with CCZ corrections and no way to do them.

Answer 1

It's possible to perform a CCCZ by consuming a $|W_{8}\rangle$ state.

The key idea is to use the state $\text{AND}_{1,2} \cdot \text{AND}_{1,3} \cdot \text{AND}_{2,3} \cdot \text{AND}_{1,2,3} \cdot |+\rangle^{\otimes 3}$ (where $\text{AND}$ allocates a $|0\rangle$ qubit and then targets it with a NOT gate controlled by the indicated qubits). This state has enough "bells and whistles" on top of the basic $|CCCZ\rangle$ state that you can perform the corrective CCZs that result from the CCCZ teleportation. And also it's possible to turn a $|W_{8}\rangle$ state into this state using only stabilizer operations. The reason this is possible is because you can think of the $|W_{8}\rangle$ state as a one-hot unary encoding of a uniform superposition, it's possible to go from unary to binary using stabilizer operations, and single controls on the one-hot unary representation act like multiple controls on the binary representation.

Here is a circuit that prepares the state $\text{AND}_{1,2} \cdot \text{AND}_{1,3} \cdot \text{AND}_{2,3} \cdot \text{AND}_{1,2,3} \cdot |+\rangle^{\otimes 3}$ and then consumes it to perform a CCCZ:

And here is a circuit that turns a $|W_{8}\rangle$ state into the state $\text{AND}_{1,2} \cdot \text{AND}_{1,3} \cdot \text{AND}_{2,3} \cdot \text{AND}_{1,2,3} \cdot |+\rangle^{\otimes 3}$:

(Note: the circuit has Toffolis inside one of the controlled XOR gates after the W8 state is prepared, but these Toffolis are uncomputing a value so they can be replaced with measurement based uncomputation.)

Put the two together, and you have a circuit that performs a CCCZ by consuming a $|W_8\rangle$ state.