Lower bounds for quantum decision trees.

摘要

The speedup of quantum algorithms over classical algorithms has been the main driving force for the current interests in quantum computing. Although dramatic speedups seem possible, as Shor's polynomial time quantum algorithms for factoring and for finding discrete logarithms suggest, provable speedups are only found in very restricted models, such as the decision trees.; In the decision tree model, the inputs x₁, x₂,…,x_n are known to an oracle, and the only way that the algorithm can access the inputs is to ask the oracle questions of the type: “x_i = ?”. The complexity measure is the number of queries used.; Many problems can be naturally formulated in this model. On the one hand many provable quantum speedups have been found. On the other hand, much progress has also been made in proving quantum lower bounds, which reveal the limitations of the quantum computational power. This dissertation is along the latter lines. We prove the following lower bound results. (a) The quantum decision tree complexity of any function is lower bounded by its average sensitivity , which measures how likely the function value will change if a random input is changed in a random coordinate. (b) With a natural quantification of the amount of information, each classical query can only obtain at most, 1 bit of information about the input, while a quantum query can obtain up to Θ(log n) bits. In contrast to an example in which one quantum query obtains log n bits of information, we show that in computing any total function, on average each quantum query can obtain at most some constant number of bits of information. (c) We prove that any comparison-based quantum algorithm for sorting n numbers must compare Ω(n log n) times. If no error is allowed, at least 0.110n log2 n−0.067n + O(1) comparisons are necessary. We also prove quantum lower bounds on some other problems related to sorting, such as the problems of element distinctness, matching nuts and bolts, and non-comparison-based sorting.