import%20marimo%0A%0A__generated_with%20%3D%20%220.23.16%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%20%20%23%20wird%20nur%20ben%C3%B6tigt%2C%20wenn%20Sie%20mit%20marimo%20Notebooks%20arbeiten%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Graphf%C3%A4rbung%20mit%20QAOA%20und%20Qiskit%0A%0A%20%20%20%20Eine%20Landkarte%20soll%20so%20eingef%C3%A4rbt%20werden%2C%20dass%20**benachbarte%20L%C3%A4nder%20verschiedene%20Farben**%20haben%2C%20und%20zwar%20mit%20m%C3%B6glichst%20wenigen%20Farben.%0A%20%20%20%20Das%20ist%20das%20**Graphf%C3%A4rbungsproblem**%3A%20Knoten%20eines%20Graphen%20sollen%20so%20mit%20Farben%20versehen%20werden%2C%0A%20%20%20%20dass%20die%20beiden%20Enden%20jeder%20Kante%20unterschiedliche%20Farben%20tragen.%0A%20%20%20%20Dasselbe%20Problem%20steckt%20hinter%20vielen%20praktischen%20Aufgaben%3A%0A%0A%20%20%20%20*%20**Stundenplan%3A**%20Knoten%20%3D%20Pr%C3%BCfungen%2C%20Kante%20%3D%20%E2%80%9Egemeinsame%20Teilnehmer%22%2C%20Farbe%20%3D%20Zeitslot.%0A%20%20%20%20*%20**Frequenzzuweisung%3A**%20Knoten%20%3D%20Funkmasten%2C%20Kante%20%3D%20%E2%80%9Est%C3%B6ren%20sich%22%2C%20Farbe%20%3D%20Frequenz.%0A%20%20%20%20*%20**Registerzuteilung**%20in%20Compilern%2C%20Sudoku%20und%20vieles%20mehr.%0A%0A%20%20%20%20F%C3%BCr%20drei%20oder%20mehr%20Farben%20ist%20die%20Frage%20%E2%80%9EL%C3%A4sst%20sich%20der%20Graph%20mit%20%24k%24%20Farben%20f%C3%A4rben%3F%22%20**NP-vollst%C3%A4ndig**.%0A%0A%20%20%20%20In%20diesem%20Notebook%20l%C3%B6sen%20Sie%20sie%20mit%20dem%20**Quantum%20Approximate%20Optimization%20Algorithm%20(QAOA)**%2C%20implementiert%20mit%20**Qiskit**%3A%0A%0A%20%20%20%201.%20das%20Problem%20als%20**QUBO**%20formulieren%2C%0A%20%20%20%202.%20daraus%20einen%20**Ising-Hamilton-Operator**%20(%60SparsePauliOp%60)%20bauen%2C%0A%20%20%20%203.%20den%20**QAOA-Schaltkreis**%20aus%20Gattern%20zusammensetzen%2C%0A%20%20%20%204.%20die%20Parameter%20**klassisch%20optimieren**%20(mit%20%60scipy%60)%20und%20das%20Ergebnis%20auswerten.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20So%20arbeiten%20Sie%20mit%20diesem%20Notebook%0A%20%20%20%20%20%20%20%20type%3A%20info%0A%0A%20%20%20%20Stellen%20mit%20**%E2%9C%8D%EF%B8%8F%20Aufgabe**%20sind%20L%C3%BCcken%2C%20die%20Sie%20selbst%20f%C3%BCllen%3A%20teils%20mit%20Mathematik%20(auf%20Papier)%2C%20teils%20mit%20Code.%0A%20%20%20%20Im%20Code%20markieren%20die%20Kommentare%20%60%23%20%3E%3E%3E%20IHR%20CODE%60%20und%20%60%23%20%3C%3C%3C%60%20die%20Stelle%2C%20an%20der%20Sie%20arbeiten.%0A%20%20%20%20L%C3%B6schen%20Sie%20dort%20die%20Zeile%20%60raise%20NotImplementedError%60%20und%20ersetzen%20Sie%20sie%20durch%20Ihre%20L%C3%B6sung.%0A%0A%20%20%20%20Nach%20jeder%20Aufgabe%20pr%C3%BCft%20ein%20**Selbsttest**%20Ihre%20L%C3%B6sung%20(%E2%9C%85%20%2F%20%E2%9D%8C%20%2F%20%E2%8F%B3).%0A%20%20%20%20Sp%C3%A4tere%20Abschnitte%20starten%20erst%2C%20wenn%20die%20Tests%20davor%20bestanden%20sind.%0A%20%20%20%20Die%20aufklappbaren%20Hinweise%20helfen%2C%20wenn%20Sie%20nicht%20weiterkommen.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20itertools%0A%20%20%20%20import%20platform%0A%0A%20%20%20%20import%20matplotlib%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20qiskit%0A%20%20%20%20import%20scipy%0A%20%20%20%20from%20qiskit%20import%20QuantumCircuit%0A%20%20%20%20from%20qiskit.circuit%20import%20Parameter%2C%20ParameterVector%0A%20%20%20%20from%20qiskit.circuit.library%20import%20PauliEvolutionGate%0A%20%20%20%20from%20qiskit.quantum_info%20import%20SparsePauliOp%2C%20Statevector%0A%20%20%20%20from%20scipy.optimize%20import%20minimize%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Parameter%2C%0A%20%20%20%20%20%20%20%20ParameterVector%2C%0A%20%20%20%20%20%20%20%20PauliEvolutionGate%2C%0A%20%20%20%20%20%20%20%20QuantumCircuit%2C%0A%20%20%20%20%20%20%20%20SparsePauliOp%2C%0A%20%20%20%20%20%20%20%20Statevector%2C%0A%20%20%20%20%20%20%20%20itertools%2C%0A%20%20%20%20%20%20%20%20matplotlib%2C%0A%20%20%20%20%20%20%20%20minimize%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20platform%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20qiskit%2C%0A%20%20%20%20%20%20%20%20scipy%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(matplotlib%2C%20mo%2C%20platform%2C%20qiskit%2C%20scipy)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20Pr%C3%BCfen%20Sie%2C%20dass%20Ihre%20installierten%20Versionen%20nicht%20zu%20weit%20von%20diesen%20hier%20abweichen%3A%0A%0A%20%20%20%20%7C%20Paket%20%7C%20Version%20%7C%0A%20%20%20%20%7C---%7C---%7C%0A%20%20%20%20%7C%20Python%20%7C%20%7Bplatform.python_version()%7D%20%7C%0A%20%20%20%20%7C%20qiskit%20%7C%20%7Bqiskit.__version__%7D%20%7C%0A%20%20%20%20%7C%20scipy%20%7C%20%7Bscipy.__version__%7D%20%7C%0A%20%20%20%20%7C%20matplotlib%20%7C%20%7Bmatplotlib.__version__%7D%20%7C%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20def%20run_check(test)%3A%0A%20%20%20%20%20%20%20%20%22%22%22F%C3%BChrt%20einen%20Selbsttest%20aus%20und%20gibt%20(bestanden%2C%20Anzeige)%20zur%C3%BCck.%22%22%22%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20test()%0A%20%20%20%20%20%20%20%20except%20NotImplementedError%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%2C%20mo.callout(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22%E2%8F%B3%20**Noch%20nicht%20bearbeitet.**%20F%C3%BCllen%20Sie%20die%20L%C3%BCcke%20oben%20und%20f%C3%BChren%20Sie%20die%20Zelle%20aus.%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20kind%3D%22neutral%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20except%20AssertionError%20as%20e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%2C%20mo.callout(mo.md(f%22%E2%9D%8C%20**Test%20nicht%20bestanden%3A**%20%7Be%7D%22)%2C%20kind%3D%22danger%22)%0A%20%20%20%20%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%2C%20mo.callout(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.md(f%22%E2%9D%8C%20**Fehler%20in%20Ihrem%20Code%3A**%20%60%7Btype(e).__name__%7D%3A%20%7Be%7D%60%22)%2C%20kind%3D%22danger%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20return%20True%2C%20mo.callout(mo.md(%22%E2%9C%85%20**Alle%20Tests%20bestanden.**%22)%2C%20kind%3D%22success%22)%0A%0A%20%20%20%20return%20(run_check%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%201%3A%20Das%20Problem%0A%0A%20%20%20%20Gegeben%20ist%20ein%20Graph%20%24G%20%3D%20(V%2C%20E)%24%20mit%20%24n%24%20Knoten%20und%20eine%20Anzahl%20%24k%24%20von%20Farben.%0A%20%20%20%20Eine%20**g%C3%BCltige%20F%C3%A4rbung**%20weist%20jedem%20Knoten%20genau%20eine%20Farbe%20zu%2C%20sodass%20f%C3%BCr%20jede%20Kante%20%24(u%2Cv)%20%5Cin%20E%24%20die%20Farben%20von%20%24u%24%20und%20%24v%24%20verschieden%20sind.%0A%0A%20%20%20%20Unsere%20Instanz%20ist%20ein%20kleiner%20Graph%20mit%20vier%20Knoten%20und%20f%C3%BCnf%20Kanten%20(zwei%20%E2%80%9EDreiecke%22%2C%20die%20sich%20eine%20Kante%20teilen).%0A%20%20%20%20Sie%20ist%20mit%20%24k%20%3D%203%24%20Farben%20f%C3%A4rbbar%2C%20mit%20%24k%20%3D%202%24%20aber%20nicht.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20n_nodes%20%3D%204%0A%20%20%20%20edges%20%3D%20%5B(0%2C%201)%2C%20(0%2C%202)%2C%20(1%2C%202)%2C%20(1%2C%203)%2C%20(2%2C%203)%5D%0A%20%20%20%20positions%20%3D%20%7B0%3A%20(0%2C%200.5)%2C%201%3A%20(1%2C%201)%2C%202%3A%20(1%2C%200)%2C%203%3A%20(2%2C%200.5)%7D%20%20%23%20nur%20zum%20Zeichnen%0A%0A%20%20%20%20n_colors%20%3D%203%20%20%23%20Anzahl%20der%20Farben%20k%0A%20%20%20%20return%20edges%2C%20n_colors%2C%20n_nodes%2C%20positions%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(edges%2C%20plt%2C%20positions)%3A%0A%20%20%20%20PALETTE%20%3D%20%5B%22tab%3Ared%22%2C%20%22tab%3Ablue%22%2C%20%22tab%3Agreen%22%2C%20%22gold%22%2C%20%22tab%3Apurple%22%5D%0A%0A%20%20%20%20def%20plot_graph(colors%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Zeichnet%20den%20Graphen.%20colors%5Bv%5D%20ist%20die%20Farbe%20von%20Knoten%20v%20(None%20%3D%20ungef%C3%A4rbt).%0A%20%20%20%20%20%20%20%20Kanten%20mit%20gleichfarbigen%20Enden%20werden%20rot%20gestrichelt%20gezeichnet.%22%22%22%0A%20%20%20%20%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(4.2%2C%202.6))%0A%20%20%20%20%20%20%20%20_ax.axis(%22off%22)%0A%20%20%20%20%20%20%20%20for%20_u%2C%20_v%20in%20edges%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_bad%20%3D%20colors%20is%20not%20None%20and%20colors%5B_u%5D%20is%20not%20None%20and%20colors%5B_u%5D%20%3D%3D%20colors%5B_v%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(*zip(positions%5B_u%5D%2C%20positions%5B_v%5D)%2C%20color%3D%22red%22%20if%20_bad%20else%20%22k%22%2C%20lw%3D3%20if%20_bad%20else%201.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ls%3D%22--%22%20if%20_bad%20else%20%22-%22%2C%20zorder%3D0)%0A%20%20%20%20%20%20%20%20for%20_v%2C%20(_x%2C%20_y)%20in%20positions.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20None%20if%20colors%20is%20None%20else%20colors%5B_v%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%5B_x%5D%2C%20%5B_y%5D%2C%20s%3D1300%2C%20color%3D%22white%22%20if%20_c%20is%20None%20else%20PALETTE%5B_c%5D%2C%20edgecolor%3D%22k%22%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(_x%2C%20_y%2C%20str(_v)%2C%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20size%3D14%2C%20zorder%3D2)%0A%20%20%20%20%20%20%20%20_ax.set_xlim(-0.4%2C%202.4)%0A%20%20%20%20%20%20%20%20_ax.set_ylim(-0.4%2C%201.4)%0A%20%20%20%20%20%20%20%20plt.close(_fig)%0A%20%20%20%20%20%20%20%20return%20_fig%0A%0A%20%20%20%20plot_graph()%0A%20%20%20%20return%20(plot_graph%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Klassische%20Referenz%3A%20Brute%20Force%0A%0A%20%20%20%20F%C3%BCr%20diese%20kleine%20Instanz%20k%C3%B6nnen%20wir%20alle%20%24k%5En%24%20F%C3%A4rbungen%20einfach%20durchprobieren.%0A%20%20%20%20Das%20dient%20sp%C3%A4ter%20als%20Vergleich%20f%C3%BCr%20QAOA.%20Bei%20gro%C3%9Fen%20Graphen%20ist%20das%20nat%C3%BCrlich%20nicht%20mehr%20m%C3%B6glich.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(edges%2C%20itertools%2C%20n_colors%2C%20n_nodes)%3A%0A%20%20%20%20proper_colorings%20%3D%20%5B%0A%20%20%20%20%20%20%20%20c%0A%20%20%20%20%20%20%20%20for%20c%20in%20itertools.product(range(n_colors)%2C%20repeat%3Dn_nodes)%0A%20%20%20%20%20%20%20%20if%20all(c%5Bu%5D%20!%3D%20c%5Bv%5D%20for%20u%2C%20v%20in%20edges)%0A%20%20%20%20%5D%0A%20%20%20%20return%20(proper_colorings%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20n_colors%2C%20n_nodes%2C%20plot_graph%2C%20proper_colorings)%3A%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Von%20%7Bn_colors**n_nodes%7D%20m%C3%B6glichen%20F%C3%A4rbungen%20sind%20**%7Blen(proper_colorings)%7D**%20g%C3%BCltig.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20Eine%20davon%20(die%20Farben%20sind%20rot%2Fblau%2Fgr%C3%BCn%2Fgelb%20nummeriert)%3A%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20proper_colorings%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20%22%20Der%20Graph%20ist%20mit%20dieser%20Farbenzahl%20nicht%20f%C3%A4rbbar.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20plot_graph(proper_colorings%5B0%5D)%20if%20proper_colorings%20else%20mo.md(%22%22)%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%202%3A%20Wie%20funktioniert%20QAOA%3F%0A%0A%20%20%20%20Bevor%20wir%20das%20Problem%20aufbereiten%2C%20lernen%20Sie%20den%20Algorithmus%20kennen.%0A%20%20%20%20Graphf%C3%A4rbung%20ist%20nur%20das%20Beispiel%2C%20QAOA%20funktioniert%20f%C3%BCr%20jedes%20Problem%20in%20QUBO-%2FIsing-Form.%0A%20%20%20%20(Wenn%20auch%20f%C3%BCr%20manche%20Instanzen%20besser%20als%20f%C3%BCr%20andere.)%0A%0A%20%20%20%20%23%23%202.1%20Optimierung%20als%20Grundzustandsproblem%0A%0A%20%20%20%20Wir%20haben%20%24N%24%20bin%C3%A4re%20Variablen%20%24x%20%5Cin%20%5C%7B0%2C1%5C%7D%5EN%24%20und%20eine%20Kostenfunktion%20%24E(x)%24%2C%20die%20wir%20**minimieren**%20m%C3%B6chten.%0A%20%20%20%20Jedem%20Bitstring%20%24x%24%20ordnen%20wir%20einen%20Basiszustand%20%24%7Cx%5Crangle%24%20von%20%24N%24%20Qubits%20zu%20und%20definieren%20den%20**Problem-Hamilton-Operator**%0A%0A%20%20%20%20%24%24%0A%20%20%20%20H_C%20%3D%20%5Csum_%7Bx%20%5Cin%20%5C%7B0%2C1%5C%7D%5EN%7D%20E(x)%5C%2C%20%7Cx%5Crangle%5Clangle%20x%7C%20.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%24H_C%24%20ist%20diagonal%2C%20seine%20Eigenwerte%20sind%20genau%20die%20Kosten%20%24E(x)%24.%20Der%20Zustand%20mit%20dem%20**niedrigsten%20Eigenwert**%0A%20%20%20%20(der%20Grundzustand)%20ist%20die%20**optimale%20L%C3%B6sung**.%0A%0A%20%20%20%20Ist%20%24E%24%20ein%20Polynom%202.%20Grades%20in%20den%20%24x_u%24%20(QUBO)%2C%20l%C3%A4sst%20sich%20%24H_C%24%20aus%20Pauli-%24Z%24-Operatoren%20aufbauen.%0A%20%20%20%20Wegen%20%24Z%7Cx%5Crangle%20%3D%20(-1)%5Ex%20%7Cx%5Crangle%24%20gilt%20%24x_u%20%3D%20%5Cfrac%7B1%20-%20Z_u%7D%7B2%7D%24%2C%20das%20ergibt%20einen%20**Ising-Hamilton-Operator**%0A%20%20%20%20(Aufgabe%20in%20Teil%204)%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20H_C%20%3D%20%5Csum_u%20h_u%20Z_u%20%2B%20%5Csum_%7Bu%3Cv%7D%20J_%7Buv%7D%20Z_u%20Z_v%20%2B%20%5Ctext%7Bconst.%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%202.2%20Die%20Idee%20von%20QAOA%0A%0A%20%20%20%20Den%20Grundzustand%20von%20%24H_C%24%20kennen%20wir%20nicht%2C%20aber%20wir%20k%C3%B6nnen%20Zust%C3%A4nde%20**vorbereiten%20und%20messen**.%0A%20%20%20%20QAOA%20bereitet%20mit%20**%24p%24%20Schichten**%20einen%20Zustand%20vor%2C%20der%20von%20%242p%24%20reellen%20Parametern%0A%20%20%20%20%24%5Cboldsymbol%7B%5Cgamma%7D%20%3D%20(%5Cgamma_1%2C%5Cdots%2C%5Cgamma_p)%24%20und%20%24%5Cboldsymbol%7B%5Cbeta%7D%20%3D%20(%5Cbeta_1%2C%5Cdots%2C%5Cbeta_p)%24%20abh%C3%A4ngt%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%7C%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D%5Crangle%0A%20%20%20%20%3D%20%5Cunderbrace%7Be%5E%7B-i%5Cbeta_p%20H_M%7D%20e%5E%7B-i%5Cgamma_p%20H_C%7D%7D_%7B%5Ctext%7BSchicht%20%7D%20p%7D%20%5Ccdots%0A%20%20%20%20%20%20%5Cunderbrace%7Be%5E%7B-i%5Cbeta_1%20H_M%7D%20e%5E%7B-i%5Cgamma_1%20H_C%7D%7D_%7B%5Ctext%7BSchicht%20%7D%201%7D%20%5C%2C%20%7C%2B%5Crangle%5E%7B%5Cotimes%20N%7D%2C%0A%20%20%20%20%5Cqquad%20H_M%20%3D%20%5Csum_%7Bu%7D%20X_u%20.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20*%20**Startzustand**%20%24%7C%2B%5Crangle%5E%7B%5Cotimes%20N%7D%24%3A%20gleichm%C3%A4%C3%9Fige%20Superposition%20aller%20Bitstrings%20(ein%20Hadamard-Gatter%20pro%20Qubit).%0A%20%20%20%20*%20**Kostenschicht**%20%24e%5E%7B-i%5Cgamma%20H_C%7D%24%3A%20Weil%20%24H_C%24%20diagonal%20ist%2C%20bekommt%20jeder%20Basiszustand%20%24%7Cx%5Crangle%24%20nur%20eine%20Phase%20%24e%5E%7B-i%5Cgamma%20E(x)%7D%24.%0A%20%20%20%20%20%20Die%20Phase%20h%C3%A4ngt%20von%20den%20Kosten%20ab.%20Das%20allein%20%C3%A4ndert%20noch%20keine%20Messwahrscheinlichkeiten.%0A%20%20%20%20*%20**Mixer**%20%24e%5E%7B-i%5Cbeta%20H_M%7D%24%3A%20dreht%20jedes%20Qubit%20um%20die%20%24x%24-Achse%20und%20vermischt%20die%20Basiszust%C3%A4nde.%0A%20%20%20%20%20%20Erst%20dadurch%20werden%20aus%20Phasenunterschieden%20*Interferenz*%3A%20Zust%C3%A4nde%20mit%20niedrigen%20Kosten%20werden%20verst%C3%A4rkt.%0A%0A%20%20%20%20%23%23%202.3%20Der%20hybride%20Optimierungskreislauf%0A%0A%20%20%20%20Welche%20Parameter%20sind%20gut%3F%20Das%20bestimmt%20ein%20**klassischer%20Optimierer**%3A%0A%0A%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%E2%94%8C%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%90%0A%20%20%20%20%20%20%20%20%E2%94%82%20%20Parameter%20(%CE%B3%2C%20%CE%B2)%20%20%E2%94%80%E2%94%80%E2%96%BA%20%20Quantenschaltkreis%20%20%20%20%E2%94%82%0A%20%20%20%20%20%20%20%20%E2%94%82%20%20%20%20%20%20%20%E2%96%B2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E2%94%82%20Messung%20%20%20%20%20%20%20%E2%94%82%0A%20%20%20%20%20%20%20%20%E2%94%82%20%20%20%20%20%20%20%E2%94%82%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E2%96%BC%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E2%94%82%0A%20%20%20%20%20%20%20%20%E2%94%82%20%20klassischer%20Optimierer%20%E2%97%84%E2%94%80%E2%94%80%20%E2%9F%A8H_C%E2%9F%A9%20%3D%20%CE%A3%20p(x)E(x)%E2%94%82%0A%20%20%20%20%20%20%20%20%E2%94%94%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%98%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%201.%20Der%20Schaltkreis%20liefert%20die%20Wahrscheinlichkeiten%20%24p(x)%24%20der%20Bitstrings.%0A%20%20%20%202.%20Daraus%20ergibt%20sich%20der%20**Erwartungswert%20der%20Kosten**%20%24%5Clangle%20H_C%20%5Crangle%20%3D%20%5Csum_x%20p(x)%5C%2CE(x)%24.%0A%20%20%20%203.%20Ein%20klassischer%20Optimierer%20%C3%A4ndert%20%24(%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D)%24%2C%20sodass%20%24%5Clangle%20H_C%20%5Crangle%24%20sinkt.%20Wir%20nutzen%20%60COBYLA%60%20aus%20%60scipy%60%2C%20ein%20gradientenfreies%20Verfahren.%0A%20%20%20%204.%20Am%20Ende%20wird%20der%20Schaltkreis%20gemessen.%20Der%20beste%20gefundene%20Bitstring%20ist%20die%20L%C3%B6sung.%0A%0A%20%20%20%20Auf%20echter%20Hardware%20m%C3%BCsste%20%24%5Clangle%20H_C%20%5Crangle%24%20aus%20Messungen%20gesch%C3%A4tzt%20werden.%20Im%20Simulator%20rechnen%20wir%20direkt%20mit%20den%20exakten%20Wahrscheinlichkeiten%20(%60Statevector%60).%0A%0A%20%20%20%20%23%23%202.4%20Der%20Zusammenhang%20mit%20Quantum%20Annealing%0A%0A%20%20%20%20QAOA%20ist%20eine%20**diskretisierte%20Variante%20des%20adiabatischen%20Quantenrechnens**%20(wie%20bei%20einem%20D-Wave-Annealer)%3A%0A%20%20%20%20Dort%20wird%20langsam%20von%20%24H_M%24%20zu%20%24H_C%24%20%C3%BCbergeblendet%2C%20und%20das%20System%20bleibt%20dabei%20im%20Grundzustand.%0A%20%20%20%20QAOA%20ersetzt%20die%20kontinuierliche%20Entwicklung%20durch%20%24p%24%20abwechselnde%20Schritte%2C%20deren%20%E2%80%9EL%C3%A4nge%22%20(%24%5Cgamma_l%24%2C%20%24%5Cbeta_l%24)%20der%20Optimierer%20w%C3%A4hlt.%0A%20%20%20%20F%C3%BCr%20%24p%20%5Cto%20%5Cinfty%24%20l%C3%A4sst%20sich%20die%20adiabatische%20Evolution%20beliebig%20genau%20nachbilden%2C%20f%C3%BCr%20kleine%20%24p%24%20ist%20QAOA%20ein%20*N%C3%A4herungsverfahren*%0A%20%20%20%20mit%20nur%20%242p%24%20Parametern%2C%20und%20kurze%20Schaltkreise%20sind%20genau%20das%2C%20was%20heutige%20Quantencomputer%20brauchen.%0A%0A%20%20%20%20%23%23%202.5%20Qiskit-Besonderheiten%0A%0A%20%20%20%20*%20**Gatter%3A**%20In%20Qiskit%20gilt%20%24R_Z(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20Z%2F2%7D%24%2C%20%24R_%7BZZ%7D(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%5C%2C%20Z%5Cotimes%20Z%2F2%7D%24%20und%20%24R_X(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20X%2F2%7D%24%0A%20%20%20%20%20%20(Methoden%20%60qc.rz%60%2C%20%60qc.rzz%60%2C%20%60qc.rx%60).%0A%20%20%20%20*%20**Operatoren%3A**%20Der%20Hamilton-Operator%20wird%20als%20%60SparsePauliOp%60%20dargestellt%2C%20also%20als%20Summe%20gewichteter%20Pauli-Strings.%0A%20%20%20%20*%20**Bit-Reihenfolge%20(little-endian)%3A**%20Qubit%200%20ist%20das%20*niedrigstwertige*%20Bit.%20In%20Bitstring-Beschriftungen%20(z.%20B.%20%60'0110'%60)%20steht%20Qubit%200%20**ganz%20rechts**%2C%0A%20%20%20%20%20%20und%20im%20Zustandsvektor%20geh%C3%B6rt%20Qubit%20%24u%24%20zum%20Bit%20%242%5Eu%24%20des%20Index.%20Wir%20rechnen%20in%20diesem%20Notebook%20mit%20Index%20und%20Bit-Arrays%2C%0A%20%20%20%20%20%20damit%20nichts%20durcheinanderkommt.%20Pauli-Strings%20in%20%60SparsePauliOp.from_list(...)%60%20sind%20ebenfalls%20rechts-nach-links%20geschrieben.%0A%20%20%20%20%20%20Es%20ist%20daher%20bequemer%2C%20mit%20%60from_sparse_list%60%20und%20expliziten%20Qubit-Indizes%20zu%20arbeiten.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%203%3A%20Das%20Problem%20als%20QUBO%20formulieren%0A%0A%20%20%20%20Wir%20brauchen%20bin%C3%A4re%20Variablen.%20Bei%20%24n%24%20Knoten%20%24v%20%3D%200..n-1%24%20und%20%24k%24%20Farben%20%24c%20%3D%200..k-1%24%20definieren%20wir%0A%0A%20%20%20%20%24%24%0A%20%20%20%20x_%7Bvc%7D%20%3D%20%5Cbegin%7Bcases%7D%0A%20%20%20%20%20%20%20%20%20%20%20%201%20%26%20%5Ctext%7Bwenn%20Knoten%20%7D%20v%20%5Ctext%7B%20die%20Farbe%20%7D%20c%20%5Ctext%7B%20bekommt%7D%20%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%200%20%26%20%5Ctext%7Bsonst%7D%0A%20%20%20%20%20%20%20%20%5Cend%7Bcases%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Diese%20Kodierung%20hei%C3%9Ft%20%5B*One-Hot-Kodierung*%5D(https%3A%2F%2Fde.wikipedia.org%2Fwiki%2F1-aus-n-Code)%3A%20Pro%20Knoten%20soll%20genau%20ein%20Bit%20%241%24%20sein.%0A%20%20%20%20**Jede%20Variable%20%24x_%7Bvc%7D%24%20ist%20ein%20Qubit.**%0A%0A%20%20%20%20Eine%20g%C3%BCltige%20F%C3%A4rbung%20erf%C3%BCllt%0A%20%20%20%201.%20**jeder%20Knoten%20hat%20genau%20eine%20Farbe%3A**%20%24%5Csum_c%20x_%7Bvc%7D%20%3D%201%24%20f%C3%BCr%20alle%20%24v%24%2C%0A%20%20%20%202.%20**keine%20Kante%20hat%20gleichfarbige%20Enden%3A**%20f%C3%BCr%20jede%20Kante%20%24(u%2Cv)%24%20und%20jede%20Farbe%20%24c%24%20ist%20nicht%20gleichzeitig%20%24x_%7Buc%7D%20%3D%20x_%7Bvc%7D%20%3D%201%24.%0A%0A%20%20%20%20Es%20gibt%20kein%20%E2%80%9EMehr%20oder%20weniger%20gut%22%2C%20jede%20g%C3%BCltige%20F%C3%A4rbung%20ist%20gleich%20gut.%20Wir%20suchen%20also%20eine%20Belegung%20mit%20Kosten%20%240%24%2C%20und%20jede%20Verletzung%20soll%20Kosten%20%24%3E%200%24%20verursachen.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20q_bits%20%3D%20mo.ui.number(start%3D0%2C%20stop%3D10000%2C%20value%3D0%2C%20label%3D%22Qubits%20f%C3%BCr%20unsere%20Instanz%20%3D%22)%0A%20%20%20%20q_big%20%3D%20mo.ui.number(start%3D0%2C%20stop%3D10000%2C%20value%3D0%2C%20label%3D%22Qubits%20f%C3%BCr%20n%20%3D%2020%20Knoten%2C%20k%20%3D%204%20Farben%20%3D%22)%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%3A%20Verst%C3%A4ndnisfragen%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%201.%20Wie%20viele%20Qubits%20braucht%20unsere%20Instanz%20(%24n%20%3D%204%24%20Knoten%2C%20%24k%20%3D%203%24%20Farben)%3F%0A%20%20%20%202.%20Wie%20viele%20Qubits%20br%C3%A4uchte%20ein%20Graph%20mit%2020%20Knoten%2C%20den%20man%20mit%204%20Farben%20f%C3%A4rben%20m%C3%B6chte%3F%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20q_bits%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20q_big%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%20q_big%2C%20q_bits%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20n_colors%2C%20n_nodes%2C%20q_big%2C%20q_bits)%3A%0A%20%20%20%20_fb%20%3D%20lambda%20ok%3A%20%22%E2%9C%85%22%20if%20ok%20else%20%22%E2%9D%8C%22%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%221.%20%7B_fb(q_bits.value%20%3D%3D%20n_nodes%20*%20n_colors)%7D%20N%20%3D%20%7Bq_bits.value%7D%5Cn%22%0A%20%20%20%20%20%20%20%20f%222.%20%7B_fb(q_big.value%20%3D%3D%2080)%7D%20N%20%3D%20%7Bq_big.value%7D%22%0A%20%20%20%20)%20if%20(q_bits.value%20or%20q_big.value)%20else%20mo.md(%22*Tragen%20Sie%20Ihre%20Antworten%20oben%20ein.*%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Aufgabe%203.1%3A%20Zwischen%20Problem-%20und%20Qubit-Raum%20%C3%BCbersetzen%0A%0A%20%20%20%20Wir%20brauchen%20eine%20Zuordnung%20zwischen%20dem%20Paar%20(Knoten%20%24v%24%2C%20Farbe%20%24c%24)%20und%20dem%20Qubit-Index%20%24u%20%5Cin%20%5C%7B0%2C%20%5Cdots%2C%20nk-1%5C%7D%24.%0A%20%20%20%20Ordnen%20Sie%20**knotenweise**%3A%20erst%20alle%20Farben%20von%20Knoten%200%2C%20dann%20alle%20von%20Knoten%201%2C%20usw.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20**a)**%20Schreiben%20Sie%20%60encode(v%2C%20c%2C%20n_colors)%60%2C%20das%20jedes%20Paar%20%24(v%2Cc)%24%20auf%20eine%20Zahl%20in%20%240..(nk-1)%24%20abbildet.%0A%0A%20%20%20%20**b)**%20Schreiben%20Sie%20die%20Umkehrfunktion%20%60decode(u%2C%20n_colors)%60%2C%20die%20%24u%24%20wieder%20in%20%24(v%2Cc)%24%20%C3%BCbersetzt.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20def%20encode(v%2C%20c%2C%20n_colors)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Bildet%20(Knoten%20v%2C%20Farbe%20c)%20auf%20den%20Qubit-Index%20u%20ab.%22%22%22%0A%20%20%20%20%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(encode)%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%20%20%20%20%23%20%3C%3C%3C%0A%0A%20%20%20%20def%20decode(u%2C%20n_colors)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Bildet%20den%20Qubit-Index%20u%20auf%20(Knoten%20v%2C%20Farbe%20c)%20ab.%22%22%22%0A%20%20%20%20%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(decode)%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%20%20%20%20%23%20%3C%3C%3C%0A%20%20%20%20return%20decode%2C%20encode%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(decode%2C%20encode%2C%20n_colors%2C%20n_nodes%2C%20run_check)%3A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20_seen%20%3D%20set()%0A%20%20%20%20%20%20%20%20for%20_v%20in%20range(n_nodes)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_c%20in%20range(n_colors)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_u%20%3D%20encode(_v%2C%20_c%2C%20n_colors)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20assert%200%20%3C%3D%20_u%20%3C%20n_nodes%20*%20n_colors%2C%20f%22encode(%7B_v%7D%2C%20%7B_c%7D)%20%3D%20%7B_u%7D%20liegt%20nicht%20in%200..%7Bn_nodes%20*%20n_colors%20-%201%7D.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_seen.add(_u)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20assert%20decode(_u%2C%20n_colors)%20%3D%3D%20(_v%2C%20_c)%2C%20f%22decode(encode(%7B_v%7D%2C%20%7B_c%7D))%20liefert%20%7Bdecode(_u%2C%20n_colors)%7D.%22%0A%20%20%20%20%20%20%20%20assert%20len(_seen)%20%3D%3D%20n_nodes%20*%20n_colors%2C%20%22Verschiedene%20Paare%20(v%2C%20c)%20werden%20auf%20denselben%20Index%20abgebildet.%22%0A%0A%20%20%20%20ok_codec%2C%20_result%20%3D%20run_check(_test)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_codec%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Aufgabe%203.2%3A%20Jeder%20Knoten%20bekommt%20genau%20eine%20Farbe%0A%0A%20%20%20%20F%C3%BCr%20die%20Kostenfunktion%20brauchen%20wir%20zwei%20Bausteine%2C%20einen%20pro%20Bedingung.%20Zuerst%20Bedingung%201.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%20(Mathematik)%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20**a)**%20Finden%20Sie%20einen%20Ausdruck%20%24k_v(%5Cmathbf%7Bx%7D)%24%2C%20der%20%240%24%20ergibt%2C%20wenn%20Knoten%20%24v%24%20**genau%20eine**%20Farbe%20hat%2C%20und%20sonst%20gr%C3%B6%C3%9Fere%20Werte.%0A%0A%20%20%20%20**b)**%20Bilden%20Sie%20daraus%20%24k(%5Cmathbf%7Bx%7D)%24%20f%C3%BCr%20alle%20Knoten%20und%20multiplizieren%20Sie%20aus.%0A%20%20%20%20Sortieren%20Sie%20nach%20linearen%2C%20quadratischen%20und%20konstanten%20Termen.%0A%0A%20%20%20%20*Tipp%3A*%20%24x_%7Bvc%7D%24%20ist%20bin%C3%A4r%2C%20also%20gilt%20%24x_%7Bvc%7D%5E2%20%3D%20x_%7Bvc%7D%24.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.accordion(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22L%C3%B6sung%20der%20Mathematik%20anzeigen%20(erst%20selbst%20versuchen!)%22%3A%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24k_v(%5Cmathbf%7Bx%7D)%20%3D%20%5CBig(%5Csum_c%20x_%7Bvc%7D%20-%201%5CBig)%5E2%2C%20%5Cqquad%20k(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_v%20k_v(%5Cmathbf%7Bx%7D)%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Ausmultiplizieren%20mit%20%24x_%7Bvc%7D%5E2%20%3D%20x_%7Bvc%7D%24%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24k(%5Cmathbf%7Bx%7D)%20%3D%20-%5Csum_%7Bv%2Cc%7D%20x_%7Bvc%7D%20%2B%202%5Csum_v%20%5Csum_%7Bc%3Cc'%7D%20x_%7Bvc%7Dx_%7Bvc'%7D%20%2B%20n%24%24%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%20(Code)%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20Die%20QUBO-Koeffizienten%20legen%20wir%20in%20einer%20%24N%5Ctimes%20N%24-Matrix%20%60Q%60%20ab%3A%20Ein%20Term%20%24a%5C%2Cx_u%20x_v%24%20steht%20an%20der%20Stelle%20%60Q%5Bu%2C%20v%5D%60%2C%0A%20%20%20%20ein%20linearer%20Term%20%24a%5C%2Cx_u%24%20steht%20wegen%20%24x_u%5E2%20%3D%20x_u%24%20auf%20der%20Diagonalen%20%60Q%5Bu%2C%20u%5D%60.%0A%20%20%20%20Konstante%20Terme%20sammeln%20wir%20als%20%60offset%60.%0A%0A%20%20%20%20Implementieren%20Sie%20%60add_one_color_per_node%60%3A%20Die%20Funktion%20addiert%20%24%5Clambda%20%5Ccdot%20k(%5Cmathbf%7Bx%7D)%24%20zur%20Matrix%20%60Q%60%20(in-place)%20und%20gibt%20den%20konstanten%20Anteil%20zur%C3%BCck.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20add_one_color_per_node(Q%2C%20lam%2C%20n_nodes%2C%20n_colors)%3A%0A%20%20%20%20%22%22%22Addiert%20lam%20*%20k(x)%20zu%20Q%20und%20gibt%20den%20konstanten%20Anteil%20(Offset)%20zur%C3%BCck.%22%22%22%0A%20%20%20%20offset%20%3D%200%0A%0A%20%20%20%20%23%20Muster%20zum%20Hinzuf%C3%BCgen%20eines%20Terms%20a%20*%20x_(v1%2Cc1)%20*%20x_(v2%2Cc2)%3A%0A%20%20%20%20%23%20%20%20u1%20%3D%20encode(v1%2C%20c1%2C%20n_colors)%0A%20%20%20%20%23%20%20%20u2%20%3D%20encode(v2%2C%20c2%2C%20n_colors)%0A%20%20%20%20%23%20%20%20Q%5Bu1%2C%20u2%5D%20%2B%3D%20a%0A%0A%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(k)%0A%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%23%20%3C%3C%3C%0A%20%20%20%20return%20offset%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20n_colors%2C%20n_nodes%2C%20np%2C%20ok_codec%2C%20run_check)%3A%0A%20%20%20%20_N%20%3D%20n_nodes%20*%20n_colors%0A%0A%20%20%20%20def%20_energy(Q%2C%20off%2C%20x)%3A%0A%20%20%20%20%20%20%20%20return%20x%20%40%20Q%20%40%20x%20%2B%20off%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(0)%0A%20%20%20%20%20%20%20%20_Q1%20%3D%20np.zeros((_N%2C%20_N))%0A%20%20%20%20%20%20%20%20_off1%20%3D%20add_one_color_per_node(_Q1%2C%201%2C%20n_nodes%2C%20n_colors)%0A%20%20%20%20%20%20%20%20_Q3%20%3D%20np.zeros((_N%2C%20_N))%0A%20%20%20%20%20%20%20%20_off3%20%3D%20add_one_color_per_node(_Q3%2C%203%2C%20n_nodes%2C%20n_colors)%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20genau%20eine%20Farbe%20pro%20Knoten%20(egal%20welche)%3A%20Kosten%20m%C3%BCssen%200%20sein%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20np.zeros((n_nodes%2C%20n_colors)%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%5Bnp.arange(n_nodes)%2C%20_rng.integers(0%2C%20n_colors%2C%20n_nodes)%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20np.isclose(_energy(_Q1%2C%20_off1%2C%20_x.reshape(-1))%2C%200)%2C%20%22F%C3%BCr%20Belegungen%20mit%20genau%20einer%20Farbe%20pro%20Knoten%20muss%20k(x)%20%3D%200%20gelten.%22%0A%20%20%20%20%20%20%20%20_cases%20%3D%200%0A%20%20%20%20%20%20%20%20while%20_cases%20%3C%2020%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20_rng.integers(0%2C%202%2C%20_N)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.all(_x.reshape(n_nodes%2C%20n_colors).sum(axis%3D1)%20%3D%3D%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20_cases%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20_e1%2C%20_e3%20%3D%20_energy(_Q1%2C%20_off1%2C%20_x)%2C%20_energy(_Q3%2C%20_off3%2C%20_x)%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20_e1%20%3E%200.5%2C%20%22Wenn%20ein%20Knoten%20nicht%20genau%20eine%20Farbe%20hat%2C%20muss%20k(x)%20%3E%200%20gelten.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20np.isclose(_e3%2C%203%20*%20_e1)%2C%20%22Der%20Strafterm%20muss%20proportional%20zu%20lam%20sein.%22%0A%0A%20%20%20%20ok_k%2C%20_result%20%3D%20(%0A%20%20%20%20%20%20%20%20run_check(_test)%20if%20ok_codec%20else%20(False%2C%20mo.callout(mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20Aufgabe%203.1.%22)%2C%20kind%3D%22neutral%22))%0A%20%20%20%20)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_k%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Aufgabe%203.3%3A%20Keine%20gleichfarbigen%20Nachbarn%0A%0A%20%20%20%20Nun%20Bedingung%202.%20Wenn%20Bedingung%201%20erf%C3%BCllt%20ist%2C%20hat%20jeder%20Knoten%20genau%20eine%20Farbe%2C%20und%20wir%20k%C3%B6nnen%20Konflikte%20z%C3%A4hlen.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20**Mathematik%3A**%0A%0A%20%20%20%20**a)**%20Finden%20Sie%20einen%20Ausdruck%20%24e_%7Buv%7D(%5Cmathbf%7Bx%7D)%24%20f%C3%BCr%20eine%20Kante%20%24(u%2Cv)%24%2C%20der%20**z%C3%A4hlt%2C%20wie%20oft%20die%20beiden%20Enden%20dieselbe%20Farbe%20haben**%0A%20%20%20%20(bei%20einer%20F%C3%A4rbung%20also%20%240%24%20oder%20%241%24).%0A%0A%20%20%20%20**b)**%20Summieren%20Sie%20%C3%BCber%20alle%20Kanten%20zu%20%24c(%5Cmathbf%7Bx%7D)%24.%20Welche%20Form%20haben%20die%20Terme%20(linear%2C%20quadratisch)%3F%20Gibt%20es%20konstante%20Terme%3F%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20%60add_edge_conflicts%60%2C%20das%20%24%5Clambda%20%5Ccdot%20c(%5Cmathbf%7Bx%7D)%24%20zu%20%60Q%60%20addiert.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.accordion(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22L%C3%B6sung%20der%20Mathematik%20anzeigen%22%3A%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20a)%20%24e_%7Buv%7D(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_c%20x_%7Buc%7D%5C%2C%20x_%7Bvc%7D%24.%20Der%20Summand%20f%C3%BCr%20Farbe%20%24c%24%20ist%20nur%20dann%20%241%24%2C%20wenn%20*beide*%20Knoten%20diese%20Farbe%20tragen.%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20b)%20%24c(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_%7B(u%2Cv)%20%5Cin%20E%7D%20%5Csum_c%20x_%7Buc%7D%5C%2C%20x_%7Bvc%7D%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20Alle%20Terme%20sind%20bereits%20quadratisch%2C%20es%20gibt%20keine%20linearen%20und%20keine%20konstanten%20Anteile.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20add_edge_conflicts(Q%2C%20lam%2C%20edges%2C%20n_colors)%3A%0A%20%20%20%20%22%22%22Addiert%20lam%20*%20c(x)%20zu%20Q%20und%20gibt%20den%20konstanten%20Anteil%20(Offset)%20zur%C3%BCck.%22%22%22%0A%20%20%20%20offset%20%3D%200%0A%0A%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(conflicts)%0A%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%23%20%3C%3C%3C%0A%20%20%20%20return%20offset%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(edges%2C%20mo%2C%20n_colors%2C%20n_nodes%2C%20np%2C%20ok_codec%2C%20run_check)%3A%0A%20%20%20%20_N%20%3D%20n_nodes%20*%20n_colors%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(2)%0A%20%20%20%20%20%20%20%20_Q%20%3D%20np.zeros((_N%2C%20_N))%0A%20%20%20%20%20%20%20%20_off%20%3D%20add_edge_conflicts(_Q%2C%201%2C%20edges%2C%20n_colors)%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(30)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20beliebige%20F%C3%A4rbung%20(auch%20ung%C3%BCltige)%3A%20c(x)%20muss%20die%20Anzahl%20der%20gleichfarbigen%20Kanten%20z%C3%A4hlen%0A%20%20%20%20%20%20%20%20%20%20%20%20_colors%20%3D%20_rng.integers(0%2C%20n_colors%2C%20n_nodes)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20np.zeros((n_nodes%2C%20n_colors)%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%5Bnp.arange(n_nodes)%2C%20_colors%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20_x.reshape(-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20_conflicts%20%3D%20sum(_colors%5Bu%5D%20%3D%3D%20_colors%5Bv%5D%20for%20u%2C%20v%20in%20edges)%0A%20%20%20%20%20%20%20%20%20%20%20%20_e%20%3D%20_x%20%40%20_Q%20%40%20_x%20%2B%20_off%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20np.isclose(_e%2C%20_conflicts)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22F%C3%BCr%20die%20F%C3%A4rbung%20%7Blist(_colors)%7D%20gibt%20es%20%7B_conflicts%7D%20Konflikt(e)%2C%20Ihr%20Code%20liefert%20c(x)%20%3D%20%7B_e%7D.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_conf%2C%20_result%20%3D%20(%0A%20%20%20%20%20%20%20%20run_check(_test)%20if%20ok_codec%20else%20(False%2C%20mo.callout(mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20Aufgabe%203.1.%22)%2C%20kind%3D%22neutral%22))%0A%20%20%20%20)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_conf%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Das%20gesamte%20QUBO%0A%0A%20%20%20%20Fast%20geschafft%2C%20aber%20noch%20stehen%20die%20**Nebenbedingung**%20(jeder%20Knoten%20genau%20eine%20Farbe)%20und%20die%20**Zielfunktion**%20(keine%20Konflikte)%20getrennt%20da.%0A%20%20%20%20Ein%20QUBO%20ist%20*unconstrained*%2C%20deshalb%20addieren%20wir%20die%20Bedingung%20als%20**Strafterm**%20mit%20Gewichten%20%24%5Clambda_A%2C%20%5Clambda_B%20%3E%200%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20Q(%5Cmathbf%7Bx%7D)%20%3D%20%5Clambda_A%5C%2C%20k(%5Cmathbf%7Bx%7D)%20%2B%20%5Clambda_B%5C%2C%20c(%5Cmathbf%7Bx%7D)%20.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Beide%20Terme%20sind%20niemals%20negativ.%20%24Q(%5Cmathbf%7Bx%7D)%20%3D%200%24%20gilt%20daher%20genau%20dann%2C%20wenn%20alle%20Knoten%20genau%20eine%20Farbe%20haben%20**und**%20keine%20Kante%20einen%20Konflikt%20hat%2C%0A%20%20%20%20also%20genau%20f%C3%BCr%20die%20**g%C3%BCltigen%20F%C3%A4rbungen**.%20Die%20Grundzustandsenergie%20ist%20%240%24%2C%20wenn%20der%20Graph%20f%C3%A4rbbar%20ist%2C%20andernfalls%20gr%C3%B6%C3%9Fer%20als%20%240%24.%0A%20%20%20%20Wir%20starten%20mit%20%24%5Clambda_A%20%3D%20%5Clambda_B%20%3D%201%24.%0A%0A%20%20%20%20Die%20Funktion%20%60build_qubo%60%20fasst%20Ihre%20beiden%20Bausteine%20zusammen.%20Sie%20liefert%20die%20Matrix%20(obere%20Dreiecksmatrix)%20und%20den%20Offset%3A%0A%0A%20%20%20%20%24%24Q(%5Cmathbf%7Bx%7D)%20%3D%20%5Cmathbf%7Bx%7D%5ET%20Q%5C%2C%20%5Cmathbf%7Bx%7D%20%2B%20%5Ctext%7Boffset%7D.%24%24%0A%0A%20%20%20%20Die%20Variable%20%60bits%60%20enth%C3%A4lt%20alle%20%242%5EN%24%20Bitstrings%20(%60bits%5Bs%2C%20u%5D%60%20ist%20der%20Wert%20von%20Qubit%20%24u%24%20in%20Zustand%20%24s%24)%2C%20und%0A%20%20%20%20%60E_all%60%20die%20zugeh%C3%B6rigen%20Energien.%20F%C3%BCr%20kleine%20%24N%24%20k%C3%B6nnen%20wir%20sie%20komplett%20berechnen%20und%20haben%20damit%20eine%20exakte%20Vergleichsbasis.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(edges%2C%20n_colors%2C%20n_nodes%2C%20np)%3A%0A%20%20%20%20N%20%3D%20n_nodes%20*%20n_colors%20%20%23%20Anzahl%20der%20Qubits%0A%0A%20%20%20%20def%20build_qubo(lam_a%2C%20lam_b)%3A%0A%20%20%20%20%20%20%20%20Q%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20offset%20%3D%200%0A%20%20%20%20%20%20%20%20offset%20%2B%3D%20add_one_color_per_node(Q%2C%20lam_a%2C%20n_nodes%2C%20n_colors)%0A%20%20%20%20%20%20%20%20offset%20%2B%3D%20add_edge_conflicts(Q%2C%20lam_b%2C%20edges%2C%20n_colors)%0A%20%20%20%20%20%20%20%20%23%20Eintr%C3%A4ge%20Q%5Bu%2C%20v%5D%20und%20Q%5Bv%2C%20u%5D%20zu%20einem%20Eintrag%20oberhalb%20der%20Diagonale%20zusammenfassen%0A%20%20%20%20%20%20%20%20Q_upper%20%3D%20np.triu(Q%20%2B%20Q.T%20-%20np.diag(np.diag(Q)))%0A%20%20%20%20%20%20%20%20return%20Q_upper%2C%20offset%0A%0A%20%20%20%20%23%20Alle%202%5EN%20Bitstrings.%20Little-endian%20wie%20in%20Qiskit%3A%20bits%5Bs%2C%20u%5D%20ist%20Bit%20u%20(%3D%20Qubit%20u)%20von%20s.%0A%20%20%20%20bits%20%3D%20(np.arange(2**N)%5B%3A%2C%20None%5D%20%3E%3E%20np.arange(N))%20%26%201%0A%0A%20%20%20%20def%20qubo_energies(Q%2C%20offset)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Energie%20x%5ET%20Q%20x%20%2B%20offset%20f%C3%BCr%20alle%202%5EN%20Bitstrings.%22%22%22%0A%20%20%20%20%20%20%20%20return%20np.einsum(%22si%2Cij%2Csj-%3Es%22%2C%20bits%2C%20Q%2C%20bits)%20%2B%20offset%0A%0A%20%20%20%20LAM_A%20%3D%20LAM_B%20%3D%201%0A%20%20%20%20return%20LAM_A%2C%20LAM_B%2C%20N%2C%20bits%2C%20build_qubo%2C%20qubo_energies%0A%0A%0A%40app.cell%0Adef%20_(N%2C%20n_colors%2C%20np%2C%20proper_colorings)%3A%0A%20%20%20%20%23%20Referenz%3A%20Masken%20der%20g%C3%BCltigen%20F%C3%A4rbungen%20unter%20allen%202%5EN%20Bitstrings%20(unabh%C3%A4ngig%20von%20Ihrem%20Code%20berechnet)%0A%20%20%20%20valid_mask%20%3D%20np.zeros(2**N%2C%20dtype%3Dbool)%0A%20%20%20%20for%20_coloring%20in%20proper_colorings%3A%0A%20%20%20%20%20%20%20%20valid_mask%5Bsum(2%20**%20(v%20*%20n_colors%20%2B%20c)%20for%20v%2C%20c%20in%20enumerate(_coloring))%5D%20%3D%20True%0A%20%20%20%20return%20(valid_mask%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20LAM_A%2C%0A%20%20%20%20LAM_B%2C%0A%20%20%20%20build_qubo%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20ok_conf%2C%0A%20%20%20%20ok_k%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20qubo_energies%2C%0A%20%20%20%20run_check%2C%0A%20%20%20%20valid_mask%2C%0A)%3A%0A%20%20%20%20mo.stop(%0A%20%20%20%20%20%20%20%20not%20(ok_k%20and%20ok_conf)%2C%0A%20%20%20%20%20%20%20%20mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.3%20(alle%20Tests%20m%C3%BCssen%20bestanden%20sein).%22)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20Q_qubo%2C%20qubo_offset%20%3D%20build_qubo(LAM_A%2C%20LAM_B)%0A%20%20%20%20E_all%20%3D%20qubo_energies(Q_qubo%2C%20qubo_offset)%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20if%20valid_mask.any()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20np.allclose(E_all%5Bvalid_mask%5D%2C%200)%2C%20%22G%C3%BCltige%20F%C3%A4rbungen%20m%C3%BCssen%20die%20Energie%200%20haben.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20E_all%5B~valid_mask%5D.min()%20%3E%200.5%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Es%20gibt%20eine%20ung%C3%BCltige%20Belegung%20mit%20Energie%200.%20Pr%C3%BCfen%20Sie%2C%20ob%20beide%20Strafterme%20alle%20Verletzungen%20erfassen.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20E_all.min()%20%3E%200.5%2C%20%22Der%20Graph%20ist%20nicht%20f%C3%A4rbbar%2C%20also%20darf%20keine%20Belegung%20die%20Energie%200%20haben.%22%0A%0A%20%20%20%20ok_qubo%2C%20_result%20%3D%20run_check(_test)%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(4.5%2C%204.5))%0A%20%20%20%20_lim%20%3D%20np.abs(Q_qubo).max()%0A%20%20%20%20_ax.imshow(Q_qubo%2C%20cmap%3D%22bwr%22%2C%20vmin%3D-_lim%2C%20vmax%3D_lim)%0A%20%20%20%20_ax.set_title(%22QUBO-Matrix%20(rot%20positiv%2C%20blau%20negativ)%22)%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20_result%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Jeder%20Eintrag%20ist%20eine%20Kopplung%20zwischen%20zwei%20Qubits.%20Die%20Diagonalbl%C3%B6cke%20(je%20ein%20Knoten)%20entstehen%20durch%20die%20One-Hot-Bedingung%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22die%20Streifen%20parallel%20zur%20Diagonalen%20durch%20die%20Kanten.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20_fig%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%20E_all%2C%20Q_qubo%2C%20ok_qubo%2C%20qubo_offset%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Aufgabe%203.4%3A%20Eine%20F%C3%A4rbung%20erkennen%0A%0A%20%20%20%20Ein%20gemessener%20Bitstring%20ist%20nicht%20automatisch%20eine%20F%C3%A4rbung.%20F%C3%BCr%20die%20Auswertung%20brauchen%20wir%20eine%20Funktion%2C%20die%20das%20pr%C3%BCft.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20Implementieren%20Sie%20%60is_valid_coloring(x%2C%20n_nodes%2C%20n_colors%2C%20edges)%60.%20Der%20Parameter%20%60x%60%20ist%20ein%20Array%20aus%20%24N%24%20Nullen%20und%20Einsen.%0A%20%20%20%20Die%20Funktion%20soll%20%60True%60%20zur%C3%BCckgeben%2C%20genau%20dann%20wenn%0A%0A%20%20%20%201.%20**jeder%20Knoten%20genau%20eine**%20Farbe%20hat%20und%0A%20%20%20%202.%20**keine%20Kante**%20gleichfarbige%20Enden%20hat.%0A%0A%20%20%20%20*Tipp%3A*%20%60x.reshape(n_nodes%2C%20n_colors)%60%20sortiert%20die%20Bits%20in%20eine%20Tabelle%20(Zeile%20%3D%20Knoten%2C%20Spalte%20%3D%20Farbe).%20Dann%20hilft%20%60argmax(axis%3D1)%60.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20is_valid_coloring(x%2C%20n_nodes%2C%20n_colors%2C%20edges)%3A%0A%20%20%20%20%22%22%22True%2C%20wenn%20der%20Bitstring%20x%20eine%20g%C3%BCltige%20F%C3%A4rbung%20kodiert.%22%22%22%0A%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(is_valid)%0A%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%23%20%3C%3C%3C%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bits%2C%20edges%2C%20mo%2C%20n_colors%2C%20n_nodes%2C%20ok_qubo%2C%20run_check%2C%20valid_mask)%3A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20for%20_s%20in%20range(len(bits))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_got%20%3D%20is_valid_coloring(bits%5B_s%5D%2C%20n_nodes%2C%20n_colors%2C%20edges)%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20bool(_got)%20%3D%3D%20bool(valid_mask%5B_s%5D)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22F%C3%BCr%20x%20%3D%20%7B''.join(map(str%2C%20bits%5B_s%5D))%7D%20(Qubit%200%20zuerst)%20geben%20Sie%20%7B_got%7D%20zur%C3%BCck%2C%20richtig%20w%C3%A4re%20%7Bbool(valid_mask%5B_s%5D)%7D.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_valid%2C%20_result%20%3D%20(%0A%20%20%20%20%20%20%20%20run_check(_test)%0A%20%20%20%20%20%20%20%20if%20ok_qubo%0A%20%20%20%20%20%20%20%20else%20(False%2C%20mo.callout(mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.3.%22)%2C%20kind%3D%22neutral%22))%0A%20%20%20%20)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_valid%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20bits%2C%20mo%2C%20n_colors%2C%20n_nodes%2C%20np%2C%20ok_qubo%2C%20ok_valid%2C%20plot_graph)%3A%0A%20%20%20%20mo.stop(not%20(ok_qubo%20and%20ok_valid))%0A%0A%20%20%20%20_gs%20%3D%20np.flatnonzero(E_all%20%3D%3D%20E_all.min())%0A%20%20%20%20_colors%20%3D%20bits%5B_gs%5B0%5D%5D.reshape(n_nodes%2C%20n_colors).argmax(axis%3D1)%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Die%20kleinste%20Energie%20des%20QUBO%20ist%20**%7BE_all.min()%3A.0f%7D**%2C%20sie%20wird%20von%20**%7Blen(_gs)%7D**%20der%20%7Blen(E_all)%7D%20Bitstrings%20angenommen%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22(Grundzustand%20mit%20Entartung).%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20Das%20sind%20genau%20die%20g%C3%BCltigen%20F%C3%A4rbungen.%20Beispiel%3A%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20E_all.min()%20%3D%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%20%22%20Weil%20der%20Graph%20nicht%20f%C3%A4rbbar%20ist%2C%20bleibt%20die%20Energie%20positiv.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20plot_graph(_colors)%20if%20E_all.min()%20%3D%3D%200%20else%20mo.md(%22%22)%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%204%3A%20Vom%20QUBO%20zum%20Hamilton-Operator%0A%0A%20%20%20%20Ein%20Quantencomputer%20arbeitet%20mit%20dem%20Operator%20%24Z%24%20(Eigenwerte%20%24%5Cpm%201%24)%20statt%20mit%20Bits.%0A%20%20%20%20Die%20%C3%9Cbersetzung%20ist%20%24x_u%20%5Cto%20%5Cfrac%7B1%20-%20Z_u%7D%7B2%7D%24.%20Aus%20Ihrer%20QUBO-Matrix%20lesen%20wir%20die%20Koeffizienten%20ab%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20Q(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_u%20a_u%20x_u%20%2B%20%5Csum_%7Bu%3Cv%7D%20b_%7Buv%7D%5C%2C%20x_u%20x_v%20%2B%20%5Ctext%7Boffset%7D%2C%0A%20%20%20%20%5Cqquad%20a_u%20%3D%20Q_%7Buu%7D%2C%5C%3B%20b_%7Buv%7D%20%3D%20Q_%7Buv%7D%5C%20(u%3Cv).%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20**Mathematik%3A**%20Setzen%20Sie%20%24x_u%20%3D%20%5Cfrac%7B1%20-%20Z_u%7D%7B2%7D%24%20ein%20und%20sortieren%20Sie%20nach%20Pauli-Operatoren.%20Geben%20Sie%20die%20Koeffizienten%0A%20%20%20%20%24h_u%24%20(vor%20%24Z_u%24)%2C%20%24J_%7Buv%7D%24%20(vor%20%24Z_u%20Z_v%24)%20und%20die%20Konstante%20(vor%20der%20Identit%C3%A4t)%20in%20Abh%C3%A4ngigkeit%20von%20%24a_u%24%2C%20%24b_%7Buv%7D%24%20und%20dem%20Offset%20an.%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20%60qubo_to_hamiltonian(Q%2C%20offset)%60.%20Die%20Funktion%20gibt%20den%20Hamilton-Operator%20als%20%60SparsePauliOp%60%20zur%C3%BCck.%0A%20%20%20%20Verwenden%20Sie%20%60SparsePauliOp.from_sparse_list(terme%2C%20num_qubits%3DN)%60%20mit%20Tupeln%20der%20Form%0A%20%20%20%20%60(%22Z%22%2C%20%5Bu%5D%2C%20h_u)%60%2C%20%60(%22ZZ%22%2C%20%5Bu%2C%20v%5D%2C%20J_uv)%60%20und%20%60(%22%5C%22%2C%20%5B%5D%2C%20konstante)%60%20f%C3%BCr%20die%20Identit%C3%A4t.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.accordion(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22L%C3%B6sung%20der%20Mathematik%20anzeigen%22%3A%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Es%20gilt%20%24a_u%20x_u%20%3D%20%5Cfrac%7Ba_u%7D%7B2%7D%20-%20%5Cfrac%7Ba_u%7D%7B2%7D%20Z_u%24%20und%0A%20%20%20%20%20%20%20%20%20%20%20%20%24b_%7Buv%7D%20x_u%20x_v%20%3D%20%5Cfrac%7Bb_%7Buv%7D%7D%7B4%7D%5Cleft(1%20-%20Z_u%20-%20Z_v%20%2B%20Z_u%20Z_v%5Cright)%24.%20Alle%20Terme%20sammeln%20ergibt%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24h_u%20%3D%20-%5Cfrac%7Ba_u%7D%7B2%7D%20-%20%5Cfrac%7B1%7D%7B4%7D%5CBig(%5Csum_%7Bv%3Eu%7D%20b_%7Buv%7D%20%2B%20%5Csum_%7Bv%3Cu%7D%20b_%7Bvu%7D%5CBig)%2C%20%5Cqquad%20J_%7Buv%7D%20%3D%20%5Cfrac%7Bb_%7Buv%7D%7D%7B4%7D%2C%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24%5Ctext%7Bconst%7D%20%3D%20%5Ctext%7Boffset%7D%20%2B%20%5Csum_u%20%5Cfrac%7Ba_u%7D%7B2%7D%20%2B%20%5Csum_%7Bu%3Cv%7D%20%5Cfrac%7Bb_%7Buv%7D%7D%7B4%7D.%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Die%20Konstante%20verschiebt%20alle%20Energien%20um%20denselben%20Wert.%20Sie%20%C3%A4ndert%20den%20Grundzustand%20nicht%2C%20nimmt%20man%20sie%20mit%20auf%2C%20stimmen%20die%0A%20%20%20%20%20%20%20%20%20%20%20%20Eigenwerte%20des%20Operators%20aber%20exakt%20mit%20den%20QUBO-Energien%20%C3%BCberein.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20qubo_to_hamiltonian(Q%2C%20offset)%3A%0A%20%20%20%20%22%22%22Wandelt%20ein%20QUBO%20(obere%20Dreiecksmatrix%20Q%2C%20Offset)%20in%20einen%20Ising-Hamilton-Operator%20(SparsePauliOp)%20um.%22%22%22%0A%20%20%20%20N%20%3D%20len(Q)%0A%0A%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(hamiltonian)%0A%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%23%20%3C%3C%3C%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20E_all%2C%0A%20%20%20%20N%2C%0A%20%20%20%20Q_qubo%2C%0A%20%20%20%20SparsePauliOp%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20ok_qubo%2C%0A%20%20%20%20qubo_offset%2C%0A%20%20%20%20run_check%2C%0A)%3A%0A%20%20%20%20mo.stop(%0A%20%20%20%20%20%20%20%20not%20ok_qubo%2C%0A%20%20%20%20%20%20%20%20mo.callout(mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.3.%22)%2C%20kind%3D%22neutral%22)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20H%20%3D%20qubo_to_hamiltonian(Q_qubo%2C%20qubo_offset)%0A%20%20%20%20%20%20%20%20assert%20isinstance(H%2C%20SparsePauliOp)%2C%20%22Die%20Funktion%20muss%20ein%20SparsePauliOp%20zur%C3%BCckgeben.%22%0A%20%20%20%20%20%20%20%20assert%20H.num_qubits%20%3D%3D%20N%2C%20f%22Der%20Operator%20muss%20auf%20%7BN%7D%20Qubits%20wirken.%22%0A%20%20%20%20%20%20%20%20assert%20all(set(label)%20%3C%3D%20%7B%22I%22%2C%20%22Z%22%7D%20for%20label%20in%20H.paulis.to_labels())%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Der%20Operator%20darf%20nur%20Z-Terme%20(und%20die%20Identit%C3%A4t)%20enthalten%2C%20er%20muss%20diagonal%20sein.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_diag%20%3D%20H.to_matrix(sparse%3DTrue).diagonal()%0A%20%20%20%20%20%20%20%20_bad%20%3D%20np.abs(_diag.real%20-%20E_all)%0A%20%20%20%20%20%20%20%20assert%20_bad.max()%20%3C%201e-8%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Die%20Eigenwerte%20stimmen%20nicht%20mit%20den%20QUBO-Energien%20%C3%BCberein%20(gr%C3%B6%C3%9Fte%20Abweichung%20%7B_bad.max()%3A.3f%7D%20bei%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Bitstring-Index%20%7Bint(_bad.argmax())%7D).%20Haben%20Sie%20die%20Konstante%20und%20alle%20Vorzeichen%20ber%C3%BCcksichtigt%3F%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_ham%2C%20_result%20%3D%20run_check(_test)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_ham%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Q_qubo%2C%20mo%2C%20ok_ham%2C%20qubo_offset)%3A%0A%20%20%20%20mo.stop(not%20ok_ham)%0A%0A%20%20%20%20H_C%20%3D%20qubo_to_hamiltonian(Q_qubo%2C%20qubo_offset)%0A%20%20%20%20_n_zz%20%3D%20sum(1%20for%20_%2C%20q%2C%20_%20in%20H_C.to_sparse_list()%20if%20len(q)%20%3D%3D%202)%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22Der%20Hamilton-Operator%20hat%20**%7Blen(H_C)%7D**%20Terme%2C%20davon%20**%7B_n_zz%7D**%20Zwei-Qubit-Terme%20%24Z_uZ_v%24.%20%22%0A%20%20%20%20%20%20%20%20f%22Jeder%20davon%20wird%20sp%C3%A4ter%20ein%20%60rzz%60-Gatter%20in%20jeder%20Schicht.%20Das%20liegt%20an%20der%20One-Hot-Kodierung%2C%20%22%0A%20%20%20%20%20%20%20%20f%22die%20viele%20Qubits%20miteinander%20koppelt.%20Die%20ersten%20Terme%3A%5Cn%5Cn%60%60%60%5Cn%7BH_C%5B%3A6%5D%7D%5Cn%60%60%60%22%0A%20%20%20%20)%0A%20%20%20%20return%20(H_C%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%205%3A%20Der%20QAOA-Schaltkreis%0A%0A%20%20%20%20Jetzt%20schreiben%20wir%20die%20Bausteine%20aus%20Teil%202%20als%20Gatter%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20U_C(%5Cgamma)%20%3D%20e%5E%7B-i%5Cgamma%20H_C%7D%20%5Csimeq%20%5Cprod_u%20e%5E%7B-i%5Cgamma%20h_u%20Z_u%7D%20%5Cprod_%7Bu%3Cv%7D%20e%5E%7B-i%5Cgamma%20J_%7Buv%7D%20Z_u%20Z_v%7D%2C%0A%20%20%20%20%5Cqquad%20U_M(%5Cbeta)%20%3D%20e%5E%7B-i%5Cbeta%20%5Csum_u%20X_u%7D%20%3D%20%5Cprod_u%20e%5E%7B-i%5Cbeta%20X_u%7D.%0A%20%20%20%20%24%24%0A%0A%20%20%20%20(Die%20Zerlegung%20in%20Einzelgatter%20ist%20exakt%2C%20weil%20alle%20%24Z%24-Terme%20untereinander%20vertauschen.%20Die%20Konstante%20ergibt%20nur%20eine%20globale%20Phase.)%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20**Mathematik%3A**%20Mit%20welchem%20Winkel%20%24%5Cvarphi%24%20m%C3%BCssen%20Sie%20%60rz%60%2C%20%60rzz%60%20und%20%60rx%60%20aufrufen%2C%20um%20%24e%5E%7B-i%5Cgamma%20h_u%20Z_u%7D%24%2C%20%24e%5E%7B-i%5Cgamma%20J_%7Buv%7D%20Z_u%20Z_v%7D%24%0A%20%20%20%20und%20%24e%5E%7B-i%5Cbeta%20X_w%7D%24%20zu%20erhalten%3F%20(Qiskit-Konvention%3A%20%24R_Z(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20Z%2F2%7D%24%20usw.)%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20die%20beiden%20Schichten.%20Beide%20f%C3%BCgen%20Gatter%20in%20den%20%C3%BCbergebenen%20Schaltkreis%20%60qc%60%20ein%20(nichts%20zur%C3%BCckgeben).%0A%0A%20%20%20%20*%20%60cost_layer(qc%2C%20gamma%2C%20H)%60%3A%20Gehen%20Sie%20mit%20%60for%20pauli%2C%20qubits%2C%20coeff%20in%20H.to_sparse_list()%3A%60%20durch%20die%20Terme%20von%20%24H_C%24.%0A%20%20%20%20%20%20%60qubits%60%20ist%20die%20Liste%20der%20Qubits%2C%20auf%20die%20der%20Term%20wirkt%2C%20%60coeff%60%20der%20(komplexe)%20Koeffizient.%20Verwenden%20Sie%20%60coeff.real%60.%0A%20%20%20%20%20%20Je%20nach%20Anzahl%20der%20Qubits%20brauchen%20Sie%20%60qc.rz(winkel%2C%20qubit)%60%20oder%20%60qc.rzz(winkel%2C%20qubit1%2C%20qubit2)%60.%20Die%20Identit%C3%A4t%20(keine%20Qubits)%20lassen%20Sie%20weg.%0A%20%20%20%20*%20%60mixer_layer(qc%2C%20beta)%60%3A%20%24U_M(%5Cbeta)%24%20mit%20%60qc.rx(winkel%2C%20qubit)%60%20auf%20allen%20Qubits%20(%60qc.num_qubits%60).%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.accordion(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Hinweis%20zu%20den%20Winkeln%22%3A%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20Vergleichen%20Sie%20die%20Exponenten%3A%20%24R_Z(%5Cvarphi)%20%3D%20e%5E%7B-i(%5Cvarphi%2F2)%20Z%7D%24%20soll%20gleich%20%24e%5E%7B-i(%5Cgamma%20h_u)%20Z%7D%24%20sein%2C%20also%20%24%5Cvarphi%2F2%20%3D%20%5Cgamma%20h_u%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20F%C3%BCr%20%24R_%7BZZ%7D%24%20und%20%24R_X%24%20geht%20es%20genauso.%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20def%20cost_layer(qc%2C%20gamma%2C%20H)%3A%0A%20%20%20%20%20%20%20%20%22%22%22F%C3%BCgt%20exp(-i%20*%20gamma%20*%20H_C)%20an%20den%20Schaltkreis%20qc%20an.%22%22%22%0A%20%20%20%20%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(cost_layer)%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%20%20%20%20%23%20%3C%3C%3C%0A%0A%20%20%20%20def%20mixer_layer(qc%2C%20beta)%3A%0A%20%20%20%20%20%20%20%20%22%22%22F%C3%BCgt%20exp(-i%20*%20beta%20*%20sum_u%20X_u)%20an%20den%20Schaltkreis%20qc%20an.%22%22%22%0A%20%20%20%20%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(mixer_layer)%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%20%20%20%20%23%20%3C%3C%3C%0A%20%20%20%20return%20cost_layer%2C%20mixer_layer%0A%0A%0A%40app.cell%0Adef%20_(ParameterVector%2C%20QuantumCircuit%2C%20cost_layer%2C%20mixer_layer)%3A%0A%20%20%20%20def%20build_qaoa_circuit(H%2C%20p)%3A%0A%20%20%20%20%20%20%20%20%22%22%22QAOA-Schaltkreis%20mit%20p%20Schichten.%20Gibt%20(Schaltkreis%2C%20gammas%2C%20betas)%20mit%20symbolischen%20Parametern%20zur%C3%BCck.%22%22%22%0A%20%20%20%20%20%20%20%20gammas%20%3D%20ParameterVector(%22%CE%B3%22%2C%20p)%0A%20%20%20%20%20%20%20%20betas%20%3D%20ParameterVector(%22%CE%B2%22%2C%20p)%0A%20%20%20%20%20%20%20%20qc%20%3D%20QuantumCircuit(H.num_qubits)%0A%20%20%20%20%20%20%20%20qc.h(range(H.num_qubits))%20%20%23%20Startzustand%20%7C%2B%3E%5EN%0A%20%20%20%20%20%20%20%20for%20layer%20in%20range(p)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20cost_layer(qc%2C%20gammas%5Blayer%5D%2C%20H)%0A%20%20%20%20%20%20%20%20%20%20%20%20mixer_layer(qc%2C%20betas%5Blayer%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20qc.barrier()%0A%20%20%20%20%20%20%20%20return%20qc%2C%20gammas%2C%20betas%0A%0A%20%20%20%20return%20(build_qaoa_circuit%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20H_C%2C%0A%20%20%20%20N%2C%0A%20%20%20%20PauliEvolutionGate%2C%0A%20%20%20%20QuantumCircuit%2C%0A%20%20%20%20SparsePauliOp%2C%0A%20%20%20%20Statevector%2C%0A%20%20%20%20build_qaoa_circuit%2C%0A%20%20%20%20cost_layer%2C%0A%20%20%20%20mixer_layer%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20ok_ham%2C%0A%20%20%20%20run_check%2C%0A)%3A%0A%20%20%20%20mo.stop(not%20ok_ham%2C%20mo.callout(mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20die%20Hamilton-Aufgabe%20(Teil%204).%22)%2C%20kind%3D%22neutral%22))%0A%0A%20%20%20%20%23%20Referenz%20mit%20Qiskits%20eingebauter%20PauliEvolutionGate%20%3D%20exp(-i%20*%20t%20*%20Operator)%0A%20%20%20%20_H_mix%20%3D%20SparsePauliOp.from_sparse_list(%5B(%22X%22%2C%20%5Bu%5D%2C%201.0)%20for%20u%20in%20range(N)%5D%2C%20num_qubits%3DN)%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(4)%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20%23%201)%20Kostenschicht%20allein%2C%20angewendet%20auf%20%7C%2B%3E%5EN%0A%20%20%20%20%20%20%20%20_gamma%20%3D%200.37%0A%20%20%20%20%20%20%20%20_mine%20%3D%20QuantumCircuit(N)%0A%20%20%20%20%20%20%20%20_mine.h(range(N))%0A%20%20%20%20%20%20%20%20cost_layer(_mine%2C%20_gamma%2C%20H_C)%0A%20%20%20%20%20%20%20%20_ref%20%3D%20QuantumCircuit(N)%0A%20%20%20%20%20%20%20%20_ref.h(range(N))%0A%20%20%20%20%20%20%20%20_ref.append(PauliEvolutionGate(H_C%2C%20time%3D_gamma)%2C%20range(N))%0A%20%20%20%20%20%20%20%20assert%20Statevector(_mine).equiv(Statevector(_ref)%2C%20atol%3D1e-8)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Ihre%20cost_layer%20erzeugt%20nicht%20exp(-i%20%CE%B3%20H_C).%20Pr%C3%BCfen%20Sie%20die%20Winkel%20(Faktor%202%3F)%20und%20welche%20Gatter%20zu%20welchen%20Termen%20geh%C3%B6ren.%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%23%202)%20Mixer%20allein%2C%20angewendet%20auf%20einen%20zuf%C3%A4lligen%20Produktzustand%20(%7C%2B%3E%20w%C3%A4re%20ein%20Eigenzustand%20und%20w%C3%BCrde%20nichts%20zeigen)%0A%20%20%20%20%20%20%20%20_beta%20%3D%200.61%0A%20%20%20%20%20%20%20%20_prep%20%3D%20QuantumCircuit(N)%0A%20%20%20%20%20%20%20%20for%20_q%20in%20range(N)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prep.ry(_rng.uniform(0%2C%20np.pi)%2C%20_q)%0A%20%20%20%20%20%20%20%20_mine%20%3D%20_prep.copy()%0A%20%20%20%20%20%20%20%20mixer_layer(_mine%2C%20_beta)%0A%20%20%20%20%20%20%20%20_ref%20%3D%20_prep.copy()%0A%20%20%20%20%20%20%20%20_ref.append(PauliEvolutionGate(_H_mix%2C%20time%3D_beta)%2C%20range(N))%0A%20%20%20%20%20%20%20%20assert%20Statevector(_mine).equiv(Statevector(_ref)%2C%20atol%3D1e-8)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Ihre%20mixer_layer%20erzeugt%20nicht%20exp(-i%20%CE%B2%20%CE%A3%20X).%20Pr%C3%BCfen%20Sie%20den%20Winkel%20(Faktor%202%3F).%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%23%203)%20Gesamtschaltkreis%20mit%20p%20%3D%202%20Schichten%0A%20%20%20%20%20%20%20%20_g%2C%20_b%20%3D%20_rng.uniform(0%2C%200.5%2C%202)%2C%20_rng.uniform(0%2C%201%2C%202)%0A%20%20%20%20%20%20%20%20_qc%2C%20_gs%2C%20_bs%20%3D%20build_qaoa_circuit(H_C%2C%202)%0A%20%20%20%20%20%20%20%20_bound%20%3D%20_qc.assign_parameters(%7B**dict(zip(_gs%2C%20_g))%2C%20**dict(zip(_bs%2C%20_b))%7D)%0A%20%20%20%20%20%20%20%20_ref%20%3D%20QuantumCircuit(N)%0A%20%20%20%20%20%20%20%20_ref.h(range(N))%0A%20%20%20%20%20%20%20%20for%20_l%20in%20range(2)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ref.append(PauliEvolutionGate(H_C%2C%20time%3D_g%5B_l%5D)%2C%20range(N))%0A%20%20%20%20%20%20%20%20%20%20%20%20_ref.append(PauliEvolutionGate(_H_mix%2C%20time%3D_b%5B_l%5D)%2C%20range(N))%0A%20%20%20%20%20%20%20%20assert%20Statevector(_bound).equiv(Statevector(_ref)%2C%20atol%3D1e-8)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Der%20Gesamtschaltkreis%20(mit%20symbolischen%20Parametern)%20stimmt%20nicht%20mit%20der%20Referenz%20%C3%BCberein.%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_layers%2C%20_result%20%3D%20run_check(_test)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_layers%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20Parameter%2C%0A%20%20%20%20QuantumCircuit%2C%0A%20%20%20%20SparsePauliOp%2C%0A%20%20%20%20cost_layer%2C%0A%20%20%20%20mixer_layer%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20ok_layers%2C%0A)%3A%0A%20%20%20%20mo.stop(not%20ok_layers)%0A%0A%20%20%20%20%23%20Ihre%20Schichten%20f%C3%BCr%20einen%20winzigen%20Beispiel-Operator%200.5%20Z0%20%2B%201.0%20Z0%20Z1%20%2B%200.25%20Z2%0A%20%20%20%20_mini%20%3D%20SparsePauliOp.from_sparse_list(%5B(%22Z%22%2C%20%5B0%5D%2C%200.5)%2C%20(%22ZZ%22%2C%20%5B0%2C%201%5D%2C%201.0)%2C%20(%22Z%22%2C%20%5B2%5D%2C%200.25)%5D%2C%20num_qubits%3D3)%0A%20%20%20%20_qc%20%3D%20QuantumCircuit(3)%0A%20%20%20%20_qc.h(range(3))%0A%20%20%20%20cost_layer(_qc%2C%20Parameter(%22%CE%B3%22)%2C%20_mini)%0A%20%20%20%20mixer_layer(_qc%2C%20Parameter(%22%CE%B2%22))%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22So%20sieht%20Ihre%20Schicht%20f%C3%BCr%20einen%20kleinen%20Beispiel-Operator%20%240%7B%2C%7D5%5C%5C%2CZ_0%20%2B%20Z_0Z_1%20%2B%200%7B%2C%7D25%5C%5C%2CZ_2%24%20aus%3A%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20_qc.draw(%22mpl%22)%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Der%20Erwartungswert%0A%0A%20%20%20%20Der%20Optimierer%20braucht%20eine%20Zahl%20zum%20Minimieren%3A%20den%20Erwartungswert%20der%20Kosten%0A%0A%20%20%20%20%24%24%5Clangle%20H_C%20%5Crangle%20%3D%20%5Csum_x%20p(x)%5C%2C%20E(x)%24%24%0A%0A%20%20%20%20Die%20Wahrscheinlichkeiten%20%24p(x)%24%20liefert%20der%20simulierte%20Zustand%20(%60Statevector(...).probabilities()%60%2C%20in%20der%20Reihenfolge%20der%20Bitstring-Indizes)%2C%0A%20%20%20%20die%20Energien%20%24E(x)%24%20haben%20wir%20klassisch%20in%20%60E_all%60%20berechnet.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20%E2%9C%8D%EF%B8%8F%20Aufgabe%0A%20%20%20%20%20%20%20%20type%3A%20warning%0A%0A%20%20%20%20Implementieren%20Sie%20%60expectation(probs%2C%20energies)%60%2C%20das%20%24%5Clangle%20H_C%20%5Crangle%24%20als%20Zahl%20(%60float%60)%20zur%C3%BCckgibt.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.function%0Adef%20expectation(probs%2C%20energies)%3A%0A%20%20%20%20%22%22%22Erwartungswert%20%3CH_C%3E%20%3D%20sum_x%20p(x)%20E(x).%22%22%22%0A%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(expectation)%0A%20%20%20%20raise%20NotImplementedError%0A%20%20%20%20%23%20%3C%3C%3C%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20mo%2C%20np%2C%20ok_layers%2C%20run_check)%3A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(5)%0A%20%20%20%20%20%20%20%20_probs%20%3D%20_rng.dirichlet(np.ones(len(E_all)))%0A%20%20%20%20%20%20%20%20_value%20%3D%20expectation(_probs%2C%20E_all)%0A%20%20%20%20%20%20%20%20assert%20np.isclose(float(_value)%2C%20float(_probs%20%40%20E_all))%2C%20%22Der%20Erwartungswert%20stimmt%20nicht.%22%0A%20%20%20%20%20%20%20%20_uniform%20%3D%20np.full(len(E_all)%2C%201%20%2F%20len(E_all))%0A%20%20%20%20%20%20%20%20assert%20np.isclose(float(expectation(_uniform%2C%20E_all))%2C%20E_all.mean())%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22F%C3%BCr%20die%20Gleichverteilung%20muss%20der%20Mittelwert%20aller%20Energien%20herauskommen.%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_expect%2C%20_result%20%3D%20(%0A%20%20%20%20%20%20%20%20run_check(_test)%0A%20%20%20%20%20%20%20%20if%20ok_layers%0A%20%20%20%20%20%20%20%20else%20(False%2C%20mo.callout(mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20die%20Schichten%20(Teil%205).%22)%2C%20kind%3D%22neutral%22))%0A%20%20%20%20)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_expect%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%206%3A%20QAOA%20ausf%C3%BChren%20und%20auswerten%0A%0A%20%20%20%20Jetzt%20wird%20optimiert.%20W%C3%A4hlen%20Sie%20die%20Anzahl%20der%20Schichten%20%24p%24%20und%20die%20maximale%20Anzahl%20an%20Funktionsauswertungen%20von%20%60COBYLA%60.%0A%0A%20%20%20%20**Startwerte%3A**%20Eine%20bew%C3%A4hrte%20Wahl%20ist%20die%20*Rampe*%2C%20inspiriert%20vom%20Annealing%20aus%20Abschnitt%202.4%3A%20%24%5Cgamma_l%24%20w%C3%A4chst%20und%20%24%5Cbeta_l%24%20sinkt%20linear%20mit%20der%20Schicht%20%24l%24.%0A%20%20%20%20Der%20Schaltkreis%20beginnt%20dann%20wie%20eine%20kurze%2C%20grob%20diskretisierte%20adiabatische%20Evolution.%20Zuf%C3%A4llige%20Startwerte%20landen%20h%C3%A4ufiger%20in%20schlechten%20lokalen%20Minima.%0A%20%20%20%20Probieren%20Sie%20beide%20aus!%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20form%20%3D%20(%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%7Bp_layers%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%7Bmaxiter%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%7Binit%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.batch(%0A%20%20%20%20%20%20%20%20%20%20%20%20p_layers%3Dmo.ui.slider(1%2C%205%2C%20value%3D3%2C%20label%3D%22Schichten%20p%22%2C%20show_value%3DTrue)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20maxiter%3Dmo.ui.slider(100%2C%202000%2C%20step%3D100%2C%20value%3D600%2C%20label%3D%22max.%20Auswertungen%20(COBYLA)%22%2C%20show_value%3DTrue)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20init%3Dmo.ui.dropdown(%5B%22Rampe%22%2C%20%22zuf%C3%A4llig%22%5D%2C%20value%3D%22Rampe%22%2C%20label%3D%22Startwerte%22)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.form(submit_button_label%3D%22QAOA%20starten%22)%0A%20%20%20%20)%0A%20%20%20%20form%0A%20%20%20%20return%20(form%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20H_C%2C%20Statevector%2C%20build_qaoa_circuit%2C%20minimize%2C%20np)%3A%0A%20%20%20%20def%20run_qaoa(p_layers%2C%20maxiter%2C%20init%3D%22Rampe%22%2C%20seed%3D0)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Optimiert%20(gamma%2C%20beta)%20mit%20COBYLA.%20Gibt%20Parameter%2C%20Kostenverlauf%20und%20die%20finalen%20Wahrscheinlichkeiten%20zur%C3%BCck.%22%22%22%0A%20%20%20%20%20%20%20%20circuit%2C%20gammas%2C%20betas%20%3D%20build_qaoa_circuit(H_C%2C%20p_layers)%0A%20%20%20%20%20%20%20%20symbols%20%3D%20list(gammas)%20%2B%20list(betas)%0A%20%20%20%20%20%20%20%20history%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20def%20cost(params)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20bound%20%3D%20circuit.assign_parameters(dict(zip(symbols%2C%20params)))%0A%20%20%20%20%20%20%20%20%20%20%20%20value%20%3D%20expectation(Statevector(bound).probabilities()%2C%20E_all)%0A%20%20%20%20%20%20%20%20%20%20%20%20history.append(value)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20value%0A%0A%20%20%20%20%20%20%20%20%23%20Skala%20f%C3%BCr%20gamma%3A%20gamma%20*%20(Gr%C3%B6%C3%9Fe%20der%20Koeffizienten)%20soll%20in%20der%20Gr%C3%B6%C3%9Fenordnung%200.1%20-%201%20liegen%0A%20%20%20%20%20%20%20%20_scale%20%3D%200.4%20%2F%20max(abs(c.real)%20for%20_%2C%20q%2C%20c%20in%20H_C.to_sparse_list()%20if%20len(q)%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20_l%20%3D%20np.arange(1%2C%20p_layers%20%2B%201)%20%2F%20(p_layers%20%2B%201)%0A%20%20%20%20%20%20%20%20if%20init%20%3D%3D%20%22Rampe%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20x0%20%3D%20np.concatenate(%5B_scale%20*%20_l%2C%200.8%20*%20(1%20-%20_l)%5D)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(seed)%0A%20%20%20%20%20%20%20%20%20%20%20%20x0%20%3D%20np.concatenate(%5B_rng.uniform(0%2C%202%20*%20_scale%2C%20p_layers)%2C%20_rng.uniform(0%2C%200.8%2C%20p_layers)%5D)%0A%0A%20%20%20%20%20%20%20%20result%20%3D%20minimize(cost%2C%20x0%2C%20method%3D%22COBYLA%22%2C%20options%3D%7B%22maxiter%22%3A%20maxiter%7D)%0A%20%20%20%20%20%20%20%20final_state%20%3D%20Statevector(circuit.assign_parameters(dict(zip(symbols%2C%20result.x))))%0A%20%20%20%20%20%20%20%20return%20result.x%2C%20history%2C%20final_state%0A%0A%20%20%20%20return%20(run_qaoa%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(form%2C%20mo%2C%20ok_expect%2C%20ok_ham%2C%20ok_layers%2C%20ok_valid%2C%20run_qaoa)%3A%0A%20%20%20%20mo.stop(%0A%20%20%20%20%20%20%20%20not%20(ok_ham%20and%20ok_layers%20and%20ok_expect%20and%20ok_valid)%2C%0A%20%20%20%20%20%20%20%20mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20alle%20Aufgaben%20oben%20(alle%20Selbsttests%20m%C3%BCssen%20%E2%9C%85%20zeigen).%22)%2C%0A%20%20%20%20)%0A%20%20%20%20mo.stop(form.value%20is%20None%2C%20mo.md(%22W%C3%A4hlen%20Sie%20die%20Einstellungen%20und%20klicken%20Sie%20auf%20**QAOA%20starten**.%22))%0A%0A%20%20%20%20settings%20%3D%20form.value%0A%20%20%20%20p_used%20%3D%20settings%5B%22p_layers%22%5D%0A%20%20%20%20with%20mo.status.spinner(title%3D%22QAOA-Optimierung%20l%C3%A4uft%20%E2%80%A6%22)%3A%0A%20%20%20%20%20%20%20%20params_opt%2C%20cost_history%2C%20final_state%20%3D%20run_qaoa(p_used%2C%20settings%5B%22maxiter%22%5D%2C%20settings%5B%22init%22%5D)%0A%20%20%20%20final_probs%20%3D%20final_state.probabilities()%0A%20%20%20%20return%20cost_history%2C%20final_probs%2C%20final_state%2C%20p_used%2C%20params_opt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20E_all%2C%0A%20%20%20%20cost_history%2C%0A%20%20%20%20final_probs%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20p_used%2C%0A%20%20%20%20params_opt%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20valid_mask%2C%0A)%3A%0A%20%20%20%20_e0%20%3D%20E_all.min()%0A%20%20%20%20_p_opt%20%3D%20final_probs%5BE_all%20%3D%3D%20_e0%5D.sum()%0A%20%20%20%20_p_valid%20%3D%20final_probs%5Bvalid_mask%5D.sum()%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6%2C%203))%0A%20%20%20%20_ax.plot(np.minimum.accumulate(cost_history))%0A%20%20%20%20_ax.axhline(_e0%2C%20color%3D%22g%22%2C%20ls%3D%22--%22%2C%20label%3D%22Optimum%20%24E_0%24%22)%0A%20%20%20%20_ax.axhline(E_all.mean()%2C%20color%3D%22gray%22%2C%20ls%3D%22%3A%22%2C%20label%3D%22Gleichverteilung%22)%0A%20%20%20%20_ax.set_xlabel(%22Auswertung%20des%20Schaltkreises%22)%0A%20%20%20%20_ax.set_ylabel(r%22bester%20Wert%20von%20%24%5Clangle%20H_C%20%5Crangle%24%22)%0A%20%20%20%20_ax.legend()%0A%20%20%20%20plt.close(_fig)%0A%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rf%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%23%20Ergebnis%20f%C3%BCr%20%24p%20%3D%20%7Bp_used%7D%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%7C%20nach%20QAOA%20%7C%20Gleichverteilung%20(zuf%C3%A4lliges%20Raten)%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C---%7C---%7C---%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%24%5Clangle%20H_C%20%5Crangle%24%20%7C%20%7Bmin(cost_history)%3A.2f%7D%20%7C%20%7BE_all.mean()%3A.2f%7D%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20Wahrscheinlichkeit%20f%C3%BCr%20eine%20**g%C3%BCltige%20F%C3%A4rbung**%20%7C%20%7B_p_valid%3A.1%25%7D%20%7C%20%7Bvalid_mask.mean()%3A.2%25%7D%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20Wahrscheinlichkeit%20f%C3%BCr%20einen%20**Grundzustand**%20(%24E%20%3D%20E_0%20%3D%20%7B_e0%3A.0f%7D%24)%20%7C%20%7B_p_opt%3A.1%25%7D%20%7C%20%7B(E_all%20%3D%3D%20_e0).mean()%3A.2%25%7D%20%7C%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Optimierte%20Parameter%3A%20%24%5Cgamma%20%3D%20%7Bnp.round(params_opt%5B%3Ap_used%5D%2C%203)%7D%24%2C%20%24%5Cbeta%20%3D%20%7Bnp.round(params_opt%5Bp_used%3A%5D%2C%203)%7D%24.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20_fig%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20bits%2C%20final_probs%2C%20mo%2C%20n_colors%2C%20n_nodes%2C%20np%2C%20plt%2C%20valid_mask)%3A%0A%20%20%20%20_top%20%3D%20np.argsort(final_probs)%5B%3A%3A-1%5D%5B%3A16%5D%0A%20%20%20%20_e0%20%3D%20E_all.min()%0A%20%20%20%20_colors%20%3D%20%5B%22tab%3Agreen%22%20if%20E_all%5Bs%5D%20%3D%3D%20_e0%20else%20%22tab%3Ablue%22%20if%20valid_mask%5Bs%5D%20else%20%22lightgray%22%20for%20s%20in%20_top%5D%0A%20%20%20%20%23%20je%20Knoten%20eine%20Gruppe%20von%20Bits%20(Farbe%200%20zuerst)%2C%20Knoten%20durch%20%7C%20getrennt%0A%20%20%20%20_label%20%3D%20lambda%20s%3A%20%22%7C%22.join(%22%22.join(map(str%2C%20bits%5Bs%2C%20v%20*%20n_colors%20%3A%20(v%20%2B%201)%20*%20n_colors%5D))%20for%20v%20in%20range(n_nodes))%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8%2C%203.5))%0A%20%20%20%20_ax.bar(range(len(_top))%2C%20final_probs%5B_top%5D%2C%20color%3D_colors)%0A%20%20%20%20_ax.set_xticks(range(len(_top))%2C%20%5B_label(s)%20for%20s%20in%20_top%5D%2C%20rotation%3D75%2C%20family%3D%22monospace%22%2C%20size%3D8)%0A%20%20%20%20_ax.set_ylabel(%22Wahrscheinlichkeit%22)%0A%20%20%20%20_ax.set_title(%22Die%2016%20wahrscheinlichsten%20Bitstrings%20(gr%C3%BCn%20%3D%20Grundzustand%2C%20grau%20%3D%20sonstige)%22)%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20_fig%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Jede%20Gruppe%20aus%20drei%20Ziffern%20geh%C3%B6rt%20zu%20einem%20Knoten%20(Knoten%200%20%7C%201%20%7C%202%20%7C%203)%2C%20die%20Ziffer%20an%20Position%20%24c%24%20ist%20das%20Bit%20%24x_%7Bvc%7D%24.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%60100%60%20hei%C3%9Ft%20also%20%E2%80%9EFarbe%200%E2%80%9C.%20Es%20gibt%20mehrere%20Grundzust%C3%A4nde%2C%20weil%20sich%20die%20Farben%20permutieren%20lassen.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Die%20Wahrscheinlichkeit%20verteilt%20sich%20deshalb%20auf%20mehrere%20Balken.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Eine%20L%C3%B6sung%20messen%0A%0A%20%20%20%20Auf%20einem%20echten%20Quantencomputer%20f%C3%BChren%20Sie%20den%20Schaltkreis%20viele%20Male%20aus%20(*Shots*)%20und%20w%C3%A4hlen%20aus%20den%20Messergebnissen%20den%20besten%20Bitstring.%0A%20%20%20%20Das%20simulieren%20wir%20mit%20%60Statevector.sample_counts%60.%20Beachten%20Sie%20die%20Bit-Reihenfolge%3A%20Die%20zur%C3%BCckgegebenen%20Beschriftungen%20sind%20**little-endian**%2C%0A%20%20%20%20Qubit%200%20steht%20rechts.%20Wir%20drehen%20sie%20deshalb%20um%2C%20damit%20sie%20zu%20unserem%20%60bits%60-Array%20passen.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20bits%2C%20edges%2C%20final_state%2C%20mo%2C%20n_colors%2C%20n_nodes%2C%20np%2C%20plot_graph)%3A%0A%20%20%20%20final_state.seed(7)%0A%20%20%20%20_counts%20%3D%20final_state.sample_counts(1000)%0A%0A%20%20%20%20%23%20Qiskit-Beschriftung%20(Qubit%200%20rechts)%20-%3E%20Index%20in%20unserem%20bits-Array%0A%20%20%20%20_to_index%20%3D%20lambda%20label%3A%20int(label%2C%202)%0A%20%20%20%20_decodable%20%3D%20%5B%0A%20%20%20%20%20%20%20%20label%20for%20label%20in%20_counts%20if%20np.all(bits%5B_to_index(label)%5D.reshape(n_nodes%2C%20n_colors).sum(axis%3D1)%20%3D%3D%201)%0A%20%20%20%20%5D%0A%20%20%20%20_n_valid%20%3D%20sum(%0A%20%20%20%20%20%20%20%20_counts%5Blabel%5D%20for%20label%20in%20_counts%20if%20is_valid_coloring(bits%5B_to_index(label)%5D%2C%20n_nodes%2C%20n_colors%2C%20edges)%0A%20%20%20%20)%0A%0A%20%20%20%20if%20not%20_decodable%3A%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.md(%22%E2%9D%8C%20Unter%20den%201000%20Messungen%20war%20keine%20Belegung%20mit%20genau%20einer%20Farbe%20pro%20Knoten.%20Probieren%20Sie%20mehr%20Schichten%20oder%20Auswertungen.%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_best%20%3D%20min(_decodable%2C%20key%3Dlambda%20label%3A%20E_all%5B_to_index(label)%5D)%0A%20%20%20%20%20%20%20%20_x%20%3D%20bits%5B_to_index(_best)%5D%0A%20%20%20%20%20%20%20%20_coloring%20%3D%20_x.reshape(n_nodes%2C%20n_colors).argmax(axis%3D1)%0A%20%20%20%20%20%20%20%20_ok%20%3D%20is_valid_coloring(_x%2C%20n_nodes%2C%20n_colors%2C%20edges)%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.vstack(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Von%201000%20Messungen%20waren%20**%7B_n_valid%7D**%20g%C3%BCltige%20F%C3%A4rbungen.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Der%20beste%20Bitstring%20mit%20genau%20einer%20Farbe%20pro%20Knoten%20hat%20die%20Qiskit-Beschriftung%20%60%7B_best%7D%60%20(Qubit%200%20rechts)%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22die%20Energie%20%7BE_all%5B_to_index(_best)%5D%3A.0f%7D%20und%20die%20F%C3%A4rbung%20%7Blist(map(int%2C%20_coloring))%7D%3A%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B%20(%22**g%C3%BCltig**%20%E2%9C%85%22%20if%20_ok%20else%20%22**ung%C3%BCltig**%20%E2%9D%8C%20(rote%20gestrichelte%20Kanten%20sind%20Konflikte)%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20plot_graph(_coloring)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20_out%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Experiment%3A%20Wie%20hilft%20eine%20gr%C3%B6%C3%9Fere%20Schichtzahl%3F%0A%0A%20%20%20%20Der%20folgende%20Lauf%20optimiert%20f%C3%BCr%20%24p%20%3D%201%2C%20%5Cdots%2C%205%24%20je%20600%20Auswertungen%20(das%20dauert%20etwa%20eine%20halbe%20Minute).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20scan_button%20%3D%20mo.ui.run_button(label%3D%22p%20%3D%201%20%E2%80%A6%205%20vergleichen%22)%0A%20%20%20%20scan_button%0A%20%20%20%20return%20(scan_button%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20E_all%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20ok_expect%2C%0A%20%20%20%20ok_ham%2C%0A%20%20%20%20ok_layers%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20run_qaoa%2C%0A%20%20%20%20scan_button%2C%0A%20%20%20%20valid_mask%2C%0A)%3A%0A%20%20%20%20mo.stop(not%20(ok_ham%20and%20ok_layers%20and%20ok_expect))%0A%20%20%20%20mo.stop(not%20scan_button.value%2C%20mo.md(%22*Klicken%20Sie%20auf%20den%20Knopf%2C%20um%20den%20Vergleich%20zu%20starten.*%22))%0A%0A%20%20%20%20_ps%20%3D%20%5B1%2C%202%2C%203%2C%204%2C%205%5D%0A%20%20%20%20_p_opt%2C%20_p_valid%20%3D%20%5B%5D%2C%20%5B%5D%0A%20%20%20%20for%20_p%20in%20mo.status.progress_bar(_ps%2C%20title%3D%22Vergleich%20%C3%BCber%20p%22)%3A%0A%20%20%20%20%20%20%20%20*_%2C%20_state%20%3D%20run_qaoa(_p%2C%20600)%0A%20%20%20%20%20%20%20%20_probs%20%3D%20_state.probabilities()%0A%20%20%20%20%20%20%20%20_p_opt.append(_probs%5BE_all%20%3D%3D%20E_all.min()%5D.sum())%0A%20%20%20%20%20%20%20%20_p_valid.append(_probs%5Bvalid_mask%5D.sum())%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(5.5%2C%203))%0A%20%20%20%20_ax.plot(_ps%2C%20_p_valid%2C%20%22o-%22%2C%20label%3D%22g%C3%BCltige%20F%C3%A4rbung%22)%0A%20%20%20%20_ax.plot(_ps%2C%20_p_opt%2C%20%22s-%22%2C%20label%3D%22Grundzustand%22)%0A%20%20%20%20_ax.set_xticks(_ps)%0A%20%20%20%20_ax.set_xlabel(%22Schichten%20p%22)%0A%20%20%20%20_ax.set_ylabel(%22Wahrscheinlichkeit%22)%0A%20%20%20%20_ax.legend()%0A%20%20%20%20plt.close(_fig)%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Teil%207%3A%20Weiterf%C3%BChrende%20Fragen%0A%0A%20%20%20%201.%20**Nicht%20f%C3%A4rbbar%3A**%20Setzen%20Sie%20in%20der%20Instanz-Zelle%20%60n_colors%20%3D%202%60.%20Alle%20Zellen%20laufen%20automatisch%20mit%208%20statt%2012%20Qubits%20neu.%0A%20%20%20%20%20%20%20Was%20ist%20die%20kleinste%20Energie%3F%20Welche%20Bitstrings%20sind%20jetzt%20Grundzust%C3%A4nde%2C%20und%20sind%20es%20g%C3%BCltige%20F%C3%A4rbungen%3F%20(Erh%C3%B6hen%20Sie%20probehalber%20%60LAM_A%60.)%0A%20%20%20%20%20%20%20Wie%20lie%C3%9Fe%20sich%20mit%20dieser%20Technik%20die%20**chromatische%20Zahl**%20des%20Graphen%20finden%3F%0A%20%20%20%202.%20**Gewichte%20der%20Strafterme%3A**%20Hier%20gilt%20f%C3%BCr%20jedes%20%24%5Clambda_A%2C%20%5Clambda_B%20%3E%200%24%2C%20dass%20die%20Grundzust%C3%A4nde%20genau%20die%20g%C3%BCltigen%20F%C3%A4rbungen%20sind%20(der%20Graph%20ist%20f%C3%A4rbbar).%0A%20%20%20%20%20%20%20Ver%C3%A4ndert%20sich%20die%20Qualit%C3%A4t%20von%20QAOA%20trotzdem%3F%20Probieren%20Sie%20%60LAM_A%20%3D%202%60%20oder%20%603%60%20und%20vergleichen%20Sie%20%24%5Clangle%20H_C%20%5Crangle%24%20nach%20der%20Optimierung.%0A%20%20%20%20%20%20%20Woran%20k%C3%B6nnte%20das%20liegen%3F%20(Hinweis%3A%20Wie%20weit%20sind%20die%20Energien%20der%20Zust%C3%A4nde%20gespreizt%2C%20und%20was%20bedeutet%20das%20f%C3%BCr%20die%20Parameter%20%24%5Cgamma%24%3F)%0A%20%20%20%203.%20**Gr%C3%B6%C3%9Ferer%20Graph%3A**%20Ein%20Graph%20mit%2020%20Knoten%20und%204%20Farben%20braucht%2080%20Qubits%2C%20das%20ist%20nicht%20mehr%20als%20Zustandsvektor%20simulierbar%20(%242%5E%7B80%7D%24%20Eintr%C3%A4ge).%0A%20%20%20%20%20%20%20Welche%20Alternativen%20gibt%20es%3F%20(Stichw%C3%B6rter%3A%20Tensornetz-Simulation%2C%20echte%20Hardware%2C%20andere%20Kodierungen%20mit%20weniger%20Qubits%2C%20z.%20B.%20bin%C3%A4re%20statt%20One-Hot-Kodierung%3A%20%24%5Clceil%20%5Clog_2%20k%20%5Crceil%24%20Qubits%20pro%20Knoten.)%0A%20%20%20%204.%20**Symmetrie%3A**%20Jede%20F%C3%A4rbung%20l%C3%A4sst%20sich%20durch%20Permutation%20der%20Farben%20in%20%24k!%24%20gleichwertige%20umwandeln.%20Wie%20k%C3%B6nnten%20Sie%20das%20ausnutzen%2C%20um%20Qubits%20zu%20sparen%3F%0A%20%20%20%20%20%20%20(Zum%20Beispiel%20einen%20Knoten%20auf%20Farbe%200%20festlegen.)%0A%20%20%20%205.%20**Besserer%20Mixer%3A**%20Der%20%24X%24-Mixer%20verl%C3%A4sst%20st%C3%A4ndig%20den%20Raum%20der%20%E2%80%9Eone-hot%22-Zust%C3%A4nde.%0A%20%20%20%20%20%20%20Mit%20einem%20*Constraint-preserving*%20Mixer%20(z.%20B.%20XY-Mixer%20auf%20den%20Qubits%20eines%20Knotens)%20w%C3%BCrden%20nur%20Zust%C3%A4nde%20mit%20genau%20einer%20Farbe%20pro%20Knoten%20erreicht%2C%0A%20%20%20%20%20%20%20und%20der%20Strafterm%20%24k%24%20w%C3%A4re%20%C3%BCberfl%C3%BCssig.%20Wie%20m%C3%BCsste%20der%20Mixer%20aussehen%3F%0A%20%20%20%206.%20**Mit%20Aer%20und%20Shots%3A**%20Ersetzen%20Sie%20die%20exakte%20%60Statevector%60-Rechnung%20durch%20den%20%60Estimator%60%2F%60Sampler%60%20aus%20%60qiskit-aer%60.%20Wie%20ver%C3%A4ndert%20das%20Shot-Rauschen%20die%20Optimierung%3F%0A%0A%20%20%20%20%23%20Zusammenfassung%0A%0A%20%20%20%20%7C%20Schritt%20%7C%20Was%20Sie%20getan%20haben%20%7C%0A%20%20%20%20%7C---%7C---%7C%0A%20%20%20%20%7C%201%20%7C%20F%C3%A4rbung%20in%20bin%C3%A4re%20Variablen%20kodiert%20(One-Hot)%3A%20%24x_%7Bvc%7D%24%20%7C%0A%20%20%20%20%7C%202%20%7C%20Bedingungen%20als%20Strafterme%20%24k(%5Cmathbf%7Bx%7D)%24%2C%20%24c(%5Cmathbf%7Bx%7D)%24%20aufgestellt%2C%20ergibt%20das%20**QUBO**%20mit%20Grundzustandsenergie%200%20genau%20f%C3%BCr%20g%C3%BCltige%20F%C3%A4rbungen%20%7C%0A%20%20%20%20%7C%203%20%7C%20%24x_u%20%3D%20%5Cfrac%7B1-Z_u%7D%7B2%7D%24%20eingesetzt%2C%20ergibt%20den%20Ising-Operator%20als%20**%60SparsePauliOp%60**%20%7C%0A%20%20%20%20%7C%204%20%7C%20%24H_C%24%20in%20Gatter%20%C3%BCbersetzt%3A%20Kostenschicht%20(%60rz%60%2C%20%60rzz%60)%20und%20Mixer%20(%60rx%60)%20%7C%0A%20%20%20%20%7C%205%20%7C%20%24(%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D)%24%20mit%20%60COBYLA%60%20so%20optimiert%2C%20dass%20%24%5Clangle%20H_C%20%5Crangle%24%20minimal%20wird%20%7C%0A%20%20%20%20%7C%206%20%7C%20Messergebnisse%20ausgewertet%20und%20die%20Bit-Reihenfolge%20von%20Qiskit%20beachtet%20%7C%0A%0A%20%20%20%20Dasselbe%20Vorgehen%20funktioniert%20f%C3%BCr%20viele%20andere%20QUBO-Probleme%2C%20zum%20Beispiel%20f%C3%BCr%20das%20Gartenproblem%20aus%20dem%20Gardening-Notebook.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
e39be52bfc45282dce211176d2cde1c5