This course will teach you how to compute using the principles of quantum mechanics. We’ll start with a simple puzzle and solve it using qubits in two ways:
- First, we’ll limit our qubits to their two computational states: and just like in a classical circuit.
- Next, we’ll try it using qubits that are in a superposition state. To do this you'll build your first quantum circuit and run it to see the quantum advantage.
Let's get started. But first, let's meet the classical version of the puzzle.
You’re given four coins. Each one looks real, but you think that one or more of them might be counterfeit, so that it weighs slightly more or less than a real coin.
Thankfully, you’re also given a coin checker: a physical black box that has a mechanism, very similar to a vending machine, that can accept one coin at a time.
Put in a real coin, and it will pass through with no problem. But put in a counterfeit coin and it will set off an alarm, alerting you that the coin was counterfeit.
How many times do you have to use this coin checker to find out which (if any) of the coins are counterfeit?
Looking at this puzzle more mathematically, we can think of the coin checker as a black box that computes a function of the four inputs that gets output as the alarm: if the alarm goes off, and if not.
Rather than physically inputting the coins, the black box checker knows which coins are counterfeit and uses this knowledge to output the function and set off the alarm. Black box circuits like this are also known as oracles.
The input is always a string of length that describes which coin is being weighed. A in a given position means that the corresponding coin is being checked.
For example, if the second coin is counterfeit, then and
At this point we're ready to attack the counterfeit coin problem with quantum computing. But first, let's get some basics out of the way.
Reading a quantum circuit left to right, we see the qubits in their initial state, followed by a sequence of quantum gates, followed by a column of measurement devices. The gates operate on qubits to change their quantum state.
When the qubits are measured, their quantum state collapses and the computation is over.
Quantum computing then is about processing information with the quantum state and extracting the final form of that information through the measurements.
Here's the coin puzzle again except, instead of inserting physical coins, each row now corresponds to a qubit.
The first four qubits represent the coins. Each qubit starts in the state so, if we want to "insert" a coin, we have to flip the corresponding qubit from to
The blue meters on the right are measurement devices, if they display it means that the given qubit was measured in the state, and means that the qubit was measured in the state.
The final qubit is the alarm. If it's measured in the state, it means that the inserted coin is counterfeit.
If we were operating on classical bits, we would use the operation to flip a to a (or vice versa), but when we operate on qubits we call it an operation, for reasons we'll see later.
You can "insert coins" one at a time by dragging the gate onto the corresponding qubit.
Submit the circuit above once you've found the counterfeit coin and set off the alarm qubit.
In the quantum circuit, we do away with strings in favor of kets to describe the state of our qubits.
If we want to "check" the first coin, we can set the state of the first qubit to using the operation, and leave the second, third, and fourth qubits in the state. The collective state of the four qubits would then be represented by
Use the gates in the circuit above to check the coins one at a time. When the alarm goes off, the qubits will have some measured state.
What is it?
We’ve learned that while bits can only be either or , the state of a qubit can be a combination of the states and at the same time: a superposition, like
This raises a natural question. Instead of checking the first coin, then the second, and so on, can we use a superposition to check every coin at once?
In fact, many quantum algorithms exploit this as part of their operation. When a qubit that's in superposition passes through a circuit, the circuit can operate on all of the states of the superposition simultaneously, so it doesn't require separate queries.
This approach is so commonplace that there's a quantum gate, called designed to prepare this sort of combination: This is one of the two most important quantum gates that you'll use in this course, and it's often the first step in transforming a classical algorithm into its quantum counterpart.
While there are different possible input strings to our checker, using on each qubit can prepare a superposition state that contains them all.
To store the classical states on the left, we would need a set of 4 physical classical bits to represent each one, or 64 physical classical bits altogether. The quantum state on the right can be stored using just 4 physical qubits.
But when we pass the superposition state to the checker circuit, it produces a muddled mess (all of the qubit measurements yield ).
By putting in a combination of every possible input, we’ve produced an incomprehensible output which seems to say that the alarm both does and does not go off.
In a way this isn't surprising — we wouldn't expect a binary light to be able to deliver nuanced feedback like "one of the coins you gave me was counterfeit but not the other".
From here on out, we have to give up on the idea of the fifth qubit as an "alarm" and figure out another way to extract information from the quantum state.
But all is not lost, the quantum state coming out of the checker has changed. Every combination of inputs containing a single counterfeit coin has been marked with an alarm; we just can't see it yet.
Using an advanced feature of the circuit simulator, which you'll use later in the course, we can see the exact quantum superposition state of the output:
How has the black box changed the quantum state? Is there any information we could use to figure out which coins are counterfeit from the quantum state alone?
The superposition state that's output from the black box checker contains all the information we need to see which coins are counterfeit.
By comparing some of the input terms to the output ones, we have the following: In only one query, all the possible coin inputs that set off the alarm have been tagged with a minus sign ().
There's a big problem here, however. As we learned in the last quiz, it isn't possible to extract the coefficients of a superposition through measurement — you'll only be able to measure a random selection of one of the superposed states (e.g. or ).
The only time we can be sure that the measurement of a qubit corresponds to the state it was in prior to measurement is when it's in one of the computational states: or
Thankfully, the operation has another trick up its sleeve: not only can it flip a computational state into a superposition, it can also do the opposite to transform different superpositions back into defined computational states:
Use the gate to find the counterfeit coins in a single query, then submit the circuit above when you think you've found it.
Hint: all the qubits need to be taken out of the superposition state, including the fifth one.
Preparing a superposition state for the oracle, followed by decoding the mixed jumble of a state it yields back into one of the computational states is a common approach in quantum algorithms. In problems like the counterfeit coin puzzle, a brute force search that could take many queries can be sped up significantly. This approach is called quantum parallelism, and we'll become well-versed in the careful choreography of quantum problem-solving in this course.
The construction of this quantum circuit is not meant to be obvious to you now, and we’ll spend much of this course unpacking how superposition and other quantum properties can be leveraged to speed up computation. Throughout the course, drag-and-drop quantum circuits like this one will allow you to try out the computation for yourself, and get a feel for the operations you’re performing as equations never could.