8 problems

Let $U_{NK}$ be the top-left $N\times K$ submatrix of an $M\times M$ Haar-random unitary matrix. Let $Z=Z_{N,K}$ be a random matrix distributed according to either…

CoRE-hardness conjecture. Deciding which of these two cases holds is $\mathrm{coRE}$-hard; equivalently, $\mathrm{MIP}^{\mathrm{co}}=\mathrm{coRE}$.

Let $G$ be sampled uniformly from graph states, and let $d4af$ be the set of eigenstates of the operators $X+Y$ and $X-Y$. For an $n$-qubit product state, write…

Let $U$ be a quantum circuit drawn from a distribution $\mathcal{D}$, and let … A classical algorithm is polynomial-time if it runs in time polynomial in the circuit description an…

Let $\mathbb{T}$ denote the unit circle, let $X$ be sampled from the complex Gaussian ensemble $\mathcal{G}=\mathcal{N}_{\mathbb{C}}(0,1)^{n\times n}$, and let…

Let $V$ be a passive or active fermionic linear-optics circuit initialized in the state $\left|\Psi_{\mathrm{in}}\right>$, let $\mathbf{x}_0$ be a fiducial outcome, and let…

Quantum supremacy conjecture. There is no classical randomized algorithm that performs RCS to inverse-polynomial total variation-distance error.

Informal supremacy conjecture. Approximating to $1/\operatorname{poly}(n)$ multiplicative error most amplitudes of most quantum circuits is a $\#P$-hard problem.