Note: This article contains spoilers for Day 1 of Advent of Code. You’ve been warned 🤗

Ever since I started working for Aqora, I’ve had to introduce myself as a “regular ol’ software engineer”. The reason being that my meetings often involve very smart people working in quantum computing, manipulating trapped ions and analyzing high energy particle physics with quantum machine learning algorithms. But no! not anymore. I want to start calling myself a “quantum software engineer”. But where do I start? Getting a PhD in quantum physics is going to take too long.

That’s where the Advent of Code comes in. If you don’t know the Advent of Code is a yearly event where in December, Eric Wastl posts a daily programming challenge leading up to Christmas. Programming challenges are a great way to hone your programming chops, compete with co-workers or learn a new programming language. I’ve used in the past to learn the basics of Haskell and Clojure. But this month, we’re going to use it to learn quantum computing.

You won’t need to know any quantum physics or anything, as I am starting from scratch, but you will need to know some python and some basics of classical computing. Also, please let me know what I get wrong. I’m learning as I go.

The “Regular ol’” Solution

Eric does a great job of describing the challenges so if you’re not familiar with it I would recommend getting it straight from the reindeer’s mouth. We have a dial with the numbers 0-99 which we can turn right and left. We start at the number 50 and receive a list of operations that dictate how far to turn right or left, and we need to count the number of times we land on 0. The first thing that comes to mind is modular arithmetic. To express this mathematically:

Let s0=50s_0 = 50 be our initial state, and let op1,op2,...,opnop_1, op_2, ..., op_n be our sequence of operations. The state after ii operations is:

si=(si−1+opi) mod 100s_i = (s_{i-1} + op_i) \bmod 100

The password is the count of states equal to 0:

password=∣{i∈{1,2,…,n}∣si=0}∣\text{password} = \left|\left{i \in {1, 2, \ldots, n} \mid s_i = 0\right}\right|

which we can implement easily in python

# we get a list of operations as a list of numbers

# a negative number means turn left, a positive number means turn right

ops = load_input()
value = 50
password = 0
for op in ops:
value = (value + op) % 100
if value == 0:
password += 1

If I run this on the provided input, I get the right answer in about 10ms running on my little laptop 🥳

Can ✨Quantum ✨ do better?

Spoiler alert! no… classical computers are really good at doing arithmetic. If you are familiar with computation complexity theory, there exists problems which we have known polynomial time solutions (P problems), and there exists problems where the time or space complexity explodes exponentially with size of the problem. There exists also a subset of problems known bounded-error quantum polynomial time (BQP) problems which are solvable by a quantum computer in polynomial time. BQP contains P and maybe expands the set of problems efficiently solveable by computing.

Because the algorithm above iterates only once through the inputs its time complexity is O(n)O(n). This fits squarely into the set of P problems, and therefore quantum computers are probably not going to help very much. I think the future of quantum computer is going to be more specialized. You will have your CPU, GPU and TPU which are specialized for classical problems, and you might have a QPU which will tackle the BQP problems.

But I wanna use a Quantum Computer 😭

Now let’s ignore all of that, throw our abacus out the window and get our multi-million dollar quantum chip cooled down to 15 mK. How would we go about implementing this on a quantum computer? The current paradigm for quantum computation is to use quantum circuits. Quantum circuits are a handy way of describing the manipulation of quantum states. Because the principles of quantum mechanics are inherently reversible, the gates that quantum computers use are also reversible. What this means is knowing the output state, and the set of reversible gates used we can determine the input state. For example let’s look at the truth tables for a classical OR gate and the quantum CNOT gate.

OR

The OR gate takes in inputs A and B and returns true if either A or B is true

A	B	OUT
0	0	0
0	1	1
1	0	1
1	1	1

CNOT

A CNOT gate has a control and a target. If the control is true, it will flip the value of the target. Here xx is the control and yy is the target (don’t mind the Braket notation)

x (IN)	y (IN)	x (OUT)	y (OUT)
0	0	0	0
0	1	0	1
1	0	1	1
1	1	1	0

This is of course ignoring all of the superposition fun stuff that quantum computers do, but that’s for another day.

1 + 1 = 10

To solve this problem, we need to add some numbers together on a quantum computer, but how would we do that? Firstly, how do we do that on a classical computer? We use a full adder circuit! Let’s look at the simplest example and the truth table.

Operations:

• Sum=A⊕B⊕CinSum = A \oplus B \oplus C_{in}
• Cout=(A∧B)∨((A⊕B)∧Cin)C_{out} = (A \land B) \lor ((A \oplus B) \land C_{in})

A	B	Carry In	Sum	Carry Out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

You can verify that 1 + 1 = 2! If AA = 1 and BB = 1 and our input carry bit or CinC_{in} = 0 then our SumSum = 0 and our output carry bit or CoutC_{out} = 1. We can see how we can chain together a few of these full adders together to do addition of bigger and bigger numbers. Can we translate this into a quantum circuit?

Finally Some “Quantum” Computing

Let’s put together our full adder quantum circuit.

First we create our circuit with inputs AA, BB and CinC_{in} and outputs SumSum and CoutC_{out} so we’ll use 5 qubits (we can do it with less, but let’s use 5 for clarity). We’ll use the Qiskit Composer to create this circuit. So first let’s create our 5 qubits

