Wolfram Cloud Document

An introduction to quantum computing
by Roman Parker
Intern, Wolfram Research

Quantum Computing is a rapidly-growing area of study which potentially has revolutionary capabilities for reducing computational complexity of certain algorithms. Assuming that some of the technical limitations with developing quantum computers can be surpassed, many tasks considered computationally intractable with a classical computer can be relatively easily accomplished with quantum algorithms. Here, we will cover many of the important topics of quantum computing, beginning with classical logic, moving to quantum gates, then to creating of quantum circuits. From there, we will talk about entangled states and their uses, then implement quantum algorithms that are more efficient computationally than their classical counterpart.

Quantum Paclet installation

In[]:=

PacletInstall[CloudObject["https://wolfr.am/DevWQCF"], ForceVersionInstall -> True]<< Wolfram`QuantumFramework`

Out[]=

PacletObject

Name: Wolfram/QuantumFramework

Version: 1.0.15



The Basics of Classical Computing

Before we get to the quantum stuff, though, let’s begin with classical computing at the basic level. All classical circuits consist of gates, which take some number of boolean inputs and return some number of boolean outputs.

Classical Logic Gates

What are gates?

Let’s start by defining two of the most basic gates, the False and True gates. We don’t usually treat these as gates, but in reality, it’s just as easy to think of the inputs into a gate as being gates which take no input and always have the same output.

Define the False and True gates:

In[]:=

falseGate[]:=False

In[]:=

trueGate[]:=True

Next, we will define both of the one-input one-output gates. The first of these is quite boring, being the identity gate.

Define the 1-input 1-output AKA (1,1) identity gate:

In[]:=

ResourceFunction["TruthTable"][{p},{p}]

Out[]=

p	p
True	True
False	False

This gate can be extended to have any number of inputs and will always output its inputs. The other (1,1) gate, on the other hand, is quite useful.

Define the NOT gate:

In[]:=

ResourceFunction["TruthTable"][{!p},{p}]

Out[]=

p	!p
True	False
False	True

The NOT gate is a non-trivial gate and gives us our first “program,” but we still can’t do anything useful with it. Once we add some two-input one-output gates, on the other hand, we can do some useful computation. First, though, we will define a one-input two-output “gate” that is commonly used, but usually not considered a logic gate.

Define the (1,2) identity gate:

In[]:=

ResourceFunction["TruthTable"][{p,p},{p}]

Out[]=

p	p	p
True	True	True
False	False	False

Normally, the identity gate is only defined for #inputs = #outputs. However, if it only takes one input, we can generalize it to give multiple identical outputs. This is necessary if we want to output multiple bytes from the same inputs. However, this is usually ignored, as it does not modify our bytes in any way. Now, we will define several of the most important (2,1) gates.

Define the (2,1) AND gate:

In[]:=

ResourceFunction["TruthTable"][{p&&q},{p,q}]

Out[]=

p	q	p&&q
True	True	True
True	False	False
False	True	False
False	False	False

Define the (2,1) OR gate:

In[]:=

ResourceFunction["TruthTable"][{p||q},{p,q}]

Out[]=

p	q	p\|\|q
True	True	True
True	False	True
False	True	True
False	False	False

The AND and OR gates are the most commonly used (2,1) gates, both in our everyday life and in computers. They can also be extended as an (n,1) gate relatively easily for all n>2, by defining AND to return True only when all inputs are True and by defining OR to return True when at least one input is True.

Define the (2,1) XOR gate:

In[]:=

ResourceFunction["TruthTable"][{p⊻q},{p,q}]

Out[]=

p	q	p⊻q
True	True	False
True	False	True
False	True	True
False	False	False

The final gate we will define in this section is the (2,1) XOR gate. This gate returns True when exactly one input is True. Extending this to be an (n,1) gate is more complicated than with AND/OR, but the easiest way to do so is through parity. Whenever there are an odd number of True inputs into an extended XOR, it will return True, while when there are an even number, it will return False. This keeps the behavior of (2,1) XOR if all other inputs are assumed to be False while functioning with multiple inputs.

