Graph entropy and quantum sorting problems

Let P = (X, <p) be a partial order on a set of n elements X = {x ₁,x₂, . . ., x_n}. Define the quantum sorting problem QSORT p as: given n distinct numbers x₁, x₂, . . .,x_n consistent with P, sort them by a quantum decision tree using comparisons of the form "x_i : x_j". Let Qε(P) be the minimum number of queries used by any quantum decision tree for solving QSORTp with error less than ε (where 0 < ε < 1/10 is fixed). It was proved by Høyer, Neerbek and Shi (Algorithmica 34 (2002), 429-448) that, when P₀ is the empty partial order, Qε(P ₀) ≥ Ω(n log n), i.e., the classical information lower bound holds for quantum decision trees when the input permutations are unrestricted. In this paper we show that the classical information lower bound holds, up to an additive linear term, for quantum decision trees for any partial order P. Precisely, we prove Qε(P) ≥ c log₂ e(P) -c′n where c, c′ > 0 are constants and e(P) is the number of linear orderings consistent with P. Our proof builds on an interesting connection between sorting and Körner's graph entropy that was first noted and developed by Kahn and Kim (JCSS 51(1995), 390-399).