{"ID":2860002,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.05028","arxiv_id":"2510.05028","title":"Cryptographic Conditions for Efficient Testing of Distributions and Quantum States","abstract":"One of the most fundamental problems in distribution testing is the identity testing problem: given samples $x_1,\\ldots,x_s$, the goal is to determine whether the samples are drawn from a target distribution $\\mathcal{D}$. When $\\mathcal{D}$ is a distribution over $\\bit^n$, the optimal sample complexity of identity testing is known to be $Ω(\\sqrt{2^n})$. Furthermore, most existing results assume that the samples $x_1,\\ldots,x_s$ are generated independently from an unknown distribution. In this work, we overcome both of these limitations by initiating study of distribution testing in a more realistic setting. In our model, the unknown distribution is promised to be efficiently samplable, while allowing the observed samples $x_1,\\ldots,x_s$ to be adversarially generated and arbitrarily correlated. Under this model, we show that polynomially many samples suffice to verify distributions. We further characterize the computational complexity of verifying classically- and quantumly-samplable distributions. Our techniques also extend to verifications of quantum states. In establishing some of our results, we employ Kolmogorov complexity techniques in a novel manner. We also present multiple applications of Kolmogorov complexity that are of independent interest. In particular, we show that certified randomness with a classical efficient prover can be achieved without computational assumptions when inefficient verification is allowed. Furthermore, we also show that a natural quantum extension of a well-studied Kolmogorov complexity measure provides a good benchmark for certifying sampling-based quantum advantage.","short_abstract":"One of the most fundamental problems in distribution testing is the identity testing problem: given samples $x_1,\\ldots,x_s$, the goal is to determine whether the samples are drawn from a target distribution $\\mathcal{D}$. When $\\mathcal{D}$ is a distribution over $\\bit^n$, the optimal sample complexity of identity tes...","url_abs":"https://arxiv.org/abs/2510.05028","url_pdf":"https://arxiv.org/pdf/2510.05028v3","authors":"[\"Bruno Cavalar\",\"Eli Goldin\",\"Matthew Gray\",\"Taiga Hiroka\",\"Min-Hsiu Hsieh\",\"Tomoyuki Morimae\"]","published":"2025-10-06T17:05:38Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}