# In-Class Assignment 24: Programming Quantum Computers ¶

In this assignment, we'll use what we learned about quantum bits and quantum circuits in previous assignments to do useful computation. We'll continue using Qiskit to write quantum algorithms (i.e., algorithms for quantum computers). You'll use a quantum computer simulator to test your algorithms, and you'll even get the chance to run the algorithms you wrote on real quantum computers!

## Itinerary ¶

 Assignment Topic Description Pre Class 23 Background for Quantum Computing How Computers Store Information In Class 23 Classsical and Quantum Bits Information in Quantum States Pre Class 24 Software for Quantum Computing High Level Software and the Circuit Model In Class 24 Programming Quantum Computers Manipulating Quantum Bits to Perform Useful Computations

## Learning Goals ¶

The learning goals for this assignment are:

1. Be able to write quantum circuits in Qiskit to perform useful computation such as generating random numbers.
2. Understand how qubits can be "copied" using the quantum teleportation protocol.
3. Reflect on the strengths/weaknesses and opportunities/challenges for quantum computing.

## Recap of Pre-Class Assignment: Quantum Circuits ¶

Here, we breifly recap a quantum circuit, which was covered in yesterday's pre-class assignment.

A quantum circuit (QuantumCircuit in Qiskit) consists of:

1. A collection of qubits, called a QuantumRegister in Qiskit.
2. A collection of bits, called a ClassicalRegister in Qiskit.
3. A collection of operations on qubits and, sometimes, bits.

For your benefit, an example of creating a QuantumCircuit in Qiskit is shown below.

In [ ]:
"""Imports for the notebook."""
import qiskit

In [ ]:
"""Example of a quantum circuit in Qiskit."""
# quantum register with two qubits
qreg = qiskit.QuantumRegister(2)

# classical register with one bit
creg = qiskit.ClassicalRegister(2)

# create a quantum circuit out with both registers
circ = qiskit.QuantumCircuit(qreg, creg)

# do some operation on the zeroth qubit
circ.x(qreg)

# do another operation on the zeroth qubit
circ.y(qreg)

# do some operation on the first qubit
circ.z(qreg)

# measure the qubits
circ.measure(qreg, creg)

# draw the circuit
circ.draw()


We read this diagram according to the rules below.

1. All qubits start in the ground state $|0\rangle$ at the left of the diagram.
2. All bits start in the state 0 at the left of the diagram (below the qubits).
3. Time flows from left to right. Qubits evolving through time are shown with a single line. Bits are shown with two lines.
4. Operations are shown as boxes with symbols representing the operation.

In the remainder of the assignment, we'll write quantum circuits that perform useful computations.

# Part 1: Quantum Random Number Generator ¶

In this problem, you'll get the chance to write a quantum algorithm that produces a random bit. We explored this problem when we wrote our own Qubit class in the previous In Class Assignment. Now, you'll use Qiskit to do this.

Question: What operation did we perform on our Qubit starting in the state $|0\rangle$ to produce a random state when measured?

## Step 1: Set up the Quantum Circuit ¶

Do this: In the following cell, use Qiskit to:

1. Create a quantum register with one qubit.
2. Create a classical register with one bit.
3. Create a QuantumCircuit object consisting of your quantum and classical registers.
4. Add the operations for a random bit generator, which consist of a Hadamard gate and a measurement.
5. Draw the resulting circuit.

Hint: If you're stuck, refer to the provided code above (or the Pre-Class Assignment) and make the appropriate modifications.

In [ ]:
"""Set up the quantum circuit."""


## Step 2: Run the Circuit and Display the Results ¶

Now that we have a quantum circuit, we need something to execute its instructions, called a backend in Qiskit. There are two options:

1. A quantum computer simulator, which is a program that runs on a classical computer designed to mimic the evolution of a quantum computer. The Qubit class you wrote was a basic version of a quantum computer simulator.

2. An actual quantum computer, which natively performs all operations in the quantum circuit.

Note: As we've seen during In Class Assignment 23, the outcome of measuring a Qubit was random. Because of this, it's common to run a quantum circuit many times and sample from the output distribution. The number of times a quantum circuit is run is called shots in Qiskit.

