Abstract: The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping the results to the AdS side. This relies on the assumption that the duality map (the `dictionary') is efficient to compute. In this talk, I will argue that the complexity of the AdS/CFT dictionary is surprisingly subtle: there might be cases in which one can efficiently apply operators to the CFT state (a task we call 'operator reconstruction') without being able to extract basic properties of the dual bulk state such as its geometry (which we call 'geometry reconstruction'), and vice versa. In order to reason about the complexity of geometry reconstruction we construct examples of holographic pseudoentanglement: that is, pairs of ensembles of states that obey the Ryu-Takayanagi formula for different geometries but which are nevertheless computationally indistinguishable. This result should be compared with existing evidence that operator reconstruction is generically easy in AdS/CFT. A useful analogy for the difference between these two tasks is quantum fully homomorphic encryption (FHE): this encrypts quantum states in such a way that no efficient adversary can learn properties of the state, but operators can be applied efficiently to the encrypted state. I will show that quantum FHE can separate the complexity of geometry reconstruction vs operator reconstruction, which raises the question whether FHE could be a useful lens through which to view AdS/CFT.