Microsoft Quantum challenge at QCHack 2021: Recap
Last month we were excited to join Quantum Coalition Hackathon and to offer one of the technical challenges for the Hackathon. It turned out to be a great event, thanks to the organizers from Yale Undergraduate Quantum Computing and Stanford Quantum Computing Association, and to over a thousand participants from all over the world! Now that the Hackathon is over, let’s take a look at our challenge, and the teams that braved it.
One of the challenges we faced in preparing for the Hackathon was striking the right balance between helping the participants prepare for solving the tasks while not disclosing too much information about the tasks themselves before the kick-off ceremony. Our challenge announcement focused on the structure of the challenge and the preparation materials, while carefully avoiding more specific mentions of the topic. In our pre-Hackathon workshop, though, we let the cat out of the bag (or was it a box?) and revealed that the challenge would focus on solving problems using Grover’s search.
The challenge consisted of two parts. In part 1 the participants were presented with 4 independent kata-style tasks of varying difficulty, each of the tasks asking to implement a quantum oracle for the given classical function. You can try out the part 1 tasks yourself in the challenge repository; we’ve also added reference solutions in case you get stuck with some of the problems.
In part 2 we gave the participants the freedom to choose a problem of their liking and to develop a project that would solve it using Grover’s search and Microsoft Quantum Development Kit.
After a very intense 24 hours of hacking, we received a total of 40 submissions to our challenge. 12 of the teams did free-form projects as a part of their submissions, the rest of the participants focused on learning the basics with oracle implementation tasks. We had the foresight to develop a testing harness similar to the Quantum Katas to judge the tasks from part 1 automatically beforehand, so after the Hackathon the human judges focused on evaluating the projects done by the teams.
Once we started judging, it became clear that the winners will be picked among the teams who completed both parts of the challenge. Fortunately, we had 6 winners to select, which was a lot easier than selecting just one or two! Without further ado, here are the winning teams and their projects.
#1: Mastermind (Mihai Zsisku, Devon Chan, Fay Wong, Kabir Dubey, Yu Pang)
The winning project implemented Mastermind board game, in which one player (“codemaker”) chooses a pattern of 4 colors, and the second player (“codebreaker”) tries to guess it by choosing query patterns and getting feedback on how close they are to the pattern. The best feature of this project? It was implemented as a quantum kata, with each piece of the code covered with unit tests, so just a little extra effort can convert it into a great tutorial!
“The combined experience of the workshops and the Hackathon allowed us to create a minimalist, but mostly functional project using the information from the presentations. It was a very enjoyable event… It was a unique experience to work with folks from across the world, especially in such short notice. I learned a lot from their dedication and became truly enthusiastic about the quantum community.”
Check out the winning project here.
#2: Battleship (Richard Li, Will Sun)
This project solved the simplified version of setting up the board for Battleship game: placing several ships on the grid so that they fit within the board without overlapping.
“What made the challenge really enjoyable was being able to ask Microsoft team members for help throughout the 24-hours, like Mariia and Guen… I very much enjoyed how the pre-hack workshops during the week covered material that directly related to the weekend’s challenge… Overall, everything about the challenge was very organized.”
#3: |GroverMind⟩ (Alessandro Marcomini, Tommaso Faorlin, Samuele Piccinelli, Giulia Campesan, Filippo Angelini)
This project was another implementation of Mastermind game. The algorithm didn’t rely on the oracle knowing the correct answer as well (to quote the team, “where’s the fun without a little effort?”), so it didn’t take advantage of the quantum speed up offered by Grover’s search algorithm. Instead, it took a trial-and-error approach, taking into account the feedback from previous iterations to formulate the next guess.
“Despite the ongoing pandemic, thanks to this challenge we had the chance to connect and work together online, putting ourselves into the game outside the usual academic setting. We have been positively surprised about the results, given that we were all Q# first-timers. One thing is for sure, the memories from this experience will stick with us forever.”
#4: 4 rooks problem (Wittmann Goh)
This project solved the “4 rooks” problem: given a 4×4 board with 3 rooks already placed on it, place the 4th rook so that none of them attack each other.
“I felt that the challenges flowed very well from one part to the next. The 4 challenges in part 1 build very nicely on top of each other and require the use of more and more advanced techniques to solve. Having the first part be about oracles and the second part be about Grover’s algorithm which relies on oracles was also nice, since it tied everything together.”
Check out the project here.
#5: Seeking a diplomatic balance (Shixing Wang, Fang Yu)
This project was inspired by the diplomatic relations between nations in Sid Meier’s Civilization VI. For simplicity it considered that each pair of countries were either in alliance or in conflict, without any intermediate stages, and was looking for a balance of relations in which no three countries were pairwise allies or pairwise enemies. Under the hood this project utilized a creative adaptation of the hardest task from part 1, the oracle that checked whether the given graph edge coloring was triangle-free, i.e., didn’t have a triangle of edges painted the same color.
Check out the project here.
#6: Subset sum problem (Takuki Kurokawa)
|This project solved the subset sum problem: given an array of integers and an integer, figure out whether there is a subset of array elements that adds up to this integer. To simplify the solution, the code assumed that all array elements were non-negative.
Check out the project here.
Congratulations to the winning teams! We really enjoyed hosting the challenge, and we are looking forward to organizing future events!