Illustrasjon av [[Grovers algoritme]] på tre [[Kvantebit]]er med en kortstokk. Blir som en litt morsom kabal å finne en løsning som aldri krever mer enn fire rader (ledd). ## Neste steg - [ ] 🖌️ Lage challenge-kort - [ ] 🖌️ Markedsføre som "3-qubit quantum computer"? Hvordan ser teleportering ut på denne? Deutsch-Josza? Bernstein-Vaszirani? Simon's algoritme? QFT? (Sistnevnte blir nok vanskelig...) - [ ] 🖌️ Lage Print&Play-variant? Kan leke med design i [Dextrous](https://www.dextrous.com.au/). #### Fullførte steg - [x] Kom opp med en bedre representasjon for minustegn? - [x] *Trenger* ikke tallene på kortene, siden rekkefølgen allerede identifiserer qubitsene. I lys av dette, kommer du på en bedre implementering? Tokens av et slag? Ønsker en intuitiv måte å representere valgene ($+/-$)(Standard-/Hadamard-basis)(første/andre basistilstand) på. Hva med en enkel mynt-token med pil, hvor éne siden er pluss og den andre er minus? (Test i morgen.) ### Metode Vi bruker phase oracle-varianten (*d* i den følgende figuren), siden det da holder med tre qubits. ![[Pasted image 20241017235222.png|600]] ### Implementasjon ##### Ny versjon Vi får maks åtte rader (e.g. hvis alle tre er i tilstand $\plusket$ og det legges ut i standarbasis), så hver spiller trenger $3 \cdot 8 = 24$ tokens. Kan være en enkel pil på et lite kort eller en token, hvor én side representerer pluss og én side representerer minus. Trenger mest sannsynlig også å holde styr på størrelsen på amplituden til hvert ledd (kolonne). Enkleste er kanskje å skrive ... men ønsker meg noe mer elegant. Vil 2d8, hvor én av d8-ene er markert med toerpotenser fra 1 til 32, være tilstrekkelig? Eller vil tall som ikke lar seg representere av dette (som 31/32) også kunne oppstå? Bruk notater foreløpig, og undersøk mens du løser forskjellige koder. Bruk 1d8 til å trille for kode (hvor $8 \coloneqq 0$). Evt. skriv hvert orakel på et kort, og trekk et kort. (Svaret sjekkes senere ved å sammenligne orakelen med tabellen.) ![[IMG_8940.jpeg|600|600]] **Operasjoner** - **H:** Vri vertikale piler 45 grader med klokken. Vri horisontale piler 45 grader mot klokken. - Har veldig lyst på en "flipp"-operasjon her, så man "flipper" basis og slipper forvirringen (som selv jeg ofte gjør feil i) rundt hvilken vei man skal vri pilen, men da må jeg finne en annen måte å representere minus på. - **X:** Vertikale piler vris 180 grader. Horisontale piler skifter fase hvis de peker mot venstre. - **Z:** Horisontale piler vris 180 grader. Vertikale piler skifter fase hvis de peker nedover. - Kontrollerte operasjoner: Kun komponenter hvor kontroll-kubitene peker nedover påfører operasjonen på målkubiten. **Omforminger** - **Omstokking** - Man kan alltid bytte plass på kolonner (ledd), men *ikke* rader (qubits). - (Addisjon er kommutativt, men multiplikasjon er ikke.) - **Basisskifte** - $\zeroket = \plusket + \minusket$: En pil opp er ekvivalent med en pil til høyre og en pil til venstre, (begge i samme fase). - $\oneket = \plusket - \minusket$: En pil ned er ekvivalent med en pil til høyre (samme fase) og en til venstre (motsatt fase). - $\plusket = \zeroket + \oneket$: En pil til høyre er ekvivalent med en pil opp og en pil ned, (begge i samme fase). - $\minusket = \zeroket - \oneket$: En pil til venstre er ekvivalent med en pil opp (samme fase) og en pil ned (motsatt fase). - Når du gjennomfører basisskiftet, lag en ny rad, hvor de resterende kubitene er identiske, og øk baseskifttellerne med $+1$. - Man kan også gå motsatt vei, og kombinere to kubits i tilfelle de resterende kubitene er identiske. Mink i så fall baseskifttelleren med $-1$. - (Baseskifttellerne er terninger som holder styr på tallet $n$ i absoluttverdien til kolonnens amplitude, $1/\sqrt{2^n}$.) - (Så langt har jeg ikke trengt $n > 4$, men dette kan fort endre seg. Likevel en mulig interessant begrensning å lage, dersom det ikke gjør spillet for utfordrende.) - **Faseskifte** - En minusfase kan flyttes mellom kubitene i en kolonne. - Partall av minus kansellerer hverandre innad i en kolonne. - Man kan alltid faseskifte hele brettet ved å legge til en ekstra minusfase til alle kolonnene på én gang. - **Identiske kolonner og kanselleringer** - Identiske kolonner med motsatt fase kansellerer hverandre, og fjernes. (Ingen av basisskifttellerne trenger endres.) - Identiske kolonner med samme fase legges sammen. Fjern én kolonne, og øk basisskifttelleren til den andre kolonnen med $+2$. - Man kan som alltid også gå motsatt vei, og legge inn to like kolonner av motsatt fase, eller kopiere en kolonne ved å øke basistelleren med $+2$, skulle man finne dette nyttig. - **Nyttige to-qubits-identiteter** - $\ket{00} + \ket{11} = \ket{++} + \ket{--}$: Dersom to av qubitene utgjør et Bell-pair, kan man skifte basis fritt, og tilstanden er invariant under Hadamard-operasjonen. - $\ket{00} - \ket{11} = \ket{+-} + \ket{-+}$: En mindre intuitivt men likefullt nyttig identitet for basisskifter av Bell-pairs. - $\ket{01} + \ket{10} = \ket{++} - \ket{--}$: Den basisskiftede varianten av den forrige. ### Moduser ##### Singleplayer Trekk en puzzle og gjennomfør algoritmen. Sjekk at du kommer frem til riktig svar. For hvert tidssteg etter orakelets implementering, skriv ned hvor mange rader den endelige tilstanden er representert av like før neste operasjon. Sluttsummen er scoren din; jo lavere, jo bedre! ##### Multiplayer, alt. 1 Hver spiller triller 1d8 eller 2d8 (avtalt på forhånd) i skjul, noterer seg tallet de fikk, og implementerer orakelet tilhørende tallet de fikk. Deretter bytter de spillerne brett, og følger algoritmen til slutten. Heretter alternerer spillet mellom operasjonsfaser, som forekommer åpent, og optimeringsfaser, som foregår skjult. For hver operasjon viser spillerne sin nåværende tilstand, og antall rader per spiller noteres på en lapp. Begge spillerne gjennomfører operasjonen i det åpne, før de igjen skjuler tilstandene sine for optimering. Når man når det siste tidssteget er algoritmen slutt, og spillerne viser sine sluttsvar. Hver spiller sjekker at motstanderens løsning er korrekt. Vinneren er spilleren med korrekt løsning, som brukte færrest antall rader underveis. (Det er mulig å ha mer enn én vinner.) Ekstraregel: Dersom man innser at man gjorde en feil i ett av de forrige stegene, kan man gå tilbake og korrigere dette, men da vil hvert steg som må korrigeres gi en $+8$ til score i stedet for hva enn som ble notert. (Merk at det vil være lett å jukse her ved å innføre slik korrigering uten å si ifra—helst skulle man verifisert "offentlig" at hvert tidssteg var korrekt implementert, men dette blir nok for tidkrevende.) ##### Multiplayer, alt. 2 Oraklene skrives på kort, men uten strengen de implementerer. Spillet foregår som beskrevet over, unntatt at begge spillerne prøver å løse samme puzzle. Kan være interessant at operasjonsfasen foregår i det åpne. Vil man ha kommet frem til samme mellomregning? Eller er tilstandene forskjellige? Og er de ekvivalente tilstander, eller har én av spillerne gjort en feil? **Åpent spørsmål:** - Hvor lett er det for samtlige spillere å spille optimalt, slik at det alltid blir uavgjort? - (Vel, da har man i hvert fall *lært* noe!) ### Puzzles ##### 1. Trekk en oppgave Enten trill 1d8 eller 2d8 for en enkeltmarkert eller dobbeltmarkert oppgave; eller skriv oraklene på kort, og trekk en oppgave fra en kortbunke. Oppgavene er bitstrenger av lengde tre. Oppgaven kan ha enten én eller to korrekte bitstrenger; i sistnevnte tilfellet skal du finne begge, ved å ende opp med en uniform superposisjon av de to markerte strengene. Det finnes $2^3 = 8$ oppgaver med én markert bitstreng, og $(8 \cdot 8 - 8)/2 = 28$ oppgaver med to markerte bitstrenger, og dermed $8 + 28 = 36$ oppgaver totalt. ##### 2. Implementer orakelet [Kilde](https://www.nature.com/articles/s41467-017-01904-7) Vi bruker "Phase Oracle" fra tabellene under. **Én markert løsning** ![[Pasted image 20241017234753.png|500]] **To markerte løsninger** ![[Pasted image 20241017234927.png|500]] ##### 3. Gjennomfør algoritmen Her er et eksempel med to markerte bitstrenger, $011$ og $101$ (hentet [herfra](https://www.nature.com/articles/s41467-017-01904-7)): ![[Pasted image 20241017232213.png|500]] ##### 3.1 Gjennomspilling med tokens **1: Setup** Start: $\ket{000}$ ![[IMG_8910.jpeg|600]] Hadamard alle tre qubitene: ![[IMG_8911.jpeg|600]] **2: Implementer (011,101)-orakelet** Gjennomfør basisskifte på kvantebit 1 (hvor $n$ på terningen representerer en faktor $1/\sqrt{2^n}$): ![[IMG_8912.jpeg|600]] Gjennomfør controlled-Z fra 1 til 3: ![[IMG_8913.jpeg|600]] Gjennomfør basisskifte på andre kvantebit: ![[IMG_8915.jpeg|600]] Gjennomfør controlled-Z fra qubit 2 til 3: ![[IMG_8916.jpeg|600]] **3: (Gi brettet til motstanderen og) finn verdiene** **T = 1:** Hadamard alle qubitsene ![[IMG_8917.jpeg|600]] Stokk om slik at like verdier for kvantebit 3 er samlet ![[IMG_8918.jpeg|600]] Bruk toqubitsidentitetene for Bell pairs til å skifte fra Hadamard-basis til standardbasis: ![[IMG_8919.jpeg|600]] **Poeng + 4 = 4** **T = 2:** X alle qubitsene ![[IMG_8920.jpeg|600]] **Poeng + 4 = 8** **T = 3:** Gjennomfør controlled-controlled-Z fra de to første til tredje qubit ![[IMG_8921.jpeg|600]] Bruk Bell-identitetene igjen til å skifte basis for qubit 1 og 2 i de to første leddene: ![[IMG_8929.jpeg|600]] ... og i de to andre leddene: ![[IMG_8931.jpeg|600]] Flytt leddene for å samle verdiene til qubit 1 og 2: ![[IMG_8932.jpeg|600]] For å gjøre det neste steget enklere, flytt minustegnene til qubit 3: ![[IMG_8933.jpeg|600]] Baseskift tredje qubit: ![[IMG_8934.jpeg|600]] **Poeng + 2 = 10** **T = 4:** X alle qubitsene. Ingen endring. **Poeng + 2 = 12** **T = 3:** Anvend de siste Hadamard-gatene, og få det endelige svaret. ![[IMG_8935.jpeg|600]] **Resultat: 011, 101** ✅ **Poeng: 12** (Sluttilstanden teller ikke mot poengscoren.) ### Kortstokkimplementering (utdatert) - La A, 2, 3 representere qubit 1, 2, og 3 henholdsvis. - Et kort som er svart og loddrett plassert representerer tilstaden $\zeroket$. - Et kort som er rødt og loddrett plassert representerer tilstanden $\oneket$. - Et kort som er svart og vannrett plassert representerer tilstanden $\plusket$. - Et kort som er rødt og vannrett plassert representerer tilstanden $\minusket$. - Et kort som er plassert diagonalt mot nord-vest representerer $-\zeroket$ eller $-\oneket$, avhengig av farge. - Et kort som er plassert diagonalt mot nord-øst representerer $-\plusket$ eller $-\minusket$, avhengig av farge. - Addisjon er kommutativt: Man kan når som helst bytte rekkefølge på rader. - Multiplikasjon er *ikke* kommutativt: Kolonnene representerer enkeltqubits og kan ikke flyttes på. - En rad kan være markert som minus eller ikke. Hvis tre rader skal markeres som minus, ganger man hele tilstanden med $-1$ og dermed heller markerer den gjenværende raden som minus. - Man kan alltids legge til og fjerne en kopi av en rad. (Misliker implementeringen av plus/minus-fase, men funker foreløpig, til jeg kommer på noe bedre. Fasen tilhører egentlig hele raden, som tilsammen utgjør ett ledd i tilstanden.) Basisskifter (vi ignorerer normaliseringsfaktorer): - $\plusket = \zeroket + \oneket$: En rad med et svart kort i vannrett posisjon kan erstattes med to rader med identiske kort unntatt at kortet i den første raden er svart og loddrett og i den andre raden rødt og loddrett. - $\minusket = \zeroket - \oneket$: En rad med et rødt kort i vannrett posisjon kan erstattes med to rader med identiske kort unntatt at kortet i den første raden er svart og loddrett og i den andre raden rødt og diagonalt mot nord-vest. - $\zeroket = \plusket + \minusket$: En rad med et svart kort i loddrett posisjon kan erstattes med to rader med identiske kort unntatt at kortet i den første raden er svart og vannrett og i den andre raden rødt og vannrett. - $\oneket = \plusket - \minusket$: En rad med et svart kort i loddrett posisjon kan erstattes med to rader med identiske kort unntatt at kortet i den første raden er svart og vannrett og i den andre raden rødt og diagonalt mot nord-øst. Operasjoner: - **Hadamard:** Kortet vris 90 grader i alle rader. - **X:** Loddrette kort skifter farge i alle rader. Vannrette røde kort skiftes mot nord-øst. Vannrette svarte kort er upåvirket. - **Z:** Vannrette kort skifter farge i alle rader. Loddrette røde kort skiftes mot nord-vest. Loddrette svarte kort er upåvirket. - **Controlled-operasjoner:** Operasjonen forekommer kun i rader hvor den kontrollerende qubiten er et rødt loddrett kort. (Dersom den kontrollerende qubiten er vannrett, gjennomfør et basisskifte først.) ##### 1. Trekk en oppgave Trekk ett eller to kort, for én eller to markerte løsninger. |Farge |Bit 1 og 2|Paritet|Bit 3| |:-----:|:--------:|:-----:|:---:| |Kløver |$00$ |Jevn |$0$ | |Spar |$01$ |Odde |$1$ | |Hjerter|$10$ |- |- | |Ruter |$11$ |- |- | **Easy mode:** Ett kort = Én markert løsning. **Hard mode:** To kort = To markerte løsninger. **Harder mode??** Tre kort = Tre markerte løsninger? (Har ikke orakler for dette enda ... med mindre det er så lett som å kombinere andre orakler? Tabellene gjør ikke det, men de kan ha blitt optimalisert.)