% Lecture 21: Quantum computing and cryptography % Boaz Barak
\newcommand{\E}{\mathbb{E}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\leftarrow_R}{\leftarrow_R;} \newcommand{\mathbb{G}}{\mathbb{G}} \newcommand{\Hp}{\mathbb{H}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\bra}[1]{\langle #1 |} \newcommand{\ket}[1]{| #1 \rangle}
"I think I can safely say that nobody understands quantum mechanics." , Richard Feynman, 1965
"The only difference between a probabilistic classical world and the equations of the quantum world is that somehow or other it appears as if the probabilities would have to go negative ", Richard Feynman, 1982
For much of the history of mankind, people believed that the ultimate "theory of everything" would be of the "billiard ball" type.
That is, at the end of the day, everything is composed of some elementary particles and adjacent particles interact with one another according to some well specified laws.
The types of particles and laws might differ, but not the general shape of the theory.
Note that this in particular means that a system of
Alas, in the beginning of the 20th century, several experimental results were calling into question the "billiard ball" theory of the world.
One such experiment is the famous "double slit" experiment.
Suppose we shoot an electron at a wall that has a single slit at position
Quantum mechanics is a mathematical theory that allows us to calculate and predict the results of this and many other examples. If you think of quantum as an explanation as to what "really" goes on in the world, it can be rather confusing. However, if you simply "shut up and calculate" then it works amazingly well at predicting the results of a great many experiments.
In the double slit experiment, quantum mechanics still allows to compute numbers
Some of the counterintuitive properties that arise from these negative probabilities include:
- Interference - As we see here, probabilities can "cancel each other out".
- Measurement - The idea that probabilities are negative as long as "no one is looking" and "collapse" to positive probabilities when they are measured is deeply disturbing. Indeed, people have shown that it can yield to various strange outcomes such as "spooky actions at a distance", where we can measure an object at one place and instantaously (faster than the speed of light) cause a difference in the results of a measurements in a place far removed. Unfortunately (or fortunately?) these strange outcomes have been confirmed experimentally.
- Entanglement - The notion that two parts of the system could be connected in this weird way where measuring one will affect the other is known as quantum entanglement.
Again, as counter-intuitive as these concepts are, they have been experimentally confirmed, so we just have to live with them.
One of the strange aspects of the quantum-mechanical picture of the world is that unlike in the billiard ball example, there is no obvious algorithm to simulate the evolution of
In the 1981, physicist Richard Feynman proposed to "turn this lemon to lemonade" by making the following almost tautological observation:
If a physical system cannot be simulated by a computer in $T$ steps, the system can be considered as performing a computation that would take more than $T$ steps
So, he asked whether one could design a quantum system such that its outcome
For a while these hypothetical quantum computers seemed useful for one of two things. First, to provide a general-purpose mechanism to simulate a variety of the real quantum systems that people care about. Second, as a challenge to the theory of computation's approach to model efficient computation by Turing machines, though a challenge that has little bearing to practice, given that this theoretical "extra power" of quantum computer seemed to offer little advantage in the problems people actually want to solve such as combinatorial optimization, machine learning, data structures, etc..
To a significant extent, this is still true today. We have no real evidence that quantum computers, if built, will offer truly significant3 advantage in 99% of the applications of computing.4
However, there is one cryptography-sized exception:
In 1994 Peter Shor showed that quantum computers can solve the integer factoring and discrete logarithm in polynomial time.
This result has captured the imagination of a great many people, and completely energized research into quantum computing.
This is both because the hardness of these particular problems provides the foundations for securing such a huge part of our communications (and these days, our economy), as well as it was a powerful demonstration that quantum computers could turn out to be useful for problems that a-priori seemd to have nothing to do with quantum physics.
As we'll discuss later, at the moment there are several intensive efforts to construct large scale quantum computers.
It seems safe to say that, as far as we know, in the next five years or so there will not be a quantum computer large enough to factor, say, a
The above summary might be all that you need to know as a cryptographer, and enough motivation to study lattice-based cryptography as we do in this course. However, because quantum computing is such a beautiful and (like cryptography) counter-intuitive concept, we will try to give at least a hint of what is it about and how does Shor's algorithm work.
Quantum cryptogrpahy: There is another way in which quantum mechanics interacts with cryptography. These "spooky actions at a distance" have been suggested by Weisner and Bennet-Brassard as a way in which parties can create a secret shared key over an insecure channel. On one hand, this concept does not require as much control as general-purpose quantum computing, and so it has in fact been demonstrated physically. On the other hand, unlike transmitting standard digital information, this "insecure channel" cannot be an arbitrary media such as wifi etc.. but rather one needs fiber optics, lasers, etc.. Unlike quantum computers, where we only need one of those to break RSA, to actually use key exchange at scale we need to setup these type of networks, and so it is unclear if this approach will ever dominate the solution of Alice sending to Bob a Brink's truck with the shared secret key. People have proposed some other ways to use the interesting properties of quantum mechanics for cryptographic purposes including quantum money and quantum software protection.
We now present some of the basic notions in quantum information. It is very useful to contrast these notions to the setting of probabilistic systems and see how "negative probabilities" make a difference. This discussion is somewhat brief. The chapter on quantum computation in my book with Arora (see draft here) is one relatively short resource that contains essentially everything we discuss here. See also this blog post of Aaronson for a high level explanation of Shor's algorithm which ends with links to several more detailed expositions. See also this lecture of Aaronson for a great discussion of the feasibility of quantum computing (Aaronson's course lecture notes and the book that they spawned are fantastic reads as well).
States: We will consider a simple quantum system that includes
Measurement: Suppose that we were in the classical probabilistic setting, and that the
Operations: In the classical probabilistic setting, if we have a system in state
Another way to state this, is that
Elementary operations: Of course, even in the probabilistic setting, not every function
Complexity: For every stochastic matrix
We say that
Computing functions: We have defined what it means for an operator to be probabilistically or quantumly efficiently computable, but we typically are interested in computing some function
Quantum and classical computation: The way we defined what it means for a function to be efficiently quantumly computable, it might not be clear that if
The "obviously exponential" fallacy: A priori it might seem "obvious" that quantum computing is exponentially powerful, since to compute a quantum computation on
To realize quantum computation one needs to create a system with
There have been several proposals to build quantum computers:
-
Superconducting quantum computers use super-conducting electric circuits to do quantum computation. Recent works have shown one can keep these superconducting qubits fairly robust to the point one can do some error correction on them (see also here).
-
Trapped ion quantum computers Use the states of an ion to simulate a qubit. People have made some recent advances on these computers too. While it's not clear that's the right measuring yard, the current best implementation of Shor's algorithm (for factoring 15) is done using an ion-trap computer.
-
Topological quantum computers use a different technology, which is more stable by design but arguably harder to manipulate to create quantum computers.
These approaches are not mutually exclusive and it could be that ultimately quantum computers are built by combining all of them together. I am not at all an expert on this matter, but it seems that progress has been slow but steady and it is quite possible that we'll see a 20-50 qubit computer sometime in the next 5-10 years.
Quantum computing is very confusing and counterintuitive for many reasons. But there is also a "cultural" reason why people sometimes find quantum arguments hard to follow. Quantum folks follow their own special notation for vectors. Many non quantum people find it ugly and confusing, while quantum folks secretly wish they people used it all the time, not just for non-quantum linear algebra, but also for restaurant bills and elemntary school math classes.
The notation is actually not so confusing. If
A quantum gate is an operation on at most three bits, and so it can be completely specified by what it does to the
There is something weird about quantum mechanics. In 1935 Einstein, Podolsky and Rosen (EPR) tried to pinpoint this issue by highlighting a previously unrealized corollary of this theory. It was already realized that the fact that quantum measurement collapses the state to a definite aspect yields the uncertainty principle, whereby if you measure a quantum system in one orthogonal basis, you will not know how it would have measured in an incohrent basis to it (such as position vs. momentum). What EPR showed was that quantum mechanics results in so called "spooky action at a distance" where if you have a system of two particles then measuring one of them would instantenously effect the state of the other. Since this "state" is just a mathematical description, as far as I know the EPR paper was considered to be a thought experiment showing troubling aspects of quantum mechanics, without bearing on experiment. This changed when in 1965 John Bell showed an actual experiment to test the predictions of EPR and hence pit intuitive common sense against the predictions of quantum mechanics. Quantum mechanics won. Nonetheless, since the results of these experiments are so obviously wrong to anyone that has ever sat in an armchair, that there are still a number of Bell denialists arguing that quantum mechanics is wrong in some way.
So, what is this Bell's Inequality?
Suppose that Alice and Bob try to convince you they have telepathic ability, and they aim to prove it via the following experiment.
Alice and Bob will be in separate closed rooms.9
You will interrogate Alice and your associate will interrogate Bob.
You choose a random bit
Now if Alice and Bob are not telepathic, then they need to agree in advance on some strategy.
The most general form of such a strategy is that Alice and Bob agree on some distribution over a pair of functions
Claim: For every two functions
Proof: Suppose toward a contradiction that
An amazing experimentally verified fact is that quantum mechanics allows for telepathy:11
Claim: There is a strategy for Alice and Bob to succeed in this game with probability at least
Proof: The main idea is for Alice and Bob to first prepare a 2-qubit quantum system in the state (up to normalization)
If
Quantum vs probabilistic strategies: It is instructive to understand what is it about quantum mechanics that enabled this gain in Bell's Inequality. For this, consider the following analogous probabilistic strategy for Alice and Bob. They agree that each one of them output
$0$ if he or she get$0$ as input and outputs$1$ with probability$p$ if they get$1$ as input. In this case one can see that their success probability would be$\tfrac{1}{4}\cdot 1 + \tfrac{1}{2}(1-p)+\tfrac{1}{4}[2p(1-p)]=0.75 -0.5p^2 \leq 0.75$ . The quantum strategy we described above can be thought of as a variant of the probabilistic strategy for$p$ is$\sin^2 (\pi/8)=0.15$ . But in the case$x=y=1$ , instead of disagreeing only with probability$2p(1-p)=1/4$ , because we can use these negative probabilities in the quantum world and rotate the state in opposite directions, the probability of disagreement ends up being$\sin^2 (\pi/4)=0.5$ .
Bell's Inequality is powerful demonstration that there is something very strange going on with quantum mechanics. But could this "strangeness" be of any use to solve computational problems not directly related to quantum systems? A priori, one could guess the answer is no. In 1994 Peter Shor showed that one would be wrong:
Theorem (Shor's Theorem): The map that takes an integer
This is an exponential improvement over the best known classical algorithms, which as we mentioned before, take roughly
We will now sketch the ideas behind Shor's algorithm. In fact, Shor proved the following more general theorem:
Theorem: There is a quantum polynomial time algorithm that given a multiplicative Abelian group
Recall that the order of
The order finding problem allows not just to factor integers in polynomial time, but also solve the discrete logarithm over arbitrary Abelian groups, hereby showing that quantum computers will break not just RSA but also Diffie Hellman and Elliptic Curve Cryptography. We merely sketch how one reduces the factoring and discrete logarithm problems to order finding: (see some of the sources above for the full details)
-
For factoring, let us restrict to the case
$m=pq$ for distinct$p,q$ . Recall that we showed that finding the size$(p-1)(q-1)=m-p-q-1$ of the group $\Z^_m$ is sufficient to recover $p$ and $q$. One can show that if we pick a few random $x$'s in $\Z^_m$ and compute their order, the least common multiplier of these orders is likely to be the group size. -
For discrete log in a group
$\mathbb{G}$ , if we get$X=g^x$ and need to recover$x$ , we can compute the order of various elements of the form$X^ag^b$ . The order of such an element is a number$c$ satisfying$c(xa+b) = 0 \pmod{|\mathbb{G}|}$ . Again, with a few random examples we will get a non trivial example (where$c \neq 0 \pmod{|\mathbb{G}|}$ ) and be able to recover the unknown$x$ .
Let
How do we generally find the period of a function? Let us consider the simplest case, where
Similarly, the main idea behind Shor's algorithm is to use a tool known as the quantum fourier transform that given a circuit computing the function
Shor carried out this approach for the group
Theorem (Simon's Algorithm): If $f:{0,1}^n\rightarrow{0,1}^$ is polynomial time computable and satisfies the property that $f(x)=f(y)$ iff $x\oplus y = h^$ then there exists
a quantum polynomial-time algorithm that outputs a random
Note that given
Proof: Let
Simon's algorithm seems to really use the special bit-wise structure of the group
Shor's Algorithm is an amazing achievement, but it only applies to very particular problems.
It does not seem to be relevant to breaking AES, lattice based cryptography, or problems not related to quantum computing at all such as scheduling, constraint satisfaction, traveling salesperson etc.. etc..
Indeed, for the most general form of these search problems, classically we don't how to do anything much better than brute force search, which takes
Theorem (Grover search , 1996): There is a quantum
Proof sketch: The proof is not hard but we only sketch it here.
The general idea can be illustrated in the case that there exists a single $x^$ satisfying $f(x^)=1$.
(There is a classical reduction from the general case to this problem.)
As in Simon's algorithm, we can efficiently initialize an
It is an exercise to show that using
Now, let
Footnotes
-
If you have seen quantum mechanics before, I should warn that I am making here many simplifications. In particular in quantunm mechanics the "probabilities" can actually be complex numbers, though one gets most of the qualitative understanding by considering them as potentially negative real numbers. I will also be focusing throughout this presentation on so called "pure" quantum states, and ignore the fact that generally the states of a quantum subsystem are mixed states that are a convex combination of pure states and can be described by a so called density matrix. This issue does not arise as much in quantum algorithms precisely because the goal is for a quantum computer is to be an isolated system that can evolve to continue to be in a pure state; in real world quantum computers however there will be interference from the outside world that causes the state to become mixed and increase its so called "von Neumann entropy"- fighting this interference and the second law of thermodynamics is much of what the challenge of building quantum computers is all about . More generally, this lecture is not meant to be a complete or accurate description of quantum mechanics, quantum information theory, or quantum computing, but rather just give a sense of the main points that are different about it from classical computing and how they relate to cryptography. ↩
-
As its title suggests, Feynman's lecture was actually focused on the other side of simulating physics with a computer, but he mentioned that as a "side remark" one could wonder if it's possible to simulate physics with a new kind of computer - a "quantum computer" which would "not [be] a Turing machine, but a machine of a different kind". As far as I know, Feynman did not suggest that such a computer could be useful for computations completely outside the domain of quantum simulation, and in fact he found the question of whether quantum mechanics could be simulated by a classical computer to be more interesting. ↩
-
I am using the theorist' definition of conflating "significant" with "super-polynomial". As we'll see, Grover's algorithm does offer a very generic quadratic advantage in computation. Whether that quadratic advantage will ever be good enough to offset in practice the significant overhead in building a quantum computer remains an open question. We also don't have evidence that super-polynomial speedups can't be achieved for some problems outside the Factoring/Dlog or quantum simulation domains, and there is at least one company banking on such speedups actually being feasible. ↩
-
This "99%" is a figure of speech, but not completely so. It seems that for many web servers, the TLS protocol (which based on the current non-lattice based systems would be completely broken by quantum computing) is responsible for about 1% of the CPU usage. ↩
-
Of course, given that we're still hearing of attacks exploiting "export grade" cryptography that was supposed to disappear with 1990's, I imagine that we'll still have products running 1024 bit RSA when everyone has a quantum laptop. ↩
-
It is a good exercise to verify that for every $g:{0,1}^n\rightarrow{0,1}^n$, $M_g$ is unitary if and only if $g$ is a permutation. ↩
-
It is a good exercise to show that if $M$ is a probabilistic process with $R(M) \leq T$ then there exists a probabilistic circuit of size, say, $100 T n^2$ that approximately computes $M$ in the sense that for every input $x$, $\sum_{y\in{0,1}^n} \left| \Pr[C(x)=y] - M_{x,y} \right| < 1/3$. ↩
-
If you are curious, there is an analog notation for row vectors as $\bra{x}$. Generally if $u$ is a vector then $\ket{u}$ would be its form as a column vector and $\bra{u}$ would be its form as a row product. Hence since $u^\top v = \iprod{u,v}$ the inner product of $u$ and $b$ can be thought of as $\bra{u}\ket{v}$ . The outer product (the matrix whose $i,j$ entry is $u_iv_j$) is denoted as $\ket{u}\bra{v}$. ↩
-
If you are extremely paranoid about Alice and Bob communicating with one another, you can coordinate with your assistant to perform the experiment exactly at the same time, and make sure that the rooms are so that Alice and Bob couldn't communicate to each other in time the results of the coin even if they do so at the speed of light. ↩
-
This form of Bell's game was shown by CHSH ↩
-
More accurately, one either has to give up on a "billiard ball type" theory of the universe or believe in telepathy (believe it or not, some scientists went for the latter option). ↩