2
$\begingroup$

Analogous to the $|T\rangle$ and $|CCZ\rangle$ magic states, one can define a $|C^n Z\rangle$ magic state. Is there any known quantification of the amount of magic of this state, and is there a way to transform $|C^n Z \rangle$ to many $|CCZ \rangle$ magic states? If so, what is the rate w.r.t. $n$?

$\endgroup$

1 Answer 1

1
$\begingroup$

The simplest thing you could possibly do is to turn one $|C^nZ\rangle$ state into $O(1/2^n)$ $|CCZ\rangle$ states by measuring out $n-3$ of the qubits and discarding if any of the measurement results are $|0\rangle$ instead of $|1\rangle$.

At the moment I can't think of anything better. It seems like there should be some way of doing a conversion that has cost $O(1/n)$ instead of $O(1/2^n)$, probably involving catalysis, but nothing came to mind for how to actually do it.

If the $|C^nZ\rangle$ state was somehow magically unfolded into a $W_{2^n}$ state via a binary-to-unary converter at no cost, then you could deterministically recover one CCZ state by using measurement based uncomputation to uncompute CSWAP gates folding it back into a $W_8$ state followed by performing $W_8 \rightarrow CCZ$ which is 1-to-1.

For an upper bound, stabilizer nullity probably shows the rate can't be more than $(n+1)/3$. So it's somehwere between $(n+1)/3$ and $4/2^n$. Wide margins.

$\endgroup$
2
  • $\begingroup$ Thanks! It's unfortunate that the bounds are so wide. What if I instead move the goalposts and say I can perform a FT $C^n Z$ gate? I wonder if I can somehow use this to perform $\Theta(n)$ $CCZ$ gates, with the idea of state catalysis also what I had in mind. Is it any clearer in that case? $\endgroup$ Commented Jul 9 at 20:35
  • $\begingroup$ @RohanMehta Being able to do the gate instead of having the state is much more flexible because there are no probabilistic corrections. So you can definitely get at least 1 CCZ per C^nZ in that case by having ancillas in the 1 state. $\endgroup$ Commented Jul 9 at 21:26

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.