20 problems

A graph class is vertex-minor-closed if it contains every vertex-minor of each of its graphs. Geelen's simulation conjecture. Measurement-based quantum computation (MBQC) is effici…

Let $L$ be a computational problem, let $h(L)$ be its ordinary homological complexity, and let $h_q(L)$ be a proposed quantum homological complexity measure. Quantum homological co…

Let $L$ be a decision problem in the bounded-error quantum polynomial-time class $\mathcal{BQP}$, and let $h(L)$ denote its homological complexity. Quantum homological obstruction…

Let $L$ be a computational problem with homological complexity $h(L)$. A physical system is said to solve $L$ efficiently when it computes solutions to $L$ within the relevant effi…

Classification of two-qudit Clifford hierarchy gates. Every hierarchy gate of two qudits is either a Clifford gate or can be uniquely expressed as

Quantum GapSVP hardness conjecture. There is no polynomial-time quantum algorithm that solves $\mathrm{GapSVP}$ to within polynomial factors.

Diagonalizing sequence conjecture. For every $U_0\in\operatorname{U}(2)$, the sequences satisfy

Let $\mathrm{SVP}$ denote the Shortest Vector Problem on lattices, and let a polynomial-factor approximation mean an approximation within a factor bounded by a polynomial in the la…

Let $\mathbb{A}$ be a finite algebra, and let a cube term be a term operation $t(x_1,\dots,x_n)$ such that, for every $i\in[n]$, there is a choice of $u_1,\dots,u_n\in\{x,y\}$ with…

Consider a quantum parallel computation performed by a quantum parallel random-access machine, or QPRAM, and let its efficiency be the ratio of the serial work to the product of th…

Let $P$ be an experimental atomic proposition referring to a quantum system in a pure state. Let the cost of a computation be the time required to solve the relevant computational…

Consider noisy non-interacting bosons, quantum circuits, and other quantum devices operating without quantum error correction. Kalai–Kindler noise-impossibility conjecture. (i) The…

QED is quantum electrodynamics and QCD is quantum chromodynamics. Feynman's quantum-simulation conjecture. Computations in high-energy physics, especially computations in QED and Q…

Let $d\geq 2$ be fixed, and let $\mathcal{G}\subset \mathrm{SU}(d)$ be a finite gate set that densely generates $\mathrm{SU}(d)$. An inverse-free Solovay–Kitaev theorem asserts tha…

Dimension criterion for localizability. Any simple $X\in\mcC$ is generalized or quasi-localizable if, and only if,

For finite-Fourier-series functions $f^{(1)},\ldots,f^{(k)}$, with coefficients supplied as inputs and with $n_j$ denoting the largest nonzero Fourier index of $f^{(j)}$, define th…

Partial-QFT and quadratic-phase simulation conjecture. There exist nontrivial families of abelian hypergroups for which the normalizer circuits of the paper's simulation theorem re…

Let $R_X:\mathbb C^m\otimes\mathbb C^m\longrightarrow\mathbb C^m\otimes\mathbb C^m$ be a unitary (generalized) $R$-matrix of finite order, used to define braid group representation…

Finite-group link-invariant conjecture. (a) There exists an FPRAS for computing $H_L(G)$ for any finite group $G$. (b) If $G$ is solvable, then there is a polynomial-time algorithm…

Jones-polynomial FPRAS conjecture. There is no FPRAS for evaluating $J_L(q^2)$ except at the special points $\ell\in\{1,2,3,4,6\}$, provided $RP\neq NP$.