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

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

108Distinct questions 99Unsolved 9Solved
Fields
Most frequent topics

Random unsolved problem

Unsolved op_17bba2d8f41697f6

Quantum query complexity of Welded Tree path-finding

Does finding an explicit ENTRANCE-to-EXIT path in the standard Welded Tree oracle problem require exponentially many quantum queries?

For an integer \(n\geq 2\), construct a graph \(G_n\) from two complete binary trees of depth \(n\). Designate the root of the left tree as ENTRANCE \(s\) and the root of the right tree as EXIT \(t\). Join the \(2^n\) leaves of the left tree and the \(2^n\) leaves of the right tree into a uniformly random cycle that alternates between leaves of the two trees. Assign the vertices distinct random binary labels of length \(2n\).

The algorithm is given the label of \(s\) and coherent quantum-query access to an adjacency-list oracle. The oracle is a static function of vertex labels: for every valid vertex label, including labels guessed without prior traversal, it returns the labels of the vertex’s neighbors, and it returns distinguished invalid outputs only for labels that are not vertices and for missing neighbor slots. Validity of a queried label is independent of the algorithm’s query history, and coherent queries may be arbitrary superpositions of label strings.

The path-finding task is to output an explicit sequence of vertex labels \(v_0,v_1,\ldots,v_\ell\) satisfying

\begin{equation} v_0=s, \qquad v_\ell=t, \qquad \{v_{j-1},v_j\}\in E(G_n) \quad \text{for every }1\leq j\leq\ell . \tag{1} \end{equation}

Let \(Q_{\mathrm{WTPath}}(n)\) denote the minimum number of oracle queries used by a quantum algorithm that outputs a valid path satisfying (1) with bounded error on the standard random Welded Tree oracle distribution. The open question is whether there exists a constant \(c>0\) such that, for all sufficiently large \(n\),

\begin{equation} Q_{\mathrm{WTPath}}(n) \geq 2^{cn}. \tag{2} \end{equation}

Equivalently, does the exponential quantum-query lower bound in (2) hold for unrestricted quantum algorithms?

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 →