Ahoy, fellow tech enthusiasts! Buckle up as I take you on a rollercoaster ride through my quantum adventure at the Inter IIT Tech Meet 12.0 in Madras, India. Picture this: 12+ events, high prep, mid prep, low prep, and a sprinkle of quantum magic. This was my second time in the competition, and guess what? We clinched the bronze medal! 🥉
The Background: What is Inter IIT Tech Meet?
Inter IIT - as its name suggests is a competition between IITs
Tech Meet - There are mainly 3 competitions (Cultural, Sports and Technical). Tech refers to the technical meet
There I was, just an ordinary day, sifting through the mundane sea of emails when BAM! I see this mail announcing the 12th edition of the Inter IIT Tech Meet. A competition in which amazing companies like Adobe and DevRev, and various others all in different domains offer problem statements that are to be solved by the students of IITs, with each IIT sending a representative team for their college. The competition is quite fierce with each college trying to prove their name and their technical skills (with all of them being IITs!).
I was very excited, and I knew I wanted to be part of the problem for AI/ML by DevRev. The interview takes place .... I don't get selected. I go for my next best interest (Algo-Trading Challenge by Zelta) .... I don't get selected.
I say lets give a last try for Quantum Computing Challenge by Mphasis. A few days pass and I am selected !!! (At this point I am pretty good at classical computing but still a beginner with quantum computing). The college forms a squad of 6 members - selected via each participant giving a proposal and then selecting the best ones from those.
The Challenge: Airline Woes and Quantum Rescues
So, there we were, a squad of six tech enthusiasts who had just met each other. The challenge was given - "Solving for passenger recovery during airline disruptions using Quantum Computing." Easy, right? Wrong! In just 15-20 days, we had to tackle this NP Hard problem and optimize like there was no tomorrow. Moreover, our squad was formed with us not having worked with each other before this! What's more, this is a field which is still emerging and has very limited literature for it, so you can't just ChatGPT it!!!
The Holiday that Wasn't 🏝️🚫
Our college vacations started, and while friends scattered like dandelion seeds in the wind, our team stayed on the campus. The campus, usually buzzing with life, transformed into a deserted tech haven. Wake up, work, work, work, sleep – rinse and repeat. Dedication level: 100!
Quantum Hesitation to Revelation 🤔➡️🌟
Confession time: I initially shrugged off quantum computing, thinking we could solve things the good old classical way. Oh, how wrong I was! A meeting with company reps showed they wanted quantum based solution and nothing else would qualify. From clueless to having some starting point – we started our journey
The Odyssey of Quantum Quirks 🌀
We start off by thinking lets make ourselves up to date with the current standards by reading some research papers. I read through a crazy ton of research papers trying to reach the current standards, also reading the same paper multiple times (realizing only after like 10-15 minutes of reading that I have already seen this). At this point we have no idea of what to do. We want to do everything. We just want to win.
We work.... We find a breakthrough solution .... We work on implementing it .... We ask, why are we doing this? This won't work !! .... Back to square one.
Again and again we went through the above process.
"I know let's ask the professors of our college," I thought. "Bravo," everyone said. The next thing we were doing was scheduling meetings with various domain experts.
Now we had some starting point. We split our problem into two and solved each separately. We would find a quantum and classical solution for both and then merge the best combination. I was assigned so solve classical solution for both the subproblems (since my teammates were just better than me quantum computing).
I was still thinking in the back of my head, "We don't need quantum computing, classical algorithms are just better in this case." My team captain then went ahead and challenged me to solve the problem classically faster (as a joke), than they could with a quantum algorithm.
I took that to heart and began my journey. My first sub-problem was, "Find alternate flight paths, subject to constraints that can change dynamically, when a given set of flights are cancelled." Now at first thought this reminded me of NP Hard problems like travelling salesman problem, and like anyone else would, I tried mapping my problem - It did not work. I started implementing algorithms like Ant Colony Optimization (ACO), Genetic Algorithms (GA), Bee Colony Optimization (BCO), Simulated Annealing and many other algorithms (All of which I learned on the way). I then created a solution with a mixture of these. It worked fine but required too much time (too many iterations for convergence). We decided that in the first sub-problem we will go with quantum approach.
I accepted my defeat at that time, but in the back of my head I was thinking of other algorithms.
A few days passed when I suddenly had this thought, "Why not take an assumption - Any alternate flight path shall have only K stopovers (k<2 logically)." I also thought, lets try a simple recursion based algorithm. It will take a long time since recursion cause exponential time complexity, but lets do it anyways.
I code the solution (without telling my teammates). Eureka!!! My code is better than any quantum approach !! It is fast and more accurate than the quantum solution. Why? Taking the assumption that maximum k stopovers are allowed reduced the time complexity from O(N!) -> O(k! * N) to O(N). Since (K!) turned out to be constant. So we now switched to choosing classical approach for pathfinding. (It was a bit slower but it had other benefits - can solve for all paths with 100% accuracy, while quantum approach solves for top k paths with lower accuracy)
Now, moving ahead to the 2nd subproblem "Reallocate affected passengers to the paths found while minimizing delay, checking available seats minimum cost for company, getting multiple solutions, flexible business rules and on and on". I knew I couldn't classically solve this faster than a quantum algorithm.
So I sat with my team mates and understood their current scenario. My captain had this idea to map the problem to the Knap-Sack problem, but since their are multiple paths, we map to multi-knapsack problem. This was fine, but we ran into some issues. There were some constraints we were not able to factor in (not easy to add constraints in quantum. We need to make the QUBO handle these constraints).
I asked my leader to explain the equation he made (cost function). I jokingly asked him, "why not add a new factor alpha, and make this factor handle everything". Then we just looked and each other and thought - That is exactly what we need. We created the factor alpha whose job to separate solutions spaces but putting then far form each other subject to the constraints of the classes.
So we now mapped our problem to Class Constrained Multi Knapsack Problem. This is a problem that has never been solved before via quantum computing (at least in all literature that we found).
Through this we now felt some confidence that we can actually win this competition - while we started with no idea what is even happening.
The Impromptu Symphony 🎶
As if our journey needed more drama, the presentation became a last-minute train escapade. Picture this: me and three team members, crafting our presentation in the train to IIT Madras. Presenting the entire project without any practice. Improv at its finest!
The Overall Experience 💡🍽️
Thorough this unbelievable experience I learnt a lot.
- Some times simple is just better. You don't always have to think outside the box
- Asking around always helps. Never hesitate to ask. People will be there to help you
- Time management is very very important. (Making then presentation at the last minute was probably not a good idea)
- Always make sure to work as a team. Keep a good rapport with your team will always help. Always try to explain your thoughts to someone, this will clear your own thoughts
- Never Give UP !!!
- And a bunch of technical skills like, Algorithms Design 🤖, OOPS, Quantum Algorithms (QAOA, Quantum Annealing, etc) 🌌, Nature-Inspired Algorithms (Ant Colony Optimization, Genetic Algorithms) 🐜, Vectorization of Algorithms using Pandas 🐼, Class Constrained Multi Knapsack Problem using Quantum Computing 🎒, In-depth Algorithm Analysis 📊, QUBO, Linear Programming
Participating in the Inter IIT Tech Meet 12.0 was more than a competition; it was a cosmic adventure of challenges, breakthroughs, and camaraderie. A huge shout out to my professors and teammates for being the real MVPs. As the curtain falls on this quantum saga, I carry forward the lessons learned and skills earned into the ever-evolving tech cosmos.
#InterIITTechMeet #InterIIT #Tech #Coding #Quantum #QuantumComputing #QuantumAlgorithm #Mphasis #MphasisFoundation #Challenge #Software #SoftwareDevelopment #Victory #IITMandi #IIT #QuantumAdventures #TechTales #BronzeVictory #TeamTechies #CodeCraftersUnleashed
Top comments (2)
Man I could really imagine the joy you had when solving the problem. To have hard problems to solve and run against it first like a wall, have an idea but it has no great performance come up with another solution or a few optimizations and finally it works. This is one of the best feelings to finally solve the problem, to stay focused and put dedication into it.
Great article!
And congratulations to the whole team!
Would be great if possible to have more in-depth articles to this topic
Thanks a lot 😄
I will most definitely post some more articles on this.