Quantum computers (part 3/n): ============================= NOTE 1: Ignore this post, if you are not a computer engineer. NOTE 2: Wall of text - please ignore spelling and grammatical errors. Previously on Quantum computers: We completed our investigation of basic big-O notation and saw why we could simply ignore lower order terms in favor of the highest order term. In this episode: We take a look at a special class of running time - exponential and this creates the foundation for quantum computers. Exponential running time: ================= NOTE: You can ignore the rest of this post, if you already understand exponential running time. NOTE: If you are new to big-O, I suggest you read my first 2 posts on this. To quickly recap, big-O notation talks about the running time of an algorithm in terms of input size. We saw different examples of running time - O(1), O(lg n), O(n), O(n^2) etc. There are numerous other types of running time. However, today, we are interested in a special type of running time. This is denoted by O(2^n). For this discussion, we consider everything at or above O(2^n) to be exponential. We will see examples of exponential running time shortly and try to understand why this class of algorithms are bad. But before we do that, lets talk about them in plain English. Exponential time simply means that the running time of an algorithm grows EXPONENTIALLY with input size. In other words, a small change in input size can have a massive effect on running time. Lets take a look at some input sizes, with an algorithm which is O(2^n): O(2^n) Input size: 1: 2 2: 4 10: 1024 100: 1267650600228229401496703205376 Yea, I will just stop at 100. And so, hopefully, you get the picture! You would not be able to run this algorithm for even small input sizes. At just n=100, the amount of time it would take to output this would be several billion centuries (read that again: several BILLION CENTURIES!!). Clearly, this is not acceptable and rightly so! Numerous years and millions, if not billions, of dollars have been spent on trying to find alternatives to exponential algorithms. For some classic exponential algorithms, you might actually end up winning the Nobel Prize if you were to create a polynomial version of it. Now that you understand the gravity of the problem, lets take a look at some examples of exponential algorithms. The number one issue with these algorithms is that they appear to be the most harmless pieces of code. Unless you are at least semi-proficient with algorithms, you will never be able to pick out the ticking bomb in your code. Example 1: Find all permutations of a string Problem explanation: Given a string of arbitrary length, say, abc, find all permutations. Input: abc (this can be of any size, abc is just an example) Output: abc, acb, bac, bca, cab, cba The output is n!. You can try this with a string of length 4, say, abcd. n! = O(n!) = Exponential running time (well technically, factorial running time, but anything higher than O(2^n), we categorize that as exponential). Code (I am providing actual working code in C#, so you can execute it and try it for yourself): ================================================ private static HashSet permutationMap; private static void Permutation(char[] chars, int current, string permutation) { ....if (current == chars.Length) ....{ ........Console.WriteLine(permutation); ........return; ....} ....for (int i = 0; i < chars.Length; i++) ....{ ........if (!permutationMap.Contains(i)) ........{ ............permutationMap.Add(i); ............Permutation(chars, current + 1, permutation + chars[i]); ............permutationMap.Remove(i); ........} ....} } Call this code in this way: permutationMap = new HashSet(); Permutation(new char[] { a, b, c }, 0, ); And off it will go on its merry way and spit out all permutations. If you understand recursion, this code should be self-explanatory. If you dont, I suggest you put this in C# and try to follow in the debugger. However, the point here is to not completely understand the code. The point here is to tell you that these 15 lines of code will run for billions of years, if you simply increase the input size to, say, 20 (or maybe a bit more). I mean, you cant even permute over all the alphabets! Lets look at running time (this time in seconds - I know, seconds are meaningless, but I am trying to drive the point home): 3 chars: 0 ms 6 chars: 78 ms 8 chars: 1466 ms (1.4 secs) 10 chars: 115581 ms (115 secs) 26 chars: 165938899921720 centuries (holy crap!!! - I obviously did not try waiting for this to complete. I promise!) A more important point to understand is the general nature of exponential algorithms. While this knowledge will best come with experience, but look out for keywords: 1) Generate all combinations 2) Generate all permutations 3) Find optimal solution 4) I will edit this post and add more as they hit me. In essence, if you have to go through the entire data set and go through all possible combinations of data, you have an exponential algorithm. A classic example, that you would frequently hear (especially, when talking about quantum computers) is the Travelling Salesman Problem. The problem simply states that say you are a salesman and you have n cities to visit. Now different orders of visiting cities will lead to different costs. You want to find the cheapest order of visit. So to solve this problem, imagine that the cities and the routes between them were ordered through a graph. Cities were vertices and the edges between them were the routes. Each edge might have a cost associated with it. Now to find the OPTIMAL (optimal = best answer), you would have to go through all permutations of visiting city. Its exactly the same as the permutation example given above. Lets see an example: Say, you had to visit 3 cities - a, b, c. What is the best way? Well the only way to guarantee that you have found the best way is to try ALL permutations of visit. So: abc acb bac bca cab cba Only after you have gone through all permutations will you be able to say for sure that you have definetely found the best order of visit! This nature of problem is called the combinatorial optimization problem - basically you need to go through O(2^n) or more combinations to find the optimal solution (with this knowledge, go see Googles quantum computer marketing bulshit of a video again). Ok, hopefully, you understand the problems of exponential algorithms and why everybody hates them so much! NP-Hard: ======== While the actual definition of NP-hard is a bit more involved, to summarize it, NP-hard problems are problems for which no polynomial time solution exists. In other words, the ONLY known solution for that problem is exponential. NP stands for, non-deterministic polynomial (yea, I know, fancy stuff). Conclusion: =========== Ok, thats it for this time. Next time, we will look at exponential problems at the bit level (promise, its way easier than it sounds). Once, we have seen the problem at bit level, we can transition into quantum computers and why they can be so powerful!
Posted on: Fri, 25 Oct 2013 10:42:12 +0000
Trending Topics
Recently Viewed Topics
© 2015