Graph entropy and quantum sorting problems

Let P = (X, 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).

Authors

• Andrew Chi-Chih Yao

Keywords

• graph entropy
• information lower bound
• partial order
• quantum algorithms
• sorting