Random unsolved problem

Unsolved op_39721600d81c6992

Quantum query complexity of Graph Collision

Does Graph Collision on every known \(n\)-vertex graph admit a bounded-error quantum algorithm using \(\widetilde O(\sqrt n)\) queries to the marked-vertex bits? Let \(G=([n],E)\) be a simple undirected graph given in full, and let \(x\in\{0,1\}^n\) be accessible through the quantum oracle \(O_x|v,b\rangle=|v,b\oplus x_v\rangle\). The task is to compute

\begin{equation} f_G(x)=\bigvee_{\{u,v\}\in E}(x_u\wedge x_v). \tag{1} \end{equation}

Only calls to \(O_x\) are counted. All computation involving the known graph is free, and the algorithm must return the value in (1) with probability at least \(2/3\) for every \(x\).

Let \(Q_2(f_G)\) be the minimum worst-case query count under this guarantee, and let \(Q_{\mathrm{GC}}(n)=\max_{G:\,|V(G)|=n}Q_2(f_G)\). The question is whether

\begin{equation} Q_{\mathrm{GC}}(n)=\widetilde O(\sqrt n). \tag{2} \end{equation}

In (2), \(\widetilde O\) hides only factors polynomial in \(\log n\) as \(n\to\infty\).

Open problem page

Random solved problem

Solved op_c37d38eda1436c12

Information causality for almost-quantum correlations

Do all almost-quantum correlations satisfy information causality? A bipartite conditional distribution \(p(a,b\mid x,y)\) with finite input and output sets is almost quantum if there are a Hilbert space \(\mathcal H\), a unit vector \(|\psi\rangle\), and projective measurements \(\{P_a^x\}_a\), \(\{Q_b^y\}_b\) on \(\mathcal H\) such that

\begin{equation} P_a^x Q_b^y|\psi\rangle=Q_b^y P_a^x|\psi\rangle, \qquad p(a,b\mid x,y)=\langle\psi|P_a^x Q_b^y|\psi\rangle. \tag{1} \end{equation}

Each measurement consists of orthogonal projections summing to the identity. The commutation condition in (1) is imposed only on the shared state, not as an operator identity.

Alice receives \(L\) independent uniform bits \(Z_1,\ldots,Z_L\). Bob receives an independent uniform index \(J\in\{1,\ldots,L\}\). They may use shared randomness and almost-quantum boxes independent of these inputs. Alice sends Bob an \(m\)-bit classical message, with no communication from Bob to Alice, and Bob outputs a binary guess \(G\) for \(Z_J\). Information causality requires

\begin{equation} \sum_{j=1}^{L} I(Z_j:G\mid J=j)\leq m, \tag{2} \end{equation}

where \(I\) is Shannon mutual information in bits. Must (2) hold for every finite protocol of this form and all integers \(L\geq1\) and \(m\geq0\)?

Open problem page

Activity

Recently edited

All problems by date →