.svg)
Rectangle Packing and Quantum Algorithm Design
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.
About "The Qubit Guy's Podcast"
Hosted by The Qubit Guy (Yuval Boger, our Chief Marketing Officer), the podcast hosts thought leaders in quantum computing to discuss business and technical questions that impact the quantum computing ecosystem. Our guests provide interesting insights about quantum computer software and algorithm, quantum computer hardware, key applications for quantum computing, market studies of the quantum industry and more.
If you would like to suggest a guest for the podcast, please contact us.