Typically, algorithms are first run on a simulator to test them (and because there's only so many quantum computers in the world today). You're only required to run quantum circuits on a simulator for this assignment, but bonus problems are available to use a real quantum computer!

Do this: In the following cell, use Qiskit to:

1. Get a backend for a quantum computer simulator.
2. Execute your random bit generator circuit above using 100 shots.
3. Make a histogram that displays the frequency of measured 0's and 1's. (Hint: Qiskit has built-in features to do this in the tools.visualization module. You may want to look back to Pre Class 24 to see how we parse the output of a circuit execution in Qiskit.)
In [ ]:
"""Get a backend and run the circuit."""


## Step 3: Extend the Random Number Generator ¶

You should have seen roughly equal frequencies of 0 and 1 outcomes above. Now, the problem we want to solve is this: How can we write a quantum circuit that generates numbers in an arbitrary range? In particular, we want to generate a random number between 0 and 31.

Question: How many bits are needed to store a number between 0 and 31? Hint: Think back to Pre-Class 23. How did we store a letter of the alphabet using bits?

Remember that when we measure a qubit, we get one bit of information. Therefore, to produce a random number between 0 and 31, we'll need the same number of qubits as the number of bits to store a number between 0 and 31 (i.e., your answer to the previous question).

Do this: In the following cell, use Qiskit to write a quantum circuit that can generate random numbers in the range 0 to 31.

In [ ]:
"""Extending the random number generator."""


Do this: In the following cell:

1. Execute the quantum circuit you've written using a quantum computer simulator backend.
2. Display the results of the frequency of ALL measurement outcomes using 1000 shots.
In [ ]:
"""Execute your quantum circuit here."""


Do this: In the following cell:

1. Compute the most probable outcome (bit string) and convert it to an integer in the range 0-31.

Hint: You can get the key of a dictionary with the maximum value by doing max(dictionary, key=dictionary.get).

Hint: In Python, int("10", 2) returns 2, and "10" is the integer 2 in binary.

In [ ]:
"""Compute the random number in the range 0-31 from the output of the circuit."""


## Executing on a Real Quantum Computer ¶

Now that you have a quantum circuit written, you can easily change the backend to run it on a real quantum computer rather than a quantum computer simulator. In order to use real quantum computers, you'll need to set up an account on the IBM Q website and get an API Token. If you haven't done this already, the steps are listed below.

If you don't have an account:

1. Go to https://quantumexperience.ng.bluemix.net/qx/experience.
4. Fill out the form.

Once you have an account:

1. Go to https://quantumexperience.ng.bluemix.net/qx/account/profile.
2. Click "Advanced" in the upper right of the page.
3. Copy your API Token into the cell below. (Should be a long string of digits and characters.)

Do this: Enter your API token between the quotes in the following cell.

In [ ]:
"""Put your API Token here. This cell will throw an error until a valid API_TOKEN is entered."""

API_TOKEN = ""
qiskit.IBMQ.enable_account(API_TOKEN)


Your account should now be enabled and you should be able to see quantum computers as backends. Run the following cell to see what backends are available.

In [ ]:
"""See all available backends."""
print(qiskit.IBMQ.backends())


Question: What backends do you see? Which ones are real quantum computers?

Do this: Pick a quantum computer as a backend to run on in the following cell.

In [ ]:
"""Select an available backend to use."""


Question: Research the quantum computer you selected on the web and write some facts about it. (How many qubits does it have? When was it first put online?) This website may be helpful.</a>

Now that you've selected a backend, pick one of the two circuits you wrote to run, and list it in the cell below.

Do this: Erase the contents of this cell and write which circuit you chose to execute here. (Random bit generator or random number generator.)

Do this: In the cell below, write code to run your circuit on a real quantum computer using Qiskit.

In [ ]:
"""Run your algorithm on a real quantum computer."""


The cell below will check the status of your submission. Note: This assumes you named your job submisstion job.

In [ ]:
"""Print the status of the job submission, as well as the queue position.
Check your status/queue position by occasionally running this cell as you work through later problems."""
print(job.status())
print(job.queue_position())


When you submit a circuit to be executed (a "job"), the job gets submitted to the queue, since these computers are available to everyone. Depending on the time of day, your job could take a few minutes to a few hours to execute.

While you wait for your job to execute, you should continue working through the notebook. You can check the status and queue position of your job periodically.

If you encounter errors: First try to fix them by asking an instructor, TA, or LA. If this fails, an alternative to running an algorithm on a quantum computer is described below. This assumes you have set up an account to use IBM's quantum computers. (If not, see these instructions above.)

1. Navigate to the IBM Quantum Composer website https://quantumexperience.ng.bluemix.net/qx/editor. You'll need to be logged in if you are not already.
2. Scroll down to the "New experiment" section with a quantum circuit diagram.
3. Drag in gates from the "Gates" section to the right and drop them on qubits to manually program your algorithm. To do the random bit generator, you should add a Hadmard gate and measurement on the same qubit.
4. Click "Run" and follow the instructions. This will submit your job. When it's finished, an email will be sent to the email address you signed up with containing the results of your algorithm.

Congratulations! You just ran an algorithm on a quantum computer!

Do this: In the code cell below, make a histogram to display the frequencies of your results in the same way as the previous steps. To do this, you'll need to make sure your job has executed. You may need to hard code in your results if you used the Quantum Composer.)

In [ ]:
"""Make a histogram of output results here."""


Question: How do your results compare to the same algorithm you ran on a simulator? Current quantum computers are noisy devices, so for algorithms with many gates, the output distribution can look very different compared to when the algorithm is run on a simulator. For algorithms with few gates, the results should be comparable.

# Part 2: Quantum Teleportation Algorithm ¶

During In Class Assignment 23, we talked about the differences between copying a bit and copying a qubit. To copy a bit, it's easy: you just look at the bit's value, record it, and write it into a new bit. For a qubit, on the other hand, which has a wavefunction which "gets destroyed" when you measure it, the problem is a bit more subtle.

As copying information is such an important routine in communication and computation, you may wonder if there's anything we can do? Luckily, there is, but it involves destroying the original qubit! (There's no free lunch with copying qubits!) It's called quantum teleportation. The image below shows a stylized quantum circuit diagram. We describe this diagram below. For clarity, let's say there's two people, Alice and Bob. Alice has some qubit $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$ that she wants to send to Bob. This is the message at the top of the above diagram. Here's what happens. Alice starts with one qubit, Bob starts with two.

