This thesis investigates uniform mixing on Cayley graphs over Z_3^d. We apply Mullin's results on Hamming quotients, and characterize the 2(d+2)-regular connected Cayley graphs over Z_3^d that admit uniform mixing at time 2pi/9. We generalize Chan's construction on the Hamming scheme H(d,2) to the scheme H(d,3), and find some distance graphs of the Hamming graph H(d,3) that admit uniform mixing at time 2pi/3^k for any k≥2. To restrict the mixing time, we derive a sufficient and necessary condition for uniform mixing to occur on a Cayley graph over Z_3^d at a given time. Using this, we obtain three results. First, we give a lower bound of the valency of a Cayley graph over Z_3^d that could admit uniform mixing at some time. Next, we prove that no Hamming quotient H(d,3)/<1> admits uniform mixing at time earlier than 2pi/9. Finally, we explore the connected Cayley graphs over Z_3^3 with connected complements, and show that five complementary graphs admit uniform mixing with earliest mixing time 2pi/9.

The inverse Chevalley formula in the equivariant K-theory of semi-infinite flag manifolds of type An−1 is given as a sum over a set of quantum walks in the quantum Bruhat graph, QBG(An−1). We establish bounds on the number of quantum steps and simple stationary steps in these quantum walks. By a result of Kato, we map this formula to the equivariant quantum K-theory of partial flag manifolds G/P to give an alternate proof of [KLNS24, Theorem 8]. / Doctor of Philosophy / The quantum Bruhat graph, is a directed graph with vertex set W . Beginning with an arbitrary element of W , at each position, we may either move to a new element of W along a directed edge (a non-stationary step), or stay at the current element (a stationary step). A quantum walk is the sequence that records the element W at each position. We establish bounds on the number of occurrences of particular kinds of stationary and non-stationary steps called simple stationary steps and quantum steps respectively. These bounds are relevant to calculations of Chevalley formulas in K-Theory.

Indiana University-Purdue University Indianapolis (IUPUI) / Over the last two decades a new theory has been developed and intensively investigated in quantum physics. The theory stipulates that a non-Hermitian Hamiltonian can also represents a physical system as long as its energy spectra can be purely real in certain regime depending on the parameters of the Hamiltonian. It was demonstrated that the reality of the eigenenergy was conditioned by a certain kind of symmetry embedded in the actual non-Hermitian system. Indeed, such systems have a combined reflection (parity) symmetry (P) and time-reversal symmetry (T), PT-symmetry. The theory opens the door to new features particularly in open systems in which there could be gain and/or loss of particle or energy from and/or to the environment. A key property of the theory is the PT-symmetry breaking transition which occurs at the exceptional point (EP). The exceptional points are special degeneracies characterized by a coalescence of not only the eigenvalues but also of the corresponding eigenvectors of the system; and the coalescence happens when the gain-loss strength, a measure of the openness of the system, exceeds the intrinsic energy-scale of the system. In recent years, quantum walks with PT-symmetric non-unitary time evolution have been realized in systems with balanced gain and loss. These systems fall in two categories namely continuous time quantum walks (CTQW) that are characterized by a unitary or non-unitary time evolution Hamiltonian, and discrete-time quantum walks (DTQW) whose dynamic is described by a unitary or non-unitary time evolution operator consisting of a product of shift, coin, and gain-loss operations. In this thesis, we investigate the PT-symmetric phase of CTQW and DTQW in a variety of non-Hermitian lattice systems with both position-dependent and position independent, parity-symmetric tunneling functions in the presence of PT-symmetric impurities located at arbitrary parity-symmetric site on the lattice. Moreover, we explore the topological phase diagram and its novel features in non-Hermitian, homogeneous and non-homogeneous, PT-symmetric DTQW with closed and open boundary conditions. We conduct our study using analytical and numerical approaches that are directly and easily implementable in physical experiments. Among others, we found that, despite their non-unitary evolution, open systems governed by parity-time symmetric Hamiltonian support conserved quantities and that the PT-symmetry breaking threshold depends on the physical structure of the Hamiltonian and its underlying symmetries.

