1
$\begingroup$

I have seen sometimes that in some protocols, one can uncompute a circuit using only Clifford + measurements. See for example

Erase the two qubits containing $p_{w,r}$ and $p_{w,s}$, then the register containing component w of p. These erasures can be done with measurements and Clifford gates.

before eq 73 in Su et al. For context, these are qubits that were "copied" via C-Nots from another register, and have been used as a control in a C-Z gate.

When can one erase registers using measurements and Clifford gates in general?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm not sure what the exact general requirement is, but a sufficient requirement is:

  1. The qubit's computational basis must be a function of other qubits' computational basis value. For example, the state should have the form:

    $$\sum_k \alpha_k |k\rangle |\dots\rangle |f(k)\rangle$$

    where $f$ is some classical function that outputs a single bit.

  2. The fixup operation $U$ which performs $U(\sum_k \alpha_k |k\rangle) = \sum_k (-1)^{f(k)} \alpha_k |k\rangle$ must be possible to do using only stabilizer operations. Because you're going to measure the qubit storing $f(k)$ in the X basis, and if the result is $|-\rangle$ then you need to apply $U$ to finish the uncomputation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! Would $U$ not amount to an unimportant global phase now that we have measured $f(k)$ (the recovery operation does no longer depend on $k$)? $\endgroup$
    – Pablo
    Dec 22, 2021 at 22:27
  • 1
    $\begingroup$ @Pablo No, because it has negated states matching $f$ relatives to states that don't. $\endgroup$
    – Craig Gidney
    Dec 22, 2021 at 22:43
  • 1
    $\begingroup$ For example, if $f$ was "an even number of bits are ON", then $U$ would negate the state $|101\rangle$ but not the state $|111\rangle$. $\endgroup$
    – Craig Gidney
    Dec 22, 2021 at 22:45
  • $\begingroup$ I think I get it: starting from $|\psi\rangle|k\rangle|f(k)\rangle$, - If $f(k) = 0$, then one applies X and gets $|\psi\rangle|k\rangle(|+\rangle+|-\rangle)$. Since controlling on $k$ the operation $U$ does nothing (because $f(k) = 0$), it stays the same in either case. - If $f(k)=1$ one would have $|\psi\rangle|k\rangle(|+\rangle-|-\rangle)$. I guess the idea is that if one measures $|-\rangle$ then applying $f(k)$ controlled on register $|k\rangle$ recovers the original state. I guess the main limitation is the need to control on $|k\rangle$. Is this right? $\endgroup$
    – Pablo
    Dec 22, 2021 at 22:51
  • 1
    $\begingroup$ @Pablo Yes, that's the main limitation. It's usually easier to do $|k\rangle \rightarrow (-1)^f(k) |k\rangle$ than it is to do $|k\rangle \rightarrow |k\rangle|f(k)\rangle$, e.g. you'll be able to apply a CZ to the qubits of $k$ instead of a Toffoli controlled by the qubits of $k$. $\endgroup$
    – Craig Gidney
    Dec 23, 2021 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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