1. Bob prepares an EPR pair with two qubits (far left of diagram), and sends one of them to Alice. (An EPR pair is a special pair of qubits that we'll cover in Step 1 below.)
2. Alice performs the same operations as Bob on her qubits in reverse, then measures both qubits.
3. Alice tells Bob her measurement results, which allows Bob to reconstruct the state $|\psi\rangle$ by performing the appropriate operations on his qubit.

We'll work through these steps in more detail as you complete this problem.

## Step 1: Bob Prepares an EPR Pair ¶

To prepare an EPR pair, it's as easy as two operations, one of which we already know: A Hadamard gate!

The other operation is called a Controlled-NOT operation, or just CNOT. The CNOT gate acts on two qubits with the following effect:

\begin{align} \text{CNOT}|0\rangle |0\rangle &= |0\rangle |0\rangle \\ \text{CNOT}|0\rangle |1\rangle &= |0\rangle |1\rangle \\ \text{CNOT}|1\rangle |0\rangle &= |1\rangle |1\rangle \\ \text{CNOT}|1\rangle |1\rangle &= |1\rangle |0\rangle \end{align}

If you look closely, you'll see that the CNOT gate flips the second qubit if the first qubit is $|1\rangle$ and does nothing otherwise. (The name makes sense: A NOT gate on the second qubit controlled on the first qubit.)

Don't worry, you won't have to code how the CNOT gate works: Qiskit has this for you. You just need to implement it.

#### ---------------- Brief Remark about EPR Pairs and Quantum Entanglement ---------------- ¶

An EPR pair has special properties that quantum teleportation exploits. Below, we create an EPR Pair with two qubits. An EPR pair shows an example of quantum entanglement in quantum mechanics. Quantum entanglement has cool and useful properties, which we'll now briefly explore. As an aside, Albert Einstein never fully understood quantum entanglement before he passed away -- here's your chance to surpass Einstein! (The E in EPR stands for Einstein.)

Do this: Read through the following code to understand what's happening, then run the cell.

In [ ]:
"""Example code: exploring quantum entanglement."""
# get a circuit with two qubits and two bits
qreg = qiskit.QuantumRegister(2)
creg = qiskit.ClassicalRegister(2)
entanglement_circuit = qiskit.QuantumCircuit(qreg, creg)

# add operations to create an entangled state
entanglement_circuit.h(qreg)
entanglement_circuit.cx(qreg, qreg)

# measure both qubits
entanglement_circuit.measure(qreg, creg)
entanglement_circuit.measure(qreg, creg)

# print out the circuit diagram
print(entanglement_circuit.draw())


The circuit (without the measurements) shown above produces an EPR Pair. When we run this circuit (with the measurements), we'll see a particular correlation in the measurement outcomes.

Do this: In the following cell, run the entanglement_circuit above on a quantum computer simulator backend for 100 shots. You could also run this on a quantum computer backend if you want!

In [ ]:
"""Put your code here for running this circuit on a quantum computer simulator."""


Question: Look at the outcome of your circuit (by making a histogram or looking at the measurement counts). You should only see two outcomes. What outcomes are they?

There's only two outcomes because of quantum entanglement, a form of correlation between qubits. The EPR Pair has the property that, when one qubit is measured, the other qubit "collapses" into the state that was measured. So, when one qubit is measured as $0$ above, the other qubit becomes $|0\rangle$, and hence is always measured as $0$. Similarly for $1$. This quantum correlation is a stronger correlation than is possible in classical systems (systems described by classical, not quantum, physics), as proved by John Stewart Bell in 1964 and verified experimentally in 2015, which refuted Einstein's disagreement with entanglement from 1935.

#### ---------------- End Brief Remark about EPR Pairs and Quantum Entanglement ---------------- ¶

Now back to the teleportation circuit, which exploits quantum entanglement.

Do this: In the following cell:

1. Create a quantum circuit with three qubits and three classical bits. Important: Make three separate QuantumRegisters and three separeate ClassicalRegisters (as opposed to one QuantumRegister of size three, etc.) This will make it easier for us to program the algorithm.
2. Perform a NOT operation on Alice's qubit -- the first (top) in the circuit. This will be the qubit (or message) she sends to Bob. In general, this could be any qubit, this is just one example.
3. Prepare an EPR pair on Bob's qubits -- the last (bottom) two in the circuit.

Your circuit diagram at the end should look something like (you can ignore the grey vertical lines): In [ ]:
"""Put your code here."""


## Step 2: Alice Reverses Bob's Operations and Measures ¶

Now we imagine Bob sends his qubit to Alice, who could in theory be as far away as she wishes. Once Alice receives the qubit (which is right away for us), she reverses the operations that Bob performed on her two qubits and measures.

Do this: Using your same quantum circuit from above, add the following operations.

1. Perform a CNOT on Alice's two qubits (control on the one she originally had).
2. Perform a Hadamard gate on Alice's first qubit (the one she originally had).
3. Measure both of Alice's qubits (the top two in the circuit shown below).

Your circuit diagram at the end should look something like (you can ignore the grey vertical lines): In [ ]:
"""Put your code here."""


## Step 3: Bob Performs Conditional Operations ¶

Now we imagine that Alice sends the results of her measurements to Bob. Remember, her measurements are just bits, so there's no problem communicating them to Bob. Note: Because Alice has to transmit classical information, quantum teleportation is not superluminal (faster than the speed of light), despite popular science misconceptions.

Bob then listens to Alice and acts accordingly on his qubit.

Do this: Using your same quantum circuit from above, add the following operations.

1. If Alice measured a 1 on her FIRST qubit, perform a Z gate on Bob's qubit. (Hint 1: Look up the Z gate in Qiskit's documentation. Hint 2: Use the c_if method to implement this gate conditioned on the measurement outcome.</i>)
2. If Alice measured a 1 on her SECOND qubit, perform a NOT gate on Bob's qubit.
3. Measure Bob's qubit. (This is just for us to see the result. In practice, the qubit wouldn't be measured if Bob wanted the quantum state.)
4. Draw the circuit diagram.