Combining Gates

Moving on from our basic gates, we will now create a few gates out of the gates we already know and prove some properties about these gates.

Define the (2,1) NAND gate:

In[]:=

ResourceFunction["TruthTable"][{p⊼q},{p,q}]

Out[]=

p	q	p⊼q
True	True	False
True	False	True
False	True	True
False	False	True

Our first composite gate will be (2,1) NAND. This isn’t a gate that’s used much in everyday communication, but is quite important from a computer perspective. NAND can be extended quite trivially, as it’s a combination of AND and NOT, but it lets us show one of the first important properties of gates.

Define (2,1) NAND using OR:

In[]:=

ResourceFunction["TruthTable"][{p⊼q,!p||!q},{p,q}]

Out[]=

p	q	p⊼q	!p\|\|!q
True	True	False	False
True	False	True	True
False	True	True	True
False	False	True	True

AND[a,b] can be defined as !OR[!a,!b], which means that NAND can be defined easily as being OR[!a,!b]. This rule (and its counterpart for OR/NOR) is known as De Morgan’s Law, and is extremely useful for simplifying complex expressions.

Define NOR using OR, and then using AND:

In[]:=

ResourceFunction["TruthTable"][{p⊽q,!(p||q),!p&&!q},{p,q}]

Out[]=

p	q	p⊽q	!(p\|\|q)	!p&&!q
True	True	False	False	False
True	False	False	False	False
False	True	False	False	False
False	False	True	True	True

Now, we will define a few general rules that are helpful:

Double Negation (applying NOT twice does nothing):

In[]:=

ResourceFunction["TruthTable"][{p,!p,!!p},{p}]

Out[]=

p	p	!p	p
True	True	False	True
False	False	True	False

OR of AND is AND:

In[]:=

ResourceFunction["TruthTable"][{p&&q,(p&&q)||(p&&q)},{p,q}]

Out[]=

p	q	p&&q	(p&&q)\|\|(p&&q)
True	True	True	True
True	False	False	False
False	True	False	False
False	False	False	False

AND/OR Of Duplicate Element (OR(x,x) and AND(x,x) are True whenever x is):

In[]:=

ResourceFunction["TruthTable"][{p&&p,p||p},{p}]

Out[]=

p	p&&p	p\|\|p
True	True	True
False	False	False

Double XOR (XOR(a, XOR(a,b)) is equivalent to b):

We can also combine these together to simplify more complex expressions. For example, the expression below can be seen as being NOT[AND[NOT[a], NOT[AND[NOT[a],b]]]] by replacing OR[x,y] with NOT[AND[NOT[x],NOT[y]]]. We can then interpret this whole expression as being NOT[AND[NOT[x],NOT[y]]], where x is a and y is AND[NOT[a],b]. This simplifies our expression to OR[a,AND[NOT[a],b]]. We know that OR[x,AND[NOT[x],y]] is the same as OR[x,y], since if x is not true, NOT[x] must be true. Therefore, our expression is the same as OR[x,y].

Use BooleanMinimize to confirm this:

Draw the truth table for NOT[AND[NOT[a],OR[a,NOT[b]]]]:

Universal Gates

Even though we have defined a bunch of gates so far, we don’t need all of them to be able to express every operation. We’ve already seen that AND, OR, NAND and NOR can be written using just NOT and either AND or OR. So, how many functions do we need to implement all logic gates?

Define XOR with AND, OR, and NOT:

(2,1) XOR (from this point on, simply called XOR) is relatively intuitive to make with AND, OR, and NOT, since the best way to explain it naturally is “it’s true if either a OR b is true but NOT both a AND b.” However, we also know that we can substitute AND for the NOR of NOT a and NOT B (or OR for the NAND of NOT a and NOT b). Therefore, we can make XOR with only NOT and either AND or OR. Something we won’t prove here, but is important to know, is that (AND, OR, NOT, XOR, NAND, NOR) is universal, which means that all logic gates can be constructed using them. From this, if we can show how to create each of those gates using only gates we have already proved, we can reduce this down.

Define XOR with only NOT and OR:

