# Zero Knowledge Proofs — A Primer

In this post we’ll get a strong taste for zero knowledge proofs by exploring the graph isomorphism problem in detail. In the next post, we’ll see how this relates to cryptography and the bigger picture. The goal of this post is to get a strong understanding of the terms “prover,” “verifier,” and “simulator,” and “zero knowledge” in the context of a specific zero-knowledge proof. Then next time we’ll see how the same concepts (though not the same proof) generalizes to a cryptographically interesting setting.

## Graph isomorphism

Let’s start with an extended example. We are given two graphs $G_1, G_2$, and we’d like to know whether they’re isomorphic, meaning they’re the same graph, but “drawn” different ways.

The problem of telling if two graphs are isomorphic seems hard. The pictures above, which are all different drawings of the same graph (or are they?), should give you pause if you thought it was easy.

To add a tiny bit of formalism, a graph $G$ is a list of edges, and each edge $(u,v)$ is a pair of integers between 1 and the total number of vertices of the graph, say $n$. Using this representation, an isomorphism between $G_1$ and $G_2$ is a permutation $\pi$ of the numbers $\{1, 2, \dots, n \}$ with the property that $(i,j)$ is an edge in $G_1$ if and only if $(\pi(i), \pi(j))$ is an edge of $G_2$. You swap around the labels on the vertices, and that’s how you get from one graph to another isomorphic one.

Given two arbitrary graphs as input on a large number of vertices $n$, nobody knows of an efficient—i.e., polynomial time in $n$—algorithm that can always decide whether the input graphs are isomorphic. Even if you promise me that the inputs are isomorphic, nobody knows of an algorithm that could construct an isomorphism. (If you think about it, such an algorithm could be used to solve the decision problem!)

## A game

Now let’s play a game. In this game, we’re given two enormous graphs on a billion nodes. I claim they’re isomorphic, and I want to prove it to you. However, my life’s fortune is locked behind these particular graphs (somehow), and if you actually had an isomorphism between these two graphs you could use it to steal all my money. But I still want to convince you that I do, in fact, own all of this money, because we’re about to start a business and you need to know I’m not broke.

Is there a way for me to convince you beyond a reasonable doubt that these two graphs are indeed isomorphic? And moreover, could I do so without you gaining access to my secret isomorphism? It would be even better if I could guarantee you learn nothing about my isomorphism or any isomorphism, because even the slightest chance that you can steal my money is out of the question.

Zero knowledge proofs have exactly those properties, and here’s a zero knowledge proof for graph isomorphism. For the record, $G_1$ and $G_2$ are public knowledge, (common inputs to our protocol for the sake of tracking runtime), and the protocol itself is common knowledge. However, I have an isomorphism $f: G_1 \to G_2$ that you don’t know.

Step 1: I will start by picking one of my two graphs, say $G_1$, mixing up the vertices, and sending you the resulting graph. In other words, I send you a graph $H$ which is chosen uniformly at random from all isomorphic copies of $G_1$. I will save the permutation $\pi$ that I used to generate $H$ for later use.

Step 2: You receive a graph $H$ which you save for later, and then you randomly pick an integer $t$ which is either 1 or 2, with equal probability on each. The number $t$ corresponds to your challenge for me to prove $H$ is isomorphic to $G_1$ or $G_2$. You send me back $t$, with the expectation that I will provide you with an isomorphism between $H$ and $G_t$.

Step 3: Indeed, I faithfully provide you such an isomorphism. If I you send me $t=1$, I’ll give you back $\pi^{-1} : H \to G_1$, and otherwise I’ll give you back $f \circ \pi^{-1}: H \to G_2$. Because composing a fixed permutation with a uniformly random permutation is again a uniformly random permutation, in either case I’m sending you a uniformly random permutation.

Step 4: You receive a permutation $g$, and you can use it to verify that $H$ is isomorphic to $G_t$. If the permutation I sent you doesn’t work, you’ll reject my claim, and if it does, you’ll accept my claim.

Before we analyze, here’s some Python code that implements the above scheme. You can find the full, working example in a repository on this blog’s Github page.

First, a few helper functions for generating random permutations (and turning their list-of-zero-based-indices form into a function-of-positive-integers form)

import random

def randomPermutation(n):
L = list(range(n))
random.shuffle(L)
return L

def makePermutationFunction(L):
return lambda i: L[i - 1] + 1

def makeInversePermutationFunction(L):
return lambda i: 1 + L.index(i - 1)

def applyIsomorphism(G, f):
return [(f(i), f(j)) for (i, j) in G]


Here’s a class for the Prover, the one who knows the isomorphism and wants to prove it while keeping the isomorphism secret:

class Prover(object):
def __init__(self, G1, G2, isomorphism):
'''
isomomorphism is a list of integers representing
an isomoprhism from G1 to G2.
'''
self.G1 = G1
self.G2 = G2
self.n = numVertices(G1)
assert self.n == numVertices(G2)

self.isomorphism = isomorphism
self.state = None

def sendIsomorphicCopy(self):
isomorphism = randomPermutation(self.n)
pi = makePermutationFunction(isomorphism)

H = applyIsomorphism(self.G1, pi)

self.state = isomorphism
return H

def proveIsomorphicTo(self, graphChoice):
randomIsomorphism = self.state
piInverse = makeInversePermutationFunction(randomIsomorphism)

if graphChoice == 1:
return piInverse
else:
f = makePermutationFunction(self.isomorphism)
return lambda i: f(piInverse(i))


The prover has two methods, one for each round of the protocol. The first creates an isomorphic copy of $G_1$, and the second receives the challenge and produces the requested isomorphism.

And here’s the corresponding class for the verifier

class Verifier(object):
def __init__(self, G1, G2):
self.G1 = G1
self.G2 = G2
self.n = numVertices(G1)
assert self.n == numVertices(G2)

def chooseGraph(self, H):
choice = random.choice([1, 2])
self.state = H, choice
return choice

def accepts(self, isomorphism):
'''
Return True if and only if the given isomorphism
is a valid isomorphism between the randomly
chosen graph in the first step, and the H presented
by the Prover.
'''
H, choice = self.state
graphToCheck = [self.G1, self.G2][choice - 1]
f = isomorphism

isValidIsomorphism = (graphToCheck == applyIsomorphism(H, f))
return isValidIsomorphism


Then the protocol is as follows:

def runProtocol(G1, G2, isomorphism):
p = Prover(G1, G2, isomorphism)
v = Verifier(G1, G2)

H = p.sendIsomorphicCopy()
choice = v.chooseGraph(H)
witnessIsomorphism = p.proveIsomorphicTo(choice)

return v.accepts(witnessIsomorphism)


Analysis: Let’s suppose for a moment that everyone is honestly following the rules, and that $G_1, G_2$ are truly isomorphic. Then you’ll always accept my claim, because I can always provide you with an isomorphism. Now let’s suppose that, actually I’m lying, the two graphs aren’t isomorphic, and I’m trying to fool you into thinking they are. What’s the probability that you’ll rightfully reject my claim?

