This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordere...
详细信息
ISBN:
(纸本)3540228233
This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordered search problem. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our argument shows that the multiple-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation that is also supplemented with advice. Our argument is also applied to the notions of computational complexity theory: quantum truth-table reducibility and quantum truth-table autoreducibility.
暂无评论