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

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.

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}$$:
Put the two together, and you have a circuit that performs a CCCZ by consuming a $$|W_8\rangle$$ state.