Quantum Computing & the Math Problems
I happened to listen to the topic of Quantum Computing and its Applications. The kind of Math Problems that it can solve in just a few seconds.. Apparently, the Classic Computers of Today take years to solve these problems..
And that set me thinking.. The 3 maths problems that were mentioned.. It took me back to my younger self as a Mommy to elementary school-going kids.. I saw glimpses of the problems, if not their solutions. And that intrigued me to ponder and write this.
Well! What even is Quantum Computing? Some serious Physics stuff.. Let's keep that aside, and dig into “what can” of the future computer.
The Traveling Salesman Problem also known as TSP
“Given a list of N cities and the distances between them.. What is the shortest possible route to cover each city only once?
It turns out that the number of possibilities grows like crazy, with the increasing number of cities.
Cities: Possible routes
5 Cities 12 routes
10 Cities 181000 routes
20 Cities 6.1 x 10^16 routes
25 Cities 3.1 x 10^23 routes
But why would this matter to us?
This is a classic problem of optimization given N resources. And there are ample applications.
Optimal combination of chemicals for a new drug.. Efficient Chip design.. Manufacturing and Optimal use of Resources.. Best route in Airlines.. Logistics & Planning
It reminds me of a fun math project during the winter break. I guess Ms. Lawson wanted her 5th-grader students to be excited about the city names and the US map, and seed the idea of optimization in a casual fun way. There was no need to use any math.. Just the human element of judgment.
Santa is planning a vacation from East Coast to West Coast. He hopes to cover one city of each alphabet fromA-Z.
And mind you.. The deer pulling the sledges run out of food pretty quickly. Can you help him plan this A-Z Intercoast City hopping trip?
The Maze Problem
We all understand what is a maze. What is different about Quantum Computers?
A classical computer is kind of serial.. It would have to run one path after the other to find the right one, whereas a quantum computer can work all possible paths at once, and return the correct path.
Check out this cool link.. The traditional computer is compared with a lady bug and quantum computer is like a bunch of Ants spreading out in all directions simultaneously, and finding all possible exists.
How to navigate from one point to another to another in a maze of roads? Seems like a Quantum Problem.
Prime Factorisation
“What? What’s the big deal about it?”
That's exactly what my friends had remarked..
Prime Numbers are like Elements and Building blocks of the Material World. They are the Golden Keys of the Universe. And every Natural Number can be expressed as a unique product of prime numbers. This is the Law of Prime Factorisation.
15 = 2*3
27 = 3*3*3
420 = 2*2*3*5*7Multiplication is long but easy peasy.. But not Prime Factoring. Let's visually examine the process of filtering prime numbers till 100.. A fun fact I learnt from my 5th grader. The Sieve of Eratosthenes.. Strike of multiples of all the unchequered numbers.. And what’s left are the prime numbers.
Prime Factorisation, which we verily do in 5th grade is kind of simple. But it gets complex as it grows. Divisibility check by 3, and divisibility check by 11 are kind of common. In Vedic math, I came across a mind-boggling algorithm to check the divisibility by any 2-digit prime number be it 13, 17, 19, 89, 97 whatever.. It was called the method of osculation.
In fact, Fermat came out with an algorithm some 400 years back to determine if a number was prime or composite. It was treated as a thing of antiquity and not much use. Then came the world of Computers, the Internet, Cyber Security, and Prime Numbers were in full business.
With Asymmetric Enryption, and pair of Public Key and Private Key, it turns out that the Private Key is a Prime Factor of the Public Key.. Transactions are secure as Private Key cannot be easily cracked. Classic computers would take an incredible amount of time to decode the Private Key using the Public Key and hence it works..
Come Quantum Computing and the Shor’s Algorithm, it seems that the keys can be easily cracked by the Quantum Computer. The Internet world has to pass through a new wave of Post Quantum Cryptology..
How far are we from Quantum computers?
Apparently, these powerful beasts have some limitations. They are sensitive to vibration, and electromagnetic signals and hence operate at low temperatures of about –460 °F. So not really out at a commercial scale.
This Universe & Quantum Computing
Is there any pattern that this Universe does not exhibit? A meditative mind focusing in a cool zone, and coming out with a breakthrough idea perhaps?
Found this interesting read. “Electronic amoeba” finds approximate solution to traveling salesman problem in linear time
