Sechs Punkte, sechs Linien, eine einfache Regel: Jeder Punkt soll mit genau zwei anderen verbunden sein. Das lässt sich als geschlossener Ring zeichnen. Oder als zwei getrennte Dreiecke. Beide Bilder erfüllen die Regel. Trotzdem sehen ihre Nachbarschaften verschieden aus: Zwei direkt verbundene Punkte im Dreieck haben einen gemeinsamen Nachbarn. Im Sechserring haben sie keinen.
Dieser kleine Unterschied führt zu einer überraschenden Grenze spezieller Optimierungsmodelle. Wer nur einzelne Verbindungen und Paare von Verbindungen bewertet, kann damit nicht unter allen Bedingungen genau die gewünschten Netzstrukturen herausheben. Für eine bestimmte Klasse solcher Aufgaben zeigt eine Arbeit von D. Osorio und Kollegen zwei Wege: zusätzliche Ja-Nein-Variablen einführen oder erzeugte Kandidaten anschließend genauer prüfen. Die entscheidende Frage lautet damit schon vor der Wahl des Rechners: Wo soll die zusätzliche Arbeit stattfinden?
Ein Netz wird zum Schalterpult
Denken wir uns für jede mögliche Linie einen Schalter. Eingeschaltet bedeutet: Die Verbindung existiert. Ausgeschaltet: Sie fehlt. Bei sechs Punkten gibt es 15 mögliche Linien, also 15 solche Entscheidungen. Nicht jeder Schalterzustand erzeugt einen Ring oder zwei Dreiecke. Die meisten erzeugen irgendein anderes Netz.
Ein Optimierer braucht deshalb eine Bewertung. Unerwünschte Zustände erhalten Strafpunkte, erwünschte möglichst wenige. Für unsere erste Regel zählt man an jedem Punkt die eingeschalteten Verbindungen, zieht zwei ab und quadriert den Rest. Zwei Verbindungen kosten null, eine oder drei kosten jeweils einen Strafpunkt. Die Summe über alle Punkte bewertet das ganze Netz.
Hier kommt QUBO ins Spiel, kurz für quadratische unbeschränkte binäre Optimierung. „Binär“ beschreibt die beiden Schalterstellungen. „Quadratisch“ bedeutet, dass die Bewertung einzelne Schalter und Produkte aus jeweils zwei Schaltern enthalten darf. „Unbeschränkt“ heißt: Regeln stehen nicht als gesonderte Verbote neben der Rechnung. Sie werden in der Bewertung untergebracht. Das beschriebene Quadrat passt hinein: Beim Ausmultiplizieren entstehen höchstens paarweise Produkte.
Was ein gemeinsamer Nachbar zusätzlich verlangt
Nun verschärfen wir die Aufgabe. Entscheidend soll auch sein, wie viele gemeinsame Nachbarn zwei Punkte besitzen. Um einen gemeinsamen Nachbarn zu zählen, müssen zwei Linien gleichzeitig vorhanden sein: die Linie vom ersten Punkt zum Nachbarn und die vom zweiten Punkt dorthin. Rechnerisch ist das ein Produkt aus zwei Schaltern.
Die Zahl aller gemeinsamen Nachbarn besteht aus einer Summe solcher Produkte. Soll auch diese Zahl mit einem quadrierten Fehler bestraft werden, multiplizieren sich die Produkte untereinander. Dabei können vier verschiedene Schalter zusammenkommen. Das Eingabeformat erlaubt aber nur zwei auf einmal. Die vertraute Methode, eine Abweichung zu quadrieren, hat die Aufgabe aus dem QUBO-Format hinausgetragen.
Das ist zunächst ein Problem dieser Formulierung. Vielleicht gibt es eine andere, klügere Bewertung? Genau hier setzt der mathematische Beitrag an. Die Autoren untersuchen stark reguläre Graphen: Netze, in denen jeder Punkt gleich viele Verbindungen hat und die Zahl gemeinsamer Nachbarn sowohl für verbundene als auch für unverbundene Punktpaare jeweils festgelegt ist.
Ihr Satz betrifft eine präzise Forderung: Die besten Zustände einer einzigen QUBO sollen genau alle gesuchten Graphen in sämtlichen Beschriftungen sein. Außerhalb bestimmter Sonderfälle gelingt das mit den ursprünglichen Verbindungsschaltern allein nicht. Eine Bewertung, die alle Punktnamen gleich behandelt und nur paarweise Schalterprodukte nutzt, erfasst hier zu wenig Struktur. Auch eine zunächst unsymmetrisch gewählte Bewertung entkommt der Grenze nicht; der Beweis mittelt sie über die Umbenennungen der Punkte.
Zu den Ausnahmen gehören der Fünferring, vollständige Paarungen und deren Komplementgraphen. Beim Fünferring reicht die Regel „zwei Verbindungen pro Punkt“ bereits aus. Die Grenze hängt also an der verlangten Struktur und an der vollständigen Lösungsmenge. Sie verbietet weder das Finden einzelner Lösungen noch andere Optimierungsmodelle.
Mehr Schalter machen die Bewertung einfacher
Der erste Ausweg erinnert an eine Zwischenablage. Ein neuer Schalter merkt sich, ob zwei ursprüngliche Schalter gleichzeitig eingeschaltet sind. Statt ein Produkt immer wieder auszuschreiben, nutzt die Rechnung seinen gespeicherten Wert. Aus einer komplizierteren Wechselwirkung werden mehrere einfachere.
Natürlich darf die Zwischenablage nicht lügen. Die Dokumentation von D-Wave beschreibt dafür zusätzliche Strafausdrücke. Der Hilfsschalter muss null sein, sobald mindestens einer seiner beiden Eingangsschalter null ist. Nur wenn beide eins sind, muss auch er eins sein. Passend gewählte Strafgewichte sichern diese Beziehung gegenüber den übrigen Vorteilen in der Bewertung ab.
Ein konkretes Beispiel: Für zwei Eingänge x und y sowie den Hilfsschalter z liefert der Ausdruck xy − 2xz − 2yz + 3z genau dann null, wenn z das Produkt xy korrekt wiedergibt. Bei x = 1 und y = 0 ist z = 0 richtig und kostet null. Der falsche Wert z = 1 kostet einen Strafpunkt. Bei zwei eingeschalteten Eingängen kehren sich die erlaubten Werte entsprechend um. Alle Terme bleiben paarweise. Die Wahrheitstabelle dieser kleinen Baueinheit lässt sich vollständig prüfen; die Suche im großen zusammengesetzten Modell ist eine andere Aufgabe.
Die Rechnung wird dadurch formal einfacher, ihr Zustandsraum größer. Jeder weitere binäre Schalter verdoppelt die Zahl möglicher Belegungen vor Berücksichtigung der Regeln. Viele dieser zusätzlichen Belegungen sind unerwünscht und erhalten Strafpunkte. Der Optimierer muss trotzdem eine Landschaft durchsuchen, deren Form nun von diesen Strafen mitbestimmt wird.
In der untersuchten vollständigen Formulierung wächst der Variablenbedarf kubisch mit der Punktzahl; die ursprünglichen Verbindungsschalter wachsen quadratisch. Eine Verdopplung der Punktzahl bedeutet in diesen Größenordnungen ungefähr viermal so viele ursprüngliche Entscheidungen, aber achtmal so viele Hilfsvariablen. Das ist eine Skalierungsbetrachtung, keine Vorhersage der Laufzeit. Geschickte Festlegungen können das konkrete Modell verkleinern.
Oder weniger modellieren und genauer nachsehen
Der zweite Weg lässt zunächst mehr Kandidaten durch. Ein einfacheres QUBO erzeugt Netze mit der richtigen Verbindungszahl. Weitere Filter verkleinern die Auswahl. Abschließend zählt ein klassischer Prüfschritt die gemeinsamen Nachbarn nach und entscheidet, ob der Kandidat die vollständigen Regeln erfüllt.
Der Unterschied zwischen Finden und Prüfen ist wesentlich. Ein fertiges Netz lässt sich systematisch durchgehen. Alle möglichen Netze zu durchsuchen ist viel aufwendiger. Ein guter Filter kann Arbeit sparen, ein schwacher reicht viele falsche Treffer weiter. Im Manuskript sind die Filter deshalb ausdrücklich keine abschließenden Zertifikate.
Beide Wege verschieben den Aufwand: Die vollständige Formulierung steckt mehr Regeln in ein größeres Modell. Die Kandidatenroute hält das Modell schlanker und trägt zusätzliche Arbeit nach der Suche. Welche Aufteilung günstiger ist, hängt davon ab, wie gut Erzeugung und Filter zur gesuchten Struktur passen.
Auch die Rechenmaschine bleibt eine eigene Entscheidung. QUBO kann mit klassischen Verfahren bearbeitet werden; D-Wave beschreibt zudem hybride Solver, die Eingaben auf höherer Ebene akzeptieren. Die Versuche der Graphenarbeit verwenden simuliertes Annealing, also eine klassische Suchmethode. Für einen fairen Vergleich zählen deshalb Übersetzung, Variablenbedarf, Suche und abschließende Prüfung zusammen. Ein schnelles Ergebnis aus einem unvollständigen Modell ist erst dann eine Lösung, wenn es auch die ursprüngliche Frage beantwortet.
Quellen
- D. Osorio, P. Andagana, V. González, J. Czartowski und D. Goyeneche: Strongly Regular Graph Construction via Quadratic Binary Optimization, Preprint, Version 1. Die Metadatenseite nennt den 31. Juli 2026; die Kennung beginnt mit 2610. Diese bibliografische Abweichung bleibt offen.
- D-Wave: Reformulating a Problem, technische Dokumentation, insbesondere höhere Polynomgrade und Reduktion durch Substitution; abgerufen am 24. Oktober 2026.
Für diesen Artikel wurden KI-gestützte Recherche- und Editierwerkzeuge verwendet. Der Inhalt wurde redaktionell geprüft.
