29 problems

Quantum closest-vector approximation conjecture. There is no polynomial time quantum algorithm which can approximate the closest vector problem within a polynomial factor.

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…

The paper considers a reversible quantum measurement performed by a hypothetical insider observer, equivalently a quantum measurement in a quantum-space background such as the fuzz…

Finite-field equations define zeta functions whose zeroes can be studied through their spectral data. The proposed correspondence is between these zeroes and the eigenvalues of fin…

Let $H$ be the hypergraph under consideration, with $N$ vertices, uniformity $r$, and matching number $\nu(H)$. Let $\operatorname{rt}_H$ denote the alternative routing number base…

Let $\mathrm{BPP}$ denote the class of decision problems solvable by probabilistic classical algorithms in bounded-error polynomial time, and let $\mathrm{BQP}$ denote the class so…

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…

Let $\mathrm{IF}$ denote the integer factorization problem, and let $\mathrm{P}$ and $\mathrm{NP}$ denote the standard classical complexity classes. A problem is NP-intermediate if…

General-sphere variance conjecture. For general random variables on $S^d$ with $d\geq 2$, Theorem holds.

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…

A quantum neural network is a parametrized quantum circuit whose output is used to generate a function, and a barren plateau is a regime in which training gradients become exponent…

Let $H_1$ and $H_2$ be the two Hamiltonian terms in a second-order Trotter product formula, and consider input quantum states for the two orderings $H_1H_2H_1$ and $H_2H_1H_2$. Asy…

Let an RSA-type semiprime be a product of two suitably large primes, and let Shor's algorithm denote the quantum algorithm for integer factorisation. Quantum factorisation conjectu…

Let $G$ be an infinite group, and consider the Hidden Subgroup Problem (HSP) for $G$, namely the problem of determining a hidden subgroup from oracle access to a function that is c…

Tensor-train operation extension conjecture. Other operations with Tensor Trains should also be extendable to quantum computers; in particular, multiplication by a TT-matrix appear…

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

A sampling task is one in which a computer produces samples from a target probability distribution $\pi$. A noisy intermediate-scale quantum (NISQ) computer is a quantum computer w…

Quantum adiabatic graph-isomorphism conjecture. The Quantum Adiabatic prescription can differentiate between all non-isomorphic graphs, given an appropriate choice of problem and d…

Let $\mathcal{A}$ be an architecture over circuits, let $\mathcal{H}_{\mathcal{A}}$ be the distribution over circuits in $\mathcal{A}$ whose local gates are independently drawn fro…

A NISQ computer is a noisy intermediate-scale quantum computer, including a noisy quantum circuit, and the noise level is a parameter describing the strength of the noise. NISQ noi…

A quantum computer is a computational model using qubits, unitary quantum gates, and measurement; polynomial-time quantum computation refers to quantum circuits of polynomial size.…

The paper considers infinite mutual coinduction as a generalization of mutual coinduction involving an infinite, possibly countable or uncountable, number of orderings and generato…

The paper considers infinite mutual coinduction as a generalization of mutual coinduction involving an infinite, possibly countable or uncountable, number of orderings and generato…

Let $P$ be a poset. Write $\mathrm{LB}(P)$ for the classical lower bound and $\mathrm{QLB}(P)$ for the quantum lower bound associated with sorting under partial information. Consta…

Let $P$ be a partial order, let $\Delta(P)$ denote the set of its linear extensions, and let $\textsc{Sort}_P$ be the problem of sorting subject to the comparisons already specifie…