Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on improving the efficiency, and in particular depth, of generating the classical snapshot. Existing constructions rely on a distribution of unitaries as a central building block, and research is devoted to simplifying this family as much as possible. We diverge from this paradigm and show that suitable distributions over states can be used as the building block instead. Concretely, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This state-based approach allows us to consider a building block with arguably weaker properties that has not been studied so far in the context of classical shadows. Notably, our cryptographically-inspired analysis shows that for efficiently computable observables, it suffices to use pseudorandom families of states. To the best of our knowledge, computational classical shadow tomography was not considered in the literature prior to our work. Finally, in terms of efficiency, the online part of our method (i. e. \ the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates.
Brakerski et al. (Mon,) studied this question.