Efficient verification of anticoncentrated quantum states

Abstract

I present a method for estimating the fidelity F ( μ ,  τ ) between a preparable quantum state μ and a classically specified pure target state $$\tau =\left|\tau \right\rangle \left\langle \tau \right|$$ τ = τ τ , using simple quantum circuits and on-the-fly classical calculation (or lookup) of selected amplitudes of $$\left|\tau \right\rangle$$ τ . The method is sample efficient for anticoncentrated states (including many states that are hard to simulate classically), with approximate cost 4 ϵ −2 (1 −  F ) d p coll where ϵ is the desired precision of the estimate, d is the dimension of the Hilbert space, and p coll is the collision probability of the target distribution. 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.