Rectangle Packing und Entwurf von Quantenalgorithmen

Beim Packen von Rechtecken geht es darum, eine gegebene Menge kleiner Rechtecke in einem gegebenen großen Polygon so zu platzieren, dass sich keine zwei kleinen Rechtecke überlappen. Ein verwandtes Problem besteht darin, das kleinste Rechteck zu finden, das alle kleinen Rechtecke ohne Überlappung enthalten kann.

Wenn wir zum Beispiel von diesen fünf Rechtecken auf einer Fläche ausgehen:

Zu einer kompakten Verpackungsanordnung von ihnen:

Einfach, nicht wahr?

Dieses Problem war Gegenstand umfangreicher akademischer Forschung, vielleicht weil es schwierig ist, vielleicht aber auch, weil es zahlreiche praktische Anwendungen hat. Wie packt man Kisten in einem UPS-LKW optimal? Wie platziert man Funktionsblöcke am besten auf einem ASIC? Welches ist die kleinste Kiste, die eine bestimmte Menge von Gegenständen aufnehmen kann? Die richtige Antwort könnte für ein Transportunternehmen oder eine Chipdesignfirma sehr wertvoll sein.

Nehmen wir nun eine größere Anzahl von Rechtecken. Hier ist das Ergebnis:

Das ist wahrscheinlich schwieriger, und ein Mensch könnte einige Minuten brauchen, um diese Antwort zu finden.

Jetzt nehmen wir noch mehr Rechtecke:

Wie lange würden Sie brauchen, um Hunderte von Rechtecken manuell anzuordnen? Und wenn Sie es tun, ist es dann die optimale Lösung? Vergeuden Sie Platz? Könnten Sie mehr Rechtecke anordnen?

Fügen wir nun einige Einschränkungen hinzu: Nehmen wir an, die Rechtecke haben unterschiedliche Farben, und Sie wollen nicht, dass zwei Rechtecke derselben Farbe nebeneinander liegen. Oder nehmen wir an, dass Sie wirklich wollen, dass bestimmte Rechtecke nahe beieinander liegen, während Sie sich um andere nicht so sehr kümmern.

Solche Probleme werden sehr schnell sehr schwierig. So schwierig, dass es schnell klar wird, dass es viel besser ist, diese Probleme mit einem Computer zu lösen, als einen Menschen damit zu beauftragen. Der Computer kann Tausende von Optionen untersuchen, ausgeklügelte Algorithmen und Berechnungen durchführen und eine gute Antwort finden.

Der Entwurf von Quantenalgorithmen weist viele ähnliche Merkmale auf

Wenn man einen Quantenalgorithmus hat, muss man ihn in die Anzahl der verfügbaren Qubits einpassen. Man muss entscheiden, welche Qubits für welchen Block verwendet werden sollen und wie man den Ausgang eines Codeblocks am besten mit dem Eingang des nächsten verbindet. Wahrscheinlich wollen Sie es in eine bestimmte Reihe von Beschränkungen einpassen, wie z. B. die Mindestanzahl von Qubits oder die kleinstmögliche Schaltungstiefe. Oder vielleicht ist die Einschränkung eine andere: Sie haben einen Computer einer bestimmten Größe und versuchen, so viele Funktionsblöcke wie möglich unterzubringen.

Genau wie bei den Rechtecken wird schnell klar, dass ein Computer bei dieser Optimierung am besten abschneidet. Ja, ein Mensch könnte mit ein paar Blöcken und fünf Qubits gute Arbeit leisten, mit 20 Qubits eine nicht so gute und mit 200 Qubits wahrscheinlich eine schlechte Arbeit.

Diese Art des Denkens - der Designer soll sich auf das "Was" konzentrieren und ein intelligentes Computerprogramm das "Wie" herausfinden lassen - ist der Kern unseres Ansatzes für die Quantenprogrammierung. Wir glauben, dass dieser automatisierte Ansatz, eine gute Passung für die Funktionsblöcke im Quantencomputer zu finden, mit immer leistungsfähigeren Computern der beste und vielleicht einzige Ansatz sein wird, um anspruchsvolle Schaltungen zu entwerfen, die funktionieren und einen echten Mehrwert liefern.