11 problems

Let $\pi=\sigma^{-1}\tau\ne e$, let $L_0(\sigma)$ be the planar loop count, and let $g(\sigma,\pi)$ be the genus determined by the bare ribbon gluing. Let $L_\Gamma(\sigma,\pi)$ be…

Let $n$ be the number of excitations and let the transition matrix be chosen from the Haar ensemble. Consider the operator norm of the map from the $d$-fold bunched subspace back i…

Let $U$ be a Haar-random unitary matrix, and let $\operatorname{perm}(U)$ denote its permanent. The quantity $n!$ is the relevant Gaussian-scale second moment, and…

Randomized-test hardness conjecture. These randomized tests are computationally hard to pass using classical means, provided there is enough experimental data.

Let $P_\text{BS}$ be the output probability distribution of Boson Sampling with $n$ input photons and $m$ modes, where the input is $\ket1^{\otimes n}\otimes\ket 0^{\otimes m-n}$ a…

Classically hard-regime conjecture. The classically hard regime exists in the red region: there, $U(t)$ does not satisfy known conditions for computing and/or sampling the distribu…

Let ${\mathcal G^{k \times k}}$ be the distribution of random $k\times k$ matrices whose entries are independent complex Gaussian random variables with mean $0$ and variance $1$. T…

Gaussian boson sampling is a variant of boson sampling in which squeezed Gaussian states are used as input. A network is unbalanced when its losses are not uniform across the optic…

Gaussian boson sampling uses squeezed Gaussian states as input to a linear-optical network. Let $k$ denote the number of input modes containing squeezed states, and let…

Extended Church–Turing thesis. A Turing machine can efficiently simulate any efficient computational process in the real world.

Let $m\geq n$ be integers. Let $\mathcal{H}_{m,n}$ be the distribution of $\sqrt{m}$ times the upper-left $n\times n$ submatrix of a Haar-distributed $m\times n$ matrix with orthon…