Published: 2014
Total Pages: 0
Get eBook
This thesis explores several theoretical questions pertaining to quantum computing. First we examine several questions regarding multi-particle quantum random walk-based algorithms for the graph isomorphism problem. We find that there exists a non-trivial difference between continuous-time walks of one and two non-interacting particles as compared to non-interacting walks of three or more particles, in that the latter are able to distinguish many strongly regular graphs (SRGs), a class of graphs with many graph pairs that are difficult to distinguish. We demonstrate analytically where this distinguishing power comes from, and we show numerically that three-particle and four-particle non-interacting continuous-time walks can distinguish many pairs of strongly regular graphs. We additionally show that this distinguishing power, while it grows with particle number, is bounded, so that no continuous-time non-interacting walk of fixed particle number can distinguish all strongly regular graphs. We then investigate the relationship between continuous-time and discrete-time walks, in the context of the graph isomorphism problem. While it has been previously demonstrated numerically that discrete-time walks of non-interacting particles can distinguish some SRGs, we demonstrate where this distinguishing power comes from. We also show that while no continuous-time non-interacting walk of fixed particle number can distinguish SRGs, it remains a possibility that such a discrete-time walk could, leaving open the possibility of a non-trivial difference between discrete-time and continuous-time walks. The last piece of our work on graph isomorphism examines limitations on certain kinds of continuous-time walk-based algorithms for distinguishing graphs. We show that a very general class of continuous-time walk algorithms, with a broad class of allowable interactions, cannot distinguish all graphs. We next consider a previously-proposed quantum adiabatic algorithm for computing the PageRank vector, a necessary step in one of Google's search algorithms. It had been previously believed that this algorithm might offer a non-trivial speedup in preparing the PageRank vector. We demonstrate, however, that when this algorithm is tested on graphs that sufficiently resemble the graph of the World Wide Web, there is no appreciable speedup. Lastly, we consider the problem of Hamiltonian determination. We show that in the high temperature limit, the classical signal processing technique of compressed sensing may be used to recover the Hamiltonian for a system of qubits, provided that the Hamiltonian does not possess too many interactions, i.e., it is ``sparse''. This new procedure allows for the determination of the Hamiltonian with a number of measurements that can be significantly smaller than required by standard techniques.