<p>Quantum phenomena related to geometric and topological phases are investigated. The first results presented are theoretical extensions of these phases and related effects. Also experimental proposals to measure some of the described effects are outlined. Thereafter, applications of geometric and topological phases in quantum computation are discussed.</p><p>The notion of geometric phases is extended to cover mixed states undergoing unitary evolutions in interferometry. A comparison with a previously proposed definition of a mixed state geometric phase is made. In addition, an experimental test distinguishing these two phase concepts is proposed. Furthermore, an interferometry based geometric phase is introduced for systems undergoing evolutions described by completely positive maps.</p><p>The dynamics of an Aharonov-Bohm system is investigated within the adiabatic approximation. It is shown that the time-reversal symmetry for a semi-fluxon, a particle with an associated magnetic flux which carries half a flux unit, is unexpectedly broken due to the Aharonov-Casher modification in the adiabatic approximation.</p><p>The Aharonov-Casher Hamiltonian is used to determine the energy quantisation of neutral magnetic dipoles in electric fields. It is shown that for specific electric field configurations, one may acquire energy quantisation similar to the Landau effect for a charged particle in a homogeneous magnetic field.</p><p>We furthermore show how the geometric phase can be used to implement fault tolerant quantum computations. Such computations are robust to area preserving perturbations from the environment. Topological fault-tolerant quantum computations based on the Aharonov-Casher set up are also investigated.</p>

<p>Quantum holonomies are investigated in different contexts.</p><p>A geometric phase is proposed for decomposition dependent evolution, where each component of a given decomposition of a mixed state evolves independently. It is shown that this geometric phase only depends on the path traversed in the space of decompositions.</p><p>A holonomy is associated to general paths of subspaces of a Hilbert space, both discrete and continuous. This opens up the possibility of constructing quantum holonomic gates in the open path setting. In the discrete case it is shown that it is possible to associate two distinct holonomies to a given path. Interferometric setups for measuring both holonomies are</p><p>provided. It is further shown that there are cases when the holonomy is only partially defined. This has no counterpart in the Abelian setting.</p><p>An operational interpretation of amplitudes of density operators is provided. This allows for a direct interferometric realization of Uhlmann's parallelity condition, and the possibility of measuring the Uhlmann holonomy for sequences of density operators.</p><p>Off-diagonal geometric phases are generalized to the non-Abelian case. These off-diagonal holonomies are undefined for cyclic evolution, but must contain members of non-zero rank if all standard holonomies are undefined. Experimental setups for measuring the off-diagonal holonomies are proposed.</p><p>The concept of nodal free geometric phases is introduced. These are constructed from gauge invariant quantities, but do not share the nodal point structure of geometric phases and off-diagonal geometric phases. An interferometric setup for measuring nodal free geometric phases is provided, and it is shown that these phases could be useful in geometric quantum computation.</p><p>A holonomy associated to a sequence of quantum maps is introduced. It is shown that this holonomy is related to the Uhlmann holonomy. Explicit examples are provided to illustrate the general idea.</p>

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

Quantum phenomena related to geometric and topological phases are investigated. The first results presented are theoretical extensions of these phases and related effects. Also experimental proposals to measure some of the described effects are outlined. Thereafter, applications of geometric and topological phases in quantum computation are discussed. The notion of geometric phases is extended to cover mixed states undergoing unitary evolutions in interferometry. A comparison with a previously proposed definition of a mixed state geometric phase is made. In addition, an experimental test distinguishing these two phase concepts is proposed. Furthermore, an interferometry based geometric phase is introduced for systems undergoing evolutions described by completely positive maps. The dynamics of an Aharonov-Bohm system is investigated within the adiabatic approximation. It is shown that the time-reversal symmetry for a semi-fluxon, a particle with an associated magnetic flux which carries half a flux unit, is unexpectedly broken due to the Aharonov-Casher modification in the adiabatic approximation. The Aharonov-Casher Hamiltonian is used to determine the energy quantisation of neutral magnetic dipoles in electric fields. It is shown that for specific electric field configurations, one may acquire energy quantisation similar to the Landau effect for a charged particle in a homogeneous magnetic field. We furthermore show how the geometric phase can be used to implement fault tolerant quantum computations. Such computations are robust to area preserving perturbations from the environment. Topological fault-tolerant quantum computations based on the Aharonov-Casher set up are also investigated.

