Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.
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(K), the symmetric product MK−1/2UNKUNKT, for UNK the top left N×K submatrix of an M×M Haar random unitary U, is close in total variation distance to both an N×N symmetric complex Gaussian matrix G with independent entries, and the symmetric product GGT/K for G an N×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.
Bipartite Gaussian boson sampling (BipartiteGBS) produces output probabilities governed by squared permanents of submatrices of arbitrary complex matrices, matching the nonsymmetric structure of directed graphs. Most GBS-based graph algorithms, however, rely on symmetric hafnian structure and are formulated for undirected problems. Here we propose a BipartiteGBS-based framework for directed-graph heuristic optimization. We introduce Max-Perm as a canonical optimization task for BipartiteGBS and derive a closed-form sampling enhancement factor relative to uniform classical sampling in this idealized setting. We then use permanent-biased BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem. Numerical experiments on Erdős--Rényi random directed graphs show that the resulting BipartiteGBS-enhanced algorithms improve success rates over a standard genetic algorithm and yield longer valid paths when no Hamiltonian cycle is found, while ablation tests indicate that BipartiteGBS-guided initialization is the dominant contributor. These results show how permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search.
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}.