A common desire in today's world is that of security. Whether it is keeping your e-mail private or stopping the government from hacking into your computer, the idea behind cryptography is to communicate between two parties in different locations, and to secure this information from outsiders. During the last half century there have been numerous advances in encryption schemes and also in the machines that process such information. Modern encryption algorithms have become increasingly more complex with advances in computers and technology, and encryption algorithms such as RSA and DES have been presented as algorithms that have remained secure for decades. These recent advances in encryption schemes will be examined in the first part of this paper. On the other hand, because the security of classical ciphers relies on the secrecy of a key, advances in research and computing may begin to compromise the security of these cryptosystems, as quantum computers would be capable of mathematical calculations that could break many modern encryption algorithms. Unlike classical cryptosystems, quantum cryptography obeys the laws of quantum physics, resulting in a much stronger, provable security. Many great advances have come in recent decades, and the latter part of this paper deals with these advances as well as the phenomena of quantum physics, the evolution of quantum computing, and the study of quantum cryptography.

No description available.

Quantum computing has generated a lot of interested in the past two decades. Research into powerful models of quantum computation has yielded important and elegant results like an efficient algorithm for factoring and a quadratic speed-up for unordered search. At the same time, given the current difficulty in the physical implementation of these general purpose models, considerable effort has also been made in estimating the power of weaker models of quantum computation: models that have a small quantum component. The first part of this thesis is an investigation into the power of interference in quantum computing. While interference in probability amplitudes is a central feature even in powerful models, it is the only extra resource available to quantum finite automata. Of particular interest is interference in automata that have both classical and quantum states (2QCFA) as proposed by Ambainis and Watrous, since it inquires into the power of a classical deterministic finite automaton when augmented with a quantum component of constant size. Our contributions in this part are as follows: • To abstract out the phenomenon of interference in quantum computing, we propose a model called the 2-way Optical Interference Automata (2OIA). The model consists of a 2DFA augmented with a simple optical arrangement. We show different ways of harnessing the power of interference in the form of algorithms on this model to recognize some non-trivial languages. We then go on to show a language recognizable by a Turing machine using O(n2) space but by no 2OIA. • A natural classical model for comparison with 2QCFA is the weighted automaton, since it has the potential to capture interference in sum of path weights. Using the Cortes-Mohri definition of language recognition, we give an efficient simulation of 2QCFAwith algebraic amplitudes by weighted automata over the complex semi ring. • We introduce quantum non-determinism to the Measure-Once 1-way Quantum Finite Automata of Moore and Crutchfield and Kondacs and Watrous and show that even then, the model can recognize only regular languages with bounded error. • We propose a group theoretic generalization of counter automata that allows a notion of counter reversal complexity. To obtain this generalization, we combine concepts from classical counter automata theory with results in 2QCFA. We examine specific instances of this generalization and compare their ii iii powers. We also show an instance recognizing a language that is not recognized by conventional 2-way counter automata. Finally, we show a strict hierarchy among the 1-way versions of the instances Discussed. The second part of the thesis deals with Quantum Adiabatic Optimization algorithms. A common trick for designing faster quantum adiabatic algorithms is to apply the adiabatic condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigen values, which is an essential ingredient in the adiabatic condition. We present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic unordered search of van Dam et al. and Roland and Cerf when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in logN, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.