Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.29739

Quantum complexity resource in Gaussian boson sampling: Core structure of the semidefinite program

Kunwar Kalra, Vitaly Kocharovsky

quant-phSubmitted Jun 29, 2026• Announced Jun 30, 2026• 1 citation
arXivHTMLPDF

Abstract

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 classically. Earlier work characterized this resource only through the trace of the quantum part, equal to its photon number. We characterize the optimizer itself, as a quantum state and as a geometric object, beyond the scalar given by its trace. We prove that it is a unique pure Gaussian state and construct an explicit oracle map, obeying an algebraic Riccati identity, that reconstructs the resource. We prove that the full problem compresses exactly onto the active symplectic sector that the dual program support generates. The passive-diagonalizable states are solved in closed form, the first explicit solvable class, and the whole program is shown to be equivalent to a minimization over the symplectic group, that is, over the Siegel upper half-space. Together these results establish that the program determines a canonical localized pure Gaussian component of the resource, and they provide the structural foundation for its detailed analysis.

Comments
20 pages

Related papers

Symplectic Rank of Non-Gaussian Quantum States

Francesco Anna Mele, Salvatore F. E. Oliviero, Varun Upreti +1 more

Non-Gaussianity is a key resource for achieving quantum advantages in bosonic platforms. Here, we investigate the : a non-Gaussianity monotone that satisfies remarkable operational and resource-theoretic properties. Mathematically, the symplectic rank of a pure state is the number of symplectic eigenvalues of the covariance matrix that are strictly larger than those of the vacuum. Operationally, it (i) is easy to compute, (ii) emerges as the smallest number of modes onto which all the non-Gaussianity can be compressed via Gaussian unitaries, (iii) lower bounds the non-Gaussian gate complexity of state preparation independently of the gate set, (iv) governs the sample complexity of quantum tomography, and (v) bounds the computational complexity of bosonic circuits. Crucially, the symplectic rank is nonincreasing under postselected Gaussian operations, leading to new no-go theorems for Gaussian conversion. Remarkably, this allows us to show that the resource theory of non-Gaussianity is irreversible under exact Gaussian operations. Finally, we show that the symplectic rank is a robust non-Gaussian measure, explaining how to witness it in experiments and how to exploit it to meaningfully benchmark different bosonic platforms. In doing so, we derive lower bounds on the trace distance (resp. total variation distance) between arbitrary states (resp. classical probability distributions) in terms of the norm distance between their covariance matrices, which may be of independent interest.

arXiv:2504.19319•PRX Quantum•Apr 6, 2026•18 citations

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.

quant-pharXiv:2604.12330•Apr 15, 2026•1 citation

Gaussian Boson Sampling

Craig S. Hamilton, Regina Kruse, Linda Sansoni +3 more

Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.

arXiv:1612.01199•Physical Review Letters•Oct 23, 2017•566 citations

Proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezed input modes

Laura Shou, Alexey V. Gorshkov, Victor Galitski +1 more

Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on $M$ optical modes, with $K$ equally squeezed input modes and $N$ observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers $K$, which is a part of the argument for classical hardness of GBS. In particular, we show that for any $K$ and $N=o(\sqrt{K})$, the symmetric product $MK^{-1/2}U_{NK}U_{NK}^T$, for $U_{NK}$ the top left $N\times K$ submatrix of an $M\times M$ Haar random unitary $U$, is close in total variation distance to both an $N\times N$ symmetric complex Gaussian matrix $\mathbf G$ with independent entries, and the symmetric product $GG^T/\sqrt{K}$ for $G$ an $N\times K$ matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with $K=cM$ if $c<1/2$. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.

quant-pharXiv:2608.19314•Aug 21, 2026•3 citations

What resources are needed for optimal learning of bosonic Gaussian states?

Senrui Chen, Francesco Anna Mele, Marco Fanizza +5 more

Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an $n$-mode Gaussian state, with energy less than $E$, to $\varepsilon$ trace distance with high probability. We prove a lower bound of $Ω(n^3/\varepsilon^2)$ for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and $Ω(n^2/\varepsilon^2)$ for arbitrary measurements. We further show an upper bound of $\widetilde{O}(n^2/\varepsilon^2)$ given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of $\widetildeΘ(E/\varepsilon^2)$ for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to $\varepsilon$ total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.

