58 problems

Average-case hardness conjecture. Approximating the corresponding amplitudes up to a multiplicative error is $\textsc{\#P}$-hard on average. This conjecture concerns the average-ca…

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…

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…

Radix-independence conjecture. As $k$ tends to infinity, the free model of the axioms using square roots coincides with that using cube roots or roots for any other radix.

Let $p$ be prime, and let $\ell_1,\ldots,\ell_r$ be primes in an interval with $X\asymp Y\asymp\log^4 p$, as in the source. Let $\varepsilon$ denote the separation parameter for th…

Let $\mathrm{NLSPL}$ be the extension of the stabiliser programming language with arbitrary classical operations, and let $c$ and $d$ be well-formed judgements in $\mathrm{NLSPL}$.…

The paper develops a denotational semantics for stabiliser quantum programs and considers the equivalence relation induced by the set of measurement outcomes that can occur. Full-a…

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…

Abstract-symmetry conjecture. The abstract symmetries of each torus $\varTheta$ can be used to implement logical Clifford gates for general LCA codes.

Let $G$ be a graph, let $V_G$ denote its vertex set, and let $|\chi\rangle$ be a magic graph state whose parameters are varied over the collection $\{\theta_{ij}\}$. Let…

A quantum circuit family using unbounded quantum AND-gates and single-qubit gates is a QAC-circuit. The converse of the known simulation of quantum AND-gates by constant-depth circ…

Let $\mathsf{P}$ be the class of decision problems solvable in polynomial time by a classical computer, let $\NP$ be the class of decision problems whose solutions can be verified…

The unknot has trivial homology, so its Hodge Laplacian has a two-dimensional ground-state kernel. Efficient cooling conjecture. It may be possible to efficiently cool the Hodge La…

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.

For odd-prime-dimensional qudits, the Wigner polytope is the set of states with non-negative discrete Wigner function; a pure magic state is a pure non-stabilizer state usable as a…

Contextuality is a property of quantum states manifested through measurements whose outcomes cannot be explained by a noncontextual hidden-variable model. Universal quantum computa…

Rajakumar et al.'s conjecture. Determining a shortest graph compilation for a given graph $G$, equivalently finding a compilation using the fewest number of $H_{\mathrm{Ising}}$ pu…

Quantum gradient-estimation conjecture. There exists a quantum algorithm for this task whose query complexity matches the lower bound established in the paper. The paper gives a qu…

A function $f(x)$ may take infinitely many values, although sampling gives a finite number of evaluated values. Quantum Church–Turing thesis. Given sufficient resources, a quantum…

Early-break conjecture. A finer analysis of the dynamics of the weight should show that, with high probability, this early-break condition is met before the runtime stated in Propo…

Simulation conjecture. Methods to provably avoid barren plateaus typically enable efficient classical simulation, either using purely classical resources or after an initial data-a…

Chen et al.'s conjecture. Better mixing properties might be attained by means of linear combinations of Gaussian filters without loss of KMS symmetry.