Define XOR with only NOT and AND:

You might have noticed something about our definition using only NOT and AND. Since NAND[a,b] is the same as NOT[AND[a,b]] and AND[a,a] is a, NAND[a,a] is the same as NOT[a]. Therefore, NAND[NAND[a,b]] is AND[a,b]. Since we have already proven that NOT and AND can create XOR, OR, and NOR, this means that NAND is universal. Below, we will implement a few functions using only NAND.

Implement XOR with NAND:

Implement AND with NAND:

Implement OR with NAND:

Implement NOT with NAND:

Boolean Algebra

Intro

Boolean Algebra is where we begin to take these gates and combine these into useful circuits. Our first circuit that we will create is a full adder. It takes three inputs: two bits and a carry, and returns a total bit and a carry. We can combine these together to create an adder which adds an arbitrary amount of bits together, allowing us to add binary numbers.

Create the truth table for a full adder:

Define the full adder as a usable function:

Use it as a ripple-carry adder:

The easiest way to combine together full adders is to go bit-by-bit for the input bits and add them together, but have the input carry be the output carry of the last stage. Then, we read these bits from bottom-to-top and can convert it back into base-10.

Find the total of the results:

Find the sum of the two inputs:

We now have added 13 and 9 using a logic circuit.

Reversibility

Something interesting about most of the logic gates we have looked at so far is that given their outputs, their inputs cannot be reconstructed. For example, if (2,1) AND returns True, we know the inputs, but otherwise, we have no idea. Creating a reversible version of a gate will be quite important for us later on.

Check if (2,2) (XOR, AND) is reversible:

Sadly, (False, True) and (True, False) are indistinguishable, so this is not a reversible gate. However, it is possible to make XOR reversible by a different choice of the second output.

Check if (2,2) (XOR, b) is reversible:

A gate is reversible if and only if the number of distinct inputs is equal to the number of distinct outputs. The number of outputs cannot be greater than the number of inputs, since otherwise, there would be at least one input with multiple outputs. If, on the other hand, there were less outputs than inputs, by the pigeonhole principle, we would have to have at least two inputs which share an output. Therefore, when running the gate “in reverse,” we wouldn’t be able to tell which of those inputs corresponds to that output. This means that there must be the same amount of distinct inputs and distinct outputs.

Now, we will create a few different gates which are reversible. For reasons which will become more apparent later, these gates are essential in quantum mechanics. The first of these is a controlled-SWAP gate. If the first input is True, the second and third inputs will be swapped. Otherwise, the outputs are the same as the inputs.

Define the (3,3) controlled-SWAP gate:

The Toffoli gate is a controlled-AND gate, where the first two outputs are the first two inputs and the third output is the AND of the first two inputs if the third input is False and the NAND of them if the third input is true. A reversible AND gate can’t be constructed with only two outputs, since it has three False values (and you can only distinguish two of them), so we need the third output to make it reversible. We could have chosen some other input as our third one, but this makes ure that every possible output is an output and gives us a secondary useful functionality.

Define the (3,3) Toffoli gate:

Finally, we will try to make the full-adder reversible. By default, its outputs are XOR[XOR[a,b],c] and OR[AND[XOR[a,b],c],AND[a,b]], which, when put in natural language, represent “Exactly one or three of a, b, and c are true” for the regular bit and “Either both a AND b are true OR c is true AND either a OR b is true” for the carry. This is not reversible in of itself, and additionally, we can’t just add one extra output to make it reversible. This is because (False,True) and (True,False) are each returned by three possibilities, representing all the sums which add to either 1 or 2. It’s relatively easy to use two inputs to distinguish three outputs, so we will simply pick some convenient values. Here, we use a and c, but some other values could be used or extra inputs could be added to make it a controlled gate.

Define a reversible full-adder:

Quantum Gates and the Bloch Sphere

Before we begin creating quantum circuits, we have to understand what quantum states are and how we can use them. The most important thing to understand is that quantum mechanics behaves unintuitively, which both causes issues and allows for some of its advantages.

Qubits

Intro

Create a quantum state:

Find the square of the real and imaginary parts:

