I'm at the start of learning about Quantum Computing and realized how important Computational Complexity is. I did a lot of research so I do understand it, but I wanted to document my understanding of it, that way I was able to help someone someday.
What is Computational Complexity?
Computational complexity refers to how hard/difficult it is to solve a specific problem as the size of the problem increases. Meaning, whenever you hear about computational complexity, it is all about how time-consuming a problem becomes as it gets bigger as time passes. This concept is important in quantum computing because it helps us understand how fast the difficulty or time to solve the puzzle grows as the puzzle gets bigger. Besides how long it takes for us to solve a problem, we also care about how much memory or space is needed for the problem to be solved, So, complexity can refer to both time and memory usage, and algorithms play a critical role in making it powerful.
So I'm going to give an example below.
Linear Time Complexity:
Imagine you have a box with dimensions 200 by 150, and you need to pack 5 items into it. Each item has a dimension of 35 by 20, and let's say it takes 2 seconds to pick up an item from its original location and place it in the box.
So, to pack 5 items, you multiply:
- 5 items × 2 seconds per item = 10 seconds to pack all the items.
Since the task is only about placing items into the box, we don’t care about arranging them perfectly. Now, if you were asked to pack 20 items, you simply multiply:
- 20 items × 2 seconds per item = 40 seconds.
In this case, the time it takes to pack the items grows directly in proportion to the number of items. The more items you pack, the more time it takes, but the relationship is linear, meaning double the items, double the time.
This is what we call linear time complexity because the time to complete the task increases at a constant rate as the number of items increases. The notation of this complexity is O(n).
Exponential Time Complexity:
Now, let's make the problem more complicated. So instead of just placing the items in the box, imagine you need to find every possible arrangement for the items to fit properly in the box. Because the box and the items have different dimensions, you need to carefully think about how to place each item. Thinking whether or not the item should go on the right, left, front, or back? Maybe you need to rotate the items to make them fit in with the rest.
Let’s break it down with a more detailed example since for just 2 or 3 items, it’s easy to figure out the arrangement:
- So suppose you start with 100 items. You already have 4 possible ways to arrange those items in the box (maybe each item can go in one of four different positions).
- Now, you add the 101st item, but when you add this new item, it creates even more possibilities because you now have to think about how this item interacts with all the previous 100 items.
- Each time you add a new item, the number of possible arrangements doesn’t just increase by 1, it increases by a factor
(n). For example, if adding the 101st item creates 4 more possible arrangements, then the 102nd item might create 5 more, and so on, thus the factor (nk).
So, for each new item, the number of possibilities grows rapidly. This means the time to figure out the right arrangement increases exponentially because you have to evaluate all these possibilities. You also have to decide whether to place each item in a different orientation, maybe rotated or placed diagonally to make it fit.
With 200 items, there could be millions of possible ways to arrange them in the box. Where each item adds more and more complexity, making the task much harder and much more time-consuming.
Impact on Computational Complexity
Now, the question I asked myself is that, is this one of the problems QC is trying to solve? The answer I found is yes. The reason is that when the number of possibilities grows exponentially, it becomes too hard for classical computers to handle.
A commonly cited example is the Traveling Salesperson Problem (TSP). In this scenario, if you have 20 cities and need to find the shortest route connecting them all, the number of possible routes grows rapidly as you add more cities for either expansion or others. For classical computers, this would mean that an enormous amount of time is required to evaluate each potential route. At the same time, QCs have the potential to evaluate multiple routes simultaneously, significantly reducing the time needed to find the optimal solution.
This capability stems from the principles of quantum mechanics, which allow quantum computers to process information in fundamentally different ways than classical computers. As a result, they hold the promise of solving complex problems more efficiently, especially in fields like optimization, cryptography, and simulation.
Conclusion
I'm moving on to the next topic in my learning journey. While I realize that this information is still quite limited, and I haven't covered Polynomial Time Complexity and other concepts I've learned, I promise to explain those in more detail later. Thank you for following along! If you have any questions or points you'd like to discuss, feel free to reach out to me through my personal website. I'm always open to feedback and conversation!