Efficient verification of anticoncentrated quantum states
I present a method for estimating the fidelity F(μ, τ) between a preparable quantum state μ and a classically specified pure target state τ=|τ> <τ|, using simple quantum circuits and on-the-fly classical calculation (or lookup) of selected amplitudes of |τ>. The method is sample efficient for anticoncentrated states (including many states that are hard to simulate classically), with approximate cost 4ϵ –2 (1 – F)dpcoll where ϵ is the desired precision of the estimate, d is the dimension of the Hilbert space, and pcoll is the collision probability of the target distribution. Furthermore, this scaling is exponentially better than that of any method based on classical sampling. I also present a more sophisticated version of the method that uses any efficiently preparable and well-characterized quantum state as an importance sampler to further reduce the number of copies of μ needed. Though some challenges remain, this work takes a significant step toward scalable verification of complex states produced by quantum processors.