Abstract. 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 ith 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. Keywords: algorithmic argument, query complexity, nonadaptive query, advice, quantum computation, ordered search A major contribution of this paper is the demonstration of a powerful argument, which we refer to algorithmic argument, to prove a lower bound of the nonadaptive query complexity for a multiple-block ordered search problem on advised quantum computation. In the literature, quantum query complexity lower bounds have been proven by classical adversary methods [11] , polynomial methods [8] , and quantum adversary methods [5, 7, 27] . Each method has its own strength and advantages over its simplicity, clarity, and dexterity. An algorithmic argument, however, is essentially different from these methods in its constructive manner. A basic scheme of our algorithmic argument is illustrated as follows: we (i) commence with the faulty assumption that a quantum algorithm A of low query complexity exists, (ii) define a compression scheme E that encodes each input s of fixed length into a shorter string E(s), and (iii) prove the one-to-oneness of E by constructing a decoding algorithm from A that uniquely extracts s from E(s), which leads to a conspicuous contradiction against the pigeonhole principle † . In this paper, we build a classical algorithm that decodes E(s) by simulating A in a deterministic fashion. We therefore reach the conclusion that any quantum algorithm should require high query complexity. When A further models "uniform" quantum computation, we can use resource-bounded Kolmogorov complexity ‡ as a technical tool in place of the pigeonhole principle. We apply our algorithmic argument to obtain a new nonadaptive query complexity lower bound on a query computation model, known as a black-box quantum computer (sometimes called a quantum network [8] ), in which a query is an essential method to access information stored outside of the computer. The minimal number of such queries, known as the query complexity, measures the smallest amount of information necessary to finish the desired computation. Query complexity lower bounds on various quantum computational models have been studied for numerous problems, including ordered search [4, 18, 24, 27] , unordered search [5, 8, 9, 11] , element distinctness [6, 17, 36] , and collision [1, 6, 36] . A black-box quantum computer starts with a fixed initial state (e.g., |0 · · · 0 ), accesses a given source x (which is called an "oracle") by way of queries-"what is the binary value at location i in x?"-and outputs a desired solution with small error probability. If any query (except the first one) is chosen according to the answers to its previous queries, such a query pattern is conventionally referred to as adaptive. Adaptive
Second, in REF , Nishimura and Yamakami give lower bounds on the nonadaptive quantum query complexity of a multiple-block variant of the ordered search problem.
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS2004), Lecture Notes in Computer Science 3153, pp. 827-838, 2004
Computer Science Physics