REVIEW 5 cited by
Complexity-theoretic foundations of BosonSampling with a linear number of modes
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of {particles} to modes -- all current hardness evidence assumes a dilute regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a saturated regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a new worst-to-average-case reduction for computing the Permanent which is robust to both large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime.
Forward citations
Cited by 5 Pith papers
-
Proof of Hiding Conjecture in Gaussian Boson Sampling
The top-left N by N submatrix of an M by M circular orthogonal ensemble random matrix, scaled by sqrt(M), converges to a complex symmetric Gaussian matrix in total variation distance for N much smaller than sqrt(M).
-
Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling
Random Gaussian permanents satisfy a weak anti-concentration bound: they rarely dip superexponentially below their standard deviation.
-
Near-Optimal Mode Scaling for Finite-Dimensional Boson Sampling via Lie-Algebraic Leakage Bounds
Bunching leakage for finite-d Lie-algebraic boson sampling concentrates at Õ(√n), tightening modes from Ω(n⁴) to Õ(n^{1+2/(d-1)}), with d=3 matching the collision-free threshold.
-
Hardness and Complexity Transition of Noisy Random Circuit Sampling
Under the standard ideal-RCS #P-hardness conjecture, noisy random circuit sampling remains hard for depolarizing noise γ = O(log n/(nd)), and matching simulability results make γ = Θ(log n/(nd)) the transition scale.
-
Quantum Supremacy through Fock State $q$ boson Sampling with Transmon Qubits
A transmon's nonlinear spectrum can be approximated by a q-boson with q=1+K/omega, and the paper argues this enables Fock-state q-boson sampling with potential quantum supremacy.
Discussion (0). Continue with ORCID to comment.