An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
<|reference_start|>An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation: 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 in which, given a block number i, we are to find a location of a target keyword in an ordered list of the i-th block. 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.<|reference_end|>
@article{nishimura2003an,
    title={An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on
  Advised Quantum Computation},
    author={Harumichi Nishimura and Tomoyuki Yamakami},
    journal={Proceedings of the 29th International Symposium on Mathematical
  Foundations of Computer Science (MFCS2004), Lecture Notes in Computer Science
  3153, pp. 827-838, 2004},
    year={2003},
    doi={10.1007/978-3-540-28629-5_65},
    archivePrefix={arXiv},
    eprint={quant-ph/0312003},
    primaryClass={quant-ph cs.CC}
}