Quantum Information and Quantum Computation
Open Problem Zoo
Random Unsolved Solved
Updated 8 September 2026

Click Search to explore the suggested topic, or type your own query. Press / to start typing.

102Distinct questions 93Unsolved 9Solved
Fields
Most frequent topics

Random unsolved problem

Unsolved op_36ac6718d2c37628

Polynomial-time quantum algorithm for approximate Shortest Vector Problem

Does the polynomial-factor approximate Shortest Vector Problem admit a polynomial-time quantum algorithm?

Let \(B\in\mathbb Q^{n\times n}\) be a nonsingular lattice basis whose entries have polynomially bounded bit length, and let

\begin{equation} \mathcal L(B)=\{Bz:z\in\mathbb Z^n\}\subset\mathbb R^n . \tag{1} \end{equation}

Define the length of a shortest nonzero lattice vector by

\begin{equation} \lambda_1(\mathcal L)=\min_{v\in\mathcal L\setminus\{0\}}|v|_2 . \tag{2} \end{equation}

For an approximation factor \(\gamma=\gamma(n)\geq 1\), the \(\gamma\)-approximate Shortest Vector Problem asks for a nonzero vector \(v\in\mathcal L(B)\) satisfying

\begin{equation} |v|_2\leq\gamma(n)\lambda_1(\mathcal L(B)). \tag{3} \end{equation}

The open question is whether, for polynomial approximation factors such as \(\gamma(n)=n^c\) for a fixed constant \(c>0\), there exists a bounded-error quantum algorithm that outputs a vector satisfying (3) in time polynomial in the bit length of \(B\).

Open problem page

Random solved problem

Solved op_a381e2ccd80cec9c

Additivity of the relative entropy of entanglement

Does the relative entropy of entanglement of every bipartite state equal its regularization, or is regularization genuinely necessary? For a finite-dimensional bipartite system \(A{:}B\), write \(\operatorname{Sep}(A{:}B)\) for the set of separable states and \(D(\rho\Vert\sigma)=\operatorname{Tr}[\rho(\log_2\rho-\log_2\sigma)]\) for the Umegaki relative entropy, defined when \(\operatorname{supp}\rho\subseteq\operatorname{supp}\sigma\), with the trace evaluated on \(\operatorname{supp}\rho\) and \(0\log_2 0:=0\). Define the relative entropy of entanglement and its regularization by

\begin{equation} E_R(\rho) :=\min_{\sigma\in\operatorname{Sep}(A{:}B)}D(\rho\Vert\sigma), \qquad E_R^\infty(\rho) :=\lim_{n\to\infty}\frac1nE_R\bigl(\rho^{\otimes n}\bigr). \tag{1} \end{equation}

The limit in Eq. (1) exists and equals \(\inf_{n\geq1}\frac1nE_R(\rho^{\otimes n})\) by Fekete’s lemma: the product of minimizing separable states is separable and \(D\) is additive on tensor products, which gives the subadditivity \(E_R(\rho\otimes\sigma)\leq E_R(\rho)+E_R(\sigma)\), and subadditivity implies convergence of the normalized terms to their infimum, not that each of them is nonincreasing. The archived question is whether single copies already suffice, that is, whether

\begin{equation} E_R^\infty(\rho)=E_R(\rho) \quad\text{for every finite-dimensional bipartite state }\rho. \tag{2} \end{equation}

Since \(E_R^\infty(\rho)\leq E_R(\rho)\) always holds, Eq. (2) can only fail strictly, through a single state \(\rho\) with

\begin{equation} E_R^\infty(\rho)<E_R(\rho). \tag{3} \end{equation}
Open problem page

Activity

Recently edited

All problems by date →