{"id":"arxiv/2606.29739","url":"https://arxiv.org/abs/2606.29739","tags":["quant-ph"],"score":0,"title":"Quantum complexity resource in Gaussian boson sampling: Core structure of the semidefinite program","domain":"quant-ph","source":"arxiv","authors":["Kunwar Kalra","Vitaly Kocharovsky"],"reviews":0,"subject":"quant-ph","summary":"We present a rigorous analysis of the algebraic and geometric structure of the quantum complexity resource of a system of bosonic modes in Gaussian boson sampling. This resource underlies the quantum advantage of the system: its photon-counting statistics require the evaluation of a hafnian of the resource covariance matrix, and that computation is #P-hard. The resource covariance matrix is the solution of a semidefinite program that extracts the minimum-trace physical quantum part of the total covariance matrix; the complementary part is positive semidefinite and can therefore be simulated…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}