Date of Award

2019

Degree Name

Mathematics

College

College of Science

Type of Degree

M.A.

Document Type

Thesis

First Advisor

Dr. Carl Mummert, Committee Chairperson

Second Advisor

Dr. JiYoon Jung

Third Advisor

Dr. Huong Nguyen

Abstract

We study quantum computers and their impact on computability. First, we summarize the history of computer science. Only a few articles have determined the direction of computer science and industry despite the fact that many works have been dedicated to the present success. We choose articles by A. M. Turing and D. Deutsch, because A. M. Turing proposed the basic architecture of modern computers while D. Deutsch proposed an architecture for the next generation of computers called quantum computers. Second, we study the architecture of modern computers using Turing machines. The Turing machine has the basic design of modern computers despite its simple structure. Then we study quantum computers. Quantum computers are believed to be the next generation, and expected to have a breakthrough in processing speed. We study what makes quantum computers have such a high processing speed. Third, we study how quantum computers gain such a processing speed with an example of Shor’s algorithm. This algorithm allows quantum computers to factor natural numbers into primes. Finally, we discuss a possible impact of quantum computers on the notion of computability.

Subject(s)

Computational complexity.

Quantum computers.

Download

Share

COinS