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%20Garten-Optimierung%20mit%20QAOA%0A%0A%20%20%20%20*Basierend%20auf%20dem%20D-Wave-Notebook%20%E2%80%9EGarden%20Optimization%20Problems%22%20von%20Carlos%20Gonzalez%20Calaza%0A%20%20%20%20(Tests%20und%20Verbesserungen%3A%20Ashwin%20Kumar%20Karnad)%20aus%20der%20JUNIQ%20School%20on%20Quantum%20Computing.%0A%20%20%20%20Ins%20Deutsche%20%C3%BCbersetzt%20und%20f%C3%BCr%20den%20**Quantum%20Approximate%20Optimization%20Algorithm%20(QAOA)**%20statt%20f%C3%BCr%20einen%20Quantum%20Annealer%20umgebaut.*%0A%0A%20%20%20%20%23%23%20Motivation%0A%0A%20%20%20%20In%20diesem%20Notebook%20l%C3%B6sen%20Sie%20ein%20reales%20diskretes%20Optimierungsproblem%20auf%20einem%20(simulierten)%20Gate-basierten%20Quantencomputer.%0A%20%20%20%20Dabei%20gehen%20Sie%20den%20kompletten%20Weg%20von%20der%20Problembeschreibung%20bis%20zum%20Ergebnis%3A%0A%0A%20%20%20%201.%20ein%20Problem%20aus%20dem%20Alltag%20**mathematisch%20formulieren**%2C%0A%20%20%20%202.%20es%20als%20**QUBO**%20(Quadratic%20Unconstrained%20Binary%20Optimization)%20aufschreiben%2C%0A%20%20%20%203.%20das%20QUBO%20in%20einen%20**Ising-Hamilton-Operator**%20%C3%BCberf%C3%BChren%2C%0A%20%20%20%204.%20daraus%20einen%20**QAOA-Schaltkreis**%20mit%20PennyLane%20bauen%2C%0A%20%20%20%205.%20die%20Parameter%20**klassisch%20optimieren**%20und%20das%20Ergebnis%20auswerten.%0A%0A%20%20%20%20Das%20QUBO-Modell%20ist%20dasselbe%2C%20das%20auch%20Quantum%20Annealer%20(z.%20B.%20D-Wave)%20verwenden.%0A%20%20%20%20Der%20Unterschied%3A%20Statt%20das%20System%20analog%20zu%20%E2%80%9Egl%C3%BChen%22%2C%20lassen%20wir%20einen%20Quantenschaltkreis%20mit%20wenigen%0A%20%20%20%20Parametern%20laufen%20und%20optimieren%20diese%20Parameter%20mit%20einem%20klassischen%20Rechner.%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%20oder%20in%20einer%20Markdown-Zelle)%2C%0A%20%20%20%20teils%20mit%20Code.%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%20Wenn%20Sie%20nicht%20weiterkommen%2C%20helfen%20die%20aufklappbaren%20Hinweise.%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%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pennylane%20as%20qml%0A%20%20%20%20from%20pennylane%20import%20numpy%20as%20pnp%0A%0A%20%20%20%20return%20itertools%2C%20np%2C%20plt%2C%20pnp%2C%20qml%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%20%23%23%20Gartenoptimierung%20durch%20Mischkultur%0A%0A%20%20%20%20Gesucht%20ist%20eine%20optimale%20Anordnung%20von%20Gem%C3%BCsepflanzen%20in%20einem%20Garten.%20Manche%20Pflanzenarten%20vertragen%20sich%20gut%2C%0A%20%20%20%20manche%20sind%20neutral%20zueinander%2C%20andere%20wirken%20sich%20gegenseitig%20schlecht%20aus%20(sogenannte%20*Mischkultur*).%0A%20%20%20%20Wir%20kodieren%20das%20Verh%C3%A4ltnis%20zweier%20Arten%20so%3A%0A%0A%20%20%20%20%7C%20Wert%20%7C%20Beziehung%20%7C%20Beispiel%20%7C%0A%20%20%20%20%7C%3A-%3A%7C---%7C---%7C%0A%20%20%20%20%7C%20%24-1%24%20%7C%20freundlich%20%7C%20Tomate%20und%20Salat%20%7C%0A%20%20%20%20%7C%20%240%24%20%7C%20neutral%20%7C%20Tomate%20und%20Zucchini%20%7C%0A%20%20%20%20%7C%20%24%2B1%24%20%7C%20feindlich%20%7C%20Tomate%20und%20Gurke%20%7C%0A%0A%20%20%20%20Von%20Hand%20w%C3%BCrden%20Sie%20die%20T%C3%B6pfe%20anordnen%2C%20Pflanzen%20kaufen%2C%20sie%20auf%20die%20T%C3%B6pfe%20verteilen%20und%20dann%20so%20lange%20umsortieren%2C%0A%20%20%20%20bis%20alle%20Pflanzen%20m%C3%B6glichst%20%E2%80%9Egl%C3%BCcklich%22%20sind.%20Genau%20dieses%20letzte%20Umsortieren%20(die%20Optimierung)%20%C3%BCbernimmt%20sp%C3%A4ter%20QAOA.%0A%20%20%20%20Daf%C3%BCr%20brauchen%20wir%20eine%20M%C3%B6glichkeit%2C%20eine%20gegebene%20Anordnung%20zu%20**bewerten**.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20%23%20Beziehungstabelle%20aus%20der%20Originalaufgabe%20(-1%20freundlich%2C%200%20neutral%2C%20%2B1%20feindlich)%0A%20%20%20%20COMPANIONS_CSV%20%3D%20%22%22%22Species%2CTomato%2CPaprika%2CCucumber%2CZuccini%2CLettuce%2CCarrot%2COnion%2CRaddish%2COregano%2CBasil%2CThyme%2CParsley%2CChives%2CRosemary%2CSage%2CDill%2CCoriander%2CMint%0A%20%20%20%20Tomato%2C-1%2C-1%2C1%2C0%2C-1%2C-1%2C-1%2C0%2C-1%2C-1%2C0%2C-1%2C-1%2C0%2C0%2C0%2C-1%2C-1%0A%20%20%20%20Paprika%2C-1%2C-1%2C-1%2C0%2C0%2C-1%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%0A%20%20%20%20Cucumber%2C1%2C-1%2C-1%2C1%2C-1%2C0%2C-1%2C-1%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C-1%2C0%2C0%0A%20%20%20%20Zuccini%2C0%2C0%2C1%2C-1%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%0A%20%20%20%20Lettuce%2C-1%2C0%2C-1%2C0%2C-1%2C-1%2C-1%2C-1%2C0%2C0%2C0%2C1%2C0%2C0%2C-1%2C-1%2C-1%2C-1%0A%20%20%20%20Carrot%2C-1%2C-1%2C0%2C0%2C-1%2C-1%2C-1%2C-1%2C0%2C0%2C0%2C0%2C-1%2C-1%2C-1%2C-1%2C0%2C-1%0A%20%20%20%20Onion%2C-1%2C0%2C-1%2C-1%2C-1%2C-1%2C-1%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C-1%2C0%2C0%0A%20%20%20%20Raddish%2C0%2C0%2C-1%2C0%2C-1%2C-1%2C0%2C-1%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%0A%20%20%20%20Oregano%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%0A%20%20%20%20Basil%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%0A%20%20%20%20Thyme%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%0A%20%20%20%20Parsley%2C-1%2C0%2C-1%2C-1%2C1%2C0%2C-1%2C-1%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C-1%2C0%0A%20%20%20%20Chives%2C-1%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C-1%2C1%2C0%0A%20%20%20%20Rosemary%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%0A%20%20%20%20Sage%2C0%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%0A%20%20%20%20Dill%2C0%2C0%2C-1%2C0%2C-1%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C-1%2C0%2C0%2C-1%2C-1%2C0%0A%20%20%20%20Coriander%2C-1%2C0%2C0%2C0%2C-1%2C0%2C0%2C0%2C0%2C-1%2C0%2C-1%2C1%2C0%2C0%2C-1%2C-1%2C0%0A%20%20%20%20Mint%2C-1%2C0%2C0%2C0%2C-1%2C-1%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C0%2C-1%22%22%22%0A%0A%20%20%20%20_rows%20%3D%20%5Bline.split(%22%2C%22)%20for%20line%20in%20COMPANIONS_CSV.splitlines()%5D%0A%20%20%20%20all_species%20%3D%20_rows%5B0%5D%5B1%3A%5D%0A%20%20%20%20C_all%20%3D%20np.array(%5B%5Bint(v)%20for%20v%20in%20r%5B1%3A%5D%5D%20for%20r%20in%20_rows%5B1%3A%5D%5D)%0A%20%20%20%20return%20C_all%2C%20all_species%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(C_all%2C%20all_species%2C%20np%2C%20plt)%3A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6.5%2C%206))%0A%20%20%20%20_im%20%3D%20_ax.imshow(C_all%2C%20cmap%3D%22RdYlGn_r%22%2C%20vmin%3D-1%2C%20vmax%3D1)%0A%20%20%20%20_ax.set_xticks(np.arange(len(all_species))%2C%20all_species%2C%20rotation%3D90)%0A%20%20%20%20_ax.set_yticks(np.arange(len(all_species))%2C%20all_species)%0A%20%20%20%20_ax.set_title(%22Beziehungen%20der%20Pflanzenarten%5Cn(gr%C3%BCn%20%3D%20freundlich%2C%20rot%20%3D%20feindlich)%22)%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%23%20Die%20konkrete%20Instanz%0A%0A%20%20%20%20Da%20wir%20QAOA%20auf%20einem%20klassischen%20Rechner%20**simulieren**%2C%20brauchen%20wir%20eine%20kleine%20Instanz%3A%0A%20%20%20%20Die%20Anzahl%20der%20Qubits%20w%C3%A4chst%20mit%20der%20Anzahl%20der%20T%C3%B6pfe%20mal%20der%20Anzahl%20der%20Pflanzenarten%0A%20%20%20%20(Details%20folgen%20in%20Teil%203)%2C%20und%20jedes%20zus%C3%A4tzliche%20Qubit%20verdoppelt%20den%20Speicherbedarf%20der%20Simulation.%0A%0A%20%20%20%20Unser%20Garten%20hat%20**%242%20%5Ctimes%202%24%20T%C3%B6pfe**%2C%20die%20in%20einem%20Quadrat%20angeordnet%20sind.%20Benachbarte%20T%C3%B6pfe%20(nicht%20diagonal)%20sind%20durch%20Kanten%20verbunden.%0A%20%20%20%20Wir%20pflanzen%20**2%20Tomaten%2C%201%20Gurke%20und%201%20Basilikum**.%20Tomate%20und%20Gurke%20vertragen%20sich%20schlecht%2C%20Basilikum%20und%20Tomate%20gut.%0A%0A%20%20%20%20Die%20Nachbarschaft%20der%20T%C3%B6pfe%20halten%20wir%20in%20einer%20Matrix%20%24J%24%20fest%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20J_%7Bii'%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%20%7D%20i%3Ci'%20%5Ctext%7B%20und%20die%20T%C3%B6pfe%20%7D%20i%20%5Ctext%7B%20und%20%7D%20i'%20%5Ctext%7B%20benachbart%20sind%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%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(C_all%2C%20all_species%2C%20np)%3A%0A%20%20%20%20k_cols%2C%20l_rows%20%3D%202%2C%202%20%20%23%20Gitter%20aus%20k%20Spalten%20und%20l%20Zeilen%0A%20%20%20%20pots%20%3D%20%5B(x%2C%20y)%20for%20x%20in%20range(k_cols)%20for%20y%20in%20range(l_rows)%5D%0A%20%20%20%20n_pots%20%3D%20len(pots)%0A%0A%20%20%20%20%23%20Nachbarschaftsmatrix%20J%20(nur%20obere%20Dreiecksmatrix%2C%20d.%20h.%20i%20%3C%20i')%0A%20%20%20%20J%20%3D%20np.zeros((n_pots%2C%20n_pots))%0A%20%20%20%20for%20_a%20in%20range(n_pots)%3A%0A%20%20%20%20%20%20%20%20for%20_b%20in%20range(_a%20%2B%201%2C%20n_pots)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20abs(pots%5B_a%5D%5B0%5D%20-%20pots%5B_b%5D%5B0%5D)%20%2B%20abs(pots%5B_a%5D%5B1%5D%20-%20pots%5B_b%5D%5B1%5D)%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20J%5B_a%2C%20_b%5D%20%3D%201%0A%0A%20%20%20%20%23%20Welche%20Pflanzen%20sollen%20gepflanzt%20werden%2C%20und%20wie%20oft%3F%0A%20%20%20%20species%20%3D%20%5B%22Tomato%22%2C%20%22Cucumber%22%2C%20%22Basil%22%5D%0A%20%20%20%20counts%20%3D%20%5B2%2C%201%2C%201%5D%0A%20%20%20%20n_species%20%3D%20len(species)%0A%20%20%20%20assert%20sum(counts)%20%3D%3D%20n_pots%0A%0A%20%20%20%20%23%20Beziehungsmatrix%20C%20nur%20f%C3%BCr%20die%20ausgew%C3%A4hlten%20Arten%3A%20C%5Bj%2C%20j'%5D%20mit%20j%2C%20j'%20in%200..n_species-1%0A%20%20%20%20_sel%20%3D%20%5Ball_species.index(s)%20for%20s%20in%20species%5D%0A%20%20%20%20C%20%3D%20C_all%5Bnp.ix_(_sel%2C%20_sel)%5D%0A%0A%20%20%20%20N%20%3D%20n_pots%20*%20n_species%20%20%23%20Anzahl%20der%20Qubits%20(siehe%20unten)%0A%20%20%20%20return%20C%2C%20J%2C%20N%2C%20counts%2C%20k_cols%2C%20l_rows%2C%20n_pots%2C%20n_species%2C%20pots%2C%20species%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(C%2C%20J%2C%20k_cols%2C%20l_rows%2C%20n_pots%2C%20plt%2C%20pots%2C%20species)%3A%0A%20%20%20%20def%20plot_garden(assignment%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Zeichnet%20den%20Garten.%20assignment%5Bi%5D%20ist%20der%20Artenindex%20in%20Topf%20i%20(oder%20None%20f%C3%BCr%20leere%20T%C3%B6pfe).%22%22%22%0A%20%20%20%20%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(1.9%20*%20k_cols%20%2B%200.5%2C%201.9%20*%20l_rows%20%2B%200.3))%0A%20%20%20%20%20%20%20%20_ax.axis(%22off%22)%0A%20%20%20%20%20%20%20%20_colors%20%3D%20%7B-1%3A%20%22tab%3Agreen%22%2C%200%3A%20%22gold%22%2C%201%3A%20%22tab%3Ared%22%7D%0A%20%20%20%20%20%20%20%20for%20_a%20in%20range(n_pots)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_b%20in%20range(_a%20%2B%201%2C%20n_pots)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20J%5B_a%2C%20_b%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_color%20%3D%20%22k%22%20if%20assignment%20is%20None%20else%20_colors%5Bint(C%5Bassignment%5B_a%5D%2C%20assignment%5B_b%5D%5D)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(*zip(pots%5B_a%5D%2C%20pots%5B_b%5D)%2C%20color%3D_color%2C%20lw%3D3%2C%20ls%3D%22--%22%20if%20assignment%20is%20None%20else%20%22-%22%2C%20zorder%3D0)%0A%20%20%20%20%20%20%20%20for%20_a%2C%20(_x%2C%20_y)%20in%20enumerate(pots)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_label%20%3D%20f%22Topf%20%7B_a%7D%22%20if%20assignment%20is%20None%20else%20species%5Bassignment%5B_a%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(_x%2C%20_y%2C%20_label%2C%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%20size%3D12%2C%20bbox%3Ddict(boxstyle%3D%22round%22%2C%20fc%3D%22w%22))%0A%20%20%20%20%20%20%20%20_ax.set_xlim(-0.5%2C%20k_cols%20-%200.5)%0A%20%20%20%20%20%20%20%20_ax.set_ylim(-0.5%2C%20l_rows%20-%200.5)%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_garden()%0A%20%20%20%20return%20(plot_garden%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%20Anordnungen%20einfach%20durchprobieren.%0A%20%20%20%20Das%20hilft%20uns%20sp%C3%A4ter%2C%20die%20Ergebnisse%20von%20QAOA%20zu%20%C3%BCberpr%C3%BCfen.%20Bei%20gro%C3%9Fen%20G%C3%A4rten%20ist%20das%20nat%C3%BCrlich%20unm%C3%B6glich.%0A%0A%20%20%20%20Die%20%E2%80%9EUnzufriedenheit%22%20einer%20Anordnung%20ist%20die%20Summe%20%C3%BCber%20alle%20Paare%20benachbarter%20T%C3%B6pfe%2C%20wobei%20ein%20Paar%0A%0A%20%20%20%20*%20%240%24%20z%C3%A4hlt%2C%20wenn%20die%20Arten%20**freundlich**%2C%0A%20%20%20%20*%20%241%24%2C%20wenn%20sie%20**neutral**%2C%0A%20%20%20%20*%20%242%24%2C%20wenn%20sie%20**feindlich**%20zueinander%20sind%20(also%20%24C_%7Bjj'%7D%2B1%24).%0A%0A%20%20%20%20Gesucht%20ist%20die%20Anordnung%20mit%20der%20**kleinsten%20Unzufriedenheit**.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(C%2C%20J%2C%20N%2C%20counts%2C%20itertools%2C%20n_pots%2C%20n_species%2C%20np)%3A%0A%20%20%20%20def%20unhappiness(assignment)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Unzufriedenheit%20einer%20Anordnung.%20assignment%5Bi%5D%20ist%20der%20Artenindex%20in%20Topf%20i.%22%22%22%0A%20%20%20%20%20%20%20%20return%20sum(%0A%20%20%20%20%20%20%20%20%20%20%20%20C%5Bassignment%5Ba%5D%2C%20assignment%5Bb%5D%5D%20%2B%201%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20a%20in%20range(n_pots)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20b%20in%20range(a%20%2B%201%2C%20n_pots)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20J%5Ba%2C%20b%5D%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20alle%20g%C3%BCltigen%20Anordnungen%3A%20jede%20Art%20j%20genau%20counts%5Bj%5D-mal%0A%20%20%20%20_multiset%20%3D%20%5Bj%20for%20j%20in%20range(n_species)%20for%20_%20in%20range(counts%5Bj%5D)%5D%0A%20%20%20%20valid_assignments%20%3D%20sorted(set(itertools.permutations(_multiset)))%0A%20%20%20%20best_unhappiness%20%3D%20min(unhappiness(a)%20for%20a%20in%20valid_assignments)%0A%20%20%20%20best_assignments%20%3D%20%5Ba%20for%20a%20in%20valid_assignments%20if%20unhappiness(a)%20%3D%3D%20best_unhappiness%5D%0A%0A%20%20%20%20%23%20Alle%202%5EN%20Bitstrings%20(Wire%2FQubit%200%20steht%20ganz%20links%2C%20wie%20in%20PennyLane)%0A%20%20%20%20bits%20%3D%20(np.arange(2**N)%5B%3A%2C%20None%5D%20%3E%3E%20np.arange(N%20-%201%2C%20-1%2C%20-1))%20%26%201%0A%0A%20%20%20%20def%20assignment_to_index(assignment)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Index%20des%20Bitstrings%20in%20%60bits%60%2C%20der%20zu%20einer%20Anordnung%20geh%C3%B6rt%20(Topf%20i%2C%20Art%20j%20-%3E%20Qubit%20i*n_species%2Bj).%22%22%22%0A%20%20%20%20%20%20%20%20return%20sum(2%20**%20(N%20-%201%20-%20(i%20*%20n_species%20%2B%20j))%20for%20i%2C%20j%20in%20enumerate(assignment))%0A%0A%20%20%20%20valid_mask%20%3D%20np.zeros(2**N%2C%20dtype%3Dbool)%0A%20%20%20%20valid_mask%5B%5Bassignment_to_index(a)%20for%20a%20in%20valid_assignments%5D%5D%20%3D%20True%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20best_assignments%2C%0A%20%20%20%20%20%20%20%20best_unhappiness%2C%0A%20%20%20%20%20%20%20%20bits%2C%0A%20%20%20%20%20%20%20%20unhappiness%2C%0A%20%20%20%20%20%20%20%20valid_assignments%2C%0A%20%20%20%20%20%20%20%20valid_mask%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(best_assignments%2C%20best_unhappiness%2C%20mo%2C%20plot_garden%2C%20valid_assignments)%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%22Es%20gibt%20%7Blen(valid_assignments)%7D%20verschiedene%20Anordnungen%2C%20davon%20sind%20%7Blen(best_assignments)%7D%20optimal%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22mit%20Unzufriedenheit%20%7Bbest_unhappiness%7D.%20Eine%20davon%3A%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%20plot_garden(best_assignments%5B0%5D)%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%20f%C3%BCr%20QAOA%20aufbereiten%2C%20lernen%20Sie%20den%20Algorithmus%20kennen.%0A%20%20%20%20Die%20Gartenaufgabe%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%20ein%20Problem%20mit%20%24N%24%20bin%C3%A4ren%20Variablen%20%24x%20%5Cin%20%5C%7B0%2C1%5C%7D%5EN%24%20und%20einer%20Kostenfunktion%20%24E(x)%24%2C%20die%20wir%20**minimieren**%20m%C3%B6chten.%0A%20%20%20%20Wir%20ordnen%20jedem%20Bitstring%20%24x%24%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)%20entspricht%20der%20**optimalen%20L%C3%B6sung**.%20Das%20Optimierungsproblem%20ist%20damit%20zur%20Suche%20nach%20einem%20Grundzustand%20geworden.%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%20Dazu%20nutzt%20man%2C%20dass%20%24Z%7Cx%5Crangle%20%3D%20(-1)%5Ex%20%7Cx%5Crangle%24%2C%20also%20%24x_u%20%3D%20%5Cfrac%7B1%20-%20Z_u%7D%7B2%7D%24.%0A%20%20%20%20Das%20ergibt%20einen%20**Ising-Hamilton-Operator**%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%20Wir%20kennen%20den%20Grundzustand%20von%20%24H_C%24%20nicht%20(sonst%20w%C3%A4re%20das%20Problem%20gel%C3%B6st)%2C%20aber%20wir%20k%C3%B6nnen%20einen%20Zustand%20**vorbereiten%20und%20messen**.%0A%20%20%20%20QAOA%20bereitet%20mit%20einem%20Schaltkreis%20aus%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%20Jede%20Schicht%20besteht%20aus%20zwei%20Teilen%3A%0A%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%20gibt%20diese%20Schicht%20jedem%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%20dadurch%20die%20Basiszust%C3%A4nde.%0A%20%20%20%20%20%20Erst%20durch%20dieses%20Mischen%20wird%20aus%20den%20Phasenunterschieden%20*Interferenz*%3A%0A%20%20%20%20%20%20Zust%C3%A4nde%20mit%20niedrigen%20Kosten%20werden%20verst%C3%A4rkt%2C%20andere%20abgeschw%C3%A4cht.%0A%0A%20%20%20%20Der%20Startzustand%20%24%7C%2B%5Crangle%5E%7B%5Cotimes%20N%7D%24%20ist%20die%20gleichm%C3%A4%C3%9Fige%20Superposition%20aller%20Bitstrings.%0A%0A%20%20%20%20%23%23%202.3%20Der%20hybride%20Optimierungskreislauf%0A%0A%20%20%20%20Welche%20Parameter%20%24(%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D)%24%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%20Quantenschaltkreis%20liefert%20die%20Wahrscheinlichkeiten%20%24p(x)%24%20der%20Bitstrings.%0A%20%20%20%202.%20Daraus%20berechnet%20man%20den%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(hier%3A%20Gradientenabstieg%20mit%20Adam%2C%20wie%20in%20der%20PennyLane-Einf%C3%BChrung)%20passt%20%24(%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D)%24%20an%2C%20sodass%20%24%5Clangle%20H_C%20%5Crangle%24%20sinkt.%0A%20%20%20%204.%20Am%20Ende%20wird%20der%20Schaltkreis%20oft%20gemessen%2C%20und%20der%20beste%20gefundene%20Bitstring%20ist%20(mit%20hoher%20Wahrscheinlichkeit)%20die%20L%C3%B6sung.%0A%0A%20%20%20%20Ist%20%24%5Clangle%20H_C%20%5Crangle%24%20klein%2C%20steckt%20viel%20Wahrscheinlichkeit%20in%20Zust%C3%A4nden%20mit%20niedrigen%20Kosten.%0A%20%20%20%20Mit%20einem%20Quantencomputer%20m%C3%BCssten%20wir%20%24%5Clangle%20H_C%20%5Crangle%24%20aus%20Messungen%20sch%C3%A4tzen%2C%0A%20%20%20%20im%20Simulator%20rechnen%20wir%20direkt%20mit%20den%20exakten%20Wahrscheinlichkeiten.%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**%2C%20das%20auch%20ein%20D-Wave-Annealer%20realisiert%3A%0A%20%20%20%20Dort%20wird%20langsam%20von%20%24H_M%24%20(Grundzustand%20%24%7C%2B%5Crangle%5E%7B%5Cotimes%20N%7D%24)%20zu%20%24H_C%24%20%C3%BCbergeblendet.%20Nach%20dem%20adiabatischen%20Theorem%0A%20%20%20%20bleibt%20das%20System%20dabei%20im%20Grundzustand%2C%20wenn%20es%20langsam%20genug%20geschieht.%0A%20%20%20%20QAOA%20ersetzt%20die%20kontinuierliche%20Entwicklung%20durch%20%24p%24%20abwechselnde%20Schritte%0A%20%20%20%20und%20l%C3%A4sst%20den%20Optimierer%20die%20%E2%80%9ESchrittl%C3%A4ngen%22%20%24%5Cgamma_l%2C%20%5Cbeta_l%24%20w%C3%A4hlen.%20F%C3%BCr%20%24p%20%5Cto%20%5Cinfty%24%20l%C3%A4sst%20sich%20die%20adiabatische%20Entwicklung%20beliebig%20genau%20nachbilden%2C%0A%20%20%20%20f%C3%BCr%20kleine%20%24p%24%20ist%20QAOA%20ein%20*N%C3%A4herungsverfahren*%20mit%20nur%20%242p%24%20Parametern.%0A%20%20%20%20Das%20macht%20es%20f%C3%BCr%20heutige%20Quantencomputer%20interessant%2C%20bei%20denen%20Schaltkreise%20kurz%20bleiben%20m%C3%BCssen.%0A%0A%20%20%20%20%23%23%202.5%20Von%20den%20Operatoren%20zu%20den%20Gattern%0A%0A%20%20%20%20F%C3%BCr%20die%20Umsetzung%20brauchen%20wir%20die%20Gatter%2C%20die%20die%20drei%20Faktoren%20realisieren.%0A%20%20%20%20In%20PennyLane%20gilt%20%24R_Z(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20Z%2F2%7D%24%2C%20%24R_X(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20X%2F2%7D%24%20und%20%24%5Ctext%7BIsingZZ%7D(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%5C%2C%20Z%5Cotimes%20Z%2F2%7D%24.%0A%20%20%20%20Da%20alle%20Terme%20in%20%24H_C%24%20untereinander%20kommutieren%2C%20l%C3%A4sst%20sich%20%24e%5E%7B-i%5Cgamma%20H_C%7D%24%20exakt%20als%20Produkt%20einzelner%20Gatter%20schreiben%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20e%5E%7B-i%5Cgamma%20H_C%7D%20%5C%3B%5Csimeq%5C%3B%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%20e%5E%7B-i%5Cbeta%20H_M%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(bis%20auf%20eine%20globale%20Phase%20durch%20die%20Konstante).%20Welche%20Gatter-Winkel%20dazu%20geh%C3%B6ren%2C%20finden%20Sie%20in%20Teil%205%20selbst%20heraus.%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%20Damit%20der%20Optimierer%20mit%20dem%20Problem%20arbeiten%20kann%2C%20brauchen%20wir%20bin%C3%A4re%20Variablen.%0A%20%20%20%20Bei%20%24n%24%20T%C3%B6pfen%20%24i%20%3D%200..n-1%24%20und%20%24t%24%20Pflanzenarten%20%24j%20%3D%200..t-1%24%20definieren%20wir%0A%0A%20%20%20%20%24%24%0A%20%20%20%20x_%7Bij%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%20Pflanze%20%7D%20j%20%5Ctext%7B%20in%20Topf%20%7D%20i%20%5Ctext%7B%20gepflanzt%20werden%20soll%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%20einer%20ganzen%20Zahl%20(Pflanzenart)%20in%20mehrere%20Bits%20hei%C3%9Ft%20%5B*One-Hot-Kodierung*%5D(https%3A%2F%2Fde.wikipedia.org%2Fwiki%2F1-aus-n-Code)%3A%0A%20%20%20%20Pro%20Topf%20darf%20genau%20ein%20Bit%20%E2%80%9Ehei%C3%9F%22%20(%241%24)%20sein.%0A%20%20%20%20Der%20Vektor%20%24%5Cmathbf%7Bx%7D%20%3D%20(x_%7B0%2C0%7D%2C%20x_%7B0%2C1%7D%2C%20%5Cldots%2C%20x_%7Bn-1%2Ct-1%7D)%24%20enth%C3%A4lt%20alle%20Variablen%2C%20**jede%20Variable%20ist%20ein%20Qubit**.%0A%0A%20%20%20%20Eine%20L%C3%B6sung%20des%20Problems%20ist%20eine%20Belegung%20von%20%24%5Cmathbf%7Bx%7D%24%2C%20die%0A%20%20%20%201.%20jeden%20Topf%20%24i%24%20mit%20**genau%20einer**%20Pflanze%20f%C3%BCllt%2C%0A%20%20%20%202.%20jede%20Art%20%24j%24%20**genau%20%24c_j%24-mal**%20pflanzt%2C%0A%20%20%20%203.%20die%20**Unzufriedenheit**%20minimiert.%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%3D1000%2C%20value%3D0%2C%20label%3D%22Anzahl%20Qubits%20N%20%3D%22)%0A%20%20%20%20q_ones%20%3D%20mo.ui.number(start%3D0%2C%20stop%3D1000%2C%20value%3D0%2C%20label%3D%22Einsen%20in%20einer%20g%C3%BCltigen%20L%C3%B6sung%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%20Unsere%20Instanz%20hat%20%24n%20%3D%204%24%20T%C3%B6pfe%20und%20%24t%20%3D%203%24%20Pflanzenarten.%0A%0A%20%20%20%201.%20Wie%20viele%20Bits%20(%3D%20Qubits)%20hat%20der%20Vektor%20%24%5Cmathbf%7Bx%7D%24%3F%0A%20%20%20%202.%20Angenommen%2C%20die%20Bedingungen%20(1)%20und%20(2)%20sind%20erf%C3%BCllt.%20Wie%20viele%20Eintr%C3%A4ge%20von%20%24%5Cmathbf%7Bx%7D%24%20sind%20dann%20%241%24%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_ones%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%20q_bits%2C%20q_ones%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(N%2C%20mo%2C%20n_pots%2C%20q_bits%2C%20q_ones)%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)%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_ones.value%20%3D%3D%20n_pots)%7D%20Anzahl%20Einsen%20%3D%20%7Bq_ones.value%7D%22%0A%20%20%20%20)%20if%20(q_bits.value%20or%20q_ones.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(Topf%20%24i%24%2C%20Art%20%24j%24)%20und%20dem%20Qubit-Index%20%24u%20%5Cin%20%5C%7B0%2C%20%5Cdots%2C%20nt-1%5C%7D%24.%0A%20%20%20%20Qubit%20%24u%24%20entspricht%20dann%20der%20Variablen%20%24x_%7Bij%7D%24.%20Ordnen%20Sie%20die%20Variablen%20**topfweise**%3A%20erst%20alle%20Arten%20von%20Topf%200%2C%20dann%20alle%20von%20Topf%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(i%2C%20j%2C%20n_species)%60%2C%20das%20jedes%20Paar%20%24(i%2Cj)%24%20auf%20eine%20Zahl%20in%20%240..(nt-1)%24%20abbildet.%0A%0A%20%20%20%20**b)**%20Schreiben%20Sie%20die%20Umkehrfunktion%20%60decode(u%2C%20n_species)%60%2C%20die%20%24u%24%20wieder%20in%20%24(i%2Cj)%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(i%2C%20j%2C%20n_species)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Bildet%20(Topf%20i%2C%20Art%20j)%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_species)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Bildet%20den%20Qubit-Index%20u%20auf%20(Topf%20i%2C%20Art%20j)%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_pots%2C%20n_species%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_i%20in%20range(n_pots)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_j%20in%20range(n_species)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_u%20%3D%20encode(_i%2C%20_j%2C%20n_species)%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_pots%20*%20n_species%2C%20f%22encode(%7B_i%7D%2C%20%7B_j%7D)%20%3D%20%7B_u%7D%20liegt%20nicht%20in%200..%7Bn_pots%20*%20n_species%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_species)%20%3D%3D%20(_i%2C%20_j)%2C%20f%22decode(encode(%7B_i%7D%2C%20%7B_j%7D))%20liefert%20%7Bdecode(_u%2C%20n_species)%7D.%22%0A%20%20%20%20%20%20%20%20assert%20len(_seen)%20%3D%3D%20n_pots%20*%20n_species%2C%20%22Verschiedene%20Paare%20(i%2C%20j)%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%20Jeden%20Topf%20f%C3%BCllen%0A%0A%20%20%20%20Wir%20bauen%20nun%20die%20drei%20Bestandteile%20der%20Kostenfunktion.%20Zuerst%20die%20Nebenbedingung%20(1).%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_i(%5Cmathbf%7Bx%7D)%24%2C%20der%20%240%24%20ergibt%2C%20wenn%20in%20Topf%20%24i%24%20**genau%20eine**%20Pflanze%20steht%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%2C%20das%20%240%24%20ergibt%2C%20wenn%20**jeder**%20Topf%20genau%20eine%20Pflanze%20enth%C3%A4lt.%0A%0A%20%20%20%20**c)**%20Multiplizieren%20Sie%20die%20Quadrate%20aus%20und%20sortieren%20Sie%20nach%20linearen%20und%20quadratischen%20Termen%20und%20konstanten%20Termen.%0A%0A%20%20%20%20*Tipp%3A*%20%24x_%7Bij%7D%24%20ist%20bin%C3%A4r%2C%20also%20gilt%20%24x_%7Bij%7D%5E2%20%3D%20x_%7Bij%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_i(%5Cmathbf%7Bx%7D)%20%3D%20%5CBig(%5Csum_j%20x_%7Bij%7D%20-%201%5CBig)%5E2%2C%20%5Cqquad%20k(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_i%20k_i(%5Cmathbf%7Bx%7D)%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Ausmultiplizieren%20und%20%24x_%7Bij%7D%5E2%20%3D%20x_%7Bij%7D%24%20verwenden%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24k(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_i%20%5CBig(%20-%5Csum_j%20x_%7Bij%7D%20%2B%202%5Csum_%7Bj%3Cj'%7D%20x_%7Bij%7Dx_%7Bij'%7D%20%2B%201%20%5CBig)%0A%20%20%20%20%20%20%20%20%20%20%20%20%3D%20-%5Csum_%7Bi%2Cj%7D%20x_%7Bij%7D%20%2B%202%5Csum_i%20%5Csum_%7Bj%3Cj'%7D%20x_%7Bij%7Dx_%7Bij'%7D%20%2B%20n%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Es%20gibt%20also%20einen%20linearen%20Teil%2C%20einen%20quadratischen%20Teil%20und%20die%20Konstante%20%24n%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%20(die%20von%20keinem%20%24x%24%20abh%C3%A4ngen)%20sammeln%20wir%20als%20%60offset%60.%0A%0A%20%20%20%20Implementieren%20Sie%20%60add_fill_every_pot%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_fill_every_pot(Q%2C%20lam%2C%20n_pots%2C%20n_species)%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_(i1%2Cj1)%20*%20x_(i2%2Cj2)%3A%0A%20%20%20%20%23%20%20%20u1%20%3D%20encode(i1%2C%20j1%2C%20n_species)%0A%20%20%20%20%23%20%20%20u2%20%3D%20encode(i2%2C%20j2%2C%20n_species)%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_(N%2C%20mo%2C%20n_pots%2C%20n_species%2C%20np%2C%20ok_codec%2C%20run_check)%3A%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%20N))%0A%20%20%20%20%20%20%20%20_off1%20%3D%20add_fill_every_pot(_Q1%2C%201%2C%20n_pots%2C%20n_species)%0A%20%20%20%20%20%20%20%20_Q3%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20_off3%20%3D%20add_fill_every_pot(_Q3%2C%203%2C%20n_pots%2C%20n_species)%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%20Pflanze%20pro%20Topf%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_pots%2C%20n_species)%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%5Bnp.arange(n_pots)%2C%20_rng.integers(0%2C%20n_species%2C%20n_pots)%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%20assert%20np.isclose(_energy(_Q1%2C%20_off1%2C%20_x)%2C%200)%2C%20%22F%C3%BCr%20Belegungen%20mit%20genau%20einer%20Pflanze%20pro%20Topf%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%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.all(_x.reshape(n_pots%2C%20n_species).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%22F%C3%BCr%20Belegungen%2C%20bei%20denen%20ein%20Topf%20nicht%20genau%20eine%20Pflanze%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%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_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%20Jede%20Pflanze%20einsetzen%0A%0A%20%20%20%20Nun%20die%20Nebenbedingung%20(2)%3A%20Art%20%24j%24%20soll%20genau%20%24c_j%24-mal%20im%20Garten%20vorkommen.%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**%20Finden%20Sie%20%24l_j(%5Cmathbf%7Bx%7D)%24%2C%20das%20%240%24%20ergibt%2C%20wenn%20Art%20%24j%24%20genau%20%24c_j%24-mal%20gepflanzt%20wird%20(sonst%20gr%C3%B6%C3%9Fere%20Werte)%2C%0A%20%20%20%20bilden%20Sie%20%24l(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_j%20l_j(%5Cmathbf%7Bx%7D)%24%20und%20multiplizieren%20Sie%20aus.%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20%60add_plant_every_plant%60.%20Die%20Liste%20%60counts%60%20enth%C3%A4lt%20die%20H%C3%A4ufigkeiten%20%24c_j%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%22%3A%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24l_j(%5Cmathbf%7Bx%7D)%20%3D%20%5CBig(%5Csum_i%20x_%7Bij%7D%20-%20c_j%5CBig)%5E2%2C%20%5Cqquad%20l(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_j%20l_j(%5Cmathbf%7Bx%7D)%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24l(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_%7Bi%2Cj%7D%20(1%20-%202c_j)%5C%2C%20x_%7Bij%7D%20%2B%202%5Csum_j%20%5Csum_%7Bi%3Ci'%7D%20x_%7Bij%7Dx_%7Bi'j%7D%20%2B%20%5Csum_j%20c_j%5E2%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.function%0Adef%20add_plant_every_plant(Q%2C%20lam%2C%20n_pots%2C%20n_species%2C%20counts)%3A%0A%20%20%20%20%22%22%22Addiert%20lam%20*%20l(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(l)%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_(N%2C%20counts%2C%20mo%2C%20n_pots%2C%20n_species%2C%20np%2C%20ok_codec%2C%20run_check)%3A%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(1)%0A%20%20%20%20%20%20%20%20_Q1%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20_off1%20%3D%20add_plant_every_plant(_Q1%2C%201%2C%20n_pots%2C%20n_species%2C%20counts)%0A%20%20%20%20%20%20%20%20_Q3%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20_off3%20%3D%20add_plant_every_plant(_Q3%2C%203%2C%20n_pots%2C%20n_species%2C%20counts)%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%20Art%20j%20kommt%20genau%20counts%5Bj%5D-mal%20vor%20(die%20T%C3%B6pfe%20sind%20egal)%3A%20l(x)%20muss%200%20sein%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20np.zeros((n_pots%2C%20n_species)%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_j%20in%20range(n_species)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_x%5B_rng.choice(n_pots%2C%20counts%5B_j%5D%2C%20replace%3DFalse)%2C%20_j%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%22Wenn%20jede%20Art%20genau%20c_j-mal%20vorkommt%2C%20muss%20l(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%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.all(_x.reshape(n_pots%2C%20n_species).sum(axis%3D0)%20%3D%3D%20counts)%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%20eine%20Art%20nicht%20genau%20c_j-mal%20vorkommt%2C%20muss%20l(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_l%2C%20_result%20%3D%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_result%0A%20%20%20%20return%20(ok_l%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.4%3A%20Die%20Unzufriedenheit%20minimieren%0A%0A%20%20%20%20Nun%20die%20eigentliche%20Zielfunktion%20(3).%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)**%20Betrachten%20Sie%20zwei%20benachbarte%20T%C3%B6pfe%20%24i%2C%20i'%24%20und%20zwei%20Arten%20%24j%2C%20j'%24.%20Finden%20Sie%20einen%20Ausdruck%20%24E(x_%7Bij%7D%2C%20x_%7Bi'j'%7D)%24%2C%20der%20%240%24%2C%20%241%24%20bzw.%20%242%24%20ergibt%2C%20wenn%20die%20Arten%20freundlich%20(%24C_%7Bjj'%7D%3D-1%24)%2C%20neutral%20(%240%24)%20bzw.%20feindlich%20(%24%2B1%24)%20sind%0A%20%20%20%20und%20beide%20Pflanzen%20tats%C3%A4chlich%20dort%20stehen%20(%24x_%7Bij%7D%20%3D%20x_%7Bi'j'%7D%20%3D%201%24)%2C%20und%20sonst%20%240%24.%0A%0A%20%20%20%20**b)**%20Summieren%20Sie%20%C3%BCber%20alle%20Topfpaare%20und%20Artenpaare%2C%20aber%20nur%20%C3%BCber%20**benachbarte**%20T%C3%B6pfe%20(verwenden%20Sie%20%24J%24)%2C%20zu%20%24E(%5Cmathbf%7Bx%7D)%24.%0A%0A%20%20%20%20**c)**%20Wie%20vereinfacht%20sich%20der%20Ausdruck%2C%20wenn%20die%20Nebenbedingung%20(1)%20erf%C3%BCllt%20ist%20(dann%20ist%20%24%5Csum_%7Bj%2Cj'%7D%20x_%7Bij%7Dx_%7Bi'j'%7D%20%3D%201%24)%3F%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20%60add_unhappiness%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%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(x_%7Bij%7D%2C%20x_%7Bi'j'%7D)%20%3D%20(C_%7Bjj'%7D%20%2B%201)%5C%2C%20x_%7Bij%7D%5C%2C%20x_%7Bi'j'%7D%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20b)%20%24E(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_%7Bi%2Ci'%7D%20J_%7Bii'%7D%20%5Csum_%7Bj%2Cj'%7D%20(C_%7Bjj'%7D%20%2B%201)%5C%2C%20x_%7Bij%7D%5C%2C%20x_%7Bi'j'%7D%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20c)%20Bei%20erf%C3%BCllter%20Nebenbedingung%20(1)%20gilt%20%24%5Csum_%7Bj%2Cj'%7D%20x_%7Bij%7Dx_%7Bi'j'%7D%20%3D%201%24%20f%C3%BCr%20jedes%20Topfpaar.%20Daher%20l%C3%A4sst%20sich%20der%20Summand%20%24%2B1%24%20als%20Konstante%20abspalten%3A%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%24%24E(%5Cmathbf%7Bx%7D)%20%3D%20%5Csum_%7Bi%2Ci'%7D%20J_%7Bii'%7D%20%5Csum_%7Bj%2Cj'%7D%20C_%7Bjj'%7D%5C%2C%20x_%7Bij%7D%5C%2C%20x_%7Bi'j'%7D%20%2B%20%5Csum_%7Bi%2Ci'%7D%20J_%7Bii'%7D%24%24%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20Diese%20Vereinfachung%20ist%20nur%20im%20erlaubten%20Unterraum%20korrekt.%20Das%20ist%20in%20Ordnung%2C%20weil%20wir%20dort%20ohnehin%20durch%20den%20Strafterm%20%24k%24%20landen%20wollen.%0A%20%20%20%20%20%20%20%20%20%20%20%20(Sie%20k%C3%B6nnen%20die%20%24%2B1%24%20auch%20im%20quadratischen%20Term%20lassen%2C%20dann%20ist%20der%20Offset%20%240%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.function%0Adef%20add_unhappiness(Q%2C%20J%2C%20C%2C%20n_pots%2C%20n_species)%3A%0A%20%20%20%20%22%22%22Addiert%20E(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(E)%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_(C%2C%20J%2C%20N%2C%20mo%2C%20n_pots%2C%20n_species%2C%20np%2C%20ok_codec%2C%20run_check%2C%20unhappiness)%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(2)%0A%20%20%20%20%20%20%20%20_Q%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20_off%20%3D%20add_unhappiness(_Q%2C%20J%2C%20C%2C%20n_pots%2C%20n_species)%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%20Anordnung%20mit%20genau%20einer%20Pflanze%20pro%20Topf%20(die%20Anzahl%20pro%20Art%20ist%20egal)%0A%20%20%20%20%20%20%20%20%20%20%20%20_assignment%20%3D%20_rng.integers(0%2C%20n_species%2C%20n_pots)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%20%3D%20np.zeros((n_pots%2C%20n_species)%2C%20dtype%3Dint)%0A%20%20%20%20%20%20%20%20%20%20%20%20_x%5Bnp.arange(n_pots)%2C%20_assignment%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_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%20unhappiness(_assignment))%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22F%C3%BCr%20die%20Anordnung%20%7Blist(_assignment)%7D%20sollte%20E(x)%20%3D%20%7Bunhappiness(_assignment)%7D%20sein%2C%20Ihr%20Code%20liefert%20%7B_e%7D.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_E%2C%20_result%20%3D%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_result%0A%20%20%20%20return%20(ok_E%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%20Wir%20haben%20nun%20die%20Terme%20%24E%24%2C%20%24k%24%20und%20%24l%24.%20Haben%20wir%20damit%20schon%20ein%20QUBO%3F%20Das%20%E2%80%9EQ%22%20f%C3%BCr%20*quadratisch*%20ist%20erf%C3%BCllt%2C%0A%20%20%20%20denn%20kein%20Term%20enth%C3%A4lt%20ein%20Produkt%20aus%20drei%20oder%20mehr%20Variablen.%20Die%20Variablen%20sind%20bin%C3%A4r%20(%E2%80%9EB%22).%20Aber%20noch%20stehen%20die%0A%20%20%20%20**Nebenbedingungen**%20(1)%20und%20(2)%20im%20Weg%2C%20ein%20QUBO%20ist%20*unconstrained*%20(%E2%80%9EU%22).%0A%0A%20%20%20%20Die%20L%C3%B6sung%3A%20**Strafterme**%20(Penalty).%20Wir%20addieren%20die%20Nebenbedingungen%2C%20mit%20gro%C3%9Fem%20Faktor%2C%20zur%20Zielfunktion.%0A%20%20%20%20Wird%20eine%20Bedingung%20verletzt%2C%20steigt%20die%20Energie%20stark%20an%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20Q(%5Cmathbf%7Bx%7D)%20%3D%20E(%5Cmathbf%7Bx%7D)%20%2B%20%5Clambda_1%5C%2C%20k(%5Cmathbf%7Bx%7D)%20%2B%20%5Clambda_2%5C%2C%20l(%5Cmathbf%7Bx%7D)%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Die%20%24%5Clambda%24%20m%C3%BCssen%20gro%C3%9F%20genug%20sein%2C%20damit%20**jede%20g%C3%BCltige%20L%C3%B6sung%20eine%20niedrigere%20Energie%20hat%20als%20jede%20ung%C3%BCltige**.%0A%20%20%20%20Wir%20w%C3%A4hlen%20zun%C3%A4chst%20%24%5Clambda_1%20%3D%20%5Clambda_2%20%3D%202%24.%0A%20%20%20%20Die%20Funktion%20%60build_qubo%60%20fasst%20Ihre%20drei%20Bausteine%20zusammen.%20Sie%20liefert%20die%20QUBO-Matrix%20(als%20obere%20Dreiecksmatrix%2C%20d.%20h.%20%60Q%5Bu%2C%20v%5D%60%20mit%20%24u%20%5Cle%20v%24)%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%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(C%2C%20J%2C%20N%2C%20bits%2C%20counts%2C%20n_pots%2C%20n_species%2C%20np)%3A%0A%20%20%20%20def%20build_qubo(lam1%2C%20lam2)%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_fill_every_pot(Q%2C%20lam1%2C%20n_pots%2C%20n_species)%0A%20%20%20%20%20%20%20%20offset%20%2B%3D%20add_plant_every_plant(Q%2C%20lam2%2C%20n_pots%2C%20n_species%2C%20counts)%0A%20%20%20%20%20%20%20%20offset%20%2B%3D%20add_unhappiness(Q%2C%20J%2C%20C%2C%20n_pots%2C%20n_species)%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%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%20LAM1%20%3D%20LAM2%20%3D%202%0A%20%20%20%20return%20LAM1%2C%20LAM2%2C%20build_qubo%2C%20qubo_energies%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20LAM1%2C%0A%20%20%20%20LAM2%2C%0A%20%20%20%20best_unhappiness%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_E%2C%0A%20%20%20%20ok_k%2C%0A%20%20%20%20ok_l%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_l%20and%20ok_E)%2C%0A%20%20%20%20%20%20%20%20mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.4%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(LAM1%2C%20LAM2)%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%20assert%20np.isclose(E_all%5Bvalid_mask%5D.min()%2C%20best_unhappiness)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Die%20kleinste%20Energie%20unter%20den%20g%C3%BCltigen%20Anordnungen%20stimmt%20nicht%20mit%20der%20besten%20Unzufriedenheit%20%C3%BCberein.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20assert%20E_all%5B~valid_mask%5D.min()%20%3E%20E_all%5Bvalid_mask%5D.min()%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Es%20gibt%20eine%20ung%C3%BCltige%20Belegung%20mit%20einer%20Energie%2C%20die%20nicht%20gr%C3%B6%C3%9Fer%20ist%20als%20die%20der%20besten%20g%C3%BCltigen.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Pr%C3%BCfen%20Sie%20Ihre%20Strafterme%20(oder%20w%C3%A4hlen%20Sie%20gr%C3%B6%C3%9Fere%20%CE%BB).%22%0A%20%20%20%20%20%20%20%20)%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%20der%20Matrix%20ist%20eine%20Kopplung%20zwischen%20zwei%20Qubits.%20Die%20dichten%20Bl%C3%B6cke%20entstehen%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22durch%20die%20Nebenbedingungen%20(Qubits%20desselben%20Topfes%20bzw.%20derselben%20Art%20sind%20gekoppelt).%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.5%3A%20Das%20QUBO%20exakt%20l%C3%B6sen%0A%0A%20%20%20%20Bei%20%24N%20%3D%2012%24%20Qubits%20gibt%20es%20nur%20%242%5E%7B12%7D%20%3D%204096%24%20Bitstrings%2C%20wir%20k%C3%B6nnen%20also%20einfach%20**alle**%20Energien%20berechnen%20(das%20steckt%20oben%20in%20%60E_all%60)%0A%20%20%20%20und%20den%20Grundzustand%20direkt%20finden.%20Das%20ist%20unsere%20Vergleichsbasis%20f%C3%BCr%20QAOA%2C%20funktioniert%20aber%20nur%20f%C3%BCr%20kleine%20%24N%24.%0A%20%20%20%20Die%20Funktion%20%60is_valid%60%20pr%C3%BCft%2C%20ob%20ein%20Bitstring%20die%20Nebenbedingungen%20erf%C3%BCllt.%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(x%2C%20n_pots%2C%20n_species%2C%20counts)%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.%20in%20**jedem%20Topf%20genau%20eine**%20Pflanze%20steht%20und%0A%20%20%20%202.%20**jede%20Art%20%24j%24%20genau%20%60counts%5Bj%5D%60-mal**%20vorkommt.%0A%0A%20%20%20%20*Tipp%3A*%20%60x.reshape(n_pots%2C%20n_species)%60%20sortiert%20die%20Bits%20in%20eine%20Tabelle%20(Zeile%20%3D%20Topf%2C%20Spalte%20%3D%20Art).%20Dann%20hilft%20%60sum(axis%3D...)%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(x%2C%20n_pots%2C%20n_species%2C%20counts)%3A%0A%20%20%20%20%22%22%22True%2C%20wenn%20der%20Bitstring%20x%20alle%20Nebenbedingungen%20erf%C3%BCllt.%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%20counts%2C%20mo%2C%20n_pots%2C%20n_species%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(bits%5B_s%5D%2C%20n_pots%2C%20n_species%2C%20counts)%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%20den%20Bitstring%20%7B''.join(map(str%2C%20bits%5B_s%5D))%7D%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%20run_check(_test)%20if%20ok_qubo%20else%20(False%2C%20mo.callout(mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.4.%22)%2C%20kind%3D%22neutral%22))%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_(%0A%20%20%20%20E_all%2C%0A%20%20%20%20best_unhappiness%2C%0A%20%20%20%20bits%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20n_pots%2C%0A%20%20%20%20n_species%2C%0A%20%20%20%20np%2C%0A%20%20%20%20ok_qubo%2C%0A%20%20%20%20ok_valid%2C%0A%20%20%20%20plot_garden%2C%0A)%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_example%20%3D%20bits%5B_gs%5B0%5D%5D.reshape(n_pots%2C%20n_species).argmax(axis%3D1)%20%20%23%20Art%20pro%20Topf%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%22Der%20Grundzustand%20des%20QUBO%20hat%20die%20Energie%20**%7BE_all.min()%3A.0f%7D**%20(beste%20Unzufriedenheit%3A%20%7Bbest_unhappiness%7D).%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22Es%20gibt%20**%7Blen(_gs)%7D**%20Bitstrings%20mit%20dieser%20Energie.%20Der%20Grundzustand%20ist%20*entartet*%2C%20denn%20die%20T%C3%B6pfe%20und%20Tomaten%20lassen%20sich%20vertauschen%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22und%20das%20Gitter%20l%C3%A4sst%20sich%20drehen%20und%20spiegeln%2C%20ohne%20dass%20sich%20die%20Unzufriedenheit%20%C3%A4ndert.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%5Cn%5CnBeispiel%20f%C3%BCr%20einen%20Grundzustand%3A%20%60%7B''.join(map(str%2C%20bits%5B_gs%5B0%5D%5D))%7D%60%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%20plot_garden(_example)%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%23%20Experiment%3A%20Wie%20gro%C3%9F%20m%C3%BCssen%20die%20Strafterme%20sein%3F%0A%0A%20%20%20%20Ver%C3%A4ndern%20Sie%20%24%5Clambda%24%20(hier%20%24%5Clambda_1%3D%5Clambda_2%3D%5Clambda%24).%20Wann%20ist%20der%20Grundzustand%20des%20QUBO%20eine%20g%C3%BCltige%20L%C3%B6sung%3F%0A%20%20%20%20Beobachten%20Sie%20auch%20die%20Spannweite%20der%20Energien.%20Gro%C3%9Fe%20%24%5Clambda%24%20machen%20die%20Landschaft%20f%C3%BCr%20den%20Optimierer%20sp%C3%A4ter%20%E2%80%9Esteiler%22.%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%20lam_slider%20%3D%20mo.ui.slider(start%3D0%2C%20stop%3D10%2C%20step%3D0.5%2C%20value%3D2%2C%20label%3D%22%CE%BB%22%2C%20show_value%3DTrue)%0A%20%20%20%20lam_slider%0A%20%20%20%20return%20(lam_slider%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(build_qubo%2C%20lam_slider%2C%20mo%2C%20ok_qubo%2C%20qubo_energies%2C%20valid_mask)%3A%0A%20%20%20%20mo.stop(not%20ok_qubo)%0A%0A%20%20%20%20_Q%2C%20_off%20%3D%20build_qubo(lam_slider.value%2C%20lam_slider.value)%0A%20%20%20%20_E%20%3D%20qubo_energies(_Q%2C%20_off)%0A%20%20%20%20_best_invalid%20%3D%20_E%5B~valid_mask%5D.min()%0A%20%20%20%20_worst_valid%20%3D%20_E%5Bvalid_mask%5D.max()%0A%20%20%20%20_ok%20%3D%20valid_mask%5B_E%20%3D%3D%20_E.min()%5D.all()%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22*%20beste%20g%C3%BCltige%20Energie%3A%20**%7B_E%5Bvalid_mask%5D.min()%3A.1f%7D**%2C%20schlechteste%20g%C3%BCltige%3A%20**%7B_worst_valid%3A.1f%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20f%22*%20beste%20ung%C3%BCltige%20Energie%3A%20**%7B_best_invalid%3A.1f%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20f%22*%20Energiespanne%20insgesamt%3A%20%7B_E.min()%3A.1f%7D%20bis%20%7B_E.max()%3A.1f%7D%5Cn%5Cn%22%0A%20%20%20%20%20%20%20%20%2B%20(%22%E2%9C%85%20Alle%20Grundzust%C3%A4nde%20sind%20g%C3%BCltig.%22%20if%20_ok%20else%20%22%E2%9D%8C%20Der%20Grundzustand%20ist%20ung%C3%BCltig%20(zu%20kleines%20%CE%BB).%22)%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%20Ising-Hamilton-Operator%0A%0A%20%20%20%20Das%20QUBO%20ist%20in%20bin%C3%A4ren%20Variablen%20%24x_u%20%5Cin%20%5C%7B0%2C1%5C%7D%24%20formuliert%2C%20ein%20Quantencomputer%20arbeitet%20mit%20dem%20Operator%20%24Z%24%20(Eigenwerte%20%24%5Cpm%201%24).%0A%20%20%20%20Die%20%C3%9Cbersetzung%20ist%20die%20Ersetzung%20%24x_u%20%5Cto%20%5Cfrac%7B1%20-%20Z_u%7D%7B2%7D%24%20(denn%20%24Z%7Cx%5Crangle%20%3D%20(-1)%5Ex%7Cx%5Crangle%24).%0A%20%20%20%20Aus%20Ihrer%20QUBO-Matrix%20lesen%20wir%20zun%C3%A4chst%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%20den%20Spin-Variablen%20%24z_u%20%5Cin%20%5C%7B-1%2C%2B1%5C%7D%24.%0A%20%20%20%20Geben%20Sie%20%24h_u%24%2C%20%24J_%7Buv%7D%24%20und%20die%20Konstante%20in%20Abh%C3%A4ngigkeit%20von%20%24a_u%24%2C%20%24b_%7Buv%7D%24%20und%20dem%20Offset%20an%2C%20sodass%0A%0A%20%20%20%20%24%24%0A%20%20%20%20Q%20%3D%20%5Csum_u%20h_u%20z_u%20%2B%20%5Csum_%7Bu%3Cv%7D%20J_%7Buv%7D%5C%2C%20z_u%20z_v%20%2B%20%5Ctext%7Bconst.%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20%60qubo_to_ising(Q%2C%20offset)%60.%20Die%20Funktion%20bekommt%20die%20obere%20Dreiecksmatrix%20%60Q%60%20und%20gibt%0A%20%20%20%20%60h%60%20(Array%20der%20L%C3%A4nge%20%24N%24)%2C%20%60Jz%60%20(obere%20Dreiecksmatrix%2C%20%60Jz%5Bu%2C%20v%5D%60%20f%C3%BCr%20%24u%3Cv%24)%20und%20die%20Konstante%20%60const%60%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.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.%0A%20%20%20%20%20%20%20%20%20%20%20%20Sammelt%20man%20alle%20Terme%2C%20ergibt%20sich%3A%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%20und%20%C3%A4ndert%20weder%20den%20Grundzustand%20noch%20die%20Wahrscheinlichkeiten.%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_(np)%3A%0A%20%20%20%20def%20qubo_to_ising(Q%2C%20offset)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Wandelt%20ein%20QUBO%20(obere%20Dreiecksmatrix%20Q%2C%20Offset)%20in%20Ising-Koeffizienten%20(h%2C%20Jz%2C%20const)%20um.%22%22%22%0A%20%20%20%20%20%20%20%20N%20%3D%20len(Q)%0A%20%20%20%20%20%20%20%20h%20%3D%20np.zeros(N)%0A%20%20%20%20%20%20%20%20Jz%20%3D%20np.zeros((N%2C%20N))%0A%20%20%20%20%20%20%20%20const%20%3D%20offset%0A%0A%20%20%20%20%20%20%20%20%23%20%3E%3E%3E%20IHR%20CODE%20(ising)%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%20%20%20%20%20return%20h%2C%20Jz%2C%20const%0A%0A%20%20%20%20return%20(qubo_to_ising%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(N%2C%20Q_qubo%2C%20mo%2C%20np%2C%20ok_qubo%2C%20qubo_offset%2C%20qubo_to_ising%2C%20run_check)%3A%0A%20%20%20%20mo.stop(not%20ok_qubo%2C%20mo.callout(mo.md(%22%E2%8F%B3%20Bearbeiten%20Sie%20zuerst%20die%20Aufgaben%203.1%20bis%203.5.%22)%2C%20kind%3D%22neutral%22))%0A%0A%20%20%20%20def%20_test()%3A%0A%20%20%20%20%20%20%20%20h%2C%20Jz%2C%20const%20%3D%20qubo_to_ising(Q_qubo%2C%20qubo_offset)%0A%20%20%20%20%20%20%20%20assert%20h.shape%20%3D%3D%20(N%2C)%2C%20f%22h%20muss%20die%20L%C3%A4nge%20%7BN%7D%20haben.%22%0A%20%20%20%20%20%20%20%20assert%20np.allclose(np.tril(Jz)%2C%200)%2C%20%22Jz%20muss%20eine%20obere%20Dreiecksmatrix%20sein%20(nur%20Eintr%C3%A4ge%20mit%20u%20%3C%20v).%22%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(3)%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_x%20%3D%20_rng.integers(0%2C%202%2C%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20_z%20%3D%201%20-%202%20*%20_x%0A%20%20%20%20%20%20%20%20%20%20%20%20_qubo%20%3D%20_x%20%40%20Q_qubo%20%40%20_x%20%2B%20qubo_offset%0A%20%20%20%20%20%20%20%20%20%20%20%20_ising%20%3D%20h%20%40%20_z%20%2B%20_z%20%40%20Jz%20%40%20_z%20%2B%20const%0A%20%20%20%20%20%20%20%20%20%20%20%20assert%20np.isclose(_qubo%2C%20_ising)%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%20_x))%7D%20liefert%20das%20QUBO%20%7B_qubo%7D%2C%20Ihr%20Ising-Modell%20aber%20%7B_ising%7D.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20ok_ising%2C%20_result%20%3D%20run_check(_test)%0A%20%20%20%20_result%0A%20%20%20%20return%20(ok_ising%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Q_qubo%2C%20mo%2C%20np%2C%20ok_ising%2C%20qubo_offset%2C%20qubo_to_ising)%3A%0A%20%20%20%20mo.stop(not%20ok_ising)%0A%0A%20%20%20%20h%2C%20Jz%2C%20ising_const%20%3D%20qubo_to_ising(Q_qubo%2C%20qubo_offset)%0A%20%20%20%20n_zz%20%3D%20int(np.count_nonzero(Jz))%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22Das%20Ising-Modell%20hat%20**%7Blen(h)%7D**%20lokale%20Felder%20%24h_u%24%20und%20**%7Bn_zz%7D**%20Kopplungen%20%24J_%7B%7Buv%7D%7D%24.%20%22%0A%20%20%20%20%20%20%20%20f%22Jede%20Kopplung%20wird%20sp%C3%A4ter%20ein%20%60IsingZZ%60-Gatter%20im%20Schaltkreis%2C%20d.%20h.%20der%20Schaltkreis%20ist%20pro%20Schicht%20ziemlich%20tief.%20%22%0A%20%20%20%20%20%20%20%20f%22Das%20liegt%20an%20der%20One-Hot-Kodierung%20und%20den%20Nebenbedingungen%2C%20die%20viele%20Qubits%20miteinander%20koppeln.%22%0A%20%20%20%20)%0A%20%20%20%20return%20Jz%2C%20h%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%20haben%20wir%20alles%2C%20um%20die%20Bausteine%20aus%20Teil%202%20als%20Gatter%20zu%20schreiben%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%20%3D%20%5Cprod_%7Bl%3Dp%7D%5E%7B1%7D%20%5CBig%5B%20U_M(%5Cbeta_l)%5C%2C%20U_C(%5Cgamma_l)%20%5CBig%5D%20%7C%2B%5Crangle%5E%7B%5Cotimes%20N%7D%2C%0A%20%20%20%20%5Cquad%20U_C(%5Cgamma)%20%3D%20e%5E%7B-i%5Cgamma%20H_C%7D%2C%5Cquad%20U_M(%5Cbeta)%20%3D%20e%5E%7B-i%5Cbeta%20%5Csum_u%20X_u%7D.%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%20Der%20Zwischenschritt%20mit%20den%20Winkeln%20ist%20die%20eigentliche%20Denkaufgabe%3A%0A%0A%20%20%20%20**Mathematik%3A**%20Mit%20welchem%20Winkel%20%24%5Cvarphi%24%20m%C3%BCssen%20Sie%20die%20Gatter%0A%0A%20%20%20%20*%20%24R_Z(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20Z%2F2%7D%24%20auf%20Qubit%20%24u%24%2C%0A%20%20%20%20*%20%24%5Ctext%7BIsingZZ%7D(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%5C%2C%20Z%5Cotimes%20Z%2F2%7D%24%20auf%20die%20Qubits%20%24u%2C%20v%24%2C%0A%20%20%20%20*%20%24R_X(%5Cvarphi)%20%3D%20e%5E%7B-i%5Cvarphi%20X%2F2%7D%24%20auf%20Qubit%20%24w%24%0A%0A%20%20%20%20ansteuern%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%20und%20%24e%5E%7B-i%5Cbeta%20X_w%7D%24%20zu%20erhalten%3F%0A%0A%20%20%20%20**Code%3A**%20Implementieren%20Sie%20die%20beiden%20Schichten.%20Ihre%20Funktionen%20werden%20**innerhalb%20eines%20QNodes**%20aufgerufen%20und%20m%C3%BCssen%20nur%20die%20Gatter%20anwenden%20(nichts%20zur%C3%BCckgeben).%0A%0A%20%20%20%20*%20%60cost_layer(gamma%2C%20h%2C%20Jz)%60%3A%20%24U_C(%5Cgamma)%24%2C%20mit%20%60qml.RZ%60%20und%20%60qml.IsingZZ%60.%20Es%20gibt%20nur%20f%C3%BCr%20Eintr%C3%A4ge%20%60Jz%5Bu%2C%20v%5D%20!%3D%200%60%20etwas%20zu%20tun.%0A%20%20%20%20*%20%60mixer_layer(beta%2C%20N)%60%3A%20%24U_M(%5Cbeta)%24%2C%20mit%20%60qml.RX%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.%0A%20%20%20%20%20%20%20%20%20%20%20%20Also%20%24%5Cvarphi%2F2%20%3D%20%5Cgamma%20h_u%24.%20Dasselbe%20gilt%20f%C3%BCr%20die%20beiden%20anderen%20Gatter.%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(gamma%2C%20h%2C%20Jz)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Wendet%20exp(-i%20*%20gamma%20*%20H_C)%20an%20(innerhalb%20eines%20QNodes%20aufrufen).%22%22%22%0A%20%20%20%20%20%20%20%20N%20%3D%20len(h)%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(beta%2C%20N)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Wendet%20exp(-i%20*%20beta%20*%20sum_u%20X_u)%20an%20(innerhalb%20eines%20QNodes%20aufrufen).%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_(N%2C%20cost_layer%2C%20mixer_layer%2C%20qml)%3A%0A%20%20%20%20dev%20%3D%20qml.device(%22default.qubit%22%2C%20wires%3DN)%0A%0A%20%20%20%20def%20make_qaoa_qnode(p%2C%20h%2C%20Jz)%3A%0A%20%20%20%20%20%20%20%20%22%22%22QNode%2C%20der%20QAOA%20mit%20p%20Schichten%20ausf%C3%BChrt%20und%20die%20Wahrscheinlichkeiten%20aller%202%5EN%20Bitstrings%20zur%C3%BCckgibt.%22%22%22%0A%0A%20%20%20%20%20%20%20%20%40qml.qnode(dev%2C%20diff_method%3D%22backprop%22)%0A%20%20%20%20%20%20%20%20def%20circuit(gammas%2C%20betas)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20w%20in%20range(N)%3A%20%20%23%20Startzustand%20%7C%2B%3E%5EN%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20qml.Hadamard(wires%3Dw)%0A%20%20%20%20%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%20%20%20%20%20cost_layer(gammas%5Blayer%5D%2C%20h%2C%20Jz)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mixer_layer(betas%5Blayer%5D%2C%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20qml.probs(wires%3Drange(N))%0A%0A%20%20%20%20%20%20%20%20return%20circuit%0A%0A%20%20%20%20return%20(make_qaoa_qnode%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(E_all%2C%20Jz%2C%20N%2C%20h%2C%20make_qaoa_qnode%2C%20mo%2C%20np%2C%20ok_ising%2C%20pnp%2C%20run_check)%3A%0A%20%20%20%20mo.stop(not%20ok_ising%2C%20mo.callout(mo.md(%22%E2%8F%B3%20L%C3%B6sen%20Sie%20zuerst%20die%20Ising-Aufgabe%20(Teil%204).%22)%2C%20kind%3D%22neutral%22))%0A%0A%20%20%20%20%23%20Referenz-Simulation%20ohne%20Quantenbibliothek%3A%20Phase%20exp(-i*gamma*E(x))%20und%20exp(-i*beta*X)%20per%20Hand%0A%20%20%20%20def%20_reference_state(gammas%2C%20betas%2C%20psi0)%3A%0A%20%20%20%20%20%20%20%20psi%20%3D%20psi0.astype(complex)%0A%20%20%20%20%20%20%20%20for%20g%2C%20b%20in%20zip(gammas%2C%20betas)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20psi%20%3D%20psi%20*%20np.exp(-1j%20*%20g%20*%20E_all)%0A%20%20%20%20%20%20%20%20%20%20%20%20psi%20%3D%20psi.reshape((2%2C)%20*%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20w%20in%20range(N)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20psi%20%3D%20np.cos(b)%20*%20psi%20-%201j%20*%20np.sin(b)%20*%20np.flip(psi%2C%20axis%3Dw)%0A%20%20%20%20%20%20%20%20%20%20%20%20psi%20%3D%20psi.reshape(-1)%0A%20%20%20%20%20%20%20%20return%20psi%0A%0A%20%20%20%20_plus%20%3D%20np.full(2**N%2C%202%20**%20(-N%20%2F%202))%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%20Gesamtschaltkreis%20mit%20p%20%3D%202%20Schichten%20gegen%20die%20Referenz-Simulation%20vergleichen%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%0A%20%20%20%20%20%20%20%20_circuit%20%3D%20make_qaoa_qnode(2%2C%20h%2C%20Jz)%0A%20%20%20%20%20%20%20%20_probs%20%3D%20np.array(_circuit(pnp.array(_g)%2C%20pnp.array(_b)))%0A%20%20%20%20%20%20%20%20_expected%20%3D%20np.abs(_reference_state(_g%2C%20_b%2C%20_plus))%20**%202%0A%20%20%20%20%20%20%20%20assert%20np.allclose(_probs%2C%20_expected%2C%20atol%3D1e-6)%2C%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Die%20Wahrscheinlichkeiten%20Ihres%20Schaltkreises%20stimmen%20nicht%20mit%20der%20Referenz-Simulation%20%C3%BCberein.%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Gr%C3%B6%C3%9Fte%20Abweichung%3A%20%7Bnp.abs(_probs%20-%20_expected).max()%3A.2e%7D.%20Pr%C3%BCfen%20Sie%20die%20Winkel%20(Faktor%202%3F)%20und%20die%20Vorzeichen.%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_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Der%20Schaltkreis%20ist%20fertig.%20Zeichnen%20k%C3%B6nnen%20Sie%20ihn%20mit%20%60qml.draw_mpl(make_qaoa_qnode(1%2C%20h%2C%20Jz))(gammas%2C%20betas)%60.%0A%0A%20%20%20%20%23%23%20Der%20Erwartungswert%0A%0A%20%20%20%20Der%20klassische%20Optimierer%20braucht%20eine%20Zahl%2C%20die%20er%20minimieren%20kann%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%20Der%20Schaltkreis%20liefert%20die%20%24p(x)%24%20(%60probs%60)%2C%20die%20%24E(x)%24%20haben%20wir%20klassisch%20in%20%60E_all%60%20ausgerechnet%20(alle%20%242%5EN%24%20Energien).%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.%20Verwenden%20Sie%20%60pnp%60%20(PennyLane-NumPy)%20statt%20%60np%60%2C%20damit%20der%20Gradient%20durch%20die%20Funktion%0A%20%20%20%20hindurch%20berechnet%20werden%20kann.%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%20pnp%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(pnp.array(_probs)%2C%20pnp.array(E_all%2C%20requires_grad%3DFalse))%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(pnp.array(_uniform)%2C%20pnp.array(E_all)))%2C%20E_all.mean())%2C%20%22F%C3%BCr%20die%20Gleichverteilung%20muss%20der%20Mittelwert%20aller%20Energien%20herauskommen.%22%0A%0A%20%20%20%20ok_expect%2C%20_result%20%3D%20run_check(_test)%20if%20ok_layers%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_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%20der%20Optimierungsschritte.%0A%0A%20%20%20%20**Startwerte%3A**%20Der%20Optimierer%20startet%20bei%20einem%20Anfangsparametersatz.%20Eine%20bew%C3%A4hrte%20Wahl%20ist%20die%20*Rampe*%2C%20inspiriert%20vom%20Annealing%20aus%20Abschnitt%202.4%3A%0A%20%20%20%20%24%5Cgamma_l%24%20w%C3%A4chst%20und%20%24%5Cbeta_l%24%20sinkt%20linear%20mit%20der%20Schicht%20%24l%24.%20Dadurch%20beginnt%20der%20Schaltkreis%20wie%20eine%20kurze%2C%20grob%20diskretisierte%20adiabatische%20Evolution.%0A%20%20%20%20Zuf%C3%A4llige%20Startwerte%20landen%20leichter%20in%20schlechten%20lokalen%20Minima.%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%7Bsteps%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%3D2%2C%20label%3D%22Schichten%20p%22%2C%20show_value%3DTrue)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20steps%3Dmo.ui.slider(20%2C%20300%2C%20step%3D10%2C%20value%3D100%2C%20label%3D%22Optimierungsschritte%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%20Jz%2C%20h%2C%20make_qaoa_qnode%2C%20np%2C%20pnp%2C%20qml)%3A%0A%20%20%20%20def%20run_qaoa(p_layers%2C%20steps%2C%20init%3D%22Rampe%22%2C%20stepsize%3D0.05%2C%20seed%3D0%2C%20progress%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Optimiert%20(gamma%2C%20beta)%20per%20Adam.%20Gibt%20Parameter%2C%20Kostenverlauf%20und%20die%20finalen%20Wahrscheinlichkeiten%20zur%C3%BCck.%22%22%22%0A%20%20%20%20%20%20%20%20circuit%20%3D%20make_qaoa_qnode(p_layers%2C%20h%2C%20Jz)%0A%20%20%20%20%20%20%20%20energies%20%3D%20pnp.array(E_all%2C%20requires_grad%3DFalse)%0A%0A%20%20%20%20%20%20%20%20def%20cost(gammas%2C%20betas)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20expectation(circuit(gammas%2C%20betas)%2C%20energies)%0A%0A%20%20%20%20%20%20%20%20%23%20Skala%20f%C3%BCr%20gamma%3A%20so%2C%20dass%20gamma%20*%20h%20in%20der%20Gr%C3%B6%C3%9Fenordnung%200.1%20-%201%20liegt%0A%20%20%20%20%20%20%20%20gamma_scale%20%3D%200.4%20%2F%20np.abs(h).max()%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%20gammas%20%3D%20pnp.array(gamma_scale%20*%20_l%2C%20requires_grad%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20betas%20%3D%20pnp.array(0.8%20*%20(1%20-%20_l)%2C%20requires_grad%3DTrue)%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%20gammas%20%3D%20pnp.array(_rng.uniform(0%2C%202%20*%20gamma_scale%2C%20p_layers)%2C%20requires_grad%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20betas%20%3D%20pnp.array(_rng.uniform(0%2C%200.8%2C%20p_layers)%2C%20requires_grad%3DTrue)%0A%0A%20%20%20%20%20%20%20%20opt%20%3D%20qml.AdamOptimizer(stepsize%3Dstepsize)%0A%20%20%20%20%20%20%20%20history%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_step%20in%20progress(range(steps))%20if%20progress%20else%20range(steps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20(gammas%2C%20betas)%2C%20value%20%3D%20opt.step_and_cost(cost%2C%20gammas%2C%20betas)%0A%20%20%20%20%20%20%20%20%20%20%20%20history.append(float(value))%0A%20%20%20%20%20%20%20%20probs%20%3D%20np.array(circuit(gammas%2C%20betas))%0A%20%20%20%20%20%20%20%20return%20gammas%2C%20betas%2C%20history%2C%20probs%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_ising%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_ising%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%20_bar%20%3D%20lambda%20it%3A%20mo.status.progress_bar(it%2C%20title%3D%22QAOA-Optimierung%22)%0A%20%20%20%20gammas_opt%2C%20betas_opt%2C%20cost_history%2C%20final_probs%20%3D%20run_qaoa(%0A%20%20%20%20%20%20%20%20p_used%2C%20settings%5B%22steps%22%5D%2C%20settings%5B%22init%22%5D%2C%20progress%3D_bar%0A%20%20%20%20)%0A%20%20%20%20return%20betas_opt%2C%20cost_history%2C%20final_probs%2C%20gammas_opt%2C%20p_used%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20E_all%2C%0A%20%20%20%20betas_opt%2C%0A%20%20%20%20cost_history%2C%0A%20%20%20%20final_probs%2C%0A%20%20%20%20gammas_opt%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20p_used%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%20%20%20%20_p_opt_uniform%20%3D%20(E_all%20%3D%3D%20_e0).mean()%0A%20%20%20%20_p_valid_uniform%20%3D%20valid_mask.mean()%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(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(%22Optimierungsschritt%22)%0A%20%20%20%20_ax.set_ylabel(r%22%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%7Bcost_history%5B-1%5D%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%2C%20einen%20**g%C3%BCltigen**%20Bitstring%20zu%20messen%20%7C%20%7B_p_valid%3A.1%25%7D%20%7C%20%7B_p_valid_uniform%3A.1%25%7D%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7C%20Wahrscheinlichkeit%2C%20einen%20**optimalen**%20Bitstring%20zu%20messen%20%7C%20%7B_p_opt%3A.1%25%7D%20%7C%20%7B_p_opt_uniform%3A.2%25%7D%20%7C%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Optimum%3A%20%24E_0%20%3D%20%7B_e0%3A.0f%7D%24.%20Parameter%3A%20%24%5Cgamma%20%3D%20%7Bnp.round(gammas_opt%2C%203)%7D%24%2C%20%24%5Cbeta%20%3D%20%7Bnp.round(betas_opt%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%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%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%22%22.join(map(str%2C%20bits%5Bs%5D))%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%20optimal%2C%20blau%20%3D%20g%C3%BCltig%2C%20grau%20%3D%20ung%C3%BCltig)%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%22Jeweils%20drei%20Bits%20geh%C3%B6ren%20zu%20einem%20Topf%20(Reihenfolge%20der%20Arten%3A%20Tomate%2C%20Gurke%2C%20Basilikum).%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Es%20gibt%20mehrere%20optimale%20Bitstrings%20(Symmetrien%20des%20Gartens)%2C%20deshalb%20verteilt%20sich%20die%20Wahrscheinlichkeit%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%20ausw%C3%A4hlen%0A%0A%20%20%20%20Auf%20einem%20echten%20Quantencomputer%20w%C3%BCrden%20Sie%20den%20Schaltkreis%20viele%20Male%20ausf%C3%BChren%20(*Shots*)%20und%20aus%20den%20Messergebnissen%20den%20besten%20g%C3%BCltigen%20Bitstring%20w%C3%A4hlen.%0A%20%20%20%20Wir%20simulieren%20das%2C%20indem%20wir%201000%20Messungen%20aus%20den%20berechneten%20Wahrscheinlichkeiten%20ziehen.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%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%20bits%2C%0A%20%20%20%20counts%2C%0A%20%20%20%20final_probs%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20n_pots%2C%0A%20%20%20%20n_species%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plot_garden%2C%0A)%3A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(7)%0A%20%20%20%20_samples%20%3D%20_rng.choice(2**N%2C%20size%3D1000%2C%20p%3Dfinal_probs%20%2F%20final_probs.sum())%0A%20%20%20%20_valid%20%3D%20%5Bs%20for%20s%20in%20np.unique(_samples)%20if%20is_valid(bits%5Bs%5D%2C%20n_pots%2C%20n_species%2C%20counts)%5D%0A%0A%20%20%20%20if%20not%20_valid%3A%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.md(%22%E2%9D%8C%20Unter%20den%201000%20Messungen%20war%20kein%20g%C3%BCltiger%20Bitstring.%20Probieren%20Sie%20mehr%20Schichten%20oder%20Optimierungsschritte.%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_best%20%3D%20min(_valid%2C%20key%3Dlambda%20s%3A%20E_all%5Bs%5D)%0A%20%20%20%20%20%20%20%20_assignment%20%3D%20bits%5B_best%5D.reshape(n_pots%2C%20n_species).argmax(axis%3D1)%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**%7Bnp.isin(_samples%2C%20_valid).sum()%7D**%20g%C3%BCltig.%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%20g%C3%BCltige%20Bitstring%20%60%7B''.join(map(str%2C%20bits%5B_best%5D))%7D%60%20hat%20die%20Energie%20**%7BE_all%5B_best%5D%3A.0f%7D**%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22(Optimum%3A%20%7BE_all.min()%3A.0f%7D).%20Die%20Kanten%20sind%20gr%C3%BCn%20(freundlich)%2C%20gelb%20(neutral)%20oder%20rot%20(feindlich)%20gef%C3%A4rbt%3A%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_garden(_assignment)%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%20Aufwand%20von%20QAOA%20w%C3%A4chst%20mit%20%24p%24%20(mehr%20Gatter%2C%20mehr%20Parameter)%2C%20daf%C3%BCr%20sollte%20die%20N%C3%A4herung%20besser%20werden.%0A%20%20%20%20Der%20folgende%20Lauf%20optimiert%20f%C3%BCr%20%24p%20%3D%201%2C%20%5Cdots%2C%204%24%20je%2080%20Schritte%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%204%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_ising%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_ising%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%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_probs%20%3D%20run_qaoa(_p%2C%2080)%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%BCltig%22)%0A%20%20%20%20_ax.plot(_ps%2C%20_p_opt%2C%20%22s-%22%2C%20label%3D%22optimal%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%20**Skalierung.**%20Ein%20Garten%20mit%20%243%20%5Ctimes%203%24%20T%C3%B6pfen%20und%209%20verschiedenen%20Arten%20braucht%20%249%20%5Ccdot%209%20%3D%2081%24%20Qubits%3A%20Das%20l%C3%A4sst%20sich%20nicht%20mehr%20als%20Zustandsvektor%20simulieren%0A%20%20%20%20(%242%5E%7B81%7D%24%20Eintr%C3%A4ge).%20Mit%20der%20Brute-Force-Methode%20der%20klassischen%20Referenz%20h%C3%A4tten%20wir%20bei%209%20T%C3%B6pfen%20%249!%20%3D%20362%5C%2C880%24%20Anordnungen%20zu%20pr%C3%BCfen.%0A%20%20%20%20Das%20ist%20noch%20machbar%2C%20bei%2020%20T%C3%B6pfen%20aber%20nicht%20mehr.%20Ab%20welcher%20Gr%C3%B6%C3%9Fe%20lohnt%20sich%20also%20ein%20Quantenverfahren%2C%20und%20welche%20Hardware%20braucht%20man%20daf%C3%BCr%3F%0A%0A%20%20%20%20**Aufgaben%20zum%20Weiterdenken%3A**%0A%0A%20%20%20%201.%20**Penalty-St%C3%A4rke%20(Aufgabe%204.1%20der%20Originalaufgabe)%3A**%20Wie%20h%C3%A4ngt%20die%20Qualit%C3%A4t%20von%20QAOA%20von%20%24%5Clambda%24%20ab%3F%20Wie%20gro%C3%9F%20muss%20%24%5Clambda%24%20mindestens%20sein%3F%0A%20%20%20%20%20%20%20%C3%9Cberlegen%20Sie%2C%20wie%20sich%20die%20schlechteste%20g%C3%BCltige%20Energie%20und%20die%20beste%20ung%C3%BCltige%20Energie%20mit%20%24%5Clambda%24%20ver%C3%A4ndern.%20Probieren%20Sie%20%24%5Clambda%3D1%2C%5C%204%2C%5C%208%24%20in%20%60LAM1%60%2C%20%60LAM2%60%20aus.%0A%20%20%20%20%20%20%20Was%20beobachten%20Sie%20bei%20gro%C3%9Fen%20%24%5Clambda%24%20in%20der%20QAOA-Optimierung%3F%0A%20%20%20%202.%20**Domain-Wall-Kodierung%20(Aufgabe%204.2)%3A**%20Statt%20One-Hot%20mit%20%24t%24%20Qubits%20pro%20Topf%20l%C3%A4sst%20sich%20eine%20Art%20mit%20%24t-1%24%20Qubits%20kodieren%0A%20%20%20%20%20%20%20(%5BChancellor%202019%5D(https%3A%2F%2Farxiv.org%2Fpdf%2F1903.05068v3)).%20Wie%20viele%20Qubits%20braucht%20die%202%C3%972-Instanz%20damit%3F%0A%20%20%20%203.%20**Problem%20erweitern%20(Aufgabe%204.3)%3A**%20%C3%84ndern%20Sie%20die%20Zielfunktion!%20Zum%20Beispiel%3A%20Kleine%20Pflanzen%20(Basilikum%2C%20Thymian%2C%20Petersilie%2C%20...)%20sollen%20nicht%20im%20Schatten%0A%20%20%20%20%20%20%20gro%C3%9Fer%20Pflanzen%20stehen%2C%20wenn%20die%20untere%20Zeile%20des%20Gartens%20nach%20S%C3%BCden%20zeigt.%20Wie%20%C3%A4ndert%20sich%20das%20QUBO%3F%0A%20%20%20%204.%20**Besserer%20Mixer%3A**%20Der%20%24X%24-Mixer%20verl%C3%A4sst%20st%C3%A4ndig%20den%20Raum%20der%20g%C3%BCltigen%20L%C3%B6sungen%0A%20%20%20%20%20%20%20(dort%20liegen%20nur%2012%20von%204096%20Zust%C3%A4nden).%20Es%20gibt%20*Constraint-preserving%20Mixer*%20(z.%20B.%20XY-Mixer)%2C%20die%20die%20%E2%80%9Eeine%20Pflanze%20pro%20Topf%22-Bedingung%20erhalten%0A%20%20%20%20%20%20%20und%20den%20Strafterm%20%24k%24%20%C3%BCberfl%C3%BCssig%20machen.%20Wie%20m%C3%BCsste%20der%20Mixer%20aussehen%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%20Problem%20in%20bin%C3%A4re%20Variablen%20kodiert%20(One-Hot)%3A%20%24x_%7Bij%7D%24%20%7C%0A%20%20%20%20%7C%202%20%7C%20Nebenbedingungen%20%24k(%5Cmathbf%7Bx%7D)%24%2C%20%24l(%5Cmathbf%7Bx%7D)%24%20als%20Strafterme%20und%20Zielfunktion%20%24E(%5Cmathbf%7Bx%7D)%24%20aufgestellt%2C%20ergibt%20das%20**QUBO**%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%20**Ising-Hamilton-Operator**%20%24H_C%24%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%60IsingZZ%60)%20und%20Mixer%20(%60RX%60)%20%7C%0A%20%20%20%20%7C%205%20%7C%20Parameter%20%24(%5Cboldsymbol%7B%5Cgamma%7D%2C%20%5Cboldsymbol%7B%5Cbeta%7D)%24%20per%20Gradientenabstieg%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%3A%20g%C3%BCltige%20und%20optimale%20Bitstrings%20gesucht%20%7C%0A%0A%20%20%20%20Dieselben%20QUBOs%2C%20die%20Sie%20hier%20aufgestellt%20haben%2C%20lassen%20sich%20auch%20auf%20einem%20Quantum%20Annealer%20(z.%20B.%20D-Wave)%20l%C3%B6sen.%0A%20%20%20%20Ein%20Vorteil%20des%20Gate-basierten%20Ansatzes%20ist%20die%20Flexibilit%C3%A4t%20(andere%20Mixer%2C%20andere%20Optimierer%2C%20Fehlerminderung)%2C%0A%20%20%20%20ein%20Nachteil%20sind%20die%20heute%20noch%20kleinen%20und%20fehleranf%C3%A4lligen%20Ger%C3%A4te.%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%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
77c240aca1ae89514bf2497cc3bb6c1e