In Part I of this thesis, we present a new model of quantum cellular automata (QCA) based on local unitary operations. We will describe a set of desirable properties for any QCA model, and show that all of these properties are satisfied by the new model, while previous models of QCA do not. We will also show that the computation model based on Local Unitary QCA is equivalent to the Quantum Circuit model of computation, and give a number of applications of this new model of QCA. We also present a physical model of classical CA, on which the Local Unitary QCA model is based, and Coloured QCA, which is an alternative to the Local Unitary QCA model that can be used as the basis for implementing QCA in actual physical systems. In Part II, we explore the quantum separability problem, where we are given a density matrix for a state over two quantum systems, and we are to determine whether the state is separable with respect to these systems. We also look at the converse problem of finding an entanglement witness, which is an observable operator which can give a verification that a particular quantum state is indeed entangled. Although the combined problem is known to be NP-hard in general, it reduces to a convex optimization problem, and by exploiting specific properties of the set of separable states, we introduce a classical algorithm for solving this problem based on an Interior Point Algorithm introduced by Atkinson and Vaidya in 1995. In Part III, we explore the use of a low-depth AQFT (approximate quantum Fourier transform) in quantum phase estimation. It has been shown previously that the logarithmic-depth AQFT is as effective as the full QFT for the purposes of phase estimation. However, with sub-logarithmic depth, the phase estimation algorithm no longer works directly. In this case, results of the phase estimation algorithm need classical post-processing in order to retrieve the desired phase information. A generic technique such as the method of maximum likelihood can be used in order to recover the original phase. Unfortunately, working with the likelihood function analytically is intractable for the phase estimation algorithm. We develop some computational techniques to handle likelihood functions that occur in phase estimation algorithms. These computational techniques may potentially aid in the analysis of certain likelihood functions.

This thesis is about minimal transitive factorizations of permutations into transpositions. We focus on finding direct combinatorial proofs for the cases where no such direct combinatorial proofs were known. We give a description of what has been done previously in the subject at the direct combinatorial level and in general. We give some new proofs for the known cases. We then present an algorithm that is a bijection between the set of elements in {1, ..., k} dropped into n cyclically ordered boxes and some combinatorial structures involving trees attached to boxes, where these structures depend on whether k > n, k = n or k < n. The inverse of this bijection consists of removing vertices from trees and placing them in boxes in a simple way. In particular this gives a bijection between parking functions of length n and rooted forests on n elements. Also, it turns out that this bijection allows us to give a direct combinatorial derivation of the number of minimal transitive factorizations into transpositions of the permutations that are the product of two disjoint cycles.

The cycle space of a finite graph is the subspace of the edge space generated by the edge sets of cycles, and is a well-studied object in graph theory. Recently progress has been made towards extending the theory of cycle spaces to infinite graphs. Graph-like spaces are a class of topological objects that reconcile the combinatorial properties of infinite graphs with the topological properties of finite graphs. They were first introduced by Thomassen and Vella as a natural, general class of topological spaces for which Menger's Theorem holds. Graph-like spaces are the natural objects for extending classical results from topological graph theory and cycle space theory to infinite graphs. This thesis focuses on the topological properties of embeddings of graph-like spaces, as well as the algebraic properties of graph-like spaces. We develop a theory of embeddings of graph-like spaces in surfaces. We also show how the theory of edge spaces developed by Vella and Richter applies to graph-like spaces. We combine the topological and algebraic properties of embeddings of graph-like spaces in order to prove an extension of MacLane's Theorem. We also extend Thomassen's version of Kuratowski's Theorem for 2-connected compact locally connected metric spaces to the class of graph-like spaces.

