10 problems

Let $X_1$ and $X_2$ be independent quantum computing errors in an $n$-qubit computation, with variances $V_1(X_1)$ and $V_2(X_2)$, respectively. Variance formula conjecture. The va…

Let $E_n$ be the explicit family of $n$-dimensional ellipsoids considered in the cited problem, accessed through a membership oracle. Determine the quantum membership-query complex…

For each $n$, let $X=\mathbb{F}_2^n$ and $N=|X|=2^n$. Let $r=(r_x)_{x\in X}$ be a fixed table of $n$-bit strings, and define $f_{h,r}:X\to X\times X\times\{0,1\}^n$ by…

Given local random-neighbor access to an unknown unweighted graph $G$ with $n$ vertices, let $N_G$ denote its normalized adjacency matrix and let…

For every $T$-query quantum algorithm $A$, there is a polynomial $p$ such that, for every $\epsilon,\delta>0$, there exists a classical randomized query algorithm $C$ making at mos…

For $N=2^n$, let $s\in\mathbb{Z}_N$ be hidden. Given polynomially many independent copies of the mixed coset state…

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

Let $V$ be a finite-dimensional complex vector space, and let $R$ be a unitary solution to the Yang–Baxter equation on $V^{\otimes 2}$. Suppose that $R$ has finite projective order…

Let $\mathcal{C}$ be a braided fusion category and let $X$ be a simple object of $\mathcal{C}$. Denote by $\rho_X$ the braid-group representations on…

Let $c3_{risk}$ and $c3_{returns}$ denote the standard deviations of portfolio risk and returns, respectively, as defined in modern portfolio theory. Let $b6$ be a lower bound infl…