code-for-a-living April 14, 2021

Understanding quantum computing through drunken walks

The jumping off point for exploring quantum computing is to understand that while many of the principles are counterintuitive, the classical universe we know and love is but a mere shadow of the quantum fabric of reality. To get a feel for that fundamental difference we will walk through an example that helps to illustrate the power of quantum computation.

Quantum computing is the biggest revolution in computing since… computing. Our world is made of quantum information, but we perceive the world in classical information. That is, there is a whole lot going on at small scales that are not accessible with our normal senses. As humans we evolved to process classical information, not quantum information: our brains are wired to think about Sabertooth cats, not Schrodinger’s cats. We can encode our classical information easily enough with zeros and ones, but what about accessing the extra information available that makes up our universe? Can we use the quantum nature of reality to process information? Of course, otherwise we would have to end this post here and that would be unsatisfying to us all. Let’s explore the power of quantum computing then get you started writing some of your own quantum code.

The jumping off point for exploring quantum computing is to understand that while many of the principles are counterintuitive, the classical universe we know and love is but a mere shadow of the quantum fabric of reality. Part of becoming comfortable with the quantum is to become comfortable with the limitations of our own perception. This limitation is analogous to drawing a 3D object on a 2D sheet of paper. Take a look at the wireframe below. It can represent either a box (we can illustrate this with a glass on top) or it can be inverted into a corner (we can put the bottle inside to make it flip to a corner in our brains).

We are forced to see either one or the other and never both. We can change them back and forth, but because we are stuck in a two dimensional representation we can only see one or the other. Two dimensions is not enough for a perfect representation of a three dimensional object. Similarly the world of classical information in its simplest encoding is represented in bits, 0s and 1s. These are not enough though to describe the quantum world. In the quantum world, we need quantum bits, or qubits, to describe our information. Like putting the drink on top of the box or in the corner, we can make a measurement that will force our qubit to tell us a classical bit, but there is more information there that we can take advantage of.

Quantum computers will use the rest of the information to achieve more computational power. This will be transformative with applications in pharma, green new materials, logistics, finance, big data and more. For example, quantum computing will be better at calculating the energy of molecules because this is a fundamentally quantum problem. So if you can imagine an industry that deals with molecules, you can imagine an application of quantum computing. Often people want to know if quantum computers will be faster, and while they will be able to do computations faster, it is not because they are doing the same thing with more cycles. Instead quantum computers take advantage of a fundamentally different way of processing information. To get a feel for that fundamental difference we will walk through an example that helps to illustrate the power of quantum computation.

Meet a quantum drunk

We are going to think about the drunken walk. In the classical drunken walk (sometimes called the random walk) we have a drunk who is leaving the restroom and trying to find his friend at the bar. 

Everyone basically looks the same at this hipster bar and he has had one too many so he is approaching a random person seated at the bar. When he discovers that the first person he has bothered is not his friend, he will randomly go to the next stool, either to the left or to the right. We can simulate our drunken walker by flipping a coin and saying heads he will go right, tails he will go left.

The next person is also wrong and his memory is short, so they will move on to either the left or right with equal probability. This will go on until security is called to throw out the drunkard.

The security team loves physics, so they decide to keep a tally of where they finally catch up to the drunk each time. Here is what security finds:

The shape is a bell curve, and the interesting feature of the bell curve is that the spread of the middle (the most likely place to find the drunk) is the square root of the number of steps the drunken walker takes. When the drunk tries nine barstools, the spread of the bell curve is three; security can likely find them within three barstools of where they started. When the drunk makes 100 attempts, security will find the most likely within the ten closest stools to where they started. These statistics help security know where they are most likely to find the drunken walker, who is somewhere near the center.

Now the security team has a model they can use to keep up with the classical drunks, but unfortunately at this bar there are also quantum drunks. Whereas the classical drunk is a simple coin flip for each direction, for the quantum drunk the coin is quantum, and can be in a superposition of heads and tails at the same time. The quantum drunk is following a path that is a superposition of left and right at each bar stool.  

Superposition is one of the fundamental concepts in quantum mechanics and one of the tools that differentiates quantum information and classical information. The treatment here is limited by necessity; for more fun with superpositions, check out this Strangeworks post on some of the fundamentals of qubits.

