Application of graph theory in quantum computer science
arXiv:2109.12978
Abstract
In this dissertation we demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. We consider two aspects of this problem. First, it is known that the standard Continuous-Time Quantum Walk (CTQW), proposed by Childs and Goldstone, can propagate quickly on the infinite path graph. However, the Schrödinger equation requires the Hamiltonian to be symmetric, and thus only undirected graphs can be implemented. In this thesis, we address the question, whether it is possible to construct a continuous-time quantum walk on general directed graphs, preserving its propagation properties. Secondly, the quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. However, most of these graphs have very simple structures. The most advanced results concerned the Erdős-Rényi model of random graphs, which is the most popular but not realistic random graph model, and Barabási-Albert random graphs, for which full quadratic speed-up was not confirmed. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
arXiv commentPhD thesis, IITiS PAN, minor fixes based on comments from reviewers. Code available at https://github.com/iitis/adam_glos_phd
References in corpus (30)
- Statistical mechanics of complex networks
- A variational eigenvalue solver on a quantum processor
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- Quantum algorithms: an overview
- Spatial search by quantum walk
- An example of the difference between quantum and classical random walks
- Stabilizing Open Quantum Systems by Markovian Reservoir Engineering
- Spatial search by quantum walk is optimal for almost all graphs
- Spectral measure of large random Hankel, Markov and Toeplitz matrices
- Limit Theorem for Continuous-Time Quantum Walk on the Line
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Quantum Navigation and Ranking in Complex Networks
- Connectivity is a Poor Indicator of Fast Quantum Search
- Singular value decomposition and matrix reorderings in quantum information theory
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Optimal quantum spatial search on random temporal networks
- On the optimality of spatial search by continuous-time quantum walk
- Continuous-Time Quantum Search on Balanced Trees
- Quantum spatial search on graphs subject to dynamical noise
- Finding a marked node on any graph by continuous-time quantum walk
- Central limit theorem for reducible and irreducible open quantum walks
- Continuous-time quantum walk spatial search on the Bollobás scale-free network
- Central Limit Theorem and Large Deviation Principle for Continuous Time Open Quantum Walks
- QSWalk.jl: Julia package for quantum stochastic walks analysis
- Space-efficient binary optimization for variational computing
- Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
- Impact of global and local interaction on quantum spatial search on chimera graph
- Nonlinear Quantum Search
- Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs