93 citations · 114 across the 5 of their papers we have counts for
Showing 2000Show all
2 papers · 1 filter
quant-ph2000
Quantum lower bound for sorting
Yaoyun Shi
We prove that Ω(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed,…
quant-ph2000
Entropy lower bounds of quantum decision tree complexity
Yaoyun Shi
We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the…