This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.
This thesis addresses two questions related to the title, Quantum Computation, Markov Chains and Combinatorial Optimisation. The first question involves an algorithmic primitive of quantum computation, quantum walks on graphs, and its relation to Markov Chains. Quantum walks have been shown in certain cases to mix faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. We design a lifted Markov chain that in some sense simulates any quantum walk. Concretely, we construct a lifted Markov chain on a connected graph G with n vertices that mixes exactly to the average mixing distribution of a quantum walk on G. Moreover, the mixing time of this chain is the diameter of G. We then consider practical consequences of this result. In the second part of this thesis we address a classic unsolved problem in combinatorial optimisation, graph isomorphism. A theorem of Kozen states that two graphs on n vertices are isomorphic if and only if there is a clique of size n in the weak modular product of the two graphs. Furthermore, a straightforward corollary of this theorem and Lovász’s sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in n. We enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. Interesting cases include complete multipartite graphs and disjoint unions of cliques. We find that all perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices. Open questions and further research directions are discussed.
Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with n2D(G) vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph G with n vertices, where D(G) is the diameter of G. Moreover, the mixing time of this chain is D(G) timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in n. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).
We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.
Quantum walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems.These links and acceleration claims have been made with various levels of detail.Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph.Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain.We here show that the same speedup can be attained with a classical process, if a similar classical coin is added.We establish a precise correspondence between the mixing performance of quantum walks and such "lifted walks" for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time.We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design.However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster.
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2
Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.