Quantum Computing for the Classical Mind
- By Grace Mary Matson
This article is a part of the Debugged Magazine released by Coding Club of Indian Institute of Technology, Guwahati. To read the entire magazine click here
You’ve probably heard this fancy term before, but does it feel distant and weird and mysterious to you? Let’s break it down. There’s absolutely nothing weird about “quantum”, it’s just an accurate description of the way the world works. In fact you are indeed a quantum object yourself! It is tougher to wrap your head around the quantum phenomena that God has packed into nature like superposition, entanglement, and tunneling because the effects are very, very tiny on the macroscopic level we are in. Still, they are very real and amazing nonetheless.
Well, quantum computing just happens to be a smarter way to harness all these phenomena, the natural properties of quantum states, and use them to solve certain computational problems by reducing exponential time complexity to polynomial-time!!
That’s… weird, how can it just do that? The crux lies in the fact that our classical computing is dependent on binary bits to store information. They can store either 0 or 1, nothing in between. But quantum bits, or “qubits”, which are the basic units of information in a quantum computer, can exist in a more “fluid” state, a superposition of the basis states 0 and 1, being neither exactly 0 nor exactly 1 at the same time! When measured, they fall back to exactly one of the basis states, but the probability of them falling onto a particular basis state is determined by their composition just before measurement. Hmm, and it’s not just this, we can also entangle these qubits, which will link their properties so that the outcome of their measurements isn’t random anymore, it will be interconnected! This entanglement is why classical computers can not simulate quantum computers.
Let’s make the idea more objective. Say I have 2 binary bits, how much information can they carry? 2 independent parameters right? I can completely describe the information contained in the system by defining the state of the first bit — 0 or 1, and the state of the second — 0 or 1. Yeah, obviously.
But what if I have 2 entangled qubits??? They are going to exist in a superposition of 4 basis states, what does that mean? For simplicity, let’s say the basis states for 2 quantum bits are — 00, 01, 10, 11 (in reality they are more complex), now there is going to be some parameter corresponding to each state, which is the probability that the quantum system of 2 qubits will fall to that state when you probe/measure it. This implies that we need 4 independent parameters to completely describe this quantum system of only 2 quantum bits! Did you see what just happened? The amount of information contained equivalently in N quantum bits, is 2^N times what can be contained in N classical bits ! Qubits can physically unlock multidimensional spaces. Quantum information is a whole lot more “dense” than classical information. To put things into perspective, in theory, all of the digital data in the world right now, can be contained in just 70 qubits!
The computation speed is greatly enhanced because we use quantum properties like interference to cancel out all the wrong answers, and amplify the right one. We use quantum logic gates to realize this. The idea might sound weird though, how can you increase the probability of getting a right answer using interference, when you don’t know what the right answer is in the first place? This boils down to knowing the properties the right answer will have, and this is kind of why quantum computing gives us a potential advantage only in certain computational problems, where you need to check an answer once you have it.
There is one thing we need to be careful about though, and that is the fact that we can not measure a superposition. All we can measure is a basis state and so we need to design algorithms carefully to make sure that the final answer is a single basis state, and not a superposition.
Okay, all of this fancy stuff is cool, but where can we use this? To solve problems which our classical computers just aren’t good at solving, because the computational complexity of the problem increases exponentially and it takes too long to solve it. A few very obvious applications of quantum computing are :
- Drug development- Right now, our classical computers are simply incapable of simulating the interactions between atoms in a single molecule perfectly. Why? Because there are too many interactions inside them for a classical computer to deal with :(. But that’s where our quantum computers jump in, they’re a much better way to deal with a quantum system problem that is, well, so inherently “quantum” in the first place :)
- Integer factorization- This is the process where you have to find the two numbers that multiply together to make a bigger, given number. There is no known process in mathematics that can perform this process efficiently: All classical computers can do is keep trying combinations of numbers until they find the ones that work. The difficulty of factoring is what protects our best encryption algorithms. But in 1994, MIT mathematician Peter Shor created an algorithm that uses quantum interference effects to factor large numbers with ease.
- Search problems- Grover’s search algorithm improves speed and efficiency drastically when you want to search for an item in an unstructured database. On a classical computer, you would need to go through N/2 items on average, and all N in the worst case, but a quantum computer would find the item after roughly sqrt(N) checks.
Well, there are a lot more interesting applications like optimization, cryptography, better weather forecasting, enhancing AI and much more but I’ll cut it short here :)
How do you physically realize this “qubit” which looks like it is working magic? There are many things you can use, like the spin of the electron, a photon, a nucleus like that of phosphorus, and a lot more. You essentially have to store these qubits at temperatures near absolute zero (about 0.01K) so that their states don’t get messed up by the thermal energy of the surroundings.
Can we say qubits are a kind of storage register? You sort of can, but there is one caveat, you can’t clone information. You can transfer, but you can’t make a copy, because once you transfer the quantum information from one P atom to another, the original data gets erased.
In conclusion, quantum computers have the potential to revolutionize computation by making certain types of classically intractable problems solvable, and though we still haven’t designed algorithms to unlock all its exponential computing power, we are making a lot of progress and it’s definitely exciting! Isn’t it simply awesome how the seemingly tiny things God has dropped into nature can make such drastic differences in our lives ?
That was a quick introduction to the topic and I hope this article has got you to feel more comfortable with the whole idea of quantum computing now!
