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:2508.00983 · Quantum

Proof of hiding conjecture in Gaussian boson sampling

Laura Shou, Sarah H. Miller, Victor M. Galitski

Published Oct 27, 2026• 0 citations
arXivHTMLPDF

Abstract

Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps in the argument for classical hardness of GBS is the so-called “hiding conjecture'', which asserts that one can “hide'' a complex Gaussian matrix as a submatrix of the symmetric product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with all input modes squeezed, which is a setup that has recently been realized experimentally \cite{madsen2022}. In this setting, the hiding conjecture states that a o ( M ) × o ( M ) submatrix of an M × M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M → ∞ . This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with the maximum number of squeezed input modes on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)] \cite{aa}.

DOI
10.22331/q-2026-10-27-2248

Related papers

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•0 citations

Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

Fei Meng, Bin Cheng, Jianan Li +1 more

Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.

quant-pharXiv:2607.22088•Jul 27, 2026•0 citations

The Complexity of Bipartite Gaussian Boson Sampling

Daniel Grier, Daniel J. Brod, Juan Miguel Arrazola +2 more

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

arXiv:2110.06964•Quantum•Nov 28, 2022•41 citations

Uniform Hiding and Two Routes to Relative Accuracy in Gaussian Boson Sampling

Hongru Zhao

Gaussian boson sampling requires control of how closely finite optical matrices follow Gaussian reference laws. We prove an explicit total variation bound of order $N^2/M$ between a rescaled Haar transpose Gram block and its Gaussian transpose Gram counterpart, where $N$ is the detected photon count and $M$ is the number of optical modes. The bound establishes quantitative product hiding uniformly over every number of squeezed inputs. The proof combines Stiefel recursion, centered circular orthogonal ensemble scores, and a rectangular entropy estimate. Applications combine hiding with local hafnian bounds to obtain relative probability guarantees and connect them to sampler error through exact photon-sector normalization.

quant-pharXiv:2609.01008•Sep 2, 2026•0 citations

Sufficient conditions for hardness of lossy Gaussian boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.

quant-pharXiv:2511.07853•Nov 12, 2025•0 citations

A complexity transition in displaced Gaussian Boson sampling

Zhenghao Li, Naomi R. Solomons, Jacob F. F. Bulmer +2 more

Abstract Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications, a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem Displaced GBS. By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.

npj Quantum Information•Jul 9, 2025•0 citations
Gaussian boson sampling (GBS) is a promising protocol for demonstrating quantum computational advantage. One of the key steps in the argument for classical hardness of GBS is the so-called “hiding conjecture'', which asserts that one can “hide'' a complex Gaussian matrix as a submatrix of the symmetric product of Haar unitary submatrices in total variation distance. In this paper, we prove the hiding conjecture for input states with all input modes squeezed, which is a setup that has recently been realized experimentally \cite{madsen2022}. In this setting, the hiding conjecture states that a o ( M ) × o ( M ) submatrix of an M × M circular orthogonal ensemble (COE) random matrix can be well-approximated by a complex symmetric Gaussian matrix in total variation distance as M → ∞ . This is the first rigorous proof of the hiding property for GBS in the experimentally relevant regime, and puts the argument for hardness of classically simulating GBS with the maximum number of squeezed input modes on a comparable level to that of the conventional boson sampling of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013)] \cite{aa}.
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.
Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.
Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.
Gaussian boson sampling requires control of how closely finite optical matrices follow Gaussian reference laws. We prove an explicit total variation bound of order N2/MN^2/MN2/M between a rescaled Haar transpose Gram block and its Gaussian transpose Gram counterpart, where NNN is the detected photon count and MMM is the number of optical modes. The bound establishes quantitative product hiding uniformly over every number of squeezed inputs. The proof combines Stiefel recursion, centered circular orthogonal ensemble scores, and a rectangular entropy estimate. Applications combine hiding with local hafnian bounds to obtain relative probability guarantees and connect them to sampler error through exact photon-sector normalization.
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.
Abstract Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications, a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem Displaced GBS. By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.