Well, regardless of what I do, I’m sending you a graph $H$ and you get to make a random choice of $t = 1, 2$ that I can’t control. If $H$ is only actually isomorphic to either $G_1$ or $G_2$ but not both, then so long as you make your choice uniformly at random, half of the time I won’t be able to produce a valid isomorphism and you’ll reject. And unless you can actually tell which graph $H$ is isomorphic to—an open problem, but let’s say you can’t—then probability 1/2 is the best you can do.

Maybe the probability 1/2 is a bit unsatisfying, but remember that we can amplify this probability by repeating the protocol over and over again. So if you want to be sure I didn’t cheat and get lucky to within a probability of one-in-one-trillion, you only need to repeat the protocol 30 times. To be surer than the chance of picking a specific atom at random from all atoms in the universe, only about 400 times.

If you want to feel small, think of the number of atoms in the universe. If you want to feel big, think of its logarithm.

Here’s the code that repeats the protocol for assurance.

def convinceBeyondDoubt(G1, G2, isomorphism, errorTolerance=1e-20):
probabilityFooled = 1

while probabilityFooled > errorTolerance:
result = runProtocol(G1, G2, isomorphism)
assert result
probabilityFooled *= 0.5
print(probabilityFooled)


Running it, we see it succeeds

$python graph-isomorphism.py 0.5 0.25 0.125 0.0625 0.03125 ... <SNIP> ... 1.3552527156068805e-20 6.776263578034403e-21  So it’s clear that this protocol is convincing. But how can we be sure that there’s no leakage of knowledge in the protocol? What does “leakage” even mean? That’s where this topic is the most difficult to nail down rigorously, in part because there are at least three a priori different definitions! The idea we want to capture is that anything that you can efficiently compute after the protocol finishes (i.e., you have the content of the messages sent to you by the prover) you could have computed efficiently given only the two graphs$ G_1, G_2$, and the claim that they are isomorphic. Another way to say it is that you may go through the verification process and feel happy and confident that the two graphs are isomorphic. But because it’s a zero-knowledge proof, you can’t do anything with that information more than you could have done if you just took the assertion on blind faith. I’m confident there’s a joke about religion lurking here somewhere, but I’ll just trust it’s funny and move on. In the next post we’ll expand on this “leakage” notion, but before we get there it should be clear that the graph isomorphism protocol will have the strongest possible “no-leakage” property we can come up with. Indeed, in the first round the prover sends a uniform random isomorphic copy of$ G_1$to the verifier, but the verifier can compute such an isomorphism already without the help of the prover. The verifier can’t necessarily find the isomorphism that the prover used in retrospect, because the verifier can’t solve graph isomorphism. Instead, the point is that the probability space of “$ G_1$paired with an$ H$made by the prover” and the probability space of “$ G_1$paired with$ H$as made by the verifier” are equal. No information was leaked by the prover. For the second round, again the permutation$ \pi$used by the prover to generate$ H$is uniformly random. Since composing a fixed permutation with a uniform random permutation also results in a uniform random permutation, the second message sent by the prover is uniformly random, and so again the verifier could have constructed a similarly random permutation alone. Let’s make this explicit with a small program. We have the honest protocol from before, but now I’m returning the set of messages sent by the prover, which the verifier can use for additional computation. def messagesFromProtocol(G1, G2, isomorphism): p = Prover(G1, G2, isomorphism) v = Verifier(G1, G2) H = p.sendIsomorphicCopy() choice = v.chooseGraph(H) witnessIsomorphism = p.proveIsomorphicTo(choice) return [H, choice, witnessIsomorphism]  To say that the protocol is zero-knowledge (again, this is still colloquial) is to say that anything that the verifier could compute, given as input the return value of this function along with$ G_1, G_2$and the claim that they’re isomorphic, the verifier could also compute given only$ G_1, G_2$and the claim that$ G_1, G_2$are isomorphic. It’s easy to prove this, and we’ll do so with a python function called simulateProtocol. def simulateProtocol(G1, G2): # Construct data drawn from the same distribution as what is # returned by messagesFromProtocol choice = random.choice([1, 2]) G = [G1, G2][choice - 1] n = numVertices(G) isomorphism = randomPermutation(n) pi = makePermutationFunction(isomorphism) H = applyIsomorphism(G, pi) return H, choice, pi  The claim is that the distribution of outputs to messagesFromProtocol and simulateProtocol are equal. But simulateProtocol will work regardless of whether$ G_1, G_2$are isomorphic. Of course, it’s not convincing to the verifier because the simulating function made the choices in the wrong order, choosing the graph index before making$ H$. But the distribution that results is the same either way. So if you were to use the actual Prover/Verifier protocol outputs as input to another algorithm (say, one which tries to compute an isomorphism of$ G_1 \to G_2$), you might as well use the output of your simulator instead. You’d have no information beyond hard-coding the assumption that$ G_1, G_2$are isomorphic into your program. Which, as I mentioned earlier, is no help at all. In this post we covered one detailed example of a zero-knowledge proof. Next time we’ll broaden our view and see the more general power of zero-knowledge (that it captures all of NP), and see some specific cryptographic applications. Keep in mind the preceding discussion, because we’re going to re-use the terms “prover,” “verifier,” and “simulator” to mean roughly the same things as the classes Prover, Verifier and the function simulateProtocol. Until then! # Big Dimensions, and What You Can Do About It Data is abundant, data is big, and big is a problem. Let me start with an example. Let’s say you have a list of movie titles and you want to learn their genre: romance, action, drama, etc. And maybe in this scenario IMDB doesn’t exist so you can’t scrape the answer. Well, the title alone is almost never enough information. One nice way to get more data is to do the following: 1. Pick a large dictionary of words, say the most common 100,000 non stop-words in the English language. 2. Crawl the web looking for documents that include the title of a film. 3. For each film, record the counts of all other words appearing in those documents. 4. Maybe remove instances of “movie” or “film,” etc. After this process you have a length-100,000 vector of integers associated with each movie title. IMDB’s database has around 1.5 million listed movies, and if we have a 32-bit integer per vector entry, that’s 600 GB of data to get every movie. One way to try to find genres is to cluster this (unlabeled) dataset of vectors, and then manually inspect the clusters and assign genres. With a really fast computer we could simply run an existing clustering algorithm on this dataset and be done. Of course, clustering 600 GB of data takes a long time, but there’s another problem. The geometric intuition that we use to design clustering algorithms degrades as the length of the vectors in the dataset grows. As a result, our algorithms perform poorly. This phenomenon is called the “curse of dimensionality” (“curse” isn’t a technical term), and we’ll return to the mathematical curiosities shortly. A possible workaround is to try to come up with faster algorithms or be more patient. But a more interesting mathematical question is the following: Is it possible to condense high-dimensional data into smaller dimensions and retain the important geometric properties of the data? This goal is called dimension reduction. Indeed, all of the chatter on the internet is bound to encode redundant information, so for our movie title vectors it seems the answer should be “yes.” But the questions remain, how does one find a low-dimensional condensification? (Condensification isn’t a word, the right word is embedding, but embedding is overloaded so we’ll wait until we define it) And what mathematical guarantees can you prove about the resulting condensed data? After all, it stands to reason that different techniques preserve different aspects of the data. Only math will tell. In this post we’ll explore this so-called “curse” of dimensionality, explain the formality of why it’s seen as a curse, and implement a wonderfully simple technique called “the random projection method” which preserves pairwise distances between points after the reduction. As usual, and all the code, data, and tests used in the making of this post are on Github. ## Some curious issues, and the “curse” We start by exploring the curse of dimensionality with experiments on synthetic data. In two dimensions, take a circle centered at the origin with radius 1 and its bounding square. The circle fills up most of the area in the square, in fact it takes up exactly$ \pi$out of 4 which is about 78%. In three dimensions we have a sphere and a cube, and the ratio of sphere volume to cube volume is a bit smaller,$ 4 \pi /3$out of a total of 8, which is just over 52%. What about in a thousand dimensions? Let’s try by simulation. import random def randUnitCube(n): return [(random.random() - 0.5)*2 for _ in range(n)] def sphereCubeRatio(n, numSamples): randomSample = [randUnitCube(n) for _ in range(numSamples)] return sum(1 for x in randomSample if sum(a**2 for a in x) &lt;= 1) / numSamples  The result is as we computed for small dimension,  &gt;&gt;&gt; sphereCubeRatio(2,10000) 0.7857 &gt;&gt;&gt; sphereCubeRatio(3,10000) 0.5196  And much smaller for larger dimension &gt;&gt;&gt; sphereCubeRatio(20,100000) # 100k samples 0.0 &gt;&gt;&gt; sphereCubeRatio(20,1000000) # 1M samples 0.0 &gt;&gt;&gt; sphereCubeRatio(20,2000000) 5e-07  Forget a thousand dimensions, for even twenty dimensions, a million samples wasn’t enough to register a single random point inside the unit sphere. This illustrates one concern, that when we’re sampling random points in the$ d$-dimensional unit cube, we need at least$ 2^d$samples to ensure we’re getting a even distribution from the whole space. In high dimensions, this face basically rules out a naive Monte Carlo approximation, where you sample random points to estimate the probability of an event too complicated to sample from directly. A machine learning viewpoint of the same problem is that in dimension$ d$, if your machine learning algorithm requires a representative sample of the input space in order to make a useful inference, then you require$ 2^d$samples to learn. Luckily, we can answer our original question because there is a known formula for the volume of a sphere in any dimension. Rather than give the closed form formula, which involves the gamma function and is incredibly hard to parse, we’ll state the recursive form. Call$ V_i$the volume of the unit sphere in dimension$ i$. Then$ V_0 = 1$by convention,$ V_1 = 2$(it’s an interval), and$ V_n = \frac{2 \pi V_{n-2}}{n}$. If you unpack this recursion you can see that the numerator looks like$ (2\pi)^{n/2}$and the denominator looks like a factorial, except it skips every other number. So an even dimension would look like$ 2 \cdot 4 \cdot \dots \cdot n$, and this grows larger than a fixed exponential. So in fact the total volume of the sphere vanishes as the dimension grows! (In addition to the ratio vanishing!) def sphereVolume(n): values = [0] * (n+1) for i in range(n+1): if i == 0: values[i] = 1 elif i == 1: values[i] = 2 else: values[i] = 2*math.pi / i * values[i-2] return values[-1]  This should be counterintuitive. I think most people would guess, when asked about how the volume of the unit sphere changes as the dimension grows, that it stays the same or gets bigger. But at a hundred dimensions, the volume is already getting too small to fit in a float. &gt;&gt;&gt; sphereVolume(20) 0.025806891390014047 &gt;&gt;&gt; sphereVolume(100) 2.3682021018828297e-40 &gt;&gt;&gt; sphereVolume(1000) 0.0  The scary thing is not just that this value drops, but that it drops exponentially quickly. A consequence is that, if you’re trying to cluster data points by looking at points within a fixed distance$ r$of one point, you have to carefully measure how big$ r$needs to be to cover the same proportional volume as it would in low dimension. Here’s a related issue. Say I take a bunch of points generated uniformly at random in the unit cube. from itertools import combinations def distancesRandomPoints(n, numSamples): randomSample = [randUnitCube(n) for _ in range(numSamples)] pairwiseDistances = [dist(x,y) for (x,y) in combinations(randomSample, 2)] return pairwiseDistances  In two dimensions, the histogram of distances between points looks like this However, as the dimension grows the distribution of distances changes. It evolves like the following animation, in which each frame is an increase in dimension from 2 to 100. The shape of the distribution doesn’t appear to be changing all that much after the first few frames, but the center of the distribution tends to infinity (in fact, it grows like$ \sqrt{n}$). The variance also appears to stay constant. This chart also becomes more variable as the dimension grows, again because we should be sampling exponentially many more points as the dimension grows (but we don’t). In other words, as the dimension grows the average distance grows and the tightness of the distribution stays the same. So at a thousand dimensions the average distance is about 26, tightly concentrated between 24 and 28. When the average is a thousand, the distribution is tight between 998 and 1002. If one were to normalize this data, it would appear that random points are all becoming equidistant from each other. So in addition to the issues of runtime and sampling, the geometry of high-dimensional space looks different from what we expect. To get a better understanding of “big data,” we have to update our intuition from low-dimensional geometry with analysis and mathematical theorems that are much harder to visualize. ## The Johnson-Lindenstrauss Lemma Now we turn to proving dimension reduction is possible. There are a few methods one might first think of, such as look for suitable subsets of coordinates, or sums of subsets, but these would all appear to take a long time or they simply don’t work. Instead, the key technique is to take a random linear subspace of a certain dimension, and project every data point onto that subspace. No searching required. The fact that this works is called the Johnson-Lindenstrauss Lemma. To set up some notation, we’ll call$ d(v,w)$the usual distance between two points. Lemma [Johnson-Lindenstrauss (1984)]: Given a set$ X$of$ n$points in$ \mathbb{R}^d$, project the points in$ X$to a randomly chosen subspace of dimension$ c$. Call the projection$ \rho$. For any$ \varepsilon > 0$, if$ c$is at least$ \Omega(\log(n) / \varepsilon^2)$, then with probability at least 1/2 the distances between points in$ X$are preserved up to a factor of$ (1+\varepsilon)$. That is, with good probability every pair$ v,w \in X$will satisfy$ \displaystyle \| v-w \|^2 (1-\varepsilon) \leq \| \rho(v) – \rho(w) \|^2 \leq \| v-w \|^2 (1+\varepsilon)$Before we do the proof, which is quite short, it’s important to point out that the target dimension$ c$does not depend on the original dimension! It only depends on the number of points in the dataset, and logarithmically so. That makes this lemma seem like pure magic, that you can take data in an arbitrarily high dimension and put it in a much smaller dimension. On the other hand, if you include all of the hidden constants in the bound on the dimension, it’s not that impressive. If your data have a million dimensions and you want to preserve the distances up to 1% ($ \varepsilon = 0.01$), the bound is bigger than a million! If you decrease the preservation$ \varepsilon$to 10% (0.1), then you get down to about 12,000 dimensions, which is more reasonable. At 45% the bound drops to around 1,000 dimensions. Here’s a plot showing the theoretical bound on$ c$in terms of$ \varepsilon$for$ n$fixed to a million. But keep in mind, this is just a theoretical bound for potentially misbehaving data. Later in this post we’ll see if the practical dimension can be reduced more than the theory allows. As we’ll see, an algorithm run on the projected data is still effective even if the projection goes well beyond the theoretical bound. Because the theorem is known to be tight in the worst case (see the notes at the end) this speaks more to the robustness of the typical algorithm than to the robustness of the projection method. A second important note is that this technique does not necessarily avoid all the problems with the curse of dimensionality. We mentioned above that one potential problem is that “random points” are roughly equidistant in high dimensions. Johnson-Lindenstrauss actually preserves this problem because it preserves distances! As a consequence, you won’t see strictly better algorithm performance if you project (which we suggested is possible in the beginning of this post). But you will alleviate slow runtimes if the runtime depends exponentially on the dimension. Indeed, if you replace the dimension$ d$with the logarithm of the number of points$ \log n$, then$ 2^d$becomes linear in$ n$, and$ 2^{O(d)}$becomes polynomial. ## Proof of the J-L lemma Let’s prove the lemma. Proof. To start we make note that one can sample from the uniform distribution on dimension-$ c$linear subspaces of$ \mathbb{R}^d$by choosing the entries of a$ c \times d$matrix$ A$independently from a normal distribution with mean 0 and variance 1. Then, to project a vector$ x$by this matrix (call the projection$ \rho$), we can compute$ \displaystyle \rho(x) = \frac{1}{\sqrt{c}}A x$Now fix$ \varepsilon > 0$and fix two points in the dataset$ x,y$. We want an upper bound on the probability that the following is false$ \displaystyle \| x-y \|^2 (1-\varepsilon) \leq \| \rho(x) – \rho(y) \|^2 \leq \| x-y \|^2 (1+\varepsilon)$Since that expression is a pain to work with, let’s rearrange it by calling$ u = x-y$, and rearranging (using the linearity of the projection) to get the equivalent statement.$ \left | \| \rho(u) \|^2 – \|u \|^2 \right | \leq \varepsilon \| u \|^2$And so we want a bound on the probability that this event does not occur, meaning the inequality switches directions. Once we get such a bound (it will depend on$ c$and$ \varepsilon$) we need to ensure that this bound is true for every pair of points. The union bound allows us to do this, but it also requires that the probability of the bad thing happening tends to zero faster than$ 1/\binom{n}{2}$. That’s where the$ \log(n)$will come into the bound as stated in the theorem. Continuing with our use of$ u$for notation, define$ X$to be the random variable$ \frac{c}{\| u \|^2} \| \rho(u) \|^2$. By expanding the notation and using the linearity of expectation, you can show that the expected value of$ X$is$ c$, meaning that in expectation, distances are preserved. We are on the right track, and just need to show that the distribution of$ X$, and thus the possible deviations in distances, is tightly concentrated around$ c$. In full rigor, we will show$ \displaystyle \Pr [X \geq (1+\varepsilon) c] < e^{-(\varepsilon^2 – \varepsilon^3) \frac{c}{4}}$Let$ A_i$denote the$ i$-th column of$ A$. Define by$ X_i$the quantity$ \langle A_i, u \rangle / \| u \|$. This is a weighted average of the entries of$ A_i$by the entries of$ u$. But since we chose the entries of$ A$from the normal distribution, and since a weighted average of normally distributed random variables is also normally distributed (has the same distribution),$ X_i$is a$ N(0,1)$random variable. Moreover, each column is independent. This allows us to decompose$ X$as$ X = \frac{k}{\| u \|^2} \| \rho(u) \|^2 = \frac{\| Au \|^2}{\| u \|^2}$Expanding further,$ X = \sum_{i=1}^c \frac{\| A_i u \|^2}{\|u\|^2} = \sum_{i=1}^c X_i^2$Now the event$ X \leq (1+\varepsilon) c$can be expressed in terms of the nonegative variable$ e^{\lambda X}$, where$ 0 < \lambda < 1/2$is parameter, to get$ \displaystyle \Pr[X \geq (1+\varepsilon) c] = \Pr[e^{\lambda X} \geq e^{(1+\varepsilon)c \lambda}]$This will become useful because the sum$ X = \sum_i X_i^2$will split into a product momentarily. First we apply Markov’s inequality, which says that for any nonnegative random variable$ Y$,$ \Pr[Y \geq t] \leq \mathbb{E}[Y] / t$. This lets us write$ \displaystyle \Pr[e^{\lambda X} \geq e^{(1+\varepsilon) c \lambda}] \leq \frac{\mathbb{E}[e^{\lambda X}]}{e^{(1+\varepsilon) c \lambda}}$Now we can split up the exponent$ \lambda X$into$ \sum_{i=1}^c \lambda X_i^2$, and using the i.i.d.-ness of the$ X_i^2$we can rewrite the RHS of the inequality as$ \left ( \frac{\mathbb{E}[e^{\lambda X_1^2}]}{e^{(1+\varepsilon)\lambda}} \right )^c$A similar statement using$ -\lambda$is true for the$ (1-\varepsilon)$part, namely that$ \displaystyle \Pr[X \leq (1-\varepsilon)c] \leq \left ( \frac{\mathbb{E}[e^{-\lambda X_1^2}]}{e^{-(1-\varepsilon)\lambda}} \right )^c$The last thing that’s needed is to bound$ \mathbb{E}[e^{\lambda X_i^2}]$, but since$ X_i^2 \sim N(0,1)$, we can use the known density function for a normal distribution, and integrate to get the exact value$ \mathbb{E}[e^{\lambda X_1^2}] = \frac{1}{\sqrt{1-2\lambda}}$. Including this in the bound gives us a closed-form bound in terms of$ \lambda, c, \varepsilon$. Using standard calculus the optimal$ \lambda \in (0,1/2)$is$ \lambda = \varepsilon / 2(1+\varepsilon)$. This gives$ \displaystyle \Pr[X \geq (1+\varepsilon) c] \leq ((1+\varepsilon)e^{-\varepsilon})^{c/2}$Using the Taylor series expansion for$ e^x$, one can show the bound$ 1+\varepsilon < e^{\varepsilon – (\varepsilon^2 – \varepsilon^3)/2}$, which simplifies the final upper bound to$ e^{-(\varepsilon^2 – \varepsilon^3) c/4}$. Doing the same thing for the$ (1-\varepsilon)$version gives an equivalent bound, and so the total bound is doubled, i.e.$ 2e^{-(\varepsilon^2 – \varepsilon^3) c/4}$. As we said at the beginning, applying the union bound means we need$ \displaystyle 2e^{-(\varepsilon^2 – \varepsilon^3) c/4} < \frac{1}{\binom{n}{2}}$Solving this for$ c$gives$ c \geq \frac{8 \log m}{\varepsilon^2 – \varepsilon^3}$, as desired.$ \square$## Projecting in Practice Let’s write a python program to actually perform the Johnson-Lindenstrauss dimension reduction scheme. This is sometimes called the Johnson-Lindenstrauss transform, or JLT. First we define a random subspace by sampling an appropriately-sized matrix with normally distributed entries, and a function that performs the projection onto a given subspace (for testing). import random import math import numpy def randomSubspace(subspaceDimension, ambientDimension): return numpy.random.normal(0, 1, size=(subspaceDimension, ambientDimension)) def project(v, subspace): subspaceDimension = len(subspace) return (1 / math.sqrt(subspaceDimension)) * subspace.dot(v)  We have a function that computes the theoretical bound on the optimal dimension to reduce to. def theoreticalBound(n, epsilon): return math.ceil(8*math.log(n) / (epsilon**2 - epsilon**3))  And then performing the JLT is simply matrix multiplication def jlt(data, subspaceDimension): ambientDimension = len(data[0]) A = randomSubspace(subspaceDimension, ambientDimension) return (1 / math.sqrt(subspaceDimension)) * A.dot(data.T).T  The high-dimensional dataset we’ll use comes from a data mining competition called KDD Cup 2001. The dataset we used deals with drug design, and the goal is to determine whether an organic compound binds to something called thrombin. Thrombin has something to do with blood clotting, and I won’t pretend I’m an expert. The dataset, however, has over a hundred thousand features for about 2,000 compounds. Here are a few approximate target dimensions we can hope for as epsilon varies. &gt;&gt;&gt; [((1/x),theoreticalBound(n=2000, epsilon=1/x)) for x in [2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20]] [('0.50', 487), ('0.33', 821), ('0.25', 1298), ('0.20', 1901), ('0.17', 2627), ('0.14', 3477), ('0.12', 4448), ('0.11', 5542), ('0.10', 6757), ('0.07', 14659), ('0.05', 25604)]  Going down from a hundred thousand dimensions to a few thousand is by any measure decreases the size of the dataset by about 95%. We can also observe how the distribution of overall distances varies as the size of the subspace we project to varies. The animation proceeds from 5000 dimensions down to 2 (when the plot is at its bulkiest closer to zero). The last three frames are for 10, 5, and 2 dimensions respectively. As you can see the histogram starts to beef up around zero. To be honest I was expecting something a bit more dramatic like a uniform-ish distribution. Of course, the distribution of distances is not all that matters. Another concern is the worst case change in distances between any two points before and after the projection. We can see that indeed when we project to the dimension specified in the theorem, that the distances are within the prescribed bounds. def checkTheorem(oldData, newData, epsilon): numBadPoints = 0 for (x,y), (x2,y2) in zip(combinations(oldData, 2), combinations(newData, 2)): oldNorm = numpy.linalg.norm(x2-y2)**2 newNorm = numpy.linalg.norm(x-y)**2 if newNorm == 0 or oldNorm == 0: continue if abs(oldNorm / newNorm - 1) &amp;gt; epsilon: numBadPoints += 1 return numBadPoints if __name__ == &amp;quot;__main__&amp;quot; from data import thrombin train, labels = thrombin.load() numPoints = len(train) epsilon = 0.2 subspaceDim = theoreticalBound(numPoints, epsilon) ambientDim = len(train[0]) newData = jlt(train, subspaceDim) print(checkTheorem(train, newData, epsilon))  This program prints zero every time I try running it, which is the poor man’s way of saying it works “with high probability.” We can also plot statistics about the number of pairs of data points that are distorted by more than$ \varepsilon$as the subspace dimension shrinks. We ran this on the following set of subspace dimensions with$ \varepsilon = 0.1$and took average/standard deviation over twenty trials:  dims = [1000, 750, 500, 250, 100, 75, 50, 25, 10, 5, 2]  The result is the following chart, whose x-axis is the dimension projected to (so the left hand is the most extreme projection to 2, 5, 10 dimensions), the y-axis is the number of distorted pairs, and the error bars represent a single standard deviation away from the mean. This chart provides good news about this dataset because the standard deviations are low. It tells us something that mathematicians often ignore: the predictability of the tradeoff that occurs once you go past the theoretically perfect bound. In this case, the standard deviations tell us that it’s highly predictable. Moreover, since this tradeoff curve measures pairs of points, we might conjecture that the distortion is localized around a single set of points that got significantly “rattled” by the projection. This would be an interesting exercise to explore. Now all of these charts are really playing with the JLT and confirming the correctness of our code (and hopefully our intuition). The real question is: how well does a machine learning algorithm perform on the original data when compared to the projected data? If the algorithm only “depends” on the pairwise distances between the points, then we should expect nearly identical accuracy in the unprojected and projected versions of the data. To show this we’ll use an easy learning algorithm, the k-nearest-neighbors clustering method. The problem, however, is that there are very few positive examples in this particular dataset. So looking for the majority label of the nearest$ k$neighbors for any$ k > 2$unilaterally results in the “all negative” classifier, which has 97% accuracy. This happens before and after projecting. To compensate for this, we modify k-nearest-neighbors slightly by having the label of a predicted point be 1 if any label among its nearest neighbors is 1. So it’s not a majority vote, but rather a logical OR of the labels of nearby neighbors. Our point in this post is not to solve the problem well, but rather to show how an algorithm (even a not-so-good one) can degrade as one projects the data into smaller and smaller dimensions. Here is the code. def nearestNeighborsAccuracy(data, labels, k=10): from sklearn.neighbors import NearestNeighbors trainData, trainLabels, testData, testLabels = randomSplit(data, labels) # cross validation model = NearestNeighbors(n_neighbors=k).fit(trainData) distances, indices = model.kneighbors(testData) predictedLabels = [] for x in indices: xLabels = [trainLabels[i] for i in x[1:]] predictedLabel = max(xLabels) predictedLabels.append(predictedLabel) totalAccuracy = sum(x == y for (x,y) in zip(testLabels, predictedLabels)) / len(testLabels) falsePositive = (sum(x == 0 and y == 1 for (x,y) in zip(testLabels, predictedLabels)) / sum(x == 0 for x in testLabels)) falseNegative = (sum(x == 1 and y == 0 for (x,y) in zip(testLabels, predictedLabels)) / sum(x == 1 for x in testLabels)) return totalAccuracy, falsePositive, falseNegative  And here is the accuracy of this modified k-nearest-neighbors algorithm run on the thrombin dataset. The horizontal line represents the accuracy of the produced classifier on the unmodified data set. The x-axis represents the dimension projected to (left-hand side is the lowest), and the y-axis represents the accuracy. The mean accuracy over fifty trials was plotted, with error bars representing one standard deviation. The complete code to reproduce the plot is in the Github repository. Likewise, we plot the proportion of false positive and false negatives for the output classifier. Note that a “positive” label made up only about 2% of the total data set. First the false positives Then the false negatives As we can see from these three charts, things don’t really change that much (for this dataset) even when we project down to around 200-300 dimensions. Note that for these parameters the “correct” theoretical choice for dimension was on the order of 5,000 dimensions, so this is a 95% savings from the naive approach, and 99.75% space savings from the original data. Not too shabby. ## Notes The$ \Omega(\log(n))$worst-case dimension bound is asymptotically tight, though there is some small gap in the literature that depends on$ \varepsilon$. This result is due to Noga Alon, the very last result (Section 9) of this paper. [Update: as djhsu points out in the comments, this gap is now closed thanks to Larsen and Nelson] We did dimension reduction with respect to preserving the Euclidean distance between points. One might naturally wonder if you can achieve the same dimension reduction with a different metric, say the taxicab metric or a$ p$-norm. In fact, you cannot achieve anything close to logarithmic dimension reduction for the taxicab ($ l_1$) metric. This result is due to Brinkman-Charikar in 2004. The code we used to compute the JLT is not particularly efficient. There are much more efficient methods. One of them, borrowing its namesake from the Fast Fourier Transform, is called the Fast Johnson-Lindenstrauss Transform. The technique is due to Ailon-Chazelle from 2009, and it involves something called “preconditioning a sparse projection matrix with a randomized Fourier transform.” I don’t know precisely what that means, but it would be neat to dive into that in a future post. The central focus in this post was whether the JLT preserves distances between points, but one might be curious as to whether the points themselves are well approximated. The answer is an enthusiastic no. If the data were images, the projected points would look nothing like the original images. However, it appears the degradation tradeoff is measurable (by some accounts perhaps linear), and there appears to be some work (also this by the same author) when restricting to sparse vectors (like word-association vectors). Note that the JLT is not the only method for dimensionality reduction. We previously saw principal component analysis (applied to face recognition), and in the future we will cover a related technique called the Singular Value Decomposition. It is worth noting that another common technique specific to nearest-neighbor is called “locality-sensitive hashing.” Here the goal is to project the points in such a way that “similar” points land very close to each other. Say, if you were to discretize the plane into bins, these bins would form the hash values and you’d want to maximize the probability that two points with the same label land in the same bin. Then you can do things like nearest-neighbors by comparing bins. Another interesting note, if your data is linearly separable (like the examples we saw in our age-old post on Perceptrons), then you can use the JLT to make finding a linear separator easier. First project the data onto the dimension given in the theorem. With high probability the points will still be linearly separable. And then you can use a perceptron-type algorithm in the smaller dimension. If you want to find out which side a new point is on, you project and compare with the separator in the smaller dimension. Beyond its interest for practical dimensionality reduction, the JLT has had many other interesting theoretical consequences. More generally, the idea of “randomly projecting” your data onto some small dimensional space has allowed mathematicians to get some of the best-known results on many optimization and learning problems, perhaps the most famous of which is called MAX-CUT; the result is by Goemans-Williamson and it led to a mathematical constant being named after them,$ \alpha_{GW} =.878567 \dots$. If you’re interested in more about the theory, Santosh Vempala wrote a wonderful (and short!) treatise dedicated to this topic. # Concrete Examples of Quantum Gates So far in this series we’ve seen a lot of motivation and defined basic ideas of what a quantum circuit is. But on rereading my posts, I think we would all benefit from some concreteness. ## “Local” operations So by now we’ve understood that quantum circuits consist of a sequence of gates$ A_1, \dots, A_k$, where each$ A_i$is an 8-by-8 matrix that operates “locally” on some choice of three (or fewer) qubits. And in your head you imagine starting with some state vector$ v$and applying each$ A_i$locally to its three qubits until the end when you measure the state and get some classical output. But the point I want to make is that$ A_i$actually changes the whole state vector$ v$, because the three qubits it acts “locally” on are part of the entire basis. Here’s an example. Suppose we have three qubits and they’re in the state$ \displaystyle v = \frac{1}{\sqrt{14}} (e_{001} + 2e_{011} – 3e_{101})$Recall we abbreviate basis states by subscripting them by binary strings, so$ e_{011} = e_0 \otimes e_1 \otimes e_1$, and a valid state is any unit vector over the$ 2^3 = 8$possible basis elements. As a vector, this state is$ \frac{1}{\sqrt{14}} (0,1,0,2,0,-3,0,0)$Say we apply the gate$ A$that swaps the first and third qubits. “Locally” this gate has the following matrix:$ \displaystyle \begin{pmatrix} 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \\ 0&0&0&1 \end{pmatrix}$where we index the rows and columns by the relevant strings in lexicographic order: 00, 01, 10, 11. So this operation leaves$ e_{00}$and$ e_{11}$the same while swapping the other two. However, as an operation on three qubits the operation looks quite different. And it’s sort of hard to describe a general way to write it down as a matrix because of the choice of indices. There are three different perspectives. Perspective 1: if the qubits being operated on are sequential (like, the third, fourth, and fifth qubits), then we can write the matrix as$ I_{2^{a}} \otimes A \otimes I_{2^{b}}$where a tensor product of matrices is the Kronecker product and$ a + b + \log \textup{dim}(A) = n$(the number of qubits adds up). Then the final operation looks like a “tiled product” of identity matrices by$ A$, but it’s a pain to write out. Let me hurt my self for your sake, dear reader. And each copy of$ A \otimes I_{2^b}$looks like That’s a mess, but if you write it out for our example of swapping the first and third qubits of a three-qubit register you get the following: And this makes sense: the gate changes any entry of the state vector that has values for the first and third qubit that are different. This is what happens to our state:$ \displaystyle v = \frac{1}{\sqrt{14}} (0,1,0,2,0,-3,0,0) \mapsto \frac{1}{\sqrt{14}} (0,0,0,0,1,-3,2,0)$Perspective 2: just assume every operation works on the first three qubits, and wrap each operation$ A$in between an operation that swaps the first three qubits with the desired three. So like$ BAB$for$ B$a swap operation. Then the matrix form looks a bit simpler, and it just means we permute the columns of the matrix form we gave above so that it just has the form$ A \otimes I_a$. This allows one to retain a shred of sanity when trying to envision the matrix for an operation that acts on three qubits that are not sequential. The downside is that to actually use this perspective in an analysis you have to carry around the extra baggage of these permutation matrices. So one might use this as a simplifying assumption (a “without loss of generality” statement). Perspective 3: ignore matrices and write things down in a summation form. So if$ \sigma$is the permutation that swaps 1 and 3 and leaves the other indices unchanged, we can write the general operation on a state$ v = \sum_{x \in \{ 0,1 \}^n } a_x e_{x}$as$ Av = \sum_{x \in \{ 0,1 \}^n} a_x e_{\sigma(x)}$. The third option is probably the nicest way to do things, but it’s important to keep the matrix view in mind for many reasons. Just one quick reason: “errors” in quantum gates (that are meant to approximately compute something) compound linearly in the number of gates because the operations are linear. This is a key reason that allows one to design quantum analogues of error correcting codes. So we’ve established that the basic (atomic) quantum gates are “local” in the sense that they operate on a fixed number of qubits, but they are not local in the sense that they can screw up the entire state vector. ## A side note on the meaning of “local” When I was chugging through learning this stuff (and I still have far to go), I wanted to come up with an alternate characterization of the word “local” so that I would feel better about using the word “local.” Mathematicians are as passionate about word choice as programmers are about text editors. In particular, for a long time I was ignorantly convinced that quantum gates that act on a small number of qubits don’t affect the marginal distribution of measurement outcomes for other qubits. That is, I thought that if$ A$acts on qubits 1,2,3, then$ Av$and$ v$have the same probability of a measurement producing a 1 in index 4, 5, etc, conditioned on fixing a measurement outcome for qubits 1,2,3. In notation, if$ x$is a random variable whose values are binary strings and$ v$is a state vector, I’ll call$ x \sim v$the random process of measuring a state vector$ v$and getting a string$ x$, then my claim was that the following was true for every$ b_1, b_2, b_3 \in \{0,1\}$and every$ 1 \leq i \leq n$:$ \displaystyle \begin{aligned}\Pr_{x \sim v}&[x_i = 1 \mid x_1 = b_1, x_2 = b_2, x_3 = b_3] = \\ \Pr_{x \sim Av}&[x_i = 1 \mid x_1 = b_1, x_2 = b_2, x_3 = b_3] \end{aligned}$You could try to prove this, and you would fail because it’s false. In fact, it’s even false if$ A$acts on only a single qubit! Because it’s so tedious to write out all of the notation, I decided to write a program to illustrate the counterexample. (The most brazenly dedicated readers will try to prove this false fact and identify where the proof fails.) import numpy H = (1/(2**0.5)) * numpy.array([[1,1], [1,-1]]) I = numpy.identity(4) A = numpy.kron(H,I)  Here$ H$is the 2 by 2 Hadamard matrix, which operates on a single qubit and maps$ e_0 \mapsto \frac{e_0 + e_1}{\sqrt{2}}$, and$ e_1 \mapsto \frac{e_0 – e_1}{\sqrt{2}}$. This matrix is famous for many reasons, but one simple use as a quantum gate is to generate uniform random coin flips. In particular, measuring$ He_0$outputs 1 and 0 with equal probability. So in the code sample above,$ A$is the mapping which applies the Hadamard operation to the first qubit and leaves the other qubits alone. Then we compute some arbitrary input state vector$ w$def normalize(z): return (1.0 / (sum(abs(z)**2) ** 0.5)) * z v = numpy.arange(1,9) w = normalize(v)  And now we write a function to compute the probability of some query conditioned on some fixed bits. We simply sum up the square norms of all of the relevant indices in the state vector. def condProb(state, query={}, fixed={}): num = 0 denom = 0 dim = int(math.log2(len(state))) for x in itertools.product([0,1], repeat=dim): if any(x[index] != b for (index,b) in fixed.items()): continue i = sum(d &lt;&lt; i for (i,d) in enumerate(reversed(x))) denom += abs(state[i])**2 if all(x[index] == b for (index, b) in query.items()): num += abs(state[i]) ** 2 if num == 0: return 0 return num / denom  So if the query is query = {1:0} and the fixed thing is fixed = {0:0}, then this will compute the probability that the measurement results in the second qubit being zero conditioned on the first qubit also being zero. And the result: Aw = A.dot(w) query = {1:0} fixed = {0:0} print((condProb(w, query, fixed), condProb(Aw, query, fixed))) # (0.16666666666666666, 0.29069767441860467)  So they are not equal in general. Also, in general we won’t work explicitly with full quantum gate matrices, since for$ n$qubits the have size$ 2^{2n}$which is big. But for finding counterexamples to guesses and false intuition, it’s a great tool. ## Some important gates on 1-3 qubits Let’s close this post with concrete examples of quantum gates. Based on the above discussion, we can write out the 2 x 2 or 4 x 4 matrix form of the operation and understand that it can apply to any two qubits in the state of a quantum program. Gates are most interesting when they’re operating on entangled qubits, and that will come out when we visit our first quantum algorithm next time, but for now we will just discuss at a naive level how they operate on the basis vectors. ### Hadamard gate: We introduced the Hadamard gate already, but I’ll reiterate it here. Let$ H$be the following 2 by 2 matrix, which operates on a single qubit and maps$ e_0 \mapsto \frac{e_0 + e_1}{\sqrt{2}}$, and$ e_1 \mapsto \frac{e_0 – e_1}{\sqrt{2}}$.$ \displaystyle H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$One can use$ H$to generate uniform random coin flips. In particular, measuring$ He_0$outputs 1 and 0 with equal probability. ### Quantum NOT gate: Let$ X$be the 2 x 2 matrix formed by swapping the columns of the identity matrix.$ \displaystyle X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$This gate is often called the “Pauli-X” gate by physicists. This matrix is far too simple to be named after a person, and I can only imagine it is still named after a person for the layer of obfuscation that so often makes people feel smarter (same goes for the Pauli-Y and Pauli-Z gates, but we’ll get to those when we need them). If we’re thinking of$ e_0$as the boolean value “false” and$ e_1$as the boolean value “true”, then the quantum NOT gate simply swaps those two states. In particular, note that composing a Hadamard and a quantum NOT gate can have interesting effects:$ XH(e_0) = H(e_0)$, but$ XH(e_1) \neq H(e_1)$. In the second case, the minus sign is the culprit. Which brings us to… ### Phase shift gate: Given an angle$ \theta$, we can “shift the phase” of one qubit by an angle of$ \theta$using the 2 x 2 matrix$ R_{\theta}$.$ \displaystyle R_{\theta} = \begin{pmatrix} 1 & 0 \\ 0 & e^{i \theta} \end{pmatrix}$“Phase” is a term physicists like to use for angles. Since the coefficients of a quantum state vector are complex numbers, and since complex numbers can be thought of geometrically as vectors with direction and magnitude, it makes sense to “rotate” the coefficient of a single qubit. So$ R_{\theta}$does nothing to$ e_0$and it rotates the coefficient of$ e_1$by an angle of$ \theta$. Continuing in our theme of concreteness, if I have the state vector$ v = \frac{1}{\sqrt{204}} (1,2,3,4,5,6,7,8)$and I apply a rotation of$ pi$to the second qubit, then my operation is the matrix$ I_2 \otimes R_{\pi} \otimes I_2$which maps$ e_{i0k} \mapsto e_{i0k}$and$ e_{i1k} \mapsto -e_{i1k}$. That would map the state$ v$to$ (1,2,-3,-4,5,6,-7,-8)$. If we instead used the rotation by$ \pi/2$we would get the output state$ (1,2,3i, 4i, 5, 6, 7i, 8i)$. ### Quantum AND/OR gate: In the last post in this series we gave the quantum AND gate and left the quantum OR gate as an exercise. Rather than write out the matrix again, let me remind you of this gate using a description of the effect on the basis$ e_{ijk}$where$ i,j,k \in \{ 0,1 \}$. Recall that we need three qubits in order to make the operation reversible (which is a consequence of all unitary gates being unitary matrices). Some notation:$ \oplus$is the XOR of two bits, and$ \wedge$is AND,$ \vee$is OR. The quantum AND gate maps$ \displaystyle e_{ijk} \mapsto e_{ij(k \oplus (i \wedge j))}$In words, the third coordinate is XORed with the AND of the first two coordinates. We think of the third coordinate as a “scratchwork” qubit which is maybe prepared ahead of time to be in state zero. Simiarly, the quantum OR gate maps$ e_{ijk} \mapsto e_{ij(k \oplus (i \vee j))}$. As we saw last time these combined with the quantum NOT gate (and some modest number of scratchwork qubits) allows quantum circuits to simulate any classical circuit. ### Controlled-* gate: The last example in this post is a meta-gate that represents a conditional branching. If we’re given a gate$ A$acting on$ k$qubits, then we define the controlled-A to be an operation which acts on$ k+1$qubits. Let’s call the added qubit “qubit zero.” Then controlled-A does nothing if qubit zero is in state 0, and applies$ A$if qubit zero is in state 1. Qubit zero is generally called the “control qubit.” The matrix representing this operation decomposes into blocks if the control qubit is actually the first qubit (or you rearrange).$ \displaystyle \begin{pmatrix} I_{2^{k-1}} & 0 \\ 0 & A \end{pmatrix}$A common example of this is the controlled-NOT gate, often abbreviated CNOT, and it has the matrix$ \displaystyle \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$## Looking forward Okay let’s take a step back and evaluate our life choices. So far we’ve spent a few hours of our time motivating quantum computing, explaining the details of qubits and quantum circuits, and seeing examples of concrete quantum gates and studying measurement. I’ve hopefully hammered into your head the notion that quantum states which aren’t pure tensors (i.e. entangled) are where the “weirdness” of quantum computing comes from. But we haven’t seen any examples of quantum algorithms yet! Next time we’ll see our first example of an algorithm that is genuinely quantum. We won’t tackle factoring yet, but we will see quantum “weirdness” in action. Until then! # Hashing to Estimate the Size of a Stream Problem: Estimate the number of distinct items in a data stream that is too large to fit in memory. Solution: (in python) import random def randomHash(modulus): a, b = random.randint(0,modulus-1), random.randint(0,modulus-1) def f(x): return (a*x + b) % modulus return f def average(L): return sum(L) / len(L) def numDistinctElements(stream, numParallelHashes=10): modulus = 2**20 hashes = [randomHash(modulus) for _ in range(numParallelHashes)] minima = [modulus] * numParallelHashes currentEstimate = 0 for i in stream: hashValues = [h(i) for h in hashes] for i, newValue in enumerate(hashValues): if newValue &lt; minima[i]: minima[i] = newValue currentEstimate = modulus / average(minima) yield currentEstimate  Discussion: The technique used here is to use random hash functions. The central idea is the same as the general principle presented in our recent post on hashing for load balancing. In particular, if you have an algorithm that works under the assumption that the data is uniformly random, then the same algorithm will work (up to a good approximation) if you process the data through a randomly chosen hash function. So if we assume the data in the stream consists of$ N$uniformly random real numbers between zero and one, what we would do is the following. Maintain a single number$ x_{\textup{min}}$representing the minimum element in the list, and update it every time we encounter a smaller number in the stream. A simple probability calculation or an argument by symmetry shows that the expected value of the minimum is$ 1/(N+1)$. So your estimate would be$ 1/(x_{\textup{min}}+1)$. (The extra +1 does not change much as we’ll see.) One can spend some time thinking about the variance of this estimate (indeed, our earlier post is great guidance for how such a calculation would work), but since the data is not random we need to do more work. If the elements are actually integers between zero and$ k$, then this estimate can be scaled by$ k$and everything basically works out the same. Processing the data through a hash function$ h$chosen randomly from a 2-universal family (and we proved in the aforementioned post that this modulus thing is 2-universal) makes the outputs “essentially random” enough to have the above technique work with some small loss in accuracy. And to reduce variance, you can process the stream in parallel with many random hash functions. This rough sketch results in the code above. Indeed, before I state a formal theorem, let’s see the above code in action. First on truly random data: S = [random.randint(1,2**20) for _ in range(10000)] for k in range(10,301,10): for est in numDistinctElements(S, k): pass print(abs(est)) # output 18299.75567190227 7940.7497160166595 12034.154552410098 12387.19432959244 15205.56844547564 8409.913113220158 8057.99978043693 9987.627098464103 10313.862295081966 9084.872639057356 10952.745228373375 10360.569781803211 11022.469475216301 9741.250165892501 11474.896038520465 10538.452261306533 10068.793492995934 10100.266495424627 9780.532155130093 8806.382800033594 10354.11482578643 10001.59202254498 10623.87031408308 9400.404915767062 10710.246772348424 10210.087633885101 9943.64709187974 10459.610972568578 10159.60175069326 9213.120899718839  As you can see the output is never off by more than a factor of 2. Now with “adversarial data.” S = range(10000) #[random.randint(1,2**20) for _ in range(10000)] for k in range(10,301,10): for est in numDistinctElements(S, k): pass print(abs(est)) # output 12192.744186046511 15935.80547112462 10167.188106011634 12977.425742574258 6454.364151175674 7405.197740112994 11247.367453263867 4261.854392115023 8453.228233608026 7706.717624577393 7582.891328643745 5152.918628936483 1996.9365093316926 8319.20208545846 3259.0787592465967 6812.252720480753 4975.796789951151 8456.258064516129 8851.10133724288 7317.348220516398 10527.871485943775 3999.76974425661 3696.2999065091117 8308.843106180666 6740.999794281012 8468.603733730935 5728.532232608959 5822.072220349402 6382.349459544548 8734.008940222673  The estimates here are off by a factor of up to 5, and this estimate seems to get better as the number of hash functions used increases. The formal theorem is this: Theorem: If$ S$is the set of distinct items in the stream and$ n = |S|$and$ m > 100 n$, then with probability at least 2/3 the estimate$ m / x_{\textup{min}}$is between$ n/6$and$ 6n$. We omit the proof (see below for references and better methods). As a quick analysis, since we’re only storing a constant number of integers at any given step, the algorithm has space requirement$ O(\log m) = O(\log n)$, and each step takes time polynomial in$ \log(m)$to update in each step (since we have to compute multiplication and modulus of$ m$). This method is just the first ripple in a lake of research on this topic. The general area is called “streaming algorithms,” or “sublinear algorithms.” This particular problem, called cardinality estimation, is related to a family of problems called estimating frequency moments. The literature gets pretty involved in the various tradeoffs between space requirements and processing time per stream element. As far as estimating cardinality goes, the first major results were due to Flajolet and Martin in 1983, where they provided a slightly more involved version of the above algorithm, which uses logarithmic space. Later revisions to the algorithm (2003) got the space requirement down to$ O(\log \log n)$, which is exponentially better than our solution. And further tweaks and analysis improved the variance bounds to something like a multiplicative factor of$ \sqrt{m}\$. This is called the HyperLogLog algorithm, and it has been tested in practice at Google.

Finally, a theoretically optimal algorithm (achieving an arbitrarily good estimate with logarithmic space) was presented and analyzed by Kane et al in 2010.