Your circuit diagram at the end should look something like (you can ignore the grey vertical lines): In [ ]:
"""Put your code here."""


## Step 4: Run the Circuit ¶

You've now written the entire quantum teleportation algorithm! Congrats! All that's left to do is execute the circuit in the same way we've done before.

Do this: In the following cell:

1. Get a quantum computer simulator as a backend.
2. Using your backend, execute your quantum teleportation circuit using 1000 shots.
3. Make a histogram of the frequency of the outcome measurements.
In [ ]:
"""Put your code here."""


1. How many measurement outcomes could there be in total for measuring three qubits?
2. How many measurement outcomes do you see in your histogram? (You should see fewer than your answer to the above question.)
3. If the quantum teleportation algorithm worked, what should Bob always measure?
4. Does this agree with your results above? (Hint: See if one of the measured bits is always the same.)

# Part 3: Other Quantum Algorithms ¶

You've just written two quantum algorithms, congrats! The first quantum algorithm, the random number generator, is useful because it generates truly random numbers guarunteed by the laws of (quantum) physics. Random numbers have a lot of practical applications ranging including communication, cryptography, and computation, of course.

This isn't just an artificial example, either! Quantum random number generation is a real protocol used in academia and industry. For example, you can run the cell below to see an online quantum random number generator by researchers at the Austrailian National University, and read about how NIST is using similar technology for internet security.

