The quantum query complexity of sorting under partial information
185 views · Published 18 December 2017 · 49:50 · Indexed 10 November 2026
Channel: Institut Henri Poincaré · 2017 · Science & Technology
By Jérémie Roland (Brussels)
Abstract: 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.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...