Information-theoretic lower bounds for quantum sorting

Jean Cardinal, Gwenaël Joret, Jérémie Roland

We analyze the quantum query complexity of sorting under partial information. In this problem, we are given a partially ordered set $P$ and are asked to identify a linear extension…