Apparaît dans la collection : Quantum Information Theory

Sorting by comparison is probably one of the most fundamental tasks in algorithmics: given $n$ distinct numbers $x_1,x_2,. . . ,x_n$, the task is to sort them by performing comparisons of the type "$xixj$?". The minimal number of comparisons required to fulfill this task is called the (classical) query complexity, or decision tree complexity, and is well-known to be $\Theta(n\log n)$. It was also proved by Hoyer, Neerbek and Shi that quantum algorithms provide no speed-up for this problem: using the quantum adversary bound, they showed that the bounded-error quantum query complexity is also $\Theta(n\log n)$. Sorting under partial information is a natural variation of this problem where the set of numbers $X={x_1,x_2,. . . ,x_n}$ is promised to be consistent with a given partial order $P=(X,_P)$. If $e(P)$ denotes the number of linear orderings consistent with $P$, then $\log e(P)$ yields a lower bound for the classical query complexity of this problem, which was shown to be tight by constructing algorithms using $O(\log e(P)$ comparisons. An important question is whether quantum algorithms can provide a speed-up for some partial orders. Yao conjectured that this was not the case, and was able to prove a lower bound for the quantum query complexity of $c\log e(P)-c'n$. This would be tight barring for the linear correction $-c'n$, which makes the bound trivial whenever $\log e(P)=o(n)$. Building on Yao's work and interesting connections between sorting problems, graph entropies and the adversary bound, we make progress toward proving Yao's conjecture by showing an $\Omega(\log e(P)$ for an extended class of partial orders. Based on joint work (in progress) with Jean Cardinal and Gwenaël Joret.