The quantum drunk will go in a superposition of left and right simultaneously with no definite position until security finds them. 

When the security looks at the distribution of positions where the quantum drunk is found, they will find a very different result from the classical drunk. 

As opposed to a smooth bell curve distribution, they will find the “fangs” distribution shown below:

What is going on? Where is the quantum drunk? Why would the peaks of the distribution be on the outside? Why are there areas inside that are very low probability and others that are higher? The quantum drunk has new properties. 

The drunkard tends to be farther away, and it is less likely to be close to the center.  Certain paths are less probable because of interference, while some are more probable. The overall spread is much different too. Instead of the spread being related to the square root, the spread is related linearly to the number or steps. A quantum drunk taking ten steps will most likely be found on the outside of a ten barstool spread, as wide as the distribution for a classical drunk taking 100 steps.

So how can we use this to our advantage? Is there some problem we can solve better with quantum drunks than with classical drunks? Well I’m glad you asked, because yes there is! To see this we are going to put the drunks to the task of solving a labyrinth. We are choosing a specific labyrinth that will illustrate the power of the quantum drunk. In this problem we have a tree structure that is mirrored and then stuck together. 

On the left is the entrance to the labyrinth and on the right is the exit. We want to see how well our drunk walkers can find the exit. Remember that the classical drunk is going to be flipping a coin at every node, whereas the quantum drunk is creating a superposition of every path at each node. The drunks tend to get stuck in the random connections in the middle, taking more time to find their way out. 

Since quantum drunks are more spread out, they can escape being stuck easier. This is why quantum drunks find the exit faster than classical drunks. 

For this problem as we send more and more drunks through, the quantum ones are going to make it through exponentially more than the classical ones!

This is the power of quantum computing. Even though this is a simple example, all quantum algorithms work the same way: by exploiting the quantum spread in clever ways that fit the structure of a problem. There are many applications for quantum algorithms, so it is an exciting time to start exploring quantum programming.

In the near term, the best applications are the design of pharmaceuticals and the engineering of new materials. Many of these chemistry applications are fundamentally quantum mechanical. This is because figuring out the energies of electrons for different molecules is more efficient using a quantum computer. Optimization problems are another area where quantum computing will have an impact in the not-too-distant future. This class of logistics problems include storage optimization (hey FedEx, call us) or the distribution of goods, such as vaccines. Risk management for finance can be tackled using similar algorithms. Further afield are the technologies to build a quantum internet that will replace some of our cryptographic systems, to ensure privacy and security. 

Get started programing quantum computers

You can get started with quantum computing right now (without getting quantum drunk and challenging a classical drunk to a race through a maze)! At Strangeworks, we are lowering the barriers to programming quantum computing so you can be part of this exciting open-source community. You can explore our ever growing library of content or create your own as a member of the Strangeworks community. You can run code right there without installation and see the results. Explore many different quantum programming languages and platforms.

Here are some great places to start:

Play with some code for simplified quantum random walk

This post details how to code a four node quantum random walker. Starting with a simplified problem will help you get directly into writing quantum code without a ton of overhead due to the complexity of the problem. The understanding you have from this post will be enough to conceptualize what is going on, while the actual code and description of the quantum circuit you will take you into the nitty-gritty of building programs for quantum computers.

Getting started with the Strangeworks platform

If you just want to get your feet wet in the world of quantum computing you can’t do better than taking a tour of the Strangeworks quantumcomputing.com platform. This guide is the perfect jumping off point for this new paradigm in computing.

Tags: ,
Podcast logo The Stack Overflow Podcast is a weekly conversation about working in software development, learning to code, and the art and culture of computer programming.

Related

newsletter April 23, 2021

The Overflow #70: Networked spreadsheets

Welcome to ISSUE #70 of the Overflow! This newsletter is by developers, for developers, written and curated by the Stack Overflow team and Cassidy Williams at Netlify. Delve into the mysteries of superpositional drunken stumbles, the physics of the correct way to hang your toilet paper, and JavaScript that returns like a GOTO command. From the blog Stack…