An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation
Harumichi Nishimura, Tomoyuki Yamakami · arXiv (Cornell University) · 2003
This paper proves lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordered search problems. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our proof employs an argument that (i) commences with the faulty assumption that a quantum algorithm of low query complexity exists, (ii) select any incompressible input, and (iii) constructs another algorithm that compresses the input, which leads to a contradiction.Using this ``algorithmic'' argument, we show that the multi-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation supplemented by advice. This main theorem can be applied directly to two important notions in structural complexity theory: nonadaptive (truth-table) reducibility and autoreducibility. In particular, we prove: 1) there is an oracle A relative to which there is a set in P^A which is not quantumly nonadaptively reducible to A in polynomial time even with polynomial advice; 2) there is a polynomial-time adaptively probabilistically-autoreducible set which is not polynomial-time nonadaptively quantum-autoreducible even with any help of polynomial advice, and; 3) there is a set in ESPACE which is not polynomial-time nonadaptively quantum-autoreducible in polynomial time even in the presence of polynomial advice. For the single-block ordered search problem, our algorithmic argument also shows a large lower bound of the quantum query complexity in the presence of advice.