How I Wrote My Bachelor’s Thesis in Quantum Computing using Qiskit — And How You Can, Too

By Julia Jeremias

Hi, I’m Julia Jeremias and I’m a Master’s student at the Universität Göttingen in Göttingen, Germany. I wrote my bachelor’s thesis in quantum computing using the Qiskit open source software development kit.

As a German undergraduate student, writing a bachelor’s thesis in quantum computing was both exciting and instructive. I learned science writing in English, implemented a quantum algorithm solving the 3SAT problem (more on that in a bit), and presented my work and project. The combination of coding, writing, discussing my ideas in weekly meetings, and learning about the quantum field still excites me very much. I thought I’d share a bit about my experience in order to help other undergraduates looking to explore quantum computing with Qiskit.

First, I needed to decide on a topic. I spoke with Prof. Dr. Stephan Waack, who is a professor at my university in the field of theoretical computer science. I asked him for help deciding on a cutting-edge topic in the field of mathematics and computational complexity. We spoke about the principles of quantum computing, which he had only just begun exploring himself. I started to study quantum as well in April 2020 by reading an introductory book (Quantum Computing verstehen Homeister, 2013) in German.

With my programming background and having heard about the availability of real quantum computers, I was actively looking for a quantum programming language online — and then found Qiskit. I immediately started to learn about and implement fundamental algorithms like Deutsch-Josza and Bernstein-Vazirani, and participated in the IBM Quantum Challenge in May of 2020 — which I found challenging indeed. A few weeks later, I attended an online Qiskit meetup for German-speaking students. Everyone I met at the event was super welcoming and supportive, which encouraged me to contact folks on the Qiskit team asking for ideas for a project that could serve as a bachelor thesis topic.

My friend and former Qiskit intern Caroline de Groot organized a meeting with members of the Qiskit team in September 2020, and I worked with Abraham Asfaw to devise a bachelor thesis topic: Solving the 3-satisfiability or 3SAT problem with quantum computing using Qiskit.

3SAT is a very famous NP-complete problem in theoretical computer science. What is NP complete? Well, NP stands for non-deterministic polynomial-time. Solutions to problems in this complexity class can be verified easily, but actually finding a solution is very hard and it’s unknown whether an easy method to find the solution exists. 3SAT is not only in NP, but it’s also NP-hard: it’s as least as hard as the hardest NP problems. NP-complete problems are a subset of the NP hard problems with the added point that any problem in NP can be reduced in polynomial time to them. Because of this specific relationship between 3SAT and other NP problems, computer scientists have a particularly high interest in solving 3SAT: If we can solve 3SAT efficiently in polynomial time, we immediately can solve other important computer science problems as well.

Before I start explaining 3SAT, please note that mathematicians don’t currently expect quantum computers to be able to solve NP-complete problems like 3SAT in polynomial time. 3SAT is still an interesting problem to study using a quantum computer, given its importance. Researchers are continuing to hunt for problems which we might be able to solve in polynomial time with quantum computers; this complexity class is called BQP, and would include some, but not all NP problems.

Let’s look at an example 3SAT problem, the formula f = ((x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ x₃)). The formula contains two clauses — the logical expressions within parentheses — with at most three literals, or variables. Between the two clauses is a logical AND, whereas the literals within the clauses are connected by a logical OR. When a function is composed of a conjunction of clauses such as this, we say that it’s in the Conjunctive Normal Form. We want to find a satisfying assignment of True and False values to the given formula so that the formula evaluates to True. We could try the brute force method, or guessing combinations of True and False until we find the right answer; the number of guesses would increase exponentially with the size of the problem, which we write as O(2ⁿ). I wanted to employ quantum computing to find one of the possible solutions, such as f = ((False ∨ True ∨ False) ∧ (False ∨ True)) = ((True) ∧ (True)) = True, with a quadratic speedup compared to the brute force algorithm.

I chose to translate the 3SAT problem into a database search problem, and then use Grover’s algorithm for calculating the correct solution. For that, I needed to build a general oracle for every 3SAT problem instance. A quantum oracle is a function with a certain input and output. In my case, the oracle applies quantum gates to the quantum circuit, depending on the input, marking all correct solutions with a sign flip. In the image below you can see a diagram of how the oracle function works: The auxiliary bit aux₀ holds the information, if and only if the first clause is satisfied.

We can use this oracle function only if the input formula is in a certain shape. We do this by converting the given CNF formula into an XOR-logic formula. A XOR-logic contains only logical XOR gates (short for “exclusive or “— it outputs True if one and only one of the inputs are true). Therefore, we must rearrange the given formula such that we do not have OR gates anymore, but only XORs and ANDs. Since quantum CNOT gates implement XOR gates and double quantum CNOT gates implement AND gates directly, we can use the new formula to build a quantum oracle. In the picture below you can see a snippet of the old formula transformed into the new one. This idea arose after reading G. Nannicini, “An introduction to quantum computing, without the physics”.

At this point, the building blocks were there: I found a simple way to encode a 3SAT formula in python using a list of lists. The negative signs indicate if a variable is negated. I was able to build the quantum circuit solving an arbitrary 3SAT formula. The 3SAT-solver starts by creating an equal superposition of all input qubits and initializing the auxiliary qubits. Grover’s algorithm has two steps: Applying the oracle to mark the desired states and applying the diffuser, which mirrors the amplitudes around the mean. Therefore, the probability of measuring the desired states increases. We repeat these steps a number of times. You can find the structure of the 3SAT-solver below.

Implementing these concepts in Qiskit were new to me and in the beginning I struggled a lot with code quality. I started by applying gates to the quantum circuit by hand, not using subroutines at all. But after a while, I got used to the gate-based programming in Qiskit with the help of YouTube tutorials about programming quantum computers, the Qiskit Textbook, and Python guides. In the picture below, you can find a simple example circuit to understand the composition of the 3SAT solver.

I executed the algorithm above on a real quantum device, giving a correct solution to the 3SAT problem with around 30% certainty. This is not as high as theory dictates. But why is that? The discrepancy came from the transpiling process, which rewrites the circuits in a Qiskit program using only gates that the quantum computer can physically implement. In theory, any unitary operator is a valid quantum gate, but in practice, we only have a finite set of so-called physical gates, which are actual manipulations of real qubits. Optimizing the automated process of converting theory-based quantum circuits into implementable circuits is still a complex problem.

So, if you’re an undergraduate student hoping to use Qiskit to write your thesis, what do you do? Be brave and enter the quantum computing area, even if it is unfamiliar to you. We all started somewhere, so don’t be afraid of going your own path in our own pace. Quantum computing in general and Qiskit in particular are two fascinating technologies, which are worth learning about. Take a look at the many resources available online. And don’t be afraid to ask other experts for help! Maybe you can connect yourself with other enthusiastic people on the Qiskit Slack or join a Qiskit programming challenge to help you come up with ideas. Stay curious and creative, the rest will follow naturally. At least, it did for me.

Get started with Qiskit here — and for more blogs like this, follow the Qiskit Medium!