Graph entropy and quantum sorting problems

ABSTRACT

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 QSORT_P with error less than ε (where 0 < ε < 1/10 is fixed). It was proved by Hoyer, 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 Korner's graph entropy that was first noted and developed by Kahn and Kim (JCSS 51(1995), 390--399).

References

1. S. Aaronson. Quantum lower bounds for the collision problem. In Proc. 34th Annual ACM Symposium on Theory of Computing, pages 635--642. ACM, 2002.
2. A. Ambainis. A better lower bound for quantum algorithms searching an ordered list. In Proc. 40th Annual IEEE Symposium on Foundations of Computer Science, pages 352--357. IEEE, 1999.
3. A. Ambainis. Quantum lower bounds by quantum arguments. In Proc. 32nd Annual ACM Symposium on Theory of Computing, pages 636--643. ACM, 2000.
4. R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science, pages 352--361. IEEE, 1998.
5. C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computation. SIAM J. on Computing, 26:1510--1523, 1997.
6. H. Buhrman and R. de Wolf. A lower bound for quantum search of an ordered list. Information Processing Letters, 70:205--209, 1999.
7. C. Csiszar, J. Korner, L. Lovasz, K. Marton, and G. Simonyi. Entropy splitting for antiblocking corners and perfect graphs. Combinatorica, 10:27--40, 1990.
8. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. A limit on the speed of quantum computation for insertion into an ordered list. arXiv. org e-Print archive, quant-ph/9812057, 1998.
9. M. Fredman. How good is the information bound in sorting. Theoretical Computer Science, 1:355--361, 1976.
10. P. Hoyer, J. Neerbek, and Y. Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34:429--448, 2002.
11. J. Kahn and J. Kim. Entropy and sorting. Journal of Computer and System Sciences, 51:390--399, 1995.
12. J. Kahn and N. Linial. Balancing poset extensions via Brunn-Minkowski. Combinatorica, 11:363--368, 1991.
13. J. Kahn and M. Saks. Balancing poset extensions. Order, 1:113--126, 1984.
14. J. Korner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Transactions of 6th Prague Conference on Information Theory, etc., pages 411--425. Academia, Prague, 1973.
15. J. Korner. Fredman-Komlos bounds and information theory. SIAM Journal on Alg. Disc. Meth., 7:560--570, 1986.
16. I. Newman, P. Ragde, and A. Wigderson. Perfect hashing, graph entropy and circuit complexity. In Proc. 5th Annual IEEE Symposium on Structure in Complexity Theory, pages 91--100. IEEE, 1990.
17. J. Radhakhrishnan. Better bounds for threshold formulas. In Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science, pages 314--323. IEEE, 1991.
18. Y. Shi. Entropy lower bounds of quantum decision tree complexity. Information Processing Letters, 81(1):23--27, 2002.
19. Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 513--519. IEEE, 2002.
20. G. Simonyi. Perfect graphs and graph entropy: An updated survey. Chapter 13 in Perfect Graphs, edited by J. Ramirez-Alfonsin and B. Reed, pages 293--328. John Wiley and Sons, 2001.
21. R. Stanley. Two poset polytopes. Discrete Computational Geometry, 1:9--23, 1986.

Index Terms

• Theory of computation

  • Models of computation

    • Abstract machines