Graph entropy and quantum sorting problems

ABSTRACT

Let P = (X, < P) be a partial order on a set of n elements X = x1, x2,..., xn. Define the quantum sorting problem QSORTP as: given n distinct numbers x1, x2,..., xn consistent with P, sort them by a quantum decision tree using comparisons of the form "xi: xj". 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 Hoyer, Neerbek and Shi (Algorithmica 34 (2002), 429--448) that, when P0 is the empty partial order, Qε(P0) ≥ Ω (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 log2 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: Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509999]
• 2: Andris Ambainis, A Better Lower Bound for Quantum Algorithms Searching an Ordered List, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.352, October 17-18, 1999
• 3: Andris Ambainis, Quantum lower bounds by quantum arguments, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.636-643, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335394]
• 4: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum Lower Bounds by Polynomials, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.352, November 08-11, 1998
• 5: Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
• 6: Harry Buhrman , Ronald de Wolf, A lower bound for quantum search of an ordered list, Information Processing Letters, v.70 n.5, p.205-209, June 21, 1999 [doi>10.1016/S0020-0190(99)00069-1]
• 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: Jeff Kahn , Jeong Han Kim, Entropy and sorting, Journal of Computer and System Sciences, v.51 n.3, p.390-399, Dec. 1995 [doi>10.1006/jcss.1995.1077]
• 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ános Körner, Fredman-Kolmo´s bounds and information theory, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.560-570, Oct. 1986 [doi>10.1137/0607062]
• 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: Jaikumar Radhakrishnan, Better bounds for threshold formulas, Proceedings of the 32nd annual symposium on Foundations of computer science, p.314-323, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185384]
• 18: Y. Shi. Entropy lower bounds of quantum decision tree complexity. Information Processing Letters, 81(1):23--27, 2002.
• 19: Yaoyun Shi, Quantum Lower Bounds for the Collision and the Element Distinctness Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.513-519, November 16-19, 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: Richard P. Stanley, Two poset polytopes, Discrete & Computational Geometry, v.1 n.1, p.9-23, 1986 [doi>10.1007/BF02187680]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory

Keywords:
graph entropy, information lower bound, partial order, quantum algorithms, sorting