Find the norm-square:

Alright, that’s enough terminology and abstraction. Let’s do some useful stuff!

Superposition

If our qubit wasn’t normalized, this total probability would not be 1, and we would have a problem. So, let’s say we have a qubit that’s not normalized. What do we do?

Create a unnormalized qubit:

Find it’s norm-square:

Obviously, we have a problem. However, in quantum mechanics, we can multiply a state by any single value and it will remain generally equivalent. Proving this goes beyond the scope of this essay, but I would recommend reading The Theoretical Minimum Vol. 2 - Quantum Mechanics for a more in-depth look at how a lot of the theory behind quantum computing works. This means that we just need to find a value we can multiply our state by to normalize it.

Solve for a value which can normalize our state:

There are other possibilities, but this one is a positive real number, which makes everything nicer.

Find the norm-square of each term now:

We can see that the terms are still proportional to each other in the correct way, but now their probabilities sum to 1.

Bases and Measuring

Now, we can substitute these out in our equation.

Quantum Gates

Now that we understand what a quantum state is, let’s define some gates.

Definitions

The best way of defining our one-qubit gates is to think of them as transformations applied to a qubit. The two (1,1) gates we know are still here as the I and X gates, but we also have five more gates defined, and in theory, we could have infinite different (1,1) gates.

Combining Gates

By putting these gates together, we can perform transformations on a quantum state.

The Y gate, when applied twice, does nothing, so it’s not surprising that doing this had no use.

Apply 11 repetitions of the X gate to our result:

Apply the Z gate 17 times to the result:

Apply ZXZX:

Creating Circuits

Start by applying an H gate:

Apply the S gate:

Apply the Y gate:

Apply the H gate:

Find the norm-square of each term:

Quantum Linear Algebra

Representing States

We can represent our states as column vectors or as row vectors, which allows us to find the product of two states.

Create a column vector:

Find the conjugate-transpose:

Multiply the conjugate-transpose with the row vector form of our states:

Do the same for a vector involving complex numbers:

Now, let’s take the inner product of the row vector form of the first state and the column vector form of the second state.

Find the inner product:

We can see that inner products are, in fact, scalars. The value of this number is related to how “close” these two states are to creating a basis, plus it gives us an easier way to measure probabilities in a basis.

Inner Products

Let’s define some properties of the inner product and see what uses it has.

Define the inner product:

Take the inner product of two state vectors:

It’s important to note that the inner product is non-commutative. The order of the state vectors matters a lot.

We can see that this is a significantly nicer way of looking at our equation from before, where we normalized a state.

Show that these values are not normal, so they don’t form a basis right now:

Outer Products

Define the outer product:

Add the two together:

All valid quantum gates are unitary in their matrix forms, which, for square matrices like the ones we are using now, means that the conjugate transpose of the matrix times the matrix is the identity matrix. This pretty much is the equivalent of a state being normalized, as the identity matrix is the equivalent of 1 and the formula is the same as that of the inner product.

Check if the X gate is valid:

Similar to the inner product, the outer product is non-commutative, but the conjugate transpose can be used to reverse the input order.

See if it is a valid gate:

The Bloch Sphere

Mapping States

The six primary states we have looked at before make up the axis points on the sphere.

Draw the six primary states:

Solve for θ and for ϕ:

Finally, all that’s left to do is to convert coordinate systems and plot.

Convert to Cartesian coordinates:

Plot it on the Bloch sphere:

Understanding Gates

Creating Gates

Now, we have seen a decent amount of ways to use quantum gates, but we haven’t yet looked at how to create quantum gates. Here, we will show how to make an arbitrary quantum gate that rotates around any axis by any amount. First, let’s prove that rotating by an arbitrary amount around the Z axis is a valid gate.

Define an arbitrary rotation:

Verify this using Reduce:

Next, we define a function which can convert an arbitrary rotation θ around any axis into a quantum gate. θ represents our rotation angle, ⋁ represents our input terms to the gate, x, y, and z represent the values of the direction vector on each of those axes, and γ represents a global phase, which can be set to any value but allows us to simplify and compare gates in a significantly easier way.

