The Max-Cut problem (Advanced Track)

Motivation: We chose this problem to solve because as an undergraduate researcher designing and testing PCBs, I came across this dilemma of deciding the locations of components. We also decided not to go to fields like finance, chemistry, etc, to stand out and also solve problems people don't know much about. We used Quantinuum's TKET as well to explore the product. Problem Overview: The Max-Cut Problem Imagine you're in the middle of designing a Printed Circuit Board (PCB), and you've reached the crucial placement stage. Your job is to arrange the components in the most efficient way. This is where the Max-Cut problem comes into play.

Picture the PCB as a flat surface with two sides—let’s call them Side 1 and Side 2. The goal is to place the circuit elements (the "nodes") on either side of the board, but here's the catch: each component needs to be connected to others by wires (the "edges") These connections come with different wire lengths, and each wire consumes space. Some connections are stronger, meaning they need shorter, thicker wires to maintain the circuit's integrity, while others are weaker and can be placed further apart. The strength of each connection is represented by a weight attached to the edge. The goal is to place components on the two sides of the PCB in such a way that the most critical (heavier) connections are split between the two sides of the board, maximizing the efficiency of the layout.

You have to figure out how to split these nodes between Side 1 and Side 2. The more you split critical connections (high weight edges), the better your PCB layout will be, as fewer long wires will run across the board, and space will be used more effectively.

In this case, the Max-Cut problem is your guide: you want to find the best partition of the nodes (components) into two sets—Side A and Side B—so that the sum of the weights of the edges between the two sides is maximized. This results in a more efficient design with shorter wire lengths and a more compact PCB.

So, as you work through the layout, you’ll be solving the Max-Cut problem, trying to find the best balance between the different components, ensuring the connections with the highest weights are placed between the two sides of the board, leading to an optimized circuit design.

Built With

• python
• tket