Introduction to Quantum Computing

Let us start by summarizing the basic ideas that we need from quantum mechanics: at any moment a physical system S is in some ``state'' $\Psi$. If we plan to measure (observe) some property Q of S, we will in general change the state into a new one, $\Psi_k$, which is a solution of the TISE $\hat Q \Psi_k = q_k \Psi_k$.

Note that (i) the observed value of Q will be $q_k$, and (ii) the probability of the new state being that particular state $\Psi_k$ (out of all the possible new (TISE-solution-) states $\Psi_1, \Psi_2, \ldots$) is simply $a_k^2$ where $\Psi = \sum_{i=1}^n a_i \Psi_i$; here $n$ can be finite or infinite. It is a useful (but mathematically trivial) fact that the probability that $\Psi_k$ results from the measurement, namely $a_k^2$, is the same as the absolute square of the ``inner product'' of $\Psi_k$ and $\Psi$:

$$\Psi_k \cdot \Psi=\Psi_k \cdot \sum_{i=1}^n a_i \Psi_i$$

$$= <\Psi_k\vert \cdot \vert\Psi> = <bra\vert \cdot \vert ket> = a_k$$

Here we are using Dirac's famous bra-ket notation; we put what we know (the old state, $\Psi$) in the ``ket'', and a possible new state in the ``bra''. The square of the absolute value of their direct (or inner) product is the probability that what we try out in the bra is in fact the new state. So: to get the probability that some eigenfunction $<bra\vert$ of $\hat Q$ (and its associated eigenvalue $q$) will result from observing property $Q$ on state $\vert ket>$, we just compute the square of the absolute value of $<bra\vert \cdot \vert ket>$, where $\Psi = \vert ket>$ is written in a convenient form, namely as a weighted sum (linear combination) of all the eigenfunctions $\Psi_i$ of $\hat Q$.

It follows that state functions are normalized: the sum of the absolute squares of their coefficients (when the state is written as such a linear combination) is exactly 1, since this sum gives the total probability of something being measured (and something always is).

We also say $\Psi$ is a ``superposition'' of the $\Psi_i$, and we think of it as indicating that S is in fact in all those states at once (until we make a measurement, and then S ``collapses'' into just one of them). This is the famous and bizarre ``quantum parallelism'' that seems like science fiction but that is also the basis for quantum computation.

The trick of quantum computation is to get the system to evolve unmeasured, in a way we want, so that all the implicit eigenstates of the quantity that we will measure eventually also evolve as we want, together - ie in parallel - until we actually do the measurement at the end (at which time all but one of those eigenstates ``collapse'' away leaving only the one we actual observe).

But to do this, we need to find ways to get a system to evolve, unmeasured, as we want. This can be extremely tricky.

For instance, suppose we have an array of $n$ numbers, and we want to multiply each of them by 2. Ordinarily this will take $n$ steps. But if we can encode each of the numbers as an eigenstate of some operator, and if we can get a physical system to be in a state $\Psi$ that not only is a superposition of all those eigenstates but also is a state that we can get to evolve so that those eigenstates change into ones encoding 2 times each of our numbers, then we will ``have'' the $n$ results all at once (ie as soon as the evolving has been done. But we are still not done since the answers are hidden inside the superposition, and if we try to observe any of the doubled data values then system changes into one of the eigenstates and the others disappear leaving us only with that one value rather than $n$ values. So a problem that requires as much output data as input tends not to be a good one for quantum computation.

But this very fact makes ``quantum information processing'' good for sending encrypted messages. Here the encryption also involves a superposition; and then if anyone intercepts the message and decodes it, the message (the superposition) collapses entirely and so even the sender and intended receiver can tell it has been read.

Examples of problems that do seem to lend themselves to quantum computation (unlike that of doubling data values) are few and far between. So far the only one of any practical interest seems to be that of factoring large numbers. There is an algorithm due to Shor, that in principle allows what would normally be a vast number of computations on many individual pieces of data to be done as a single computation (evolution of the wavefunction that is a superposition of all the individual data) in such a way that the answer can be read out from any of the eigenstates at all, once the final measurement is made.

And quantum computers have in fact been built, and applied to Shor's algorithm. But the technology so far is very primitive, and the ``large'' numbers are not yet large. A few years ago one such machine was able to factor the number 6 using Shor's algorithm, and this year the number 15. But the difficulties are practical ones of machine design; it appears clear that the underlying principles are correct, so it may only be a matter of time until we have vast computational power at our hands, but only a handful (or less) of algorithms that we know how to encode.

A key notion on quantum computation is that of a qubit, the quantum mechanical analogue of a bit. A single qubit is normally construed as being "built" out of a two-state system, ie one that can take on either of two observed states (such as low energy or high energy, or polarization vertical or horizontal), which we may repr as |0> and |1>. In that regard, it is like a bit. But, when it is not being observed, the qubit can also be in any of an infinite number of ``superpositions'' of those two states: $a\vert> + b\vert 1>$ where $\vert a\vert^2+\vert b\vert^2=1$ and a and b may be complex numbers. That is, it can, in some sense, be in *both* of its two observable states at once. This is the same thing we were saying about the state function $\Psi$, except now it is a special case where there are only two observable states.

Now imagine a qubit suitably prepared as a superposed state, and then manipulated so that the $\vert>$ and $\vert 1>$ components of it evolve in some desired way (eg so that they undergo certain computations) while they remain superposed (no measurement made). This is in a sense a parallel processing of both computations at once (the one on $\vert>$ and the one on $\vert 1>$) even though we cannot "see" both of them since observation will destroy on or the other (or maybe even both, depending on what we measure).

What about an array of n qubits? This is analogous to a n-bit register. But while the latter at any one time can represent only one n-bit number, n quibits can represent (at the same time) a (superposed) total of $2^n$ such numbers, namely all the $2^n$ possible observable outcomes for those n qubits. Consider, for example, $n=2$. Then the two qubits (call them A and B) can be in any of the four states $\vert0>,\vert1>,\vert 10>,\vert 11>$. (We are using a notation in which each ``ket'' $\vert ab>$ indicates that qubit A is in state $\vert a>$ and quibit B in state $\vert b>$.) This is the same as a classical 2-bit register. But the two-qubit AB system can also be in the superposed state $0.5(\vert0>+\vert1>+\vert 10>+\vert 11>)$, thus representing all four classical states at once.