Polynomial Complexity of Quantum Sample Tomography

Abstract Efficient quantum tomography is crucial for advancing quantum computing technologies. Traditional quantum state tomography requires an exponential number of measurements for complete reconstruction. Therefore, developing methods that reduce measurement complexity to polynomial scale is essential for practical applications. In this paper, we show that quantum sample tomography can be accomplished with polynomial scale measurements while maintaining accuracy with a high probability. We present a novel approach using conditional recurrent neural networks (RNNs) with solid theoretical foundations from Rademacher complexity and random projection theory. The effectiveness of our method is validated through several quantum models.