Quantum Computability and Complexity and the Limits of Quantum Computation Eric Benjamin Kenny Huang Amir Kamil Jimmy Kittiyachavalit University of California Berkeley December 7 2003 This paper will present an overview of the current beliefs of quantum complexity theorists and discuss in detail the impacts these beliefs may have on the future of the field In section one we give a brief fundamental overview of classical complexity theory defining the time and space hierarchies and providing examples of problems that fit into several important categories thereon In section two we introduce quantum complexity and discuss its relationship to classical complexity Section three presents an overview of the successful existing quantum algorithms and section four presents a discussion on the actual practical gains that might be realized by quantum computation Finally in section five we speculate briefly on the direction we believe the field to be headed and what might reasonably be expected in the future 1 Introduction to Computability and Complexity In computability and complexity theory all problems are reduced to language recognition where a language is defined as a set of strings over some alphabet typically 0 1 For example L1 0 00 000 is the language that contains all strings that contain only the letter 0 Once we have a language L there are some interesting questions we can ask about it Given an input x can a machine decide if x L If so how long does it take to make this decision with respect to the size of the input x In order to answer these questions it is necessary to define a model of computation 1 1 Computational Models There are many useful models of computation Some examples include Boolean circuits push down automata with two stacks Java programs and Turing machines Of these Turing machines will be the most useful to our discussion For a detailed formal discussion of Turing machines see 11 All reasonable deterministic models are essentially equivalent since they can simulate one another in polynomial time We will take advantage of this result by using the particular models that are most convenient for our discussion 1 2 Classical Computability Many people even those who have studied computer science erroneously believe that any conceivable welldefined problem can be computed In fact a language is computable also called decidable if and only if there exists a Turing machine that halts on all inputs such that the final state is the accept state if the given input is in the language and the final state is the reject state if not The simplest example of a problem that fails this criteria and is therefore uncomputable is the halting problem Given a machine M and its input x is it possible to decide if M will ever halt on x A na ve way to try answering this question is to run on M on x But how do we know when to stop Perhaps if we run M a little longer it might halt Since we have no idea how long M might run on x this solution fails In fact it can be formally proven that no solution exists 11 This problem is uncomputable A useful property of computability is that it is a property of a language That is to say the decidability of a language does not depend on any particular computational model This means for example that anything that can be computed on a nondeterministic machine can also be computed on a deterministic machine 11 1 1 3 Classical Complexity Classes Once we have determined that a language is computable we are often interested in how much it costs to decide the language There are two resources of interest the amount of time required and the amount of space necessary to compute the language Languages are classified into complexity classes according to how much of each of the resources they require 1 3 1 The Class P The set of all languages that can be computed in polynomial time on a deterministic Turing machine is called the class P Familiar examples of problems in P include sorting a list of elements computing the maximum flow between two points in a network of pipes and finding the shortest path between two points in a graph 1 3 2 The Class NP The nondeterministic analog to P is the class NP This is the set of all languages that can be computed in polynomial time on a nondeterministic Turing machine Examples of problems in this class include factoring and determining whether or not a Boolean formula is satisfiable by some input That is given a boolean formula f x1 x2 xn over n boolean variables is the following statement true x1 x2 xn f x1 x2 xn This particular problem is known as SAT Another equivalent definition of NP is that it contains all languages that are verifiable in polynomial time on a deterministic machine This means that given an input and a certificate of the input s membership in a language a machine can check if the certificate is valid in polynomial time For example in determining whether a number k is composite one of the factors of k could be used as the certificate A machine could then determine the validity of the certificate by dividing k by it and checking that the remainder is 0 Since a deterministic Turing machine is just a specific type of nondeterministic machine P NP 1 3 3 The NP Complete Languages The hardest problems in NP are known as the NP complete languages These languages have an interesting characteristic a solver for an NP complete language can be used to solve any problem in NP with only polynomial overhead The classic example of an NP complete language is SAT Intuitively this is because Boolean circuits are the building blocks of a computer and we can thus build a circuit that simulates a Turing machine Other NP complete problems include finding a given size fully connected subgraph of a graph determining whether the nodes of a graph can be colored using only three colors such that no two nodes of the same color are adjacent and determining whether a set of numbers contains a subset that adds up to a particular number Though these problems appear unrelated any NP problem can be quickly converted into each of them 1 3 4 Is P NP Perhaps the most famous open question in computer science is whether or not the classes P and NP are equivalent Does nondeterminism increase the power of a Turing machine to the point where we can quickly solve problems that we otherwise couldn t Although it may appear obvious that these two classes are not equivalent given that a nondeterministic machine can perform parallel computation no one has