In [ ]:
"""Livestream truly random numbers guarunteed by quantum physics!

You may have to scroll down in the webpage after executing this cell."""
from IPython.display import HTML
HTML(
"""
<iframe
src="https://qrng.anu.edu.au/RainBin.php"
width="80%"
height="+1200px"
frameborder="0"
marginheight="0"
marginwidth="0">
</iframe>
"""
)


The second algorithm, the quantum teleportation algorithm, is used for memory systems in quantum computers as well as in communication protocols for the quantum internet. (Read about the quantum internet being developed in Europe here if you're interested.) Generating an EPR pair is also used in a lot of quantum cryptography applications as well.

One of the most exciting aspects of quantum computing is that some problems, though not all, can be solved a LOT faster on quantum computers than on classical computers. Shor's algorithm, a quantum algorithm for factoring numbers, is the most famous and what started the field. It got a lot of people interested because the security of, say, your credit card information when you buy something on Amazon is protected by the fact that no one has come up with a fast algorithm for factoring numbers on classical computers.

Question: Do a web search for other quantum algorithms and list at least three of them here, including what they're called, what they do, and any other information you can find. Cite your source(s). Hint: This webiste may be useful: http://quantumalgorithmzoo.org/.

About Shor's algorithm breaking cryptography with a quantum computer... Don't worry! Your credit card information and messages are still safe online! In principle, they could be hacked if we had a big enough quantum computer, but currently we don't. Not even close! Building a good quantum computer with many qubits is one of the biggest engineering challenges facing many technology companies like IBM, Microsoft, Rigetti, and Google today. (And also academics as well! The Labratory for Hybrid Quantum Systems (LHQS) at MSU and run by Dr. Johannes Pollanen works on qubit technologies based superconducting qubits and electrons on the surface of helium.)

Question: Do a web search to find out some challenges in building quantum computers. List at least two of them here. Cite your source(s).

Even with these challenges, the problem of demonstrating a computational speedup on a quantum computer is the million dollar question... literally! If you come up with a quantum algorithm and prove it's faster than any existing algorithm on a current classical computer, you're entitled to a million dollars from a quantum computing company called Rigetti. (Read about the "Quantum Advantage Prize" here if you're interested.)

And of course, the question of what else we could do with a good quantum computer is one of the most interesting and exciting questions in physics and computational science today.

# Assignment Wrap-up ¶

Take a moment to fill out the following brief survey to complete your assignment.

## Survey ¶

In [ ]:
from IPython.display import HTML
HTML(
"""
<iframe
src="https://goo.gl/forms/AgAUQ5ckrnv1VZG82"
width="80%"
height="1200px"
frameborder="0"
marginheight="0"
marginwidth="0">