# Quantum computing for dummies A single bit has two possible values: {0, 1}. Three bits have 2x2x2 = 8: {000, 001, 010, 011, 100, 101, 110, 111}. These can also be written: {0, 1, 2, 3, 4, 5, 6, 7} (which you may recognize as binary coding). In a classical 3-bit computer, the state at any point in time will be *one* of those 8 combinations. In a quantum computer, thanks to the *superposition* principle, instead the state being just one value, all eight will get some "weight." Although those weights are in general complex numbers, here we will simplify and assign them real numbers. The only constraint is that the sum of their squares must be 1 (for reasons we shall soon see). We can write down those weights in vector form. Examples include: ``` 1/sqrt(8) * (1, 1, 1, 1, 1, 1, 1, 1) (0, 1, 0, 0, 0, 0, 0, 0) ... ``` When written in column form, such a vector can be left-multiplied (or "operated on") by an Nx8 matrix. Because we want another 8x1 vector out, we use an 8x8 matrix: ``` [image of 8x8 matrix multiplying an 8x1 vector] ``` In QM, only certain 8x8 matrices are allowed, called *unitary* matrices. You needn't worry too much about what that means, but in the case of real coefficients, these turn out to be *rotation* matrices. This ensures that the length of the input vector remains unchanged. Now, suppose your input vector *v* has just one nonzero value (such as (0, *x*, 0, 0, ...)). Then the result is: ``` [image of M x v] ``` And if input vector *w* has a nonzero value in a different spot (such as (0, 0, y, 0, ...)), you get: ``` [image of M x w] ``` By the laws of linear algebra, feeding M the *sum* of w and v will yield the sum of the two previous results: ``` [image of M x (w + v) = (M x w) + (M x v)] ``` You can think of this as "parallelizing" the two computations --- and since there are 8 slots, we can parallelizing up to 8. Quantum computers can do this very efficiently. This is, in part, responsible for their speedup. But it would be a big mistake to think of this as the whole story. That's because of what happens when we try to read out the result. According to QM, you can't simply read off the entirety of the output vector to get its contents. Instead, when you try to read it, you'll get told that the answer is just *one* of the eight states -- and the *probability* of getting a given state is the *square* of the corresponding coefficient. For example, if the output is: ``` 1/sqrt(8) * (1, 1, 1, 1, 1, 1, 1, 1) => each result will be returned 1/8 of the time (0, 1, 0, 0, 0, 0, 0, 0) => the second result will be returned with 100% probability ... ``` This explains why the coefficients must always square-sum to one: they correspond to *probabilities*. Moreover, you don't get back the actual values from *inside* the vector; you simply get told which *position* got selected. For example, you might get told: ``` 1/sqrt(8) * (1, 1, 1, 1, 1, 1, 1, 1) => "the third position!" (randomly) (0, 1, 0, 0, 0, 0, 0, 0) => "the second position!" (every time) ... ``` Therefore, the output of our quantum algorithm will only be one of 8 possible values --- that is, a classical 3-bit result. So although it *is* a kind of parallelism, it's not *at all* the kind we often read about in popular articles, where quantum computers somehow do the same thing classical computers can, but 8 (or 16, or 2^N) times faster. Something much more curious is going on. To understand what that is, first look at the following vector when plotted on a line chart: ``` 1/2 * (-1, 0, 1, 0, -1, 0, 1, 0) ``` ![](https://i.imgur.com/fA1vpaj.png) This looks like a very pixelated sine wave. If we had more bits and thus more fidelity, we could make it look more and more like a true sine wave. And in fact, according to QM, each vector (also called a *state vector*) is indeed a kind of wave --- the kind you hear about in the famous "wave-particle" duality. *During* the computation, we have vectors (waves), but when we read the result, we get a single point-like value (particle) because we have "collapsed the wavefunction." Now, consider a special matrix F that behaves in the following way. Recall that we can label the 8 positions of our vector with the numbers 0 through 7. When given an input vector with a *single* nonzero coefficient, F will output a sine wave with corresponding frequency: ``` (1, 0, 0, 0, 0, 0, 0, 0) (only contains value 0) => sine wave with zero frequency = straight line (0, 1, 0, 0, 0, 0, 0, 0) (only contains value 1) => sine wave with frequency 1 = sin(x) ... (0, 0, 0, 0, 0, 0, 0, 1) (only contains value 7) => sine wave with frequency 7 = sin(7x) [with corresponding images] ``` By the aforementioned laws, if the input has *two* nonzero values, the output wave will be the sum of their corresponding waves: ``` (0, 1, 0, 1, 0, 0, 0, 0) => sin 1x + sin 3x [image] ``` Notice how there are "interference effects": sometimes the two waves add, and sometimes they cancel each other out. This leads to an idea: what if we could orchestrate a chain of matrices in a clever way so that the resulting vector has a nonzero weight in only the location containing the correct answer? For example, if the right answer is 2, then we would like our matrix chain to produce this output vector: ``` (0, 0, 1, 0, 0, 0, 0, 0) ``` That way, when we read off the answer, we have a 100% chance of being told "two." In practice, this turns out to be very hard. The available operations generally allow us only to get incrementally *closer* to this ideal output. So we may get: ``` (e0, e1, x, e3, e4, e5, e6, e7) (where e_n are close to zero, and x is close to 1) ``` But that's okay: probabilistically, we will *very likely* get "2" as our answer! Okay, so how exactly does this speed up computation? Well, it depends on entirely the problem we are trying to solve. It turns out that for certain problems, people have found clever ways to combine operations such that the total number of steps is provably less than would be required on any classical machine. Factorization is the most famous, and it makes use of F above (which you may have recognized as the *Fourier transform*). If you want to understand the details, check out [this incredible explainer](https://www.youtube.com/watch?v=lvTqbM5Dq4Q). Unstructured search is another problem for which [a quantum algorithm has been found]((https://en.wikipedia.org/wiki/Grover%27s_algorithm)). But in general, we know of no process by which we can design quantum algorithms that can solve problems faster.