Understanding quantum computing through drunken walks
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.
The Stack Overflow blog is committed to publishing interesting articles by developers, for developers. From time to time that means working with companies that are also clients of Stack Overflow’s through our advertising, talent, or teams business. When we publish work from clients, we’ll identify it as Partner Content with tags and by including this disclaimer at the bottom.Tags: partnercontent, quantum computing
I’ve written a quick tutorial that explains the basic model of a quantum computer at: https://cirosantilli.com/programmer-s-model-of-quantum-computers in very concrete terms (matrix multiplication) that many programmers will be able to appreciate
The “box” example is not good. The box has all six sides present. It is ALWAYS a box and never a corner. The box can appear to have different orientations depending on which face you pick as the front, but it is always a box.
Excactly! I was almost giving up reading any further because of the hoax box example. Seemed to be a single mistake though, after all.
It is always a box indeed, and actually it has TWO corners – front-top outermost and rear-bottom innermost ones BOTH visible ALL THE TIME, as all the borderlines and merely the borderlines are shown, thus it being essentially a transparent box.
I am not a expert in computer savvy, but I know perfectly that the smartest of us don’t know absolutely nothing about who we really are and can create, that I know. I deeply feel that there is a greater force at the moment that impels us to know more so that we can begin to know the truths and in this way contribuite to having a better would.
Actualizar fecha cuántica.
Suggest a time delay where questions are not closable for 24 hours except for graphic language or copyright. I spend 2 hours writing a question, with all of the troubleshooting steps taken so far (20+ of them), with URL links to relevant help pages for those troubleshooting steps along with details of my dev environment and the question gets immediately closed and down voted without a reason.
First, I spent the time to research and do significant troubleshooting before asking on stackoveflow.
Second, I summarized in short bullet points the troubleshooting steps and provide URL links to the source pages for them
Third, I found several extra possible solutions to the problem not found in a simple or deep google search and asked if they were feasible for long term use
To what extent does StackOverflow become a troll farm of moderators expecting only short expert level questions that they can answer?
I could downvote each question I cannot quickly answer and answer those that I can to rapidly gain points.
A conflict of interest?
1. Limit the number of upside points a person can gain in a 24 hour period,
2. Limit the number of down votes a person can cast in a 24 hour period to 3
3. Do not let a question get closed for 24 hours after being asked unless it violates graphic language or copyright infringement
4. Consider adding a ‘re-tag’ option instead of down votes for moderators that have an opinion that a question is not in the right StackOverflow message tag group
5. Require moderator to provide comments as to why a question or answer is down voted and also importantly a way for the user whose question or comment is down voted to report for abuse the moderator
Stackoverflow should promote working together and not let toxic behavior drive away questions even simplistic ones. Otherwise, it will be little better that most vendor’s ‘Closed, not a bug, could not reproduce, please submit an enhancement request’ message bases with few answers and mostly deferrals.
Most of your suggestions already exist on the site in some form:
1. You can only gain 200 rep points in one day (excluding bounties)
2. You can only cast a total of 40 up/down votes per day
4. A “re-tag” option is available already — the tags on a post can be edited, and moderators are able to move posts to a selection of other stackexchange sites.
5. If you feel a moderator or community volunteer has abused their power or made a mistake, you can message the mods or ask a question on meta.
It’s important to realise that most close / downvote actions on the site aren’t performed by moderators — just normal community members that have earnt those privilages at their respective rep gates.
The comments of an unrelated blog post are an in-appropriate place to disucss this any further. I’d recommend you make a question on meta (https://meta.stackoverflow.com/) containing links to your closed questions to ask about it further there, as you’re likely to get better replies.