AWS Quantum Technologies Blog
How we learned to program with atoms in 24 hours flat
Earlier this year, QuEra Computing, in collaboration with AWS, sponsored the first-ever public hackathon to include a neutral-atom quantum computer: iQuHack 2023. The event was hosted January 27-29th on the Massachusetts Institute of Technology (MIT) campus in Cambridge, MA. Over the course of 24 hours, competing teams were tasked with developing innovative solutions to the maximum independent set problem using QuEra’s Aquila quantum processor on Amazon Braket.
Representatives from both QuEra and Amazon Braket had the privilege to support the hackathon in person, witnessing the incredible work by over 300 hackathon participants. In particular, we want to highlight the work of a group of individuals from Yale University, known as the “5-headed cat,” who demonstrated ingenuity and true hacking spirit, ultimately taking home the QuEra challenge first prize. In this blog they share their story and give a glimpse into the experience of being a “quantum hacker!”
The impact of iQuHack 2023 extends far beyond the competition itself. Many participants have remained in contact with QuEra, accepting internship opportunities and participating in student workshops organized by the company. The “5-headed cat” team themselves had the opportunity to present their work at QuEra headquarters in Boston, including potential extensions to their original project.
Be sure to also check out their project source code and amazing GUI on GitHub!
The story of the hackathon
This section authored by Alex Deters, Pranav Parakh, Sofia Fausone, Ben McDonough, and Wyatt Kremer.
Over the weekend of Jan. 28th 2023, our team had the privilege of participating in the QuEra challenge at iQuHACK 2023. After an introduction to MIT’s campus, a discussion between a panel of quantum information science experts, a tutorial from the folks at QuEra, and a solid night’s sleep, the hacking commenced at 10:00 am!
The challenge posed by QuEra was to find the largest independent set (IS) on a unit disk graph of our choice, using the least number of shots, with the constraint that we could use up to 100 atoms on their neutral-atom Aquila quantum processor. The goal was to maximize the total number of nodes in our IS, not the fraction of the total number of nodes (i.e., an IS of 20 out of 100 nodes would win over an IS with 7 out of 10 nodes). In 24 hours, with no sleep and a ton of coffee and energy drinks, we managed to come up with a solution that won the challenge. If you’ve ever wondered how hackathons work, here is the five-minute version of our 24 hours of learning and hacking!
10:00am: Maximal and maximum Independent Sets
To solve the challenge problem, we first had to understand the concept of a maximal independent set: we start out with a connected graph with nodes that can either be marked “on” or “off.” The rule that makes a set of nodes independent is that no two adjacent nodes (those sharing an edge on the graph) can be marked “on”. Finding a set of nodes that is just independent is trivial: just switch all the nodes to “off”! The catch is the “maximal” property: switching any node from “off” to “on” must produce a graph that is no longer independent.
One of the first facts we encountered when researching this topic is that the problem of finding maximal independent sets is already solved, accomplished by a classical computer with logarithmic complexity1. How is a quantum computer useful here? Even though a clever classical algorithm is able to produce a maximal independent set, we haven’t said anything about the number of “on” nodes in the set!
Here’s an example of two maximal independent sets:
Fig. 1. Two maximal independent sets on a chain of three nodes.
Both of these are maximal independent sets in the same graph, because if you switch any of the “off” nodes to “on,” you no longer have an independent set. The challenge for the hackathon was to always produce sets like the second one, with the highest number of “on” nodes: a maximum independent set.
Solving the maximum independent set problem in an arbitrary graph is a formidable task with no known classically efficient algorithm.
1:00pm: Rydberg atoms
A qubit is a generalization of a classical bit, where the familiar 0s and 1s are replaced with the quantum states |0〉and |1〉. QuEra’s platform uses neutral rubidium atoms as qubits. A high-energy state of the outermost electron corresponding to a high principal quantum number is called a Rydberg state, and an atom with one electron in the Rydberg state is known as a Rydberg atom. The and states of the atoms are used as the computational and, denoted by and for ground and Rydberg, respectively.
In the excited Rydberg state, quantum fluctuations puff the atom up to many times its ground-state size, giving it the propensity to interact strongly with its neighbors via the van der Waals force. The energy associated with two atoms interacting is known as the interaction potential. The strength of the interaction is dependent on the distance between two atoms, and it takes a huge amount of energy to place two neighboring atoms in the Rydberg state: the so-called Rydberg blockade effect. We can control the state of the atoms by driving them with a laser at different power levels and frequencies so that the excited states become favored. If this process is executed sufficiently slowly, the amount of energy added will be insufficient to excite pairs of neighboring atoms into the Rydberg state. This makes Rydberg atoms well-suited to the problem of finding maximum independent sets.
6:00pm: Unit Disk Graphs
To solve the maximum independent set problem using the quantum hardware, each atom will represent a node in the graph. They are connected by an edge in the graph, which needs to lie within the blockade radius. The blockade radius refers to the distance between two Rydberg atoms at which the excitation of one atom to a Rydberg state strongly inhibits the excitation of the other atom. We can tune the blockade radius by varying the drive amplitude, which controls is the power of the laser.
In other words, two atoms within the blockade radius will satisfy the adjacency condition for an MIS. By rescaling the graph so that the blockade radius equals one, transforms the graph into a unit disk graph, defined by the property that connected nodes are within a unit length of each other.
Before we could submit jobs to Aquila, we had to generate large unit disk graphs (of 100 atoms). We created a GUI tool to help us visually place points and create graphs. This tool also allowed us to easily work within the hardware constraints, which were the following:
- All nodes must lie on a stage 75μm x 75μm x 75μm
- Nodes must lie in rows spaced by at least 4μm
- Nodes cannot be closer than 4μm in any direction
Using this, we created several graphs that we wanted to test.
Fig. 2. Screenshot from the GraphFactory library showing a sample graph
GraphFactory allowed us to play around with different types of graphs, automatically imposing the conditions required to run them on the quantum processing unit (QPU). The features include adding and deleting nodes, visualizing when two atoms are within the blockade radius as edges in the graph, creating a library of stored graphs, and exporting graphs as .csv files to run through the Amazon Braket API.
8:00pm: Stitching Graphs with Boundary Conditions
Although we were only given 100 atoms on QuEra’s QPU to create our solution, we quickly realized that we could go bigger while still technically remaining within this constraint. If we could use the QPU to find maximum independent sets for small graphs and then devise a way to “stitch” them together into larger graphs, we could in theory produce solutions for arbitrarily large graphs. To ensure that we maintained a maximal independent set after stitching graphs together, we needed to find a way to control the states of atoms on the boundary of the atom arrangements.
Analog quantum computing is fundamentally different from the more familiar gate-based approach to quantum programming. Instead of having meticulous control over the state of each qubit at each step throughout the computation, analog machines perform a time evolution where the physics of the system does most of the work for you. But this makes it difficult to force individual qubits (say, those on the boundary of your graph) to be in any particular state.
Fig. 3. Comparison of n=5 and n=6 chains of atoms.
To tackle this boundary condition problem, we compared two different cases, shown in the above figure, where we can see that the ends of the chain are in the Rydberg state with high probability in both cases. In the n = 5 case, shown on the right, there is only one possible MIS. However, for n = 6 of the four possible MIS solutions, the two with both ends in the excited state are highly favored. From this we deduced that as a result of the interaction, atoms with a smaller number of neighbors have a far greater probability of ending up in the Rydberg state.
This provided a solution to our modularization and boundary condition problem. Using carefully placed tails, we could control the state of qubits at the edges of the graph.
Fig. 4. Here we change a node on the edge of the graph from Rydberg to ground state by using the “tail” strategy. This result was obtained with 100 shots on the free simulator that is provided in the Amazon Braket SDK.
In Figure 4 (above), we added two tails to node 1 in order to change it from the Rydberg state to the ground state. Each of the tails is likely to be in the Rydberg state, which influences the desired node to go from being in the Rydberg state to the ground state. By adding these tails, we could enforce boundary conditions that enabled us to stitch modular graph sections together.
3:00am: Our Solution
We tested the modularization process by starting with a larger graph that could be divided into a sparsely connected set of dense subsets, as shown below:
Fig. 5. The graph used to test the modularization process. The red dotted lines show how the graph is separated into four sparsely connected subsets
The process for solving the modular maximum independent set problem was to
- Divide the graph into n subsets
- For each i ∈ [1, 2, 3, … n] do:
a. Use QuEra Aquila to produce a solution to the MIS problem for the ith subset
b. If i > 1 then
i. Choose the solution out of the shots taken with the most atoms in the excited state that is compatible with the boundary of the previous set. The tails successfully enforce boundary conditions with high probability, but not always.
c. If i < n then
i. Record the edges shared with the i+1th subset
ii. Add appropriate tails to the subset to ensure boundary compatibility
3. Remove the tails from the data and put the pieces back together
Fig. 6. The iterative process in action with each of the four subsets of the original graph shown in Fig 5. Dotted lines show the edges between sections adding boundary conditions. The tails that we added are circled in red.
After stitching the four subsets together to get back to the original graph, here is the final result!
Fig. 7. The combined MIS solution with all four subsets.
This solution provided a proof-of concept for our method of solving the MIS problem on subgraphs to produce larger solutions. In the era of NISQ computing, finding ways to leverage the limited capacity of today’s hardware is essential to applying quantum computing to real-world problems. Although the challenge only allowed us to use 100 atoms in our solution, we could technically argue that we had found a way to produce arbitrarily large solutions within that condition.
7:00am: Mad Dash to the End
The relief at finally having a working solution was mitigated by the impending 10:00 am deadline for our writeup submission. We worked frantically around a table in the MIT Museum, sending files back and forth over Discord, hurriedly merging pull requests, and having mini heart-attacks when our programs crashed. Although the legibility of our documentation was evidence of our sleepless night, we managed to press the “submit” button at exactly 10:00 am.
10:00am: Sleep
Fig. 7. Rest state of the team
This was an amazing opportunity! We’d like to thank the capable team at QuEra who created this challenge and patiently fielded our questions throughout the evening, as well as the organizers of iQuHACK for making this experience possible. If you are interested in seeing our solution or using G for yourself, links to the GitHub repositories can be found below.
Conclusion
We on the Amazon Braket and QuEra teams had the privilege of supporting the “5-headed cat” team in their iQuHACK hackathon project this year, and we are eager to see more projects like this in the future. Consider joining us for a future hackathon, whether iQuHACK, QHack, or UnitaryHACK and beyond!
Do you want to experiment with the maximum independent set problem on Aquila yourself?
About QuEra
QuEra Computing is a neutral-atom quantum computing hardware company, based on pioneering research at Harvard and MIT in the groups of Drs. Mikhail Lukin, Markus Greiner and Vladan Vuletic, headquartered in Boston, MA. Their quantum computing hardware is available on Amazon Braket. In addition to solving MIS graph problems, the Aquila device also supports Analog Hamiltonian Simulation (AHS).
1 Ghaffari, Mohsen. “An improved distributed algorithm for maximal independent set.” In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 270-277. Society for Industrial and Applied Mathematics, 2016.