Spelling suggestions: "subject:"combinatorics anda aptimization"" "subject:"combinatorics anda anoptimization""
1 
On Algorithms, Separability and Cellular Automata in Quantum ComputingCheung, Donny January 2007 (has links)
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
NPhard 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 lowdepth AQFT (approximate quantum
Fourier transform) in quantum phase estimation. It has been shown previously
that the logarithmicdepth AQFT is as effective as the full QFT for the
purposes of phase estimation. However, with sublogarithmic depth, the phase
estimation algorithm no longer works directly. In this case, results of the
phase estimation algorithm need classical postprocessing 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.

2 
A Combinatorial Interpretation of Minimal Transitive Factorizations into Transpositions for Permutations with two Disjoint CyclesPrévilleRatelle, LouisFrançois 23 January 2008 (has links)
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.

3 
MacLane's Theorem for GraphLike SpacesRooney, Brendan January 2008 (has links)
The cycle space of a finite graph is the subspace of the edge space generated by the edge sets of cycles, and is a wellstudied object in graph theory. Recently progress has been made towards extending the theory of cycle spaces to infinite graphs.
Graphlike 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. Graphlike 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 graphlike spaces, as well as the algebraic properties of graphlike spaces. We develop a theory of embeddings of graphlike spaces in surfaces. We also show how the theory of edge spaces developed by Vella and Richter applies to graphlike spaces. We combine the topological and algebraic properties of embeddings of graphlike spaces in order to prove an extension of MacLane's Theorem. We also extend Thomassen's version of Kuratowski's Theorem for 2connected compact locally connected metric spaces to the class of graphlike spaces.

4 
A More Accurate Measurement Model for FaultTolerant Quantum ComputingOuyang, Yingkai January 2009 (has links)
Aliferis, Gottesman and Preskill [1] reduce a nonMarkovian noise model to a local noise model, under assumptions on the smallness of the norm of the systembath 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 faulttolerant architecture, in addition to more assumptions [1]. These two results combined give us a faulttolerant threshold theorem for nonMarkovian noise, provided that the strength of the effective local noise model is smaller than a positive number that depends on the faulttolerant architecture we choose. However the ideal measurement process may involve a strong systembath interaction which necessarily gives a local noise model of large strength. We refine the reduction of the nonMarkovian noise model to the local noise model such that this need not be the case, provided that systembath interactions from the nonideal 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 systembath 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.

5 
Discrete Logarithm CryptographyKarabina, Koray January 2010 (has links)
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 characteristictwo and characteristicthree 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 locationprivacy 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.

6 
On Algorithms, Separability and Cellular Automata in Quantum ComputingCheung, Donny January 2007 (has links)
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
NPhard 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 lowdepth AQFT (approximate quantum
Fourier transform) in quantum phase estimation. It has been shown previously
that the logarithmicdepth AQFT is as effective as the full QFT for the
purposes of phase estimation. However, with sublogarithmic depth, the phase
estimation algorithm no longer works directly. In this case, results of the
phase estimation algorithm need classical postprocessing 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.

7 
A Combinatorial Interpretation of Minimal Transitive Factorizations into Transpositions for Permutations with two Disjoint CyclesPrévilleRatelle, LouisFrançois 23 January 2008 (has links)
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.

8 
MacLane's Theorem for GraphLike SpacesRooney, Brendan January 2008 (has links)
The cycle space of a finite graph is the subspace of the edge space generated by the edge sets of cycles, and is a wellstudied object in graph theory. Recently progress has been made towards extending the theory of cycle spaces to infinite graphs.
Graphlike 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. Graphlike 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 graphlike spaces, as well as the algebraic properties of graphlike spaces. We develop a theory of embeddings of graphlike spaces in surfaces. We also show how the theory of edge spaces developed by Vella and Richter applies to graphlike spaces. We combine the topological and algebraic properties of embeddings of graphlike spaces in order to prove an extension of MacLane's Theorem. We also extend Thomassen's version of Kuratowski's Theorem for 2connected compact locally connected metric spaces to the class of graphlike spaces.

9 
A More Accurate Measurement Model for FaultTolerant Quantum ComputingOuyang, Yingkai January 2009 (has links)
Aliferis, Gottesman and Preskill [1] reduce a nonMarkovian noise model to a local noise model, under assumptions on the smallness of the norm of the systembath 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 faulttolerant architecture, in addition to more assumptions [1]. These two results combined give us a faulttolerant threshold theorem for nonMarkovian noise, provided that the strength of the effective local noise model is smaller than a positive number that depends on the faulttolerant architecture we choose. However the ideal measurement process may involve a strong systembath interaction which necessarily gives a local noise model of large strength. We refine the reduction of the nonMarkovian noise model to the local noise model such that this need not be the case, provided that systembath interactions from the nonideal 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 systembath 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.

10 
Discrete Logarithm CryptographyKarabina, Koray January 2010 (has links)
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 characteristictwo and characteristicthree 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 locationprivacy 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.

Page generated in 0.1341 seconds