Immer wie­der liest man, dass nur mit Quan­ten­com­pu­tern schwie­ri­ge Op­ti­mie­rungs­pro­ble­me ge­löst wer­den könn­ten. Als Bei­spiel wird oft das Traveling-Salesperson-​Problem ge­nannt, bei dem eine kür­zes­te Rund­rei­se in einem Gra­phen ge­sucht wird. In letz­ter Zeit hört man auch oft vom so­ge­nann­ten MaxCut-​Problem, bei dem ein Graph so in zwei Teile auf­ge­teilt wer­den soll, dass die Kan­ten zwi­schen den bei­den Tei­len ma­xi­ma­les Ge­wicht haben. Die stei­gen­de Po­pu­la­ri­tät des MaxCut-​Problems er­klärt sich da­durch, dass es sich ein­fach als ein „Qua­dra­ti­sches un­ein­ge­schränk­tes bi­nä­res Op­ti­mie­rungs­pro­blem“ (QUBO) mo­del­lie­ren lässt, das auf Quan­ten­com­pu­tern be­son­ders gut be­han­del­bar ist. Das liegt wie­der­um daran, dass man zur Lö­sung des MaxCut-​Problems „nur“ den Kno­ten des Gra­phen die Sei­ten links oder rechts zu­wei­sen muss, und diese Sei­ten über­set­zen sich di­rekt in die bei­den Zu­stän­de „0“ und „1“ eines Quan­ten­bits (Qubits).

Mit den am For­schungs­cam­pus MODAL ent­wi­ckel­ten Ver­fah­ren kön­nen QUBOs nun schnel­ler auf einem Smart­pho­ne ge­löst wer­den als auf dem neus­ten Quan­tenannealer und ein Raspberry-Pi löst Traveling-Salesperson-​Probleme schnel­ler als jeder ak­tu­el­le Quan­ten­com­pu­ter. Dank die­ser Al­go­rith­men be­nö­tigt unser QUBO-​Verfahren auf einem nor­ma­len PC nur 0,2 Se­kun­den, um eine Lö­sung von ver­gleich­ba­rer Qua­li­tät zu fin­den, wie sie ein Quan­ten­com­pu­ter be­rech­net. Nach zwei Tagen wird die best­mög­li­che Lö­sung über­haupt ge­fun­den und nach drei wei­te­ren Tagen auch ma­the­ma­tisch be­wie­sen, dass es keine bes­se­re Lö­sung gibt.

Sol­che Pro­ble­me tre­ten in ver­schie­de­nen Be­rei­chen in der In­for­ma­tik, der Phy­sik und den In­ge­nieur­wis­sen­schaf­ten auf:

• Ma­schi­nel­les Ler­nen: QUBO-​Probleme kön­nen ver­wen­det wer­den, um die Pa­ra­me­ter von ma­schi­nel­len Lern­mo­del­len zu op­ti­mie­ren.
• Fi­nanz­wis­sen­schaft: QUBO-​Probleme kön­nen ver­wen­det wer­den, um In­vest­ment­port­fo­li­os zu op­ti­mie­ren, z. B. zur Mi­ni­mie­rung von Ri­si­ken und zur Ma­xi­mie­rung von Er­trä­gen.
• Gra­phen­theo­rie: QUBO-​Probleme kön­nen ver­wen­det wer­den, um gra­phen­theo­re­ti­sche Pro­ble­me zu lösen, z. B. das Fin­den des ma­xi­ma­len Schnit­tes in einem Gra­phen.
• Lo­gis­tik: QUBO-​Probleme kön­nen ver­wen­det wer­den, um Trans­port­lo­gis­tik zu op­ti­mie­ren, z. B. um Lie­fer­zei­ten und Kos­ten zu mi­ni­mie­ren.
• Bild­er­ken­nung: QUBO-​Probleme kön­nen ver­wen­det wer­den, um die Er­ken­nung von Bil­dern zu op­ti­mie­ren, z. B. bei der Ge­sichts­er­ken­nung oder der Ob­jekt­er­ken­nung.
• En­er­gie­ma­nage­ment: QUBO-​Probleme kön­nen ver­wen­det wer­den, um den En­er­gie­ver­brauch zu op­ti­mie­ren, z. B. in in­tel­li­gen­ten Net­zen oder beim En­er­gie­ma­nage­ment von Ge­bäu­den.

Auf­grund sei­ner gro­ßen Be­deu­tung hat sich auch der For­schungs­cam­pus MODAL mit dem Thema QUBO be­fasst. Die Forschungscampus-​Mitglieder Da­ni­el Rehl­feldt, Thors­ten Koch und Yuji Shin­no haben einen neuen Al­go­rith­mus „Qubowl“ ent­wi­ckelt, der in Kürze in der in­ter­na­tio­na­len Fach­zeit­schrift „Mathematical Programming: Computation“ ver­öf­fent­licht wird.  Für die Im­ple­men­tie­rung wur­den die im Syn­Lab des For­schungs­cam­pus MODAL ent­wi­ckel­ten Frame­works SCIP https://sci­po­pt.org und UG https://ug.zib.de ver­wen­det. Die Ar­bei­ten er­folg­ten in Ko­ope­ra­ti­on mit der I²DAMO GmbH und dem as­so­zi­ier­ten Fach­ge­biet Soft­ware und Al­go­rith­men für die dis­kre­te Op­ti­mie­rung von Prof. Dr. Thors­ten Koch an der TU Ber­lin, sowie der School of Informatics and Data Science der Hi­ro­shi­ma University, dem Fu­ji­sa­wa Laboratory am Institute of Mathematics for Industry der Kyus­hu University und dem Departement of Mathematics der National University of Singapore.

Nach dem der­zei­ti­gen Stand der For­schung be­nö­tigt die be­weis­bar op­ti­ma­le Lö­sung von QUBO-​Problemen im schlech­tes­ten Fall eine ex­po­nen­ti­el­le Lauf­zeit, und es gibt keine Re­sul­ta­te, die zei­gen, dass sich daran durch den Ein­satz von Quan­ten­com­pu­tern etwas än­dern wird. Die bes­ten Ver­fah­ren wer­den in in­ter­na­tio­na­len Wett­be­wer­ben mit­ein­an­der ver­gli­chen. Die be­kann­ten Bench­marks von Prof. Dr. Hans Mit­tel­mann http://plato.asu.edu/ftp/qubo.html zei­gen, dass der vom For­schungs­cam­pus MODAL ent­wi­ckel­te QUBO Löser der­zeit (Stand März 2023) das schnells­te der ge­tes­te­ten Pro­gram­me beim Nonconvex QUBO-QPLIB Benchmark ist.