Quantum walks are very useful tools in designing quantum algorithms. Amplitude amplification is a key technique to increase the success probability of a quantum-walk-based algorithm, and it is quadratically faster than classical probabilistic amplification. However, amplitude amplification only applies to quantum walks with one-shot hitting time, where no measurements except a final one are performed, and not to quantum walks with concurrent hitting time, where measurements happen or absorbing boundaries exist at each step. In this paper, we propose a procedure to modify quantum walks with concurrent hitting time by removing measurements from them. This procedure enables us to use amplitude amplification to design algorithms based on the modified quantum walks which are faster than those based on the original walks with a concurrent hitting time and more robust than those based on the corresponding walks with a one-shot hitting time.
Quantum walks are very useful tools in designing quantum algorithms. Amplitude amplification is a key technique to increase the success probability of a quantum-walk-based algorithm, and it is quadratically faster than classical probabilistic amplification. However, amplitude amplification only applies to quantum walks with one-shot hitting time, where no measurements except a final one are performed, and not to quantum walks with concurrent hitting time, where measurements happen or absorbing boundaries exist at each step. In this paper, we propose a procedure to modify quantum walks with concurrent hitting time by removing measurements from them. This procedure enables us to use amplitude amplification to design algorithms based on the modified quantum walks which are faster than those based on the original walks with a concurrent hitting time and more robust than those based on the corresponding walks with a one-shot hitting time.
Abstract Quantum walks are powerful tools for building quantum search algorithms. However, these success probabilities are far below 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problem follows. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in the practical application of the algorithm when the optimal number of steps is unknown. In this work, we define generalized interpolated quantum walks instead of amplitude amplification, which can not only improve the success probability but also avoid the soufflé problem. We choose a special case of generalized interpolated quantum walks and construct a series of new search algorithms based on phase estimation and quantum fast-forwarding, respectively. Especially, by combining our interpolated quantum walks with quantum fast-forwarding, we both reduce the time complexity of the search algorithm from Θ ( ( ε − 1 ) H T ) to Θ ( log ( ε − 1 ) HT ) and reduce the number of ancilla qubits required from Θ ( log ( ε − 1 ) + log H T ) to Θ ( log log ( ε − 1 ) + log H T ) , where ɛ denotes the precision and H T denotes the classical hitting time. In addition, we show that our generalized interpolated quantum walks can improve the construction of quantum stationary states corresponding to reversible Markov chains. Finally, we give an application to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
We propose a new framework for turning quantum search algorithms that decide into quantum algorithms for finding a solution. Consider we are given an abstract quantum search algorithm A that can determine whether a target g exists or not. We give a general construction of another operator U that both determines and finds the target, whenever one exists. Our amplification method at most doubles the cost over using A, has little overhead, and works by controlling the evolution of A. This is the first known general framework to the open question of turning abstract quantum search algorithms into quantum algorithms for finding a solution. We next apply the framework to random walks. We develop a new classical algorithm and a new quantum algorithm for finding a unique marked element. Our new random walk finds a unique marked element using H update operations and 1/eps checking operations. Here H is the hitting time, and eps is the probability that the stationary distribution of the walk is in the marked state. Our classical walk is derived via quantum arguments. Our new quantum algorithm finds a unique marked element using H^(1/2) update operations and 1/eps^(1/2) checking operations, up to logarithmic factors. This is the first known quantum algorithm being simultaneously quadratically faster in both parameters. We also show that the framework can simulate Grover's quantum search algorithm, amplitude amplification, Szegedy's quantum walks, and quantum interpolated walks.
In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk P and a single marked state, the quantum walk corresponding to P can find the solution using a number of queries that is quadratically smaller than the classical hitting time of P. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.
Quantum walks are powerful tools for building quantum search algorithms or quantum sampling algorithms named the construction of quantum stationary state. However, the success probability of those algorithms are all far away from 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problems follow. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in practical application of the algorithm when the optimal number of steps is not known. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the soufflé problems. Then we combine generalized interpolation quantum walks with quantum fast-forwarding. The combination both reduce the times of calling walk operator of searching algorithm from $Θ((\varepsilon^{-1})\sqrt{\Heg})$ to $Θ(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla qubits required from $Θ(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to $Θ(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem is avoided while the success probability is improved, where ε denotes the precision and $\Heg$ denotes the classical hitting time. Besides, we show that our generalized interpolated quantum walks can be used to improve the construction of quantum states corresponding to stationary distributions as well. Finally, we give an application that can be used to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.
Quantum walks play an important role in the area of quantum algorithms. Many interesting problems can be reduced to searching marked states in a quantum Markov chain. In this context, the notion of quantum hitting time is very important, because it quantifies the running time of the algorithms. Markov chain-based algorithms are probabilistic, therefore the calculation of the success probability is also required in the analysis of the computational complexity. Using Szegedy's definition of quantum hitting time, which is a natural extension of the definition of the classical hitting time, we present analytical expressions for the hitting time and success probability of the quantum walk on the complete graph.