In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist.
With the purpose of finding new techniques to develop quantum algorithms, there has been
an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development.
We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators.
In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive.
Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require
classical hardware and software.
Quantum walks can be used either as tools for quantum algorithm development or as entanglement generators, potentially useful to test quantum hardware. We present a novel algorithm based on a discrete Hadamard quantum walk on a line with one coin and two walkers whose purpose is to generate entanglement between walkers. We provide several classical computer simulations of our quantum algorithm in which we show that, although the asymptotical amount of entanglement generated between walkers does not reach the highest degree of entanglement possible at each step for either coin measurement outcome, the entanglement ratio (entanglement generated/highest value of entanglement possible, for each step) tends to converge, and the actual convergence value depends on the coin initial state and on the coin measurement outcome. Furthermore, our numerical simulations show that, for the quantum walks used in our algorithm, the value towards which entanglement ratio converges also depends on the position probability distribution symmetry of a quantum walk computed with one single walker and the same coin initial state employed in the corresponding quantum walk with two walkers.
The field of quantum information applies the concepts of quantum physics to problems in computer science, and shows great potential for allowing efficient computation. \nIn this thesis I concentrate on a particular quantum information theoretic tool known as the quantum walk. There are two widely studied versions of the quantum walk, the continuous time walk, and the discrete time walk. The discrete time walk is particularly amenable to investigation using numerical methods, from which most of the results in this thesis are derived, and is the main focus of the work presented. Two aspects of the discrete time walk are investigated: their transport properties \nand their interpretation as quantum computers. I investigated the transport properties in two ways, by looking for a particular type of transport known as perfect \nstate transfer, and examining the transport properties of a new type of coin operator. \nThe search for perfect state transfer concentrated on modifications of small cycles. I found that perfect state transfer is rare for the choices of coin operators \ntested. The structures tested for perfect state transfer were based on cycles, and it appears that the type of modification has more of an effect than the size of the \ncycle. This makes intuitive sense, as the modifications found to lead to walks exhibiting perfect state transfer affected only the initial and target node of the cycle. \nI then investigated a new type of coin operator which does not allow amplitude to return to the node it has come from. This effectively simulates a dimer. Using the general form of this type of operator and random variables for each parameter, I found that the expected distance of the walker from the origin, and standard deviation, were independent of the initial condition. The second half of the thesis concentrates on computational applications of quantum \nwalks using the language acceptance model. I first note their equivalence to a type of quantum automaton known as the QFA-WOM, and this provides an intuitive understanding of the role of the WOM. I then use a more direct construction to show that they can accept a range of formal languages. Using this construction allows us to use superpositions of words as inputs, and the insights provided by investigating these suggest a new way of approaching the problem of quantum state discrimination.
Quantum computing aims to harness and exploit the quantum mechanical phenomena such as superposition, entanglement and contextuality in order to encode and process information. In this context, quantum walks, which has been suggested as the quantum counterpart of classical random walks, is an emerging topic in quantum computing that provides powerful techniques for developing new quantum algorithms, quantum simulation and quantum state transfer. This thesis intends to investigate the properties of quantum walks which may potentially promote further work in such techniques in quantum computation. We first propose a novel method for transferring arbitrary unknown qubit state between two points in space with quantum walk architecture. We determine the cases providing perfect state transfers over both finite and infinite lattices with different boundary conditions and we introduce recovery operators assisting the transfer process. Next, by modeling the incoherent and coherent transport with classical random walks and quantum walks, respectively, we calculate the transport efficiencies over an explosive percolation lattice. We show that the minimal correlation between discrete clusters leads to maximal localizations which originating from random scatterings. These localization effects, however, are rather small when compared to the supportive effect of the abrupt growth of the largest cluster on transport efficiency, which eventually allows us to obtain more efficient transports in case of minimal correlations. We support our results with further calculations on whether the eigenstates of the systems we study are localized or not. Lastly, we turn our attention to the spreading dynamics and the coin-position entanglement for two-dimensional quantum walks under an artificial magnetic fields by introducing Peierls phases to the system. In particular, we show that the spreading of the quantum walk is diffusive rather than ballistic when the ratio of the magnetic flux through unit cell - where the walk takes place - to the flux quantum is an irrational number. On the contrary, the walk recovers its original ballistic behavior when this ratio is chosen to be a rational number. Furthermore, we demonstrate that coin-position entanglement is nearly maximum under an artificial magnetic field, even for large number of steps.
Quantum computing is a developing field that applies the properties of quantum mechanics to develop solutions to complex problems that the most powerful classical computers cannot solve or cannot solve efficiently. Solving difficult tasks requires sophisticated and efficient algorithms that can utilize stochastic processes as the primary techniques. The typical models of these stochastic processes include discrete-time random walks and continuous ones. Quantum walks represent a quantum extension of discrete random walks, whose demonstrated utility in algorithm design has motivated signi cant interest in quantum computational research. Therefore, the purpose of this thesis is to explore the potential of discrete-time coined quantum walks using the Python package with high-performance computing (HPC) compared to classical walks by conducting a literature review. To supplement this research, some simulations are implemented to analyze the spreading behavior of coined quantum walks, compare them with classical walks, and demonstrate their application in search tasks, such as binary hypercube search algorithm. These simulations aim to clarify the extent to which quantum walks can be effectively modeled and applied in computational contexts. The results gained show that coined quantum walks exhibit faster spreading than classical random walks, which contributes to a deeper understanding of potential applications of quantum walks, such as quantum simulation, in the future.
We introduce a generalization of quantum walks with entangled coins consisting of a model of discrete quantum walks with coin pairs under various degrees of entanglement and walkers in quantum superposition as initial states. We introduce novel position probability distributions that may be used for algorithm development based on quantum-mechanical phenomena. Also, we numerically show that the skewness of position probability distribution produced by using coin initial state with various degrees of entanglement cannot be easily inferred.