Adiabatisches Quantencomputing > Adiabatisches Quantencomputing > Elisabeth Lobe, Tobias Stollenwerk > 5.5.2015DLR.de Folie 1 Elisabeth Lobe, Tobias Stollenwerk

Adiabatisches Quantencomputing

> Adiabatisches Quantencomputing > Elisabeth Lobe, Tobias Stollenwerk > 5.5.2015DLR.de • Folie 1

Elisabeth Lobe, Tobias StollenwerkSimulations- und SoftwaretechnikHPCN Workshop, Braunschweig

• Einführung adiabatischer Quantencomputer

• Netzwerkoptimierung und Cliquenproblem

• Demonstration am Simulator


Inhalt

Motivation: Quanten-Speed-Up

DLR.de • Folie 3 > Adiabatisches Quantencomputing > Elisabeth Lobe, Tobias Stollenwerk > 5.5.2015

• Diskrete Optimierung ist die Grundlage für viele Probleme:

® Packungen

® PartitionenNP-schwere Probleme!

® Zuordnungen

® Scheduling

• Vermutung: Quantencomputer löst diese schneller als klassische Rechner

Unterschiede zum klassischen Computer


Klassische Bits Quantenbits (Qubits)

• Elektrische Spannung • Zustand ist Superposition aus „0“ und „1“

• Messung verändert Zustand

® Messen „0“ mit Wahrscheinlichkeit

® Messen „1“ mit Wahrscheinlichkeit

1

0

• Kommerzieller Hersteller: D-Wave Systems Inc., Kanada

• Simulator- und Programmierschnittstelle „Quantum Apprentice“

• Nicht zu verwechseln mit konventionellem Quantencomputer


Was ist ein adiabatischer Quantencomputer?

Quelle: D-Wave Systems


Adiabatischer Quantencomputer löst diskrete Optimierungsprobleme

Zielfunktion:

𝐸 (𝑞1 ,… ,𝑞𝑛)=∑𝑖=1

𝑛

𝑔𝑖𝑞𝑖

𝑞𝑖={0 ,1 , f ü r Schalter ausf ü r Schalter an

𝑔𝑖∈ Gewichte

∀ 𝑖=1,…,𝑛Quelle: D-Wave Systems


Zielfunktion:

𝐸 (𝑞1 ,… ,𝑞𝑛)=∑𝑖=1

𝑛

𝑔𝑖𝑞𝑖+ ∑𝑖 , 𝑗=1𝑖> 𝑗

𝑛

𝑠𝑖 𝑗𝑞𝑖𝑞 𝑗

𝑞𝑖={0 ,1 , f ü r Schalter ausf ü r Schalter an

𝑔𝑖∈ Gewichte

∀ 𝑖 , 𝑗=1 ,…,𝑛

𝑠𝑖𝑗∈ Stärken der Kopplungen

Adiabatischer Quantencomputer löst QUBOs

Quelle: D-Wave Systems

Quadratic Unconstrained Binary Optimization


Funktionsweise des adiabatischen Quantencomputers

• Kodiere Zielfunktion in niedrigstem Energiezustand eines Quantensystems

Ene

rgie

Anfangssystem Zielsystem

Zeit

Energieniveaus

schnelle Änderung



• Hinreichend langsame Überführung in Zielsystem

Ene

rgie

Anfangssystem Zielsystem

Zeit

Energieniveaus

Langsame Änderung

Δ 𝐸 bestimmtLaufzeit

01

01

01

01 0

1

01

Alle Qubits in einem Zustandzwischen 0 und 1



Energieprogramm

0 1

0

10

1

Beste Lösung



Abbildung der Hardware im Simulator


• Einheitszelle aus 8 Qubits mit 2 Partitionen

• Insgesamt 4x4 Einheitszellen in Simulationssoftware

128 Qubits zur Zeit 8x8 Einheitszellen auf D-Wave-Chip 512 Qubits

• Gewichte und Stärken sind jeweils einstellbar

𝒔 𝒋𝒌

𝒈𝒊

Simulator Quantum Apprentice


• Darstellung im D-Wave-Simulator„Quantum Apprentice“

Einschränkungen durch Chipstruktur


• Nicht alle Qubits koppeln untereinander

• Lösung:

® Verbindung über andere Qubits Verteilen der Stärke über Strang

® Darstellung eines logischen Qubits durch mehrere echte Qubits Verteilen des Gewichts

• Beispiel für 6 Knoten:• Beispiel für 7 Knoten:

Darstellung vollständiger Graphen


Beispielgraph


-1

05 2

1

3-1

2

-41

-2 3

-1

-4

2

-2

-1

2

5-1

-1

2

-4

-3

-2 5

1

7

4

10

3

86 9

2 5

Beispielgraph


1

7

4

10

3

8

69

2

5

Beispiel: Cliquenproblem


• Finde größten vollständigen Teilgraph (Clique)

• Eigenschaften und Strukturen erkennen

• Anwendung: z.B. Facebook: Finde maximale Gruppe von Freunden

1

7

4

10

3

86 9

2 5

7

43

8

Cliquenproblem auf Quantencomputer


•als quadratisches 0/1-Minimierungsproblem formulieren:

- Maximale Knotenzahl

- Kanten des Graphs ohne Einschränkungen aktivierbar

- Alle anderen Kanten dürfen nie benutzt werden

→ Knotengewichte negativ, z.B. -1

→ Stärke 0

→ Hohe Strafe: Stärke +10



1

7

4

10

3

8

69

2

5

Komplementgraph


• Realisierung auf D-Wave-Hardware

→ Bei 10 Knoten: 1 logischer Knoten = 4 Qubits

→ Gewicht des logischen Knoten = -1= Summe über allen Gewichten und Stärken im Qubitstrang

→ Kopplung zwischen den Qubits ist wichtig → negative Stärken


-1

5 5 55

-7 -7-7



1

2 3 4 5

6 7 8 9

10


• nächstkleinere Cliquen finden: gefundene Kanten entfernen (nur solche, deren Knoten keinen gemeinsamen Nachbarn haben)

1

7

4

10

3

86 9

2 5


7

43

8

1

43

7

10

8

• Implementierung mit weniger Qubits möglich!

→ 15 Qubits


Nutzen der Lösung für Netzwerkoptimierung1

2 3 4 5

6 7 8 9

10

Netzwerkminimierung


-1

05 2

1

3-1

2

-41

-2 3

-1

-4

2

-2

-1

2

5-1

-1

2

-4

-3

-2 5

1

7

4

10

3

6 9

2 5

8

Ausblick


• Scheduling-Probleme für Satellitenaufgabenplanung lösen

• Partitionieren des Cliquen-Problems zum Lösen komplexerer Probleme in Kombination mit klassischen Rechnern

• Machine Learning, Pattern Matching

Vielen Dank für ihre Aufmerksamkeit!

DLR.de • Folie 27

Fragen?

Tobias StollenwerkElisabeth Lobe Simulations- und Softwaretechnik

Abt. Verteilte Systeme und Komponentensoftware

[email protected]

[email protected]

http://www.DLR.de/sc

> Adiabatisches Quantencomputing > Elisabeth Lobe, Tobias Stollenwerk > 5.5.2015

mailto:[email protected]

mailto:[email protected]



Documents

Adiabatisches Quantencomputing > Adiabatisches Quantencomputing > Elisabeth Lobe, Tobias Stollenwerk > 5.5.2015DLR.de Folie 1 Elisabeth Lobe, Tobias Stollenwerk