How a graduate student solved one of the most important questions in quantum computation.
As we make progress in the exciting field of quantum computing, one question has been hanging over our heads- how can we be sure that the results spit out by these incredible machines are right? After all, quantum computers are completely different from regular computers, so how can we know that these quantum systems are even doing the operations we’re telling them to do? One scientist, Urmila Mahadev, recently discovered the answer, and she solved this problem before she even finished her education!
Table of Contents:
What is a Quantum Computer?
At the most basic level, traditional (classical) computers, like the one you’re using to read this, store information. We call this information “bits”. Each bit can be either 0 or 1 and the more complicated the information is, the more bits you need to store it. Physically, the bits in your computer are different electric charges. For example, a positive charge means 0 and a negative charge means 1. What’s important is that bits only have two possible states represented by one index, or “slot.”
On the other hand, quantum computers store information in the form of qubits (pronounced “q bit” for quantum bits). You might have heard the word quantum before in superhero movies or sci-fi adventures, but it’s actually a pretty simple concept! “Quantum” just means that some quantity (for example, energy) can only have discrete (quantized) values. This might mean that the value of the quantity could be 1 or 2 or 3, but it’s not allowed to be 1.5. You can think of quantized energy as individual packets of energy that can’t be broken down any further. This effect isn’t usually noticeable in everyday life because the spacing between values is so small that the discrete nature of energy is impossible to see without special experiments.
Another special thing about quantum systems is that there is a fundamental limit on how much we can know about the system at the same time. This isn’t a limitation of the equipment we’re using to observe the system, but a fundamental fact about nature! Whenever we measure, or “observe,” a quantum system, some information about that system must be lost.
A quick explanation of vectors
With one index, you can describe motion in one direction. For example, let’s say your friend is standing on a number line, and you’re in charge of giving them directions. You could tell them exactly where to go by only giving them one number. For example, if you said, “4,” your friend would know where to go on the number line! In math terms, this instruction to go to 4 is written as [4].
If you have two indices, you can now describe motion in 2D. Instead of a straight line, your friend is standing on a 2D surface. Therefore, you can specify where your friend should walk by giving them two numbers. For example, “2 east, 6 north” means that your friend should walk 2 steps east and 6 steps north. In math, we write this as [2, 6]. [2,6] corresponds to the vector pointing from the origin to your friend’s position!
In both of the previous examples, you and your friend both needed to agree on some definitions, such as the position of the origin (0 on the number line, or [0,0] on the plane) and the positions of the axes ([1,0] and [0,1] for the x and y axis respectively in the above definition). You also must agree on the “length” of one unit. If another friend came by and wanted to play the same game, their definitions of the directions might be different (we’ll call their directions North-Prime). We refer to your friend’s definitions as being in a different basis than yours. For example, [0,1] in your basis would not correspond to the same point in your friend’s basis. But if we know the definition of each others' directions, then we can translate between them to describe the same point!
Now, back to qubits. While the bits used by typical computers only have one slot, (0 or 1), qubits are vectors, which means they have two slots! Each slot can take on 0 or 1. So if we make a list of all possible vectors we could make, we would find that there are two options for what to put in the first slot, and two for what to put in the second slot, for a total of four different vectors.
| 0 | 1 |
0 | [0,0] | [1,0] |
1 | [0,1] | [1,1] |
The cool thing about a qubit is that one qubit actually has more information than two regular bits, even though it would have the same number of slots as a two bits. This is because of an idea called “superposition.” Superposition is a way to describe a qubit when we don’t actually know the value that it has. Say we have a single qubit with equal probability of being in the 0 or 1 states- we call this a superposition of states 0 and 1. If we observed the qubit to see what state it was in, our qubit would actually be either 0 or 1, so then it would appear identical to a regular bit. But if we waited a while and then looked at the same qubit again, it might have a different value! To estimate what the actual state of the qubit is, we would have to look at it over and over again and collect data on how often we see a 0 and how often we see a 1.
This means that while qubits are NOT bits, when we interact with them all we observe are bits (if this is confusing, that is ok! It’s pretty crazy that the universe acts like this!). This is fundamentally why quantum computers are different from classical computers.
Storing information in qubits makes certain types of computer processes much faster. This is because of both the fact that qubits have two slots and because of this special idea of superposition. To capture the information contained in just 100 qubits, we would need 2¹⁰⁰ regular bits. That’s 1.26 x 10³⁰ bits, which is about the same as the Sun’s mass in kilograms! Wow!
The Quantum Verification Problem
So quantum computers can hold huge amounts of information, but we want to be able to use them to solve problems, particularly the kind that can’t be solved on a classical computer. But how can we trust that any answer we get out is correct? After all, we’re trying to solve problems that regular computers can’t even solve! Another way to say this question is to ask have the right operations been performed on the input? One reason this question is so hard is because when we try to measure what’s going on inside a quantum computer, the qubits look like regular bits as they collapse into simple 0s and 1s.
For certain problems, surprisingly, regular computers can come to the rescue! While they may not be able to solve the problems we’re trying to solve, classical computers may be able to help us check whether our quantum computers are doing what we’re asking them to do.
One example of a problem that’s hard for classical computers to solve but easy for them to check is called prime factoring. Prime factoring is actually a super important problem, because we use it to secure information online. This problem is trying to find the two particular prime numbers that you can multiply together to get another larger number.
For example, if we’re trying to find the prime factors of 15, we’re looking for two prime numbers that multiply to 15. In math terms, we want p₁ and p₂ such that
p₁ x p₂ = n =15.
Since there are only a few prime numbers less than 15 (they are 2, 3, 5, 7, 11, 13), it’s pretty easy to identify that
p₁ = 5 and p₂ = 3.
But what if n=49,944,743 instead? Now, there are tons of prime numbers that we need to check to find p₁ and p₂, so it’s much harder to identify the correct solution
p₁ = 6959 and p₂ = 7177.
But importantly, once we know the solution, checking it is super easy (just multiply the numbers together and see if they match)! So this is a great example of a problem where regular computers can help us check the results we get from our quantum computers.
But for other problems, this question of checking our results isn’t so easy. With classical computers, it’s possible (in theory) to check each step of a calculation, but the quantum nature of qubits prevents this from being done on a quantum computer, because measuring changes the quantum state. Similarly, you could use another quantum computer to check the answer produced by the first quantum computer, but that begs the question of how you know either computer is correct, even if they come to the same result. So the quantum verification problem comes down to this: how do we check our results?
Urmila Mahadev to the Rescue!
Very recently, a scientist named Urmila Mahadev came up with a very clever solution to the problem, a solution she thought up while she was still finishing up her graduate school education. Her idea was this- let’s force the quantum computer we’re using to verify itself!
Mahadev’s solution involves something called a “secret state,” which is a state known to the user but not the quantum computer. Secret states are constructed using “secret keys,” which allow a user to determine the input of a function based on its output. The functions used in this solution are special “two-to-one” functions. Two-to-one means that for every output y,
y = f(x)
has two different input solutions, {x₀, x₁}. The quantum computer only has access to the output y, and the secret state is the corresponding inputs {x₀, x₁} such that
f(x₀) = y = f(x₁).
Examples of two-to-one functions
An example of a two-to-one function is
y = f(x) = x² = (-x)² = f(-x) = y.
For a given y, x₀ = √y and x₁ = -√y. So when y = 4, x₀ = 2 and x₁=-2 !
The quantum computer can only measure the output (ex. y = 4). Without knowing the secret key, the computer cannot determine the input, because the secret key could be any function whose output equals 4!
Let’s connect two-to-one functions back to the idea of secret keys. Say we have a function
f(x) = x² + 4x - 4.
The secret key for this function is its inverse, or
x=√(y + 8) - 2.
Therefore, for y = 1, we know x₀ = 1and x₁ = -5. However, if we had no knowledge of f(x) (our secret key), we would have an infinite number of possible functions (all those that cross the line y = 1) to check to find the correct {x₀, x₁} pair! For example,
f(x) = x²
crosses the line y = 1 twice. Therefore, its inverse,
x = √y ,
is a potential secret key. However, if its inverse was the correct secret key, then the solutions would be x₀ = 1 and x₁ = -1, which we (as users) know to be incorrect! Can you think of other functions that could be secret keys?
Next, we need two assumptions. (Assumptions can be powerful tools in science because they allow you to solve a simpler, but related, problem to a much more complex one. The simpler problem can then teach you how to approach the more complex problem.)
The first assumption is that it would be impossible for a quantum computer to guess the inputs {x₀, x₁} using only the output y. With knowledge of the secret key, however, is it easy to determine the correct {x₀, x₁}. So if the user has the secret key f(x), she can easily find the inputs {x₀, x₁} which correspond to f(x₀) = y = f(x₁). The quantum computer doesn’t have the secret key, so it would have to check every possible set of inputs {x₀, x₁}-- that would take a really long time.
The second assumption is that a classical device cannot remember both of the solutions
{x₀, x₁} at the same time unless the secure cryptography has been broken (meaning someone told the computer what the secret key is).
To sum up our two assumptions are:
The quantum computer cannot guess the {x₀, x₁} without the secret key
A classical computer cannot remember both parts of the solution without the secret key
Solution Part 1: Proof of Quantumness of the Computer
The second assumption can be used to prove that the quantum computer is actually quantum. After all, the whole point of a quantum computer is to perform calculations that classical computers can’t! To prove the computer is quantum, the user needs to request either x₀ or x₁, then request it again but in a different basis (remember our basis transformation example from the quick explanation of vectors).
Transforming the basis requires that the computer uses information about both x₀ and x₁ at the same time-- so based on our second assumption, a successful transformation would mean our computer is indeed quantum. The user then checks the computer’s solutions, in both the original and transformed bases, using their secret key. If they match, the user can be sure that the quantum computer really has performed a quantum computation!
How to think about entanglement
Say you have a collection of 6 items. Each item can be described by two different features, its shape (circle or square) and color (red, yellow, or blue).
In the set of objects above, every shape can be any color, so there is no dependence of color on shape or vice versa. Think of this collection as “unentangled.”
Meanwhile, in the set of objects below, there is a dependence of color on shape (and vice versa). All red objects are squares (or all squares are red). All circles are either yellow or blue (or all yellow and blue objects are circles). Think of this collection as “entangled” since there is a dependence between color and shape of the object!
Solution Part 2: Proof of Correctness of the Result
Once we are sure that our quantum computer really is quantum (so that we know it’s capable using superpositions) we can entangle the secret solution state {x₀, x₁} with Ψ (pronounced like “sigh”, this symbol represents the state we will perform operations on). By entangling the secret solution state with our operational state, we ensure that the same operations are performed on both.
We do this by
Setting up a state in a uniform superposition (so that we know exactly how it starts before the operations)
Measuring the qubit (which gives us the output y, entangling the quantum computer to a particular solution state {x₀, x₁} that satisfies the secret key)
Now we can perform quantum operations on the entangled state (both the secret solution state and the operational state). With our knowledge of the secret key, we know exactly how {x₀, x₁} should change under the operations. So if after all the operations are complete the quantum computer returns the state {x₀, x₁} that we (with our secret insight) were expecting, then we can trust our answer for the operational state!
The Future of Quantum Computing
Quantum computing is going to be a really powerful tool in the coming years as we get better and better at making these complex systems. By taking advantage of how wonderful and weird the quantum world is, using things like superposition and the fact that measurements change the system we’re looking at, we can create machines far more powerful than traditional computers. But the very weirdness that makes quantum computing so powerful also makes it very difficult to trust.
Dr. Urmila Mahadev has done remarkable work to figure out a way to verify that our quantum computers are doing what we ask. By adding in a secret state to the operations done by our computer, we can ensure our quantum computers are doing what we think they’re doing. This secret knowledge that we have of the secret key allows us to know how the state should have changed if the operation was performed correctly. If it changes in the correct way, we can be confident that the quantum computer is performing as it should.
Dr. Mahadev’s work solving this problem isn’t the end of road for these big ideas, though. There are still huge, exciting problems left to figure out in this wacky world of quantum physics. In the future there will be many more breakthroughs on these kinds of problems, with discoveries from Urmila, from other scientists, and maybe even from you!
Photo courtesy of Quanta Magazine
Written by Jackie Lodman and Yanting Teng
Edited by Katie Fraser, Manasvi Verma, Cayla Dedrick,
Caroline Martin, and Madelyn Leembruggen
Cartoons by Nicole Naporano
Primary sources and additional reading:
"Graduate Student Solves Quantum Verification Problem" from Quanta Magazine
"Quantum Computing for the Very Curious" from Quantum Country
"Classical Verification of Quantum Computations" lecture by Urmila Mahadev
Learn more about quantum computers!
Remember (30-45 minutes): Crack a code, navigate a maze, solve a word search, and more on your journey to become a quantum engineer on this Quantum Adventure.
Play (15-60 minutes): Play mini-games that run on real quantum computers!
Play (15-45 minutes): Become a beta-tester for a new game called Quantum Navigator where Joey the Otter follows the rules of quantum mechanics. (This game is still being developed, so it might have some bugs! Always have a grown up help you when downloading files from the Internet.)
Expand (20-30 minutes): Read more about the importance of quantum computing and how weirdness turns into awesomeness.