Study of Cubelike Graphs for Parallel and Quantum Computation

Abstract

In this thesis, we study Cayley graphs over Znr for their utility in multiprocessorcomputing and quantum computing. For multiprocessor computing, we investigateproblems of graph embedding on cubelike interconnection networks suchas hypercubes and augmented cubes. These embeddings are required for efficientsimulation of divide-and-conquer based algorithms on multiprocessor systemsbuilt on such interconnection networks. In particular, we discuss Havel�sconjecture which states that an equibipartite binary tree on 2n vertices spans then-dimensional hypercube. We develop an efficient embedding technique to provethe conjecture for a subfamily of equibipartite binary tree. We also worked ona related conjecture which states that a binary tree on 2n vertices spans the ndimensionalaugmented cube. For this, we propose a recursive technique to embedand a method to count the spanning binary trees of the augmented cube. Forexploring the utility of cubelike graphs for quantum computation, we study quantumwalks that can be used to develop quantum algorithms for searching andcommunication. We study both theoretical and experimental aspects of quantumwalks on cubelike graphs as well as Cayley graphs over Znr . For discrete-timequantum walk, our work gives a closed form for the quantum state of the systemassociated with cubelike graphs, after finitely many time steps; this work is thekey to studying hitting times on the graphs which is a measure of how quickly thewalker reaches a specific target node. We also decompose the quantum circuits ofthe corresponding evolution operators that were run on IBM�s quantum computingplatform. We conjecture that there is a linear relation between the quantumhitting times and dimension of cubelike graphs. For continuous-time quantumwalk, we investigate weighted Cayley graphs over Znr in order to classify them into three categories of graphs - those that admit PST, those that do not admit PSTbut are periodic, and those that are not periodic. In continuation to this work, weconstructed quantum circuits of the evolution operators for CTQW on weightedcubelike graphs.