Define a formula for a rotation around an axis:

Find the exponential form of the x and y coefficients:

Show the T gate:

We can see that this is identical to the T gate, which makes sense, as both are quarter-turns around the Z axis. This verifies our ability to create gates with whatever characteristics we want.

Computing with Gates

Product States Entangled States

Display it in vector form:

To calculate our product, we pretty much just multiply each term of the first vector by the second vector. We can do the same for a combination of three states as well.

These can be summed and used just like we would a regular state as well.

Compute the norm-square of this vector:

Find the norm-square:

Solve for a global phase to fix:

Find the new vector:

Find the probabilities:

Solve for the global phase:

Multiply it out:

Find the probabilities:

Create a tensor product state:

Define variables for each of our 2-qubit product states:

Create a sum of these states that adds to our product state:

Plot other possible values:

Give an example of one of these values:

Using One-Bit Gates

Now, we are going to look at actually using quantum gates using the Wolfram Quantum Framework.

This allows us to work much more directly with quantum circuits than we could before and gives us access to some level of analysis that was difficult previously.

Create a very basic quantum circuit:

Now, let’s use a custom gate which is a partial X gate.

Create the circuit:

Plot it:

We can see that this works well. We can also measure these states in a different basis.

Measure in the Pauli Y basis:

Using Multi-Bit Gates

We don’t have to just apply quantum gates to a single state, either. We can apply different gates to different parts of a product state, and we can also create multi-qubit gates which complete far more complicated tasks.

Redefine TensorProduct to take QuantumStates as input:

Give an example of this:

Doing this lets us use the TensorProduct symbol () to multiply our QuantumState objects, while before we would need to use QuantumTensorProduct. Now, let’s create a basic multi-bit circuit:

Create a simple two-bit circuit:

Plot it:

Define the four basic two-bit states:

Apply this quantum circuit to them:

Find the formulae for these:

We can see that this behaved as expected.

Apply CNOT to these default states:

Create a circuit using CNOT:

The solid dot represents the control qubit, while the other dot represents the modified qubit.

Find the values of this quantum circuit:

Now, let’s create another circuit which is identical to this one.

Crete a new circuit:

Apply it to the states:

Inverting a CNOT is the same as inverting the control bit of the CNOT. This is because CNOT will return the opposite results for the second bit if the first bit is inverted. CNOT can also be used to create entanglement, just like the Hadamard gate.

Now, let’s use CNOT to create some quantum gates that are more similar to classical gates. Our first one of these gates will be a controlled XOR gate.

Create the quantum circuit for controlled-XOR:

Show the diagram:

Create eight three-qubit product states:

Apply our gate to it:

Create the truth table for a controlled-XOR gate:

This classical gate takes three inputs and returns {a, b, XOR[a,b]} if c is False and {a, b, NOT[XOR[a,b]]} if c is True. The quantum gate behaves identically on standard states but also works on quantum states.

Next, we will use the SWAP gate, which is a two-qubit gate that can be created using three CNOT gates. It’s a relatively basic gate which just swaps the two qubits, but it is surprisingly important in some circuits.

Run the SWAP gate:

Finally, let’s create the Toffoli gate. It’s possible to define this using only gates we already know, which we will do later, but for now, let’s just think of it as a controlled AND gate.

Create the default three-qubit product states:

Apply the Toffoli gate to them:

Look at the classical Toffoli gate:

Just like the classical Toffoli gate, this outputs a, b, and either AND[a,b] if c is False and NAND[a,b] if c is True.

Creating an Adder

Here, we will create a quantum full adder, just like we did with the classical full adder near the beginning of this essay. You can find more information about this here: https://community.wolfram.com/groups/-/m/t/2491392

Create a reversible half adder out of two CNOT gates and a Toffoli gate:

Diagram it:

Create the four-qubit states:

Apply the half adder to them:

Find the probabilities of obtaining each state:

We can treat this two-qubit product state as a binary number, where the first bit is the carry and the second bit is the standard output. To see these values in decimal, we can get the formula.

