Blog

Rectangle Packing and Quantum Algorithm Design

18
October
,
2021

Rectangle packing is the process of placing a given set of small rectangles inside a given large polygon, in such a way that no two small rectangles overlap. A related problem is finding the smallest rectangle that can contain all the small rectangles without overlap.

So for instance, going from these five rectangles on a surface:

To a compact packing arrangement of them:

Easy, right?

This problem has been the topic of significant academic research, perhaps because it's difficult, but perhaps also because it has numerous practical applications. What's the optimal packing of boxes in a UPS truck? How to best place functional blocks on an ASIC? What's the minimum box that can hold a certain set of items? Getting the right answer could be very valuable to a shipping company, or a chip design firm.

Now let's take a larger number of rectangles. Here's the result:

That's probably more difficult, and might take a human a good number of minutes to find this answer.

Now let's take even more rectangles:

How long would it take you to manually arrange hundreds of rectangles? And, if you do, is it the optimal solution? Are you wasting space? Could you fit in more rectangles?

Now let's add some constraints: let's say that rectangles are of different colors, and you don't want two rectangles of the same color to be adjacent. Or let's assume you really want certain rectangles to be close to each other while you don't care that much about others.

Such problems become really difficult, really fast. So difficult, that it quickly becomes obvious that it's much better to solve these problems using a computer than asking a human to solve it. The computer that can explore thousands upon thousands of options, run through sophisticated algorithms and calculations and come up with a good answer.

Quantum algorithm design has many similar features

When you have a quantum algorithm, you need to fit it into the number of available qubits. You need to decide which qubits to use for which block, how to best connect the output of one code block to the input of the next. You probably want to fit it into a certain set of constraints such as the minimum number of qubits or the smallest possible circuit depth. Or maybe the constraint is different: you have a certain size computer and you are trying to fit as many functional blocks into it as possible.

Just like rectangles, it quickly becomes obvious that a computer is best at this optimization. Yes, a human could do a good job with a few blocks and five qubits, a not-so-good job at 20 qubits and probably a bad job a 200 qubits.

This kind of thinking - let the designer focus on the 'what' and let a smart computer program figure out the 'how' - is core to our approach for quantum programming. We believe that as computers get more powerful, this automated approach of finding a good fit for the functional blocks in the quantum computer, will be the best and perhaps only approach to designing sophisticated circuits that work and deliver true value.

Rectangle packing is the process of placing a given set of small rectangles inside a given large polygon, in such a way that no two small rectangles overlap. A related problem is finding the smallest rectangle that can contain all the small rectangles without overlap.

So for instance, going from these five rectangles on a surface:

To a compact packing arrangement of them:

Easy, right?

This problem has been the topic of significant academic research, perhaps because it's difficult, but perhaps also because it has numerous practical applications. What's the optimal packing of boxes in a UPS truck? How to best place functional blocks on an ASIC? What's the minimum box that can hold a certain set of items? Getting the right answer could be very valuable to a shipping company, or a chip design firm.

Now let's take a larger number of rectangles. Here's the result:

That's probably more difficult, and might take a human a good number of minutes to find this answer.

Now let's take even more rectangles:

How long would it take you to manually arrange hundreds of rectangles? And, if you do, is it the optimal solution? Are you wasting space? Could you fit in more rectangles?

Now let's add some constraints: let's say that rectangles are of different colors, and you don't want two rectangles of the same color to be adjacent. Or let's assume you really want certain rectangles to be close to each other while you don't care that much about others.

Such problems become really difficult, really fast. So difficult, that it quickly becomes obvious that it's much better to solve these problems using a computer than asking a human to solve it. The computer that can explore thousands upon thousands of options, run through sophisticated algorithms and calculations and come up with a good answer.

Quantum algorithm design has many similar features

When you have a quantum algorithm, you need to fit it into the number of available qubits. You need to decide which qubits to use for which block, how to best connect the output of one code block to the input of the next. You probably want to fit it into a certain set of constraints such as the minimum number of qubits or the smallest possible circuit depth. Or maybe the constraint is different: you have a certain size computer and you are trying to fit as many functional blocks into it as possible.

Just like rectangles, it quickly becomes obvious that a computer is best at this optimization. Yes, a human could do a good job with a few blocks and five qubits, a not-so-good job at 20 qubits and probably a bad job a 200 qubits.

This kind of thinking - let the designer focus on the 'what' and let a smart computer program figure out the 'how' - is core to our approach for quantum programming. We believe that as computers get more powerful, this automated approach of finding a good fit for the functional blocks in the quantum computer, will be the best and perhaps only approach to designing sophisticated circuits that work and deliver true value.

See Also

No items found.

Start Creating Quantum Software Without Limits

contact us