Tractability of computation

• We can generally categorize computational algorithms according to how the resources needed for execution of the algorithm increase as we increase the size of the input. Typical resources are time and (storage) space. In different contexts, we may be interested in worst-case or average-case performance of the algorithm. For theoretical purposes, we will typically be interested in large input sets ...
• The hope of quantum computing is that problems that are difficult or impossible for classical computers to solve can be handled by quantum computers.
• A standard mechanism for comparing the growth of functions with domain $\mathbb{N}$ is ``big-Oh.'' One way of defining this notion is to associate each function with a set of functions. We can then compare algorithms by looking at their ``big-Oh'' categories.
• Given a function f, we define O(f) by:
  
  $$g \in O(f) \iff$$
  
  
  there exist c > 0 and $N \ge 0$ such that
  $\vert g(n) \vert \le c\vert f(n) \vert$ for all $n \ge N$.
• We further define $\theta(f)$ by:
  $g \in \theta(f)$ iff $g \in O(f)$ and $f \in O(g)$.
• In general we will consider the run-time of algorithms in terms of the growth of the number of elementary computer operations as a function of the number of bits in the (encoded) input. Some important categories - an algorithm's run-time f is:

  1.

  Logarithmic if $f \in \theta(\log(n))$.

  2.

  Linear if $f \in \theta(n)$.

  3.

  Quadratic if $f \in \theta(n^2)$.

  4.

  Polynomial if $f \in \theta(P(n))$ for some polynomial P(n).

  5.

  Exponential if $f \in \theta(b^n)$ for some constant b > 1.

  6.

  Factorial if $f \in \theta(n!)$.

• Typically we say that a problem is tractable if (we know) there exists an algorithm whose run-time is (at worst) polynomial that solves the problem. Otherwise, we call the problem intractable.

• There are many problems which have the interesting property that if someone (an oracle?) provides you with a solution to the problem, you can tell in polynomial time whether what they provided you actually is a solution. Problems with this property are called Non-deterministically Polynomial, or NP, problems. One way to think about this property is to imagine that we have arbitrarily many machines available. We let each machine work on one possible solution, and whichever machine finds the (a) solution lets us know.
• There are some even more interesting NP problems which are universal for the class of NP problems. These are called NP-complete problems. A problem S is NP-complete if S is NP and, there exists a polynomial time algorithm that allows us to translate any NP problem into an instance of S. If we could find a polynomial time algorithm to solve a single NP-complete problem, we would then have a polynomial time solution for all NP problems.
• Some examples:

  1.

  Factoring a number is NP. First, we recognize that if M is the number we want to factor, then the input size m is approximately $\log(M)$ (that is, the input size is the number of digits in the number). The elementary school algorithm (try dividing by each number less than $\sqrt M$) has run-time approximately $10^{\frac{m}{2}}$, which is exponential in the number of digits. On the other hand, if someone hands you two numbers they claim are factors of M, you can check by multiplying, which takes on the order of m² operations.

  It is worth noting that there is a polynomial time algorithm to determine whether or not a number is prime, but for composite numbers, this algorithm does not provide a factorization. Factoring is a particularly important example because various encryption algorithms such as RSA (used in the PGP software) depend for their security on the difficulty of factoring numbers with several hundred digits.

  2.

  Satisfiability of a boolean expression is NP-complete. Suppose we have n boolean variables $\{b_1,b_2,\ldots,b_n\}$ (each with the possible values 0 and 1). We can form a general boolean expression from these variables and their negations:
  

  $$f(b_1,b_2,\ldots,b_n) = \bigwedge_k(\bigvee_{i,j\le n}(b_i,\sim b_j)).$$

  
  

  A solution to such a problem is an assignment of values 0 or 1 to each of the b_i such that $f(b_1,b_2,\ldots,b_n) =$1. There are 2ⁿ possible assignments of values. We can check an individual possible solution in polynomial time, but there are exponentially many possibilities to check. If we could develop a feasible quantum computation for this problem, we would in some sense resolve the traditional P $\overset{?} =$NP problem ...

  3.

  The discrete Fourier transform of a sequence $\overset{\rightharpoonup} a=\langle a_j\rangle_{j=0}^{q-1}$ is the sequence $\overset{\rightharpoonup} A=\langle A_k\rangle_{k=0}^{q-1}$ where
  

  $$A_k=\frac{1}{\sqrt{q}}\sum_{j=0}^{q-1}a_je^{\frac{2\pi ijk}{q}}$$

  
  

  One way to think about this is that $\overset{\rightharpoonup} A=F\overset{\rightharpoonup} a$ where the linear transformation F is given by:
  

  $$[F]_{j,k}=\frac{1}{\sqrt{q}}e^{\frac{2\pi ijk}{q}}$$

  
  

  Note that the inverse of F is $F^\dag$ - that is,
  

  $$[F^{-1}]_{k,j}=\frac{1}{\sqrt{q}}e^{-\frac{2\pi ijk}{q}}.$$

  
  

  Suggestively, this says that the discrete Fourier transform is a unitary operation.

  The action of this transformation on a vector of dimension q looks as though it would take the q² operations of matrix multiplication, but there is enough structure that the classical fast Fourier transform algorithm can be done in $q\log(q)$ operations.

  The corresponding quantum Fourier transform U_QFT with base 2ⁿ is defined by
  

  $$U_{QFT}: \vert{x}\rangle \mapsto \frac{1}{\sqrt{2^n}}\sum_{c=0}^{2^n-1}e^{\frac{2\pi icx} {2^n}}\vert{c}\rangle.$$

  
  

  We will see that this can be accomplished in approximately n² operations rather than n2ⁿ. This is an exponential speed-up of the process.