Aliferis, Gottesman and Preskill [1] reduce a non-Markovian noise model to a local noise model, under assumptions on the smallness of the norm of the system-bath interaction. They also prove constructively that given a local noise model, it is possible to simulate an ideal quantum circuit with size L and depth D up to any accuracy, using circuit constructed out of noisy gates from the Boykin set with size $L' = O(L (log L)^a)$ and depth $D'=O(D (log D)^b)$, where $a$ and $b$ are constants that depend on the error correction code that we choose and the design of the fault-tolerant architecture, in addition to more assumptions [1]. These two results combined give us a fault-tolerant threshold theorem for non-Markovian noise, provided that the strength of the effective local noise model is smaller than a positive number that depends on the fault-tolerant architecture we choose. However the ideal measurement process may involve a strong system-bath interaction which necessarily gives a local noise model of large strength. We refine the reduction of the non-Markovian noise model to the local noise model such that this need not be the case, provided that system-bath interactions from the non-ideal operations is sufficiently small. We make all assumptions that [1] has already made, in addition to a few more assumptions to obtain our result. We also give two specific instances where the norm of the fault gets suppressed by some paramater other than the norm of the system-bath interaction. These include the large ratio of the norm of the ideal Hamiltonian to the norm of the perturbation, and frequency of oscillation of the perturbation. We hence suggest finding specific phenomenological models of noise that exhibit these properties.

The security of many cryptographic schemes relies on the intractability of the discrete logarithm problem (DLP) in groups. The most commonly used groups to deploy such schemes are the multiplicative (sub)groups of finite fields and (hyper)elliptic curve groups over finite fields. The elements of these groups can be easily represented in a computer and the group arithmetic can be efficiently implemented. In this thesis we first study certain subgroups of characteristic-two and characteristic-three finite field groups, with the goal of obtaining more efficient representation of elements and more efficient arithmetic in the corresponding groups. In particular, we propose new compression techniques and exponentiation algorithms, and discuss some potential benefits and applications. Having mentioned that intractability of DLP is a basis for building cryptographic protocols, one should also take into consideration how a system is implemented. It has been shown that realistic (validation) attacks can be mounted against elliptic curve cryptosystems in the case that group membership testing is omitted. In the second part of the thesis, we extend the notion of validation attacks from elliptic curves to hyperelliptic curves, and show that singular curves can be used effectively in such attacks. Finally, we tackle a specific location-privacy problem called the nearby friend problem. We formalize the security model and then propose a new protocol and its extensions that solve the problem in the proposed security model. An interesting feature of the protocol is that it does not depend on any cryptographic primitive and its security is primarily based on the intractability of the DLP. Our solution provides a new approach to solve the nearby friend problem and compares favorably with the earlier solutions to this problem.

In Part I of this thesis, we present a new model of quantum cellular automata (QCA) based on local unitary operations. We will describe a set of desirable properties for any QCA model, and show that all of these properties are satisfied by the new model, while previous models of QCA do not. We will also show that the computation model based on Local Unitary QCA is equivalent to the Quantum Circuit model of computation, and give a number of applications of this new model of QCA. We also present a physical model of classical CA, on which the Local Unitary QCA model is based, and Coloured QCA, which is an alternative to the Local Unitary QCA model that can be used as the basis for implementing QCA in actual physical systems. In Part II, we explore the quantum separability problem, where we are given a density matrix for a state over two quantum systems, and we are to determine whether the state is separable with respect to these systems. We also look at the converse problem of finding an entanglement witness, which is an observable operator which can give a verification that a particular quantum state is indeed entangled. Although the combined problem is known to be NP-hard in general, it reduces to a convex optimization problem, and by exploiting specific properties of the set of separable states, we introduce a classical algorithm for solving this problem based on an Interior Point Algorithm introduced by Atkinson and Vaidya in 1995. In Part III, we explore the use of a low-depth AQFT (approximate quantum Fourier transform) in quantum phase estimation. It has been shown previously that the logarithmic-depth AQFT is as effective as the full QFT for the purposes of phase estimation. However, with sub-logarithmic depth, the phase estimation algorithm no longer works directly. In this case, results of the phase estimation algorithm need classical post-processing in order to retrieve the desired phase information. A generic technique such as the method of maximum likelihood can be used in order to recover the original phase. Unfortunately, working with the likelihood function analytically is intractable for the phase estimation algorithm. We develop some computational techniques to handle likelihood functions that occur in phase estimation algorithms. These computational techniques may potentially aid in the analysis of certain likelihood functions.

