We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^ 2 3 ) query quantum algorithm. This improves the previous O(N^ 3 4 ) query quantum algorithm of Buhrman this http URL. (quant-ph 0007016) and matches the lower bound by Shi (quant-ph 0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^ k (k+1) ) query quantum algorithm.
Quantum walks. There has been considerable amount of research on quantum walks (surveyed in @cite_25 ) and their applications (surveyed in @cite_35 ). Applications of walks @cite_35 mostly fall into two classes. The first class is exponentially faster hitting times @cite_21 @cite_7 @cite_30 . In these applications, quantum walks are used to find a certain vertex exponentially faster than classically. (The first results @cite_34 @cite_21 @cite_30 were quantum walk algorithms that are exponentially faster than classical algorithms based on classical random walks. The most recent result @cite_7 is a quantum walk algorithm which is exponentially faster than any classical algorithm.) Our result is quite different from those, both in the problem that we consider and the way how we solve. While polynomial speedup achieved in our paper is smaller than exponential speedup in @cite_7 , our result has the advantage that we solve a natural problem which has been widely studied in both classical and quantum computing. The second class is quantum walk search algorithms @cite_2 @cite_1 @cite_32 .
@cite_30 @cite_35 @cite_7 @cite_21 @cite_1 @cite_32 @cite_2 @cite_34 @cite_25
2025956887 2040927484 2009948449 1727475799 1770148716 2566350286 1888573181 2611161794 2127608358
Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still unclear how to use these novel properties to gain an algorithmic speedup over classical algorithms. In this paper, we present a quantum search algorithm based on the quantum random-walk architecture that provides such a speedup. It will be shown that this algorithm performs an oracle search on a database of N items with O( radical (N)) calls to the oracle, yielding a speedup similar to other quantum search algorithms. It appears that the quantum random-walk formulation has considerable flexibility, presenting interesting opportunities for development of other, possibly novel quantum algorithms. Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order radical (N) for d>2, and in time of order radical (N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that radical (N) speedup can also be achieved on the hypercube. We show that full radical (N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order radical (N) poly(log N), and in d<4, the algorithm does not provide substantial speedup. We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time. In his seminal paper, Grover points out the prospect of faster solutions for an NP-complete problem like SAT. If there are n variables, then an obvious classical deterministic algorithm checks out all 2n truth assignments in about 2n steps, while his quantum search algorithm can find a satisfying truth assignment in about 2n 2 steps. For several NP-complete problems, many sophisticated classical algorithms have been designed. They are still exponential, but much faster than the brute force algorithms. The question arises whether their running time can still be decreased from T(n) to O (√T(n)) by using a quantum computer. Isolated positive examples are known, and some speed-up has been obtained for wider classes. Here, we present a simple method to obtain the full T(n) to O(√T(n)) speed-up for most of the many nontrivial exponential time algorithms for NP-hard problems. The method works whenever the widely used technique of recursive decomposition is employed. This included all currently known algorithms for which such a speedup has not yet been known. Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider quantum walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the Hadamard walk''''. In particular, we show that after @math time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval @math . This implies that the same walk defined on the circle mixes in linear time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs. In the near future, there will likely be special-purpose quantum computers with 40--50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the Quantum AI group at Google. We show that there's a natural average-case hardness assumption, which has nothing to do with sampling, yet implies that no polynomial-time classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work -- for example, on BosonSampling and IQP -- the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled. Second, in an attempt to refute our hardness assumption, we give a new algorithm, inspired by Savitch's Theorem, for simulating a general quantum circuit with n qubits and depth d in polynomial space and dO(n) time. We then discuss why this and other known algorithms fail to refute our assumption. Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem -- of the form "if approximate quantum sampling is classically easy, then the polynomial hierarchy collapses"-- must be non-relativizing. This sharply contrasts with the situation for exact sampling. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that there is a sampling task, namely Fourier Sampling, with a 1 versus linear separation between its quantum and classical query complexities. Fifth, in search of a "happy medium" between black-box and non-black-box arguments, we study quantum supremacy relative to oracles in P poly. Previous work implies that, if one-way functions exist, then quantum supremacy is possible relative to such oracles. We show, conversely, that some computational assumption is needed: if SampBPP = SampBQP and NP ⊆ BPP, then quantum supremacy is impossible relative to oracles with small circuits. We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the ''1-to-1 versus 2-to-1'' problem and of Hidden Translation. In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds. Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP qpoly is contained in PP poly, where BQP qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state" that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP is not contained in BQP qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. We show how to search N items arranged on a √N × √N grid in time O(√N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom. since it has been shown recently that such a continuous time walk needs time Ω(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(√N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).