We’ll add a “measurement” to our last two qubits so that we can retrieve the outputs. This is necessary because the state of a qubit is by nature unknowable until we measure it, and again I’m not going to get into, but it has to do with superposition, decoherence and the No-cloning Theorem if you’re interested in learning more about it.

Now let’s start building up our logic! Specifically we’ll have to create our operations

• Sum=A⊕B⊕CinSum = A \oplus B \oplus C_{in}
• Cout=(A∧B)∨((A⊕B)∧Cin)C_{out} = (A \land B) \lor ((A \oplus B) \land C_{in})

It looks like there are some XORs in there. If we look at the truth table of the CNOT from above, you’ll notice that the yy state looks a lot like the output of an XOR, so we’ll just use that! To build our circuit, we’ll also need a common gate called a Toffoli gate or a CCNOT gate.

If we look at the truth table in the image above, we can use the Toffoli gate to create AND operations! So with that, let’s start with building the carry out state (A∧B)∨((A⊕B)∧Cin)(A \land B) \lor ((A \oplus B) \land C_{in})

We’ve added 3 gates

1. A Toffoli gate with controls AA and BB and target CoutC_{out} ⇒\Rightarrow A∧BA \land B
2. A CNOT gate with control AA and target BB ⇒\Rightarrow A⊕BA \oplus B
3. A Toffoli gate with controls CinC_{in} and BB (now A⊕BA \oplus B) and target CoutC_{out} ⇒\Rightarrow (A⊕B)∧Cin(A \oplus B) \land C_{in}

Because A⊕BA \oplus B and A∧BA \land B are mutually exclusive this means CoutC_{out} holds our desired state (A∧B)∨((A⊕B)∧Cin)(A \land B) \lor ((A \oplus B) \land C_{in})!

Now let’s do our Sum!

We’ve added two gates

1. A CNOT with control BB (which remember holds A⊕BA \oplus B) and target Cin⇒A⊕B⊕CinC_{in} \Rightarrow A \oplus B \oplus C_{in}
2. A swap gate which just switches qubits with CinC_{in} and Sum⇒A⊕B⊕CinSum \Rightarrow A \oplus B \oplus C_{in}

And that’s it! We have a full adder circuit. We can verify by playing with the inputs. By default the inputs to a circuit are the ∣0⟩|0\rangle state. We can change this to a ∣1⟩|1\rangle by add NOT gates to the circuit

So that now AA and BB are ∣1⟩|1\rangle and we can see in the histogram below that we measure 1010 as the output!

But where’s the Code?

We’ve used a graphical interface to create our circuit, but normally circuits are created programmatically using a classical computer. Quantum algorithms are often hyprid as well, where a classical computer will ingest data, prepare a quantum circuit, send the circuit to a quantum computer to run and then retrieve the resulting data repeating where necessary. You can run the script below to see how we can build our adder circuit with Qiskit

# /// script

# dependencies = ["qiskit"]

# ///

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit

adder = QuantumRegister(5, "adder")
meas = ClassicalRegister(2, "meas")
qc = QuantumCircuit(adder, meas)

qc.ccx(adder[0], adder[1], adder[4])
qc.cx(adder[0], adder[1])
qc.ccx(adder[1], adder[2], adder[4])
qc.cx(adder[1], adder[2])
qc.swap(adder[2], adder[3])
qc.barrier(adder)
qc.measure(adder[3], meas[0])
qc.measure(adder[4], meas[1])

print(qc.draw())

Of course, we can also run our circuit like so

from qiskit.providers.basic_provider import BasicSimulator
print(BasicSimulator().run(qc, shots=1024).result().get_counts())

Which will sample from our circuit 1024 times and return the number of measurements for each result. Try tweaking the inputs with NOT gates (qc.x(adder[i])) and seeing how the outputs change.

But where’s the Quantum Computer?

At the moment we’ve been running all of this on a classical computer, simulating a quantum computer. The number of qubits is small enough that it’s easier to just simulate on classical hardware. But let’s go ahead and try running it on one of IBMs quantum computers! So after 10 minutes and $3.20 later the results are in 🎉

We took about 1000 measurements, and about 500 of those measurements came out to be the right answer. So why such poor performance? At the moment, quantum computers are very expensive and very noisy unfortunately. We call the current era of quantum computing noisy intermediate-scale quantum era or NISQ. It will be a while until we have industrial scale, high fidelity quantum computers, but progress is being made every day

Is any of this useful?

Obviously this is a very circuitous (pardon the pun) way to add two bits together. To use this in our algorithm we would need to chain a few of these together to create a larger adder to handle the input size. We would also need to extend this to allow for subtraction, and we would probably have to use repetitive subtraction to implement the modulo 100. We could also do some optimizations to reduce the number of qubits needed as well as the number of gates needed for our adder. If we really want to get fancy there’s an adder that can perform in place addition using quantum Fourier transforms, but maybe that’s for another day. To use my favorite expression from quantum physics textbooks, “I’ll leave it as an exercise for the reader”.

But why do all of this classical computing on quantum computers at all? Because of the loss of information when measuring due to decoherence, it’s not easy to simply flip between quantum and classical computation. Famous algorithms like Shor’s and Grover’s need to use arithmetic circuits on quantum states in order to amplify the final desired states. For right now, it’s a good opportunity to learn about the quantum circuit model and reversible computing, which is a fundamental building block for quantum computing. It’s exciting to see how much more there is to explore!

I’ll see you soon for the next advent of code challenge!