Show the in and out values:

Now that we have a half adder, let’s make a full adder.

Create our full adder:

Diagram it:

We can see that our first three inputs are simply outputted, while the other five outputs change. These represent our sum, the carry out, and a few extra values not needed.

Create our states:

Find the totals of two values with an input carry:

We can see that we have created a technique to sum two numbers using only NOT, CNOT, and Toffoli gates. This raises the question: What gates are needed for universality?

Universal Gates

To have a universal set of gates, we need to create:
Superpositions: Of our one-qubit gates, H gate creates them, other gates don’t.
Entanglement: We haven’t talked much about it yet, but it’s important to be able to create states that aren’t simply the tensor product of two existing states. We need a 2-qubit gate for this, since it needs to entangle two qubits. CNOT is an easy choice.
Complex numbers for amplitudes: We need a quarter-turn or similar to be able to create complex numbers, since otherwise we lose our on a lot of the power of quantum computing. The S gate works well for this.
However, the set of gates {H, CNOT, S} is not enough. It is only as powerful as a classical computer, so we need more.

However, if we use the T-gate instead of the S-gate (an eighth-turn instead of a quarter-turn), we do have a set of universal gates. It is currently unknown if the four properties above are enough to guarantee universality, but they are one of the simplest set of conditions known. We could also use a Toffoli gate instead of CNOT, or some other combinations, but for now, we will reconstruct several gates using CNOT, T, and H.

Define the Z gate using T gates:

Show the Z gate:

By definition, the Z-gate is just four T-gates, so we can use Z now.

Create an X gate out of H and Z:

Show the X gate:

From earlier, we know that HZH is X, so X is possible.

Create the Y gate (with a global phase) from H and Z:

Show the Y gate:

This is equivalent to Y except for a global phase of , so therefore, we have constructed Y.

Create the S gate using the T gate:

Show the S gate:

This is the S-gate, the last of our one-qubit gates. Now, let us see if we can get our two-qubit gate, the SWAP gate. For this, we will have to use CNOT.

Use three CNOT gates to create SWAP:

Show SWAP:

Now that we have that, we can try to create our three-qubit gate, the Toffoli gate.

First, however, we will create the inverse T-gate. This is relatively easy, as the T-gate is simply an eighth-rotation around the Z-axis. Therefore, we can just use seven T-gates to get its inverse.

Show it:

Create Toffoli:

Show the Toffoli gate:

Apply it to our three-qubit states:

This shows again that just using CNOT, T, and H, we can make any quantum gate.
Interestingly enough, it is possible to create a single gate that is universal, just like NAND in regular computing. This can be done by creating the controlled-Hadamard gate, which takes two a two-qubit input and applies H to the right qubit if the left qubit is one.

Entanglement and Its Uses

We mentioned entangled states earlier on, and then included them in our list of requirements for quantum computing, but we never really went beyond a basic definition. In this section, we will find out why entanglement is essential to quantum computing, which will help us create circuits that can be far faster than their classical equivalent.

What is entanglement?

From earlier, we know that an entangled state can’t be factored. Let’s take some examples and see what this really means.

Create a state that can be factored:

Find the formula for this product state:

Show that it’s equal:

On the other hand, we can combine our qubits differently such that there is no factorization. This is an entangled state.

Show its formula:

Let us try to express this as a regular state using the technique from before.

When we measure an entangled state, we always affect both parts. This is different from a normal superposition, where measuring the left qubit of a product state has no impact on the right qubit. This gives us the ability to convey a lot more information than standard bits could. Qubits can also be partially entangled, which means that measuring the left qubit doesn’t determine the right qubit entirely, but still gives us information about their value. We will not be using these very much, but it is important to know that they do exist.

How can we use it?

Entanglement Monogamy

To take an example from Susskind and Friedman’s The Theoretical Minimum: Quantum Mechanics, assume you have three people Alice, Bob, and Charlie. Charlie has a penny and a dime. At random, he gives one of the coins to Alice and the other to Bob, and Alice heads to Alpha Centauri. When Alice looks at her coin, she knows exactly what Bob’s coin is. Now, instead imagine that Charlie gives Alice and Bob each a qubit from a non-entangled product state. However, in the quantum version of this, even if Alice measures her qubit, she won’t know what Bob will measure. On the other hand, if Charlie gave them an entangled state, we have something far more similar to the classical case. No matter in what basis they measure their qubits, they will get opposite values.