Quantum holonomies are investigated in different contexts. A geometric phase is proposed for decomposition dependent evolution, where each component of a given decomposition of a mixed state evolves independently. It is shown that this geometric phase only depends on the path traversed in the space of decompositions. A holonomy is associated to general paths of subspaces of a Hilbert space, both discrete and continuous. This opens up the possibility of constructing quantum holonomic gates in the open path setting. In the discrete case it is shown that it is possible to associate two distinct holonomies to a given path. Interferometric setups for measuring both holonomies are provided. It is further shown that there are cases when the holonomy is only partially defined. This has no counterpart in the Abelian setting. An operational interpretation of amplitudes of density operators is provided. This allows for a direct interferometric realization of Uhlmann's parallelity condition, and the possibility of measuring the Uhlmann holonomy for sequences of density operators. Off-diagonal geometric phases are generalized to the non-Abelian case. These off-diagonal holonomies are undefined for cyclic evolution, but must contain members of non-zero rank if all standard holonomies are undefined. Experimental setups for measuring the off-diagonal holonomies are proposed. The concept of nodal free geometric phases is introduced. These are constructed from gauge invariant quantities, but do not share the nodal point structure of geometric phases and off-diagonal geometric phases. An interferometric setup for measuring nodal free geometric phases is provided, and it is shown that these phases could be useful in geometric quantum computation. A holonomy associated to a sequence of quantum maps is introduced. It is shown that this holonomy is related to the Uhlmann holonomy. Explicit examples are provided to illustrate the general idea.

We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. We accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. The result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

Recent advances in quantum computational science promise substantial improvements in the speed with which certain classes of problems can be computed. Various algorithms that utilize the distinctively non-classical characteristics of quantum mechanics have been formulated to take advantage of this promising new approach to computation. One such algorithm was formulated by David Deutsch and Richard Jozsa. By measuring the output of a quantum network that implements this algorithm, it is possible to determine with N 1 measurements certain global properties of a function f(x), where N is the number of network inputs. Classically, it may not be possible to determine these same properties without evaluating f(x) a number of times that rises exponentially as N increases. Hitherto, the potential power of this algorithm has been explored in the context of qubits, the quantum computational analogue of classical bits. However, just as one can conceive of classical computation in the context of non-binary logic, such as ternary or quaternary logic, so also can one conceive of corresponding higher-order quantum computational equivalents.<p>This thesis investigates the behaviour of the Deutsch-Jozsa algorithm in the context of these higher-order quantum computational forms of logic and explores potential applications for this algorithm. An important conclusion reached is that, not only can the Deutsch-Jozsa algorithms known computational advantages be formulated in more general terms, but also a new algorithmic property is revealed with potential practical applications.

We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. We accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. The result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

This thesis deals with the question of what resources are necessary and sufficient for quantum computational speedup. In particular, we study what resources are required to promote fault tolerant stabilizer computation to universal quantum computation. In this context we discover a remarkable connection between the possibility of quantum computational speedup and negativity in the discrete Wigner function, which is a particular distinguished quasi-probability representation for quantum theory. This connection allows us to establish a number of important results related to magic state computation, an important model for fault tolerant quantum computation using stabilizer operations supplemented by the ability to prepare noisy non-stabilizer ancilla states. In particular, we resolve in the negative the open problem of whether every non-stabilizer resource suffices to promote computation with stabilizer operations to universal quantum computation. Moreover, by casting magic state computation as resource theory we are able to quantify how useful ancilla resource states are for quantum computation, which allows us to give bounds on the required resources. In this context we discover that the sum of the negative entries of the discrete Wigner representation of a state is a measure of its usefulness for quantum computation. This gives a precise, quantitative meaning to the negativity of a quasi-probability representation, thereby resolving the 80 year debate as to whether this quantity is a meaningful indicator of quantum behaviour. We believe that the techniques we develop here will be widely applicable in quantum theory, particularly in the context of resource theories.

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.