This thesis is about minimal transitive factorizations of permutations into transpositions. We focus on finding direct combinatorial proofs for the cases where no such direct combinatorial proofs were known. We give a description of what has been done previously in the subject at the direct combinatorial level and in general. We give some new proofs for the known cases. We then present an algorithm that is a bijection between the set of elements in {1, ..., k} dropped into n cyclically ordered boxes and some combinatorial structures involving trees attached to boxes, where these structures depend on whether k > n, k = n or k < n. The inverse of this bijection consists of removing vertices from trees and placing them in boxes in a simple way. In particular this gives a bijection between parking functions of length n and rooted forests on n elements. Also, it turns out that this bijection allows us to give a direct combinatorial derivation of the number of minimal transitive factorizations into transpositions of the permutations that are the product of two disjoint cycles.

The cycle space of a finite graph is the subspace of the edge space generated by the edge sets of cycles, and is a well-studied object in graph theory. Recently progress has been made towards extending the theory of cycle spaces to infinite graphs. Graph-like spaces are a class of topological objects that reconcile the combinatorial properties of infinite graphs with the topological properties of finite graphs. They were first introduced by Thomassen and Vella as a natural, general class of topological spaces for which Menger's Theorem holds. Graph-like spaces are the natural objects for extending classical results from topological graph theory and cycle space theory to infinite graphs. This thesis focuses on the topological properties of embeddings of graph-like spaces, as well as the algebraic properties of graph-like spaces. We develop a theory of embeddings of graph-like spaces in surfaces. We also show how the theory of edge spaces developed by Vella and Richter applies to graph-like spaces. We combine the topological and algebraic properties of embeddings of graph-like spaces in order to prove an extension of MacLane's Theorem. We also extend Thomassen's version of Kuratowski's Theorem for 2-connected compact locally connected metric spaces to the class of graph-like spaces.

Aliferis, Gottesman and Preskill [1] reduce a non-Markovian noise model to a local noise model, under assumptions on the smallness of the norm of the system-bath interaction. They also prove constructively that given a local noise model, it is possible to simulate an ideal quantum circuit with size L and depth D up to any accuracy, using circuit constructed out of noisy gates from the Boykin set with size $L' = O(L (log L)^a)$ and depth $D'=O(D (log D)^b)$, where $a$ and $b$ are constants that depend on the error correction code that we choose and the design of the fault-tolerant architecture, in addition to more assumptions [1]. These two results combined give us a fault-tolerant threshold theorem for non-Markovian noise, provided that the strength of the effective local noise model is smaller than a positive number that depends on the fault-tolerant architecture we choose. However the ideal measurement process may involve a strong system-bath interaction which necessarily gives a local noise model of large strength. We refine the reduction of the non-Markovian noise model to the local noise model such that this need not be the case, provided that system-bath interactions from the non-ideal operations is sufficiently small. We make all assumptions that [1] has already made, in addition to a few more assumptions to obtain our result. We also give two specific instances where the norm of the fault gets suppressed by some paramater other than the norm of the system-bath interaction. These include the large ratio of the norm of the ideal Hamiltonian to the norm of the perturbation, and frequency of oscillation of the perturbation. We hence suggest finding specific phenomenological models of noise that exhibit these properties.

The security of many cryptographic schemes relies on the intractability of the discrete logarithm problem (DLP) in groups. The most commonly used groups to deploy such schemes are the multiplicative (sub)groups of finite fields and (hyper)elliptic curve groups over finite fields. The elements of these groups can be easily represented in a computer and the group arithmetic can be efficiently implemented. In this thesis we first study certain subgroups of characteristic-two and characteristic-three finite field groups, with the goal of obtaining more efficient representation of elements and more efficient arithmetic in the corresponding groups. In particular, we propose new compression techniques and exponentiation algorithms, and discuss some potential benefits and applications. Having mentioned that intractability of DLP is a basis for building cryptographic protocols, one should also take into consideration how a system is implemented. It has been shown that realistic (validation) attacks can be mounted against elliptic curve cryptosystems in the case that group membership testing is omitted. In the second part of the thesis, we extend the notion of validation attacks from elliptic curves to hyperelliptic curves, and show that singular curves can be used effectively in such attacks. Finally, we tackle a specific location-privacy problem called the nearby friend problem. We formalize the security model and then propose a new protocol and its extensions that solve the problem in the proposed security model. An interesting feature of the protocol is that it does not depend on any cryptographic primitive and its security is primarily based on the intractability of the DLP. Our solution provides a new approach to solve the nearby friend problem and compares favorably with the earlier solutions to this problem.