In of itself, this doesn’t seem too strange, as this could happen in the classical case as well. However, the difference in quantum mechanics is that even if we know everything there is to know about our entangled product state, there is still no way to determine what the values will be of the entangled state. Charlie could have “peeked” at the coins and determined who would get which, but that is impossible with the quantum states. This leads to a whole bunch of other strange things.

The first of these that we will look at is monogamy of entanglement. Say that we have an entangled state.

Create an entangled state:

Now, let’s try to add another entangled qubit to things. Classically, this would be like if Charlie held onto a bit of information which determines who got which coin. If you removed any of these three individuals from the equation, they would maintain correlation. In quantum mechanics, however, things work a bit differently.

Try to add a new state:

We can compute the concurrence to determine how entangled our product state is.

Find the concurrence of our original state:

Find the concurrence of the new state:

We can see that this isn’t fully entangled. Is it possible to find one that is? Let’s look at the equation for our quantum state.

Switch to the Z basis:

Show our probabilities in this basis:

Superdense Coding

Define our quantum state:

Let us go through each way to send it:

Apply it to our state:

Use it:

We can see that we have four different states only from changing one bit. Now, all we have to do is translate them back. For this, we will create a circuit which takes each of these four states and transforms them into our elementary product states

Define our translation circuit:

Simply using CNOT and an H gate converts our entangled states back into a regular state. This shows how we can change only one qubit to convey two bits of information, as long as we have another entangled bit.

Encryption

Classical private-key encryption relies on a process which is easy to do but hard to reverse: multiplying two primes.

Create two prime numbers:

Find how long it takes to multiply them:

Find how long it takes to factor them:

It is significantly slower to factor a number than to create it. We can use this to encrypt (if we used significantly larger primes).

Create two new primes:

Next, we will take the product of these primes.

Find the product:

This is the first of our public keys, which can be used to encrypt a message.

Take the product of the primes minus one:

This is a multiple of four, and is therefore not prime. We will use this to find a random number coprime to this product.

Find the coprime:

This is our second of our public keys. Now, let us find the number d for which our second public key times d is equal to 1 mod phi.

Find our private key:

This number will serve as our private key. Now, let’s encrypt a message.

Take a message and convert it to a number:

Encrypt it using the product and the coprime:

Decrypt using our key and time it:

This let us decrypt, since we just have to perform a few multiplications. Now, say we want to decrypt without having the key. To do this, we need to find the two primes which form the product so we can find phi. That will let us solve for d, but we still need the random coprime.

Even the factorization takes a long time, not even including the work required to find the proper coprime value. We can use quantum mechanics to create these keys in such a way that it is very difficult to intercept them.
Let’s say our message is 1100111. For each of these values, we will randomly pick Z or X basis and get the qubit for that basis.

Create our message:

Choose at random whether to use Z or X basis:

Create a quantum state for each bit:

Now, our second person (who also needs the private key to be able to decode) chooses Z or X at random for each bit as well.

Choose the basis:

Measure each value in that basis:

Now, let’s exchange the lists of which bases were used. Wherever these are the same, we can use these bits to determine whether we were observed.

Find the locations where this was the same:

Find the values here:

This process lets us share a secret key (the list of choices at each location) privately between two individuals without a good chance of interception. It is possible that the bits are observed, but, for each bit, doing so would have a 25% chance of causing the results between a and b to differ, even though they measured in the same basis. In a case like this, where we had eight bits (in my example, we got lucky and seven were valid), we would on average have a 68% chance of catching someone, and in the lucky case, we would have an 87% chance. Obviously, this means we had to compare these bits, and therefore gave them away (and can’t use them as a private key), but simply adding more bits will let us confirm. If we send around 100 bits for verification, our chance of someone being able to observe each bit without detection would be less than one in a million.