Submitted by Maria Cristina (library@lncc.br) on 2015-11-25T13:28:47Z No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-11-25T13:29:04Z (GMT) No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) / Made available in DSpace on 2015-11-25T13:29:13Z (GMT). No. of bitstreams: 1 dissertacao-aaron.pdf: 1893812 bytes, checksum: f036c76c3f4c1ba338a4e1075106ced6 (MD5) Previous issue date: 2015-11-04 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / The development of quantum algorithms is not a easy task. Elements such as entanglement and quantum paralelism, intrinsics to quantum computation, difficult this task. Quantum walks are crucial tools for development of algorithms, mainly search algorithms. There are many types of quantum walks: with coin toss, Szegedy's, using tessellation (grouping of vertices) and the continuous-time quantum walk. To extract statistics data of a quantum walk, we need to perform its simulation. In this work, we develped the simulator Hiperwalk, a new simulator of quantum walks in graphs of one and two dimension for the quantum walk with a coin toss and coinless using tessellation. The Hiperwalk allows the user to perform simulations of quantum walks in graphs using high performance computing (HPC), even though the user does not knowing parallel programming. The user can employ the parallel devices such as CPU, GPGPU and accelerators cards to speedup the overall process of the walk. / O desenvolvimento de algoritmos quânticos não é uma tarefa trivial. Elementos como emaranhamento e paralelismo quântico, intrínsecos à computação quântica, dificultam esta tarefa. As caminhadas quânticas são ferramentas cruciais para o desenvolvimento de algoritmos, principalmente algoritmos de busca. Existem na literatura vários tipos de caminhadas: com lançamento de moeda, de Szegedy, utilizando tesselagem (agrupamento de vértices) e a caminhada a tempo contínuo. Para extrair dados estatísticos de uma determinada caminhada quântica, necessitamos fazer sua simulação. Neste trabalho, desenvolvemos o simulador Hiperwalk, um novo simulador de caminhadas quânticas, em grafos de uma e duas dimensões para as caminhadas com moeda e sem moeda utilizando tesselagem. O Hiperwalk permite ao usuário efetuar simulações de caminhadas quânticas em grafos utilizando processamento de alto desempenho, mesmo que o usuário não saiba programação paralela. O usuário pode empregar os dispositivos de paralelismo como CPU, GPGPU e co-processadores para acelerar o processo geral da caminhada.

One of the newer and rapidly developing approaches in quantum computing is based on "quantum walks," which are quantum processes on discrete space that evolve in either discrete or continuous time and are characterized by mixing of components at each step. The idea emerged in analogy with the classical random walks and stochastic techniques, but these unitary processes are very different even as they have intriguing similarities. This thesis is concerned with study of discrete-time quantum walks. The original motivation from classical Markov chains required for discrete-time quantum walks that one adds an auxiliary Hilbert space, unrelated to the one in which the system evolves, in order to be able to mix components in that space and then take the evolution steps accordingly (based on the state in that space). This additional, "coin," space is very often an internal degree of freedom like spin. We have introduced a general framework for construction of discrete-time quantum walks in a close analogy with the classical random walks with memory that is rather different from the standard "coin" approach. In this method there is no need to bring in a different degree of freedom, while the full state of the system is still described in the direct product of spaces (of states). The state can be thought of as an arrow pointing from the previous to the current site in the evolution, representing the one-step memory. The next step is then controlled by a single local operator assigned to each site in the space, acting quite like a scattering operator. This allows us to probe and solve some problems of interest that have not had successful approaches with "coined" walks. We construct and solve a walk on the binary tree, a structure of great interest but until our result without an explicit discrete time quantum walk, due to difficulties in managing coin spaces necessary in the standard approach. Beyond algorithmic interests, the model based on memory allows one to explore effects of history on the quantum evolution and the subtle emergence of classical features as "memory" is explicitly kept for additional steps. We construct and solve a walk with an additional correlation step, finding interesting new features. On the other hand, the fact that the evolution is driven entirely by a local operator, not involving additional spaces, enables us to choose the Fourier transform as an operator completely controlling the evolution. This in turn allows us to combine the quantum walk approach with Fourier transform based techniques, something decidedly not possible in classical computational physics. We are developing a formalism for building networks manageable by walks constructed with this framework, based on the surprising efficiency of our framework in discovering internals of a simple network that we so far solved. Finally, in line with our expectation that the field of quantum walks can take cues from the rich history of development of the classical stochastic techniques, we establish starting points for the work on non-Abelian quantum walks, with a particular quantum walk analog of the classical "card shuffling," the walk on the permutation group. In summary, this thesis presents a new framework for construction of discrete time quantum walks, employing and exploring memoried nature of unitary evolution. It is applied to fully solving the problems of: A walk on the binary tree and exploration of the quantum-to-classical transition with increased correlation length (history). It is then used for simple network discovery, and to lay the groundwork for analysis of complex networks, based on combined power of efficient exploration of the Hilbert space (as a walk mixing components) and Fourier transformation (since we can choose this for the evolution operator). We hope to establish this as a general technique as its power would be unmatched by any approaches available in the classical computing. We also looked at the promising and challenging prospect of walks on non-Abelian structures by setting up the problem of "quantum card shuffling," a quantum walk on the permutation group. Relation to other work is thoroughly discussed throughout, along with examination of the context of our work and overviews of our current and future work. / Graduation date: 2012

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. We will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. Let A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. We will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. Let A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated. / Mathematics

Quantum random walks are a generalization of classical Markovian random walks to a quantum mechanical or quantum computing setting. Quantum walks have promising applications but are complicated by quantum decoherence. We prove that the long-time limiting behavior of the class of quantum operations which are the convex combination of norm one operators is governed by the eigenvectors with norm one eigenvalues which are shared by the operators. This class includes all operations formed by a coherent operation with positive probability of orthogonal measurement at each step. We also prove that any operation that has range contained in a low enough dimension subspace of the space of density operators has limiting behavior isomorphic to an associated Markov chain. A particular class of such operations are coherent operations followed by an orthogonal measurement. Applications of the convergence theorems to quantum walks are given. / Mathematics

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.