quant-pharXiv:2603.18136•Mar 20, 2026•14 citations

Quantum-advantage resource of a two-mode Gaussian state: Analytical theory of convex optimization and a Galois no-go for the closed-form solution

Kunwar Kalra, V. V. Kocharovsky

We study the problem of extracting a quantum complexity resource from a mixed Gaussian state of the multimode light. We present the first complete, certificate-checked solution to this problem in a genuinely coupled sector. We carry this out for the two-mode case, the smallest case in which modes are genuinely coupled. Even in this case the solution is highly nontrivial, and we rigorously prove that it cannot be given in a closed form.

quant-pharXiv:2607.00266•AVS Quantum Science•Jul 2, 2026•0 citations
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 classically. Earlier work characterized this resource only through the trace of the quantum part, equal to its photon number. We characterize the optimizer itself, as a quantum state and as a geometric object, beyond the scalar given by its trace. We prove that it is a unique pure Gaussian state and construct an explicit oracle map, obeying an algebraic Riccati identity, that reconstructs the resource. We prove that the full problem compresses exactly onto the active symplectic sector that the dual program support generates. The passive-diagonalizable states are solved in closed form, the first explicit solvable class, and the whole program is shown to be equivalent to a minimization over the symplectic group, that is, over the Siegel upper half-space. Together these results establish that the program determines a canonical localized pure Gaussian component of the resource, and they provide the structural foundation for its detailed analysis.
Non-Gaussianity is a key resource for achieving quantum advantages in bosonic platforms. Here, we investigate the : a non-Gaussianity monotone that satisfies remarkable operational and resource-theoretic properties. Mathematically, the symplectic rank of a pure state is the number of symplectic eigenvalues of the covariance matrix that are strictly larger than those of the vacuum. Operationally, it (i) is easy to compute, (ii) emerges as the smallest number of modes onto which all the non-Gaussianity can be compressed via Gaussian unitaries, (iii) lower bounds the non-Gaussian gate complexity of state preparation independently of the gate set, (iv) governs the sample complexity of quantum tomography, and (v) bounds the computational complexity of bosonic circuits. Crucially, the symplectic rank is nonincreasing under postselected Gaussian operations, leading to new no-go theorems for Gaussian conversion. Remarkably, this allows us to show that the resource theory of non-Gaussianity is irreversible under exact Gaussian operations. Finally, we show that the symplectic rank is a robust non-Gaussian measure, explaining how to witness it in experiments and how to exploit it to meaningfully benchmark different bosonic platforms. In doing so, we derive lower bounds on the trace distance (resp. total variation distance) between arbitrary states (resp. classical probability distributions) in terms of the norm distance between their covariance matrices, which may be of independent interest.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.
Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on MMM optical modes, with KKK equally squeezed input modes and NNN observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers KKK, which is a part of the argument for classical hardness of GBS. In particular, we show that for any KKK and N=o(K)N=o(\sqrt{K})N=o(K​), the symmetric product MK−1/2UNKUNKTMK^{-1/2}U_{NK}U_{NK}^TMK−1/2UNK​UNKT​, for UNKU_{NK}UNK​ the top left N×KN\times KN×K submatrix of an M×MM\times MM×M Haar random unitary UUU, is close in total variation distance to both an N×NN\times NN×N symmetric complex Gaussian matrix G\mathbf GG with independent entries, and the symmetric product GGT/KGG^T/\sqrt{K}GGT/K​ for GGG an N×KN\times KN×K matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with K=cMK=cMK=cM if c<1/2c<1/2c<1/2. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.
Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an nnn-mode Gaussian state, with energy less than EEE, to ε\varepsilonε trace distance with high probability. We prove a lower bound of Ω(n3/ε2)Ω(n^3/\varepsilon^2)Ω(n3/ε2) for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and Ω(n2/ε2)Ω(n^2/\varepsilon^2)Ω(n2/ε2) for arbitrary measurements. We further show an upper bound of O~(n2/ε2)\widetilde{O}(n^2/\varepsilon^2)O(n2/ε2) given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of Θ~(E/ε2)\widetildeΘ(E/\varepsilon^2)Θ(E/ε2) for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to ε\varepsilonε total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.