AWS Quantum Technologies Blog

How we learned to program with atoms in 24 hours flat

How we learned to program with atoms in 24 hours flatEarlier 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:

two chains of circles with alternating blue and red nodes labeled as "on" or "off"

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.

purple graph on black background with 31 nodes connected in an irregular manner

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.

two plots of the x and y positions of a chain of atoms. In the lefthand plot, there are 6 atoms, where indices 0 and 5 are in dark blue (Rydberg density of 1), 2 and 3 are in light blue (Rydberg density 5), and 1 and 4 are white (Rydberg density 0). In the righthand plot, atoms labeled 1-5 with a color map from white to blue representing their Rydberg density, where along the vertical axis, atoms 0, 1, and 4 are in blue (i.e. a Rydberg density of 1)

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.

two unit disc graphs with Rydberg densities plotted in space. Top graph has 8 nodes with the outermost ones in dark blue (Rydberg density of 1). Bottom plot contains two additional nodes at the left edge of the graph, with the topmost nodes having Rydberg density 1, and several nodes near the new nodes at Rydberg densities 0.5 and 0.25

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:

images of 96 total nodes in 4 different gfraphs sticeked together at their edges ("tails) to foarm a large graph

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

  1. Divide the graph into n subsets
  2. 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

four maximal independent sets with the on and off conditions repesented in blue and red, with labells showing the edges where are used to connect them into one larger graph

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!

four subset graphs in red and blue repsentating maximal independent sets stitched together into one larger graph with sparse connections

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

the team of hackers sleeping while sitting around the table at the hackathon

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.

Project source code

GraphFactory source code


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.

Alex Deters

Alex Deters

Alexander Deters is a third-year undergraduate at Yale, double majoring in intensive physics and mathematics. He conducts research in Robert Schoelkopf’s Lab, focusing on FPGA quantum control for superconducting circuits. As co-president of the Yale Undergraduate Quantum Computing society, Alexander is passionate about the intersection of theory and experiment. After graduation, he plans to pursue further education in experimental physics. In his free time, Alexander enjoys powerlifting, brewing coffee, and goat herding.

Sofia Fausone

Sofia Fausone

Sofia Fausone is a junior at Yale studying Physics and Mathematics + Philosophy. She conducts research in Prof. Howard’s quantitative biology lab and has experience in machine learning analysis and condensed matter physics. Sofia is interested in the intersection of mathematical and physical beauty, and using novel tools to answer theoretical questions. Her goal is to pursue theoretical physics and explore topics that challenge our current framework.

Wyatt Kremer

Wyatt Kremer

Wyatt Kremer is a third-year undergraduate Intensive Physics major pursuing an advanced language certificate in Middle Egyptian hieroglyphic at Yale University. His research interests include quantum many-body theory, quantum gravity, field theory, and quantum information technology. He is passionate about physics education and serves as a tutor for the Global Teaching Project, Yale Education Tutoring Initiative, and Yale Center for Language Study. Wyatt was born and raised in Minden, Nevada.

Benjamin McDonough

Benjamin McDonough

Ben McDonough (He/Him) is a Yale junior in the class of 2024, majoring in physics with a focus on quantum information and condensed matter theory. His research interests include quantum error correction, quantum error mitigation, circuit-QED platforms, and continuous-variable quantum computing. Ben is co-president of the Yale undergraduate Quantum Computing group (YuQC) and values the interdisciplinary nature of the quantum computing community. In his free time, he enjoys rock-climbing, language learning, and playing flute in the Yale DPops Orchestra.

Pranav Parakh

Pranav Parakh

Pranav Parakh is a third-year undergraduate at Yale majoring in Mathematics and Physics with a Computer Science certificate. He conducts research in quantum computing at Quantronics Lab under Prof. Michel Devoret, focusing on simulating superconducting circuits. Pranav is a project leader at the Yale Undergraduate Quantum Computing society and a member of the Yale Net Impact consulting group. He enjoys playing guitar and piano, and is also a member of the Yale Climbing Team.