5
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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:

enter image description here

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}$:

enter image description here

(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.