Creating Useful(ish) Programs

Now that we’ve spent a very long time covering how to create and work with states and gates, let’s create some toy programs which could potentially be useful and are “better” than their classical equivalent. Most of these problems will be set up as follows. We are given an “oracle” x which takes some given input and tells us a value. From that, our goal is to find out some property of the oracle based on the values it returns. Often, this is “guessing” a secret value.

Balanced Function

Let’s say that we have a function F which takes two inputs and returns either 0 or 1. We know it’s either constant or has a 50/50 chance of returning each value. Our goal is to determine which it is.

Check to see whether XOR is balanced or constant.

From this, we can see that XOR is balanced.

Create a quantum circuit that determines whether our function is balanced:

H converts our qubits from 0/1 to +/-, so when we feed them into our function, we have a superposition of all possible values. This is the key to why we only need one measurement. We only have to do the computation once because we do it on a superposition of all possibilities. We then transform it back using another Hadamard gate and output.

Test our function:

Dot Product String

We have a “string” of bits which is secret, and a function which takes the dot product of an input string and this string. Our goal is to find the secret string using this function.

Take the dot product of our string 100 with 001:

Take the dot product of our string 100 with 010:

Take the dot product of our string 100 with 100:

Classically, we must try at least n queries if the string is n bits long, one for each digit. Additionally, we can’t find a probabilistic solution in any less bits either. Quantum, however, lets us use the same technique from before of just applying a Hadamard gate, running our operation, and using Hadamard again. This lets us set up an oracle with a secret string, and using only one query, find that string.

Create our quantum oracle:

Show the matrix of this oracle for 100:

This is a reasonably complex quantum operator which, in its matrix form, has 1 or -1 on its main diagonal based on the values of the secret string.

Create the Bernstein-Vazirani quantum circuit:

Show the diagram for 100:

Apply it to 000 and find the probability:

When given 000 as input, this will always output the correct string with only one query. In cases where you want to give a non-zero input, it will take the XOR of your input with the secret string.

XOR Mask

Our goal is to find a secret “string” again, but this time, our function takes a string as input and gives us an output such that any two strings who, when XORed with the secret string, return each other have the same output. This is useful for finding collisions in hash functions.

Take 1011 with our secret string of 1111:

Take 0100 with our secret string of 1111:

Whatever our oracle is, it would return the same value for 1011 as for 0100 if our secret string was 1111.

Define our oracle:

Interestingly enough, we can actually use the same oracle here as for the last problem, we just use a different circuit surrounding it.

Create the Simon quantum circuit:

Diagram it:

Here, we have four “empty” inputs which are measured as part of this process, but we still use the superposition trick.

Show these values:

From this, we can reconstruct that our secret was 0101 in a linear amount steps, while a classical algorithm would take exponential time.

Grover’s Algorithm

This algorithm is a little more complicated, but far more useful. It searches a list of numbers for a specific binary value and finds its position. For a standard brute force search, it will take a linear amount of time to complete, as you have to check each value. A quantum solution on the other hand, can do it based on the square root of the number of elements.

Define the oracle:

Verify the oracle:

The value of the oracle’s matrix representation is -1 only at the position of the correct value.

Create the circuit:

Display it:

Create our input state:

Apply our gate to this state and plot it:

Try with a different search target:

Shor’s Algorithm

Get our circuit:

This is quite a bit more complicated than our previous ones, since we use an InverseFourier gate, which can be constructed out of SWAPS, controlled rotations, and Hadamard gates but is a reasonably complicated gate. Here, we use a Hadamard gate, followed by three Controlled-NOT gates, followed by a Toffoli gate. Then, we have two more CNOT gates, a Toffoli gate, an inverse QFT on the top and a CNOT on the bottom, and finally, our measurement.

Create the full circuit:

Create a test state:

Apply our circuit:

Find the possible results:

Solve for the factors:

We always get at least one nontrivial factor. Sometimes, we get two. This lets us factor a number in probabilistic polynomial time. This shows the value of quantum computing i that this is a polynomial algorithm for an exponential task.