How I built the quantum search algorithm in 2 weeks without prior knowledge

and how you could too! - My quantum computing journey so far

Laura Gao

10 Feb 2021 • 7 min read

Picture this: in 2 weeks, you have to speak in front of 70 people about something you built in quantum computing.

Today, you don't know anything about quantum computing beyond a few analogies presented in popular science.

That's where I was on December 28, 2020.

Here's how I went from zero to implementing my own algorithm in 11 days.

1. Learn the Basics

I didn't know where to start, so I did a simple Google search of "quantum computing basics." One of the items that came up was the IBM Qiskit YouTube series, which is what I chose to start with because IBM is credible.

Note: make the distinction between popular science QC basics and the math-y ones. Searching up "quantum computing basics" will yield many edu-tainment videos such as this (or this). You cannot learn QC from Kurzgesagt (as much as I love them). An understanding of QC requires understanding of the mathematical and technical details. Rule of thumb: If a video/article does not talk about math, you cannot learn QC from it. (Including this one - this blog post has no math, so therefore you can't learn QC from it.)

I went through the first 3 videos of the Qiskit series - setting up my IBM Q account, linking it with Anaconda, and coding a simple CNOT circuit. Then came the video about quantum gates, where it was recommended that I learn the gates from their website before progressing through the series.

This is how I found out about the Qiskit docs. (Note: this is different from the Qiskit textbook. Yes, it was confusing for me as well.)

I started reading through the Qiskit docs in chronological order. However, I quickly hit a roadblock within the first few pages - not understanding the linear algebra. I couldn't really progress forward as I wasn't really understanding.

So, I went on a hunt for more. Luckily, I'm part of TKS, so I can go on the quantum computing channel in the TKS Slack to look for resources. I stumbled across one that Pavan posted: the Quantum Cxountry essay for Grover's Search Algorithm by Andy Matuschak and Michael Nielsen.

This essay recommended me to learn the basics from their earlier essay, Quantum Computing for the Very Curious. (Also known as QCVC)

QCVC was hands down the best QC resource. It has zero fluff and isn't scared to work out the math, a problem I had with many other quantum resources. (Well, other resources: either they're basic, high level, and don't scratch the math at all; or they go into the linear algebra right away at a pace where a beginner like me cannot follow along. If you're looking to get into QC, I think reading QCVC is the best way.

I started reading QCVC on ~day 3 of my QC journey. I worked through all the math and finished it in ~5 hours on one day.

Note, my background with linear algebra is minimal. I know linalg up to multiplying matrices. (Which TBH is all you need to know - if you know how to multiply matrices, you're good.)

2. Grover's Algorithm Logic & Intuition

After reading QCVC, I read the Grover's Algorithm essay by the same authors. I read this essay over ~2 days and worked through ~80% of the math. I would recommend working through as much of the math as you can.

Now, I had good intuition and mathematical knowledge of how Grover's Algorithm works. Time to learn to code.

3. Build Grover's Algorithm

First, I went to IBM's textbook page on Grover's algorithm. The notiation here was a bit different from quantum country, so I made sure to work through the math again to get familiar with & make sure I know what they're saying.

Next, I copy pasted the code they provide on the page. I ran it on my jupyter notebook.

At this point, it was well into the 2nd week with about 5 days left till the presentation. Once I got the copy pasted code to run effectively, I went to grind the presentation right away.

But… after 3 or so days, I wasn't happy with my copy and pasted code. On Friday morning, 24 hours before my presentation, I deleted the code and re-wrote it on my own with the logic I knew from the quantum knowledge essay. I spent ~2 hours on this one morning. It took less time than I thought.

Or more specifically, I rewrote the 2 main components of the algorithm: the Oracle and the Diffuser.

Extra: More intuition & The QC content landscape

If you really want to understand quantum computing, you have to know the technical weedy math details - what all the gates do to the matrices of qubits. When building Grover's Algorithm - yes you can do it by just dragging and drop gates, but I'd feel unsatisfied unless I knew why the gates work, not just how they work.

I had a hard time understanding the intuition, specifically how the matrix representations of qubits relates to the geometric ones. (Geometric representation of qubits = Bloch sphere & waves) This article by Pavan on phase factors helped me… but still left me with more questions.

QC is hard. Be prepared for the treacherous journey if you choose to embark on it. Whenever I learn something new within QC, I'm in a superposition of simoutaneously understanding better and being more confused. (Yea, I know, terrible joke 🙄)

I found that content that aims to teach QC generally falls into 2 categories:

  1. Popsci that doesn't explain the math - this includes Ted Talks and edutainment YouTube videos.
  2. Dives into the math without much precursor - it's easy for beginners to get lost. A lot of content that falls here is written by professionals, this includes research papers, and in my opinion, the Qiskit docs and even Musty Thoughts VQA articles. (No no they're great, just maybe I'm small brain and can't work out all the math.) If you know QC, you'll understand these articles, and if you don't know QC, you won't understand. As a person who has understood the math, you may think an explanation is clear while someone who does not understand will not think the explanations are clear. These are industry experts that may be falling into the Knowledge Paradox - they know the field so well that they are unable to sympathize with someone that doesn't understand.

This is what makes quantum country essays amazing - it strikes the perfect balance between both sides.

Right now, I'm trying to learn more QC: Shor's Algorithm, QML, and VQEs. I found that it's difficult to understand them, because all resources are either too technical or not technical enough. I'm having much more trouble learning QML than Grover's algorithm. If only every algorithm had a quantum country essay…

TL;DR / All resources compiled in one place / More tips

This blogpost does not talk about how Grover's algorithm works, only how I learned it.

My presentation on Grover's Algorithm

Github repo

Hope you found something useful here. Have a good day!

Connect w/ me @laurgao on Twitter and most places. Or not. Your loss.

(Jkjkjk... unless? :p)

Release Notes

I wrote a blog post about how I learned Grover's Algorithm instead of explaining Grover's Algorithm. Why? Because this is how I can see value being added. If I choose to explain Grover's algorithm, there are different levels of depth I can choose to go:

This is based off of my limited experience. I am looking to improve - let me know if you agree/disagree with these placements.
  • Go super deep and super technical: fully flush out the math/logic/intuition, the cirucit, and the code.
  • Go mathy: fully flush out the math/logic/intuition and the circuit, but not the code. (This is quantum country)
  • Go mathy, except without fully flushing out the intuition behind the math: displaying the equations and the circuit diagrams. Not fully flushing out what each gate does in the circuit either. (This is where I find quite a few articles written by TKS students, such as this and this. Also where I think the Qiskit docs belongs.)
  • Intuition based: explain the intuition behind how the algorithm works geometrically alongside the circuit, but not the code or math. (What I attempted in my presentation)
  • The short/popsci explanation: "Grover's search algorithm allows you to find objects in the square root of the amount of time that classical computers would take... exponential growth go vroom vroom..." Vague terms like "Grover's algo searches all states at once and then you can manipulate the superposition to bring out the state we're looking for." (This is what I hear from edutainment, short buzzfeed 600 words style articles, and what most people say when I talk to them."

I suppose you can think of it like a spectrum from least complex/shortest/shallowest to most complex/longest/deepest.

Next, I analyzed what I would do if I tried to go with each of these cases.

  • 1 & 2: If I flush out the math/logic & the circuit, this will probably be a 1 hour read. It'll be something along the length of the quantum country essay. Even longer if I explain the code. I don't mind putting in lots of work into a long essay, I actually think that this is a task that I would enjoy -- devoting lots of time to making a high quality piece of work. However, I think this might be a waste of human resources: quantum country's essay on Grover's algo does a great job. Another one doing the same job will not benefit people much. The quantum country essay probably took weeks to write and months to perfect, it's not worth it to devote a lot of time into something that won't provide much benefit.
  • 3: I feel like articles like this are ones that will be understood by someone who knows Grover's algorithm and won't be helpful for someone's who's genuinely trying to learn. Because it doesn't fully flush out the math.
  • 4: Similarly, this explains the intuition and may be entertaining, but doesn't help someone genuinely learn. To resate, rule of thumb: if a video/article does not talk about math, you cannot learn QC from it.
  • 5: Same as 4: You can't learn QC without knowing the math. Another popsci representation of QC will not help anyone. I do not want to create content that has zero potential to be helpful.

What I'm saying is that for a beginner to QC, any non-fully-flushed-out-article will not be wholistic enough to be helpful to a beginner. Nothing less than the 1 hour long quantum country essay would be helpful.

Then, why is this article helpful?

I hope it is helpful... I could warn people about common pitfalls in trying to learn QC that I have experienced.

Instead of trying to re-create a quantum country article, I will just point people towards it ;)