3
$\begingroup$

The paper states that classical shadows can be stored efficiently by stabilizer formalism. But I'm confused what information is stored? I can't tell the efficiency come from.

In the paper，the statement is “we combine the mindset of shadow tomography (predict target functions, not the full state) with recent insights from quantum state tomography (rigorous statistical convergence guarantees) and the stabilizer formalism (efficient implementation).” and “In both cases, the resulting classical shadow can be stored efficiently in a classical memory using the stabilizer formalism.” I don't find another detail to explain the efficiency.

My question is how many bits we need to store $U^\dagger|b\rangle\langle b|U$? and how to use stabilizer formalism?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think it might help if you put the paragraph where you suspect the answer might be hidden or missing. $\endgroup$
    – luciano
    Commented Dec 15, 2022 at 12:47

1 Answer 1

Reset to default
2
$\begingroup$

In general, in the approach to shadow tomography introduced in that paper, the "classical shadows" are effectively operators which have the same dimensionality as the states to be estimated (you can see them as estimators for the state itself). This means that if you think about the many-qubit scenario, you won't even be able to save this in your computer as they'll be $2^n\times 2^n$ dimensional matrices.

The stabilizer formalism allows you to represent efficiently these shadows. Rather than writing out the entire operators, you can represent them efficiently via their stabilizers. I think the main reason you can do this is that in at least the main cases studied in the paper, if I remember correctly, the shadows are proportional to the state associated to the observed outcome, so representing efficiently the state is the same as representing efficiently the shadows. See e.g. What is a stabilizer state? for a concise explanations of how stabilizers work in general.

Let me clarify a little bit the above paragraph.

  1. At the measurement stage, the gist of the protocol is that you perform projective measurements in random directions. You can see this as equivalent to performing a POVM with infinitely many outcomes, with each outcome corresponding to a pure state. When this protocol is implemented via Clifford circuits, the pure states corresponding to the different outcomes can all be described in the stabilizer formalism.
  2. At the estimation stage, you take the different outcomes obtained from the measurement, and convert each outcome into the corresponding "classical shadow", which is an operator that at least in the cases considered in the paper is mostly proportional to the state corresponding to that outcome. These shadows are by construction such that they reproduce the correct state in expectation value, and you can show that they estimate expectation values of observables and other stuff pretty well.
Improve this answer
$\endgroup$
5
  • $\begingroup$ "the pure states corresponding to the different outcomes" is measurement outcome $|b\rangle$? Every $|b\rangle$ is n bits. Can stabilizer formalism be more efficient? $\endgroup$
    – LinZaisheng
    Commented Dec 15, 2022 at 15:27
  • $\begingroup$ not quite, but I understand the confusion. The protocol involves doing a different projective measurement in different bases. In each basis, the outcome is some $|b\rangle$, but you also have to take into account to what measurement this $|b\rangle$ corresponds to. I find the problem to be more easily understood reframing the overall scheme as a single POVM measurement, whose outcomes are labeled by the choice of projective measurement (that is, of unitary $U$ applied) and associated outcome $b$. You'll notice the shadows depend on both $U$ and $b$, so that's what they effectively do $\endgroup$
    – glS ♦
    Commented Dec 15, 2022 at 15:30
  • $\begingroup$ We should store the $U|b\rangle$ efficiently, not only the $|b\rangle$? Clifford group can be efficiently stored by stabilizer formalism? $\endgroup$
    – LinZaisheng
    Commented Dec 15, 2022 at 15:37
  • $\begingroup$ precisely. The shadows correspond to $U$ and $|b\rangle$. They effectively correspond to $U^\dagger |b\rangle$. If $U$ are implemented via Clifford circuits, like they are in the paper, then you can easily store $U^\dagger|b\rangle$ via the stabilizer formalism $\endgroup$
    – glS ♦
    Commented Dec 15, 2022 at 15:38
  • $\begingroup$ Ok, thanks. I need more about stabilizer. $\endgroup$
    – LinZaisheng
    Commented Dec 15, 2022 at 15:42

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.