Rejtett részcsoportok és kvantum-számítógépek

Rejtett részcsoportok és kvantum-számítógépek Ivanyos Gábor MTA SZTAKI

MTA, 2007 május 23.

Ivanyos Gábor MTA SZTAKI

Rejtett részcsoportok és kvantum-számítógépek

Kvantum bitek és kvantum-áramkörök A rejtett részcsoport problémája Algoritmus a kommutatív esetre Próbálkozások nemkommutatív általánosításra

Kvantum bitek Kvantum kapuk Kvantum-ármakörök

Tartalom 1 Kvantum bitek és kvantum-áramkörök

Kvantum bitek Kvantum kapuk Kvantum-ármakörök 2 A rejtett részcsoport problémája Háttér Deníció, példák 3 Algoritmus a kommutatív esetre Orákulum hívása szuperpozícióra Fourier-transzformáció 4 Próbálkozások nemkommutatív általánosításra Nemkommutatív Fourier-transzformáció A standard módszer a szimmetrikus csoportban Pozitív eredmények - rekordok Ivanyos Gábor MTA SZTAKI




Kvantum bit

Állapot: a B = C2 komplex euklideszi tér egy egységvektora: az a|0i + b|1i szuperpozíció (lineáris kombináció),

ahol |a|2 + |b|2 = 1

Kitüntetett bázis: |0i, |1i Mérés után: 0: |a|2 valószín¶séggel, 1: |b|2 valószín¶séggel.





n kvantum bites rendszer

Állapot: a B ⊗n = C2 komplex euklideszi tér egy n

egységvektora: P a s ∈S as |s i szuperpozíció, P ahol S = {0, 1}n és s ∈S |as |2 = 1.

Kitüntetett bázis: |s i, ahol s ∈ S :

|0 . . . 00i, |0 . . . 01i, |1 . . . 11i.

Mérés után: az s bitsorozat: |as |2 valószín¶séggel.





Kvantum kapuk d bites kvantum kapu: egy 2d dimenziós unitér transzformáció

Példák: Hadamard-kapu: H : |0i 7→ |1i 7→

Kontrollált fáziseltolás:

√1

(|0i + |1i),

2 √1 (|0i − |1i). 2

|0x i 7→ |0x i, |10i 7→ |10i,

|11i 7→ ω|11i, ahol |ω| = 1.





Kvantum-áramkör: számolás

n kvantum bites rendszeren

egy- és kétbites kvantum kapuk sorozata megadva az is, hogy mely kvantum bit(ek)en hatnak ("drótozás", sorrend is számít) formálisan: a megfelel® transzformáció ⊗ identitás

M¶velet: a kapuknak megfelel® transzformációk szorzata Id®igény (lépésszám): a sorozat hossza Megjegyzés: konstans d > 2-re legfeljebb d bites kapukból álló áramkörök: az 1-2 bitessel polinomiálisan ekvivalens modell.





Kvantum-áramkör: mérés/m¶ködés

a kapuk szorzata az input bitsorozatnak megfelel® báziselemre végül mérés randomizált algoritmushoz hasonló jelleg¶ a megfelel® nyelvosztály: BPQ

Megjegyzés: Véges ún. univerzális kapukészlettel a kapuk közelítése segítségével szintén polinomiálisan ekvivalens modell hapható.




Háttér Deníció, példák






Háttér

Shor 1994: faktorizáció és diszkrét logaritmus polinomid®ben kvantum-számítógéppel megsokszorozódtak a kvantum-számítógépek építésére fordított er®források

a rejtett részcsoport problémája: fenti feladatok érdemi

részfeladatainak a grázomorzmus-problémát is tartalmazó közös általánosítása

Jelenleg minden kvantumos exponeciális gyorsulás lényegében ide tartozik





Deníció

G

(véges) csoport Az f : G → {bitsorozatok} függvény a H ≤ G részcsoportot rejti, ha f

f

(x ) = f (y ) ⇔ xH = yH

orákulummal (vagy hatékony algoritmussal) adott. Kvantum orákulum: |x i|0i 7→ |x i|f (x )i

H -t (pl. H egy generátorrendszerét) lehet®leg poly log |G | id®ben!

Feladat: keressük meg





Példák

Csoportelem rendje G = Z, a ∈ A, k f (k ) = a . H = m Z, ahol m = a rendje. Diszkrét logaritmus G = Z × Z, a, b ∈ A k −` . f (k , `) = a b k ` H = {(k , `)|a = b }.





Grázimorzmus permutált gráf:

Γ gráf az {1, . . . , n} csúcsokon, σ ∈ Sn , a permutált Γσ gráf élei: [i , j ], ahol [σ(i ), σ(j )] éle Γ-nak.

Automorzmuscsoport, mint rejtett részcsoprt G

= Sn f (σ) = Γσ .

a rejtett részcsoport = Aut (Γ) Gráfok izomorája ← Gráfok automorizmuscsoportja Γ1 , Γ2 összefügg®. S Γ1 ∼ = Γ2 ⇔ |Aut (Γ1 ˙ Γ2 )| = 2 · |Aut (Γ1 )| · |Aut (Γ2 )|.




Orákulum hívása szuperpozícióra Fourier-transzformáció






Orákulum szuperpozícióra 1.

|1G i|0..0i → (uniform szuperpozíció elkészítése) 1 X p |x i|0..0i → (orákulum hívása) |G | x ∈G 1 X p |x i|f (x )i = |G | x ∈G X 1 X 1 XX p |x i|s i = p |ax i|f (a)i |G | s |G | a∈T x ∈H x ∈G

f (x ) = s

T:

baloldali mellékosztályok reprezentánsrendszere Ivanyos Gábor MTA SZTAKI




Orákulum szuperpozícióra 2.

1 XX p |ax i|f (a)i = |G | a∈T x ∈H ! X 1 X 1 p p |ax i |f (a)i |G : H | a∈T |H | x ∈H rögzített a ∈ T -re az els® regiszter tartalma 1 X mellékosztályátlag: |aH i := p |ax i |H | x ∈H a második regiszter tartalma állandó, azt nem bántjuk tovább mintha "el®rehoznánk" a második regiszter mérését Ivanyos Gábor MTA SZTAKI




Fourier-transzformáció Kommutatív

G

csoport Fourier-transzformációja 1 X |g i 7→ p χ(g )|χi |G | ˆ χ∈G

lineáris kiterjsztése CG -re. Hatékony közelít® kvantum implmentációk vannak. 1 X p |ax i → |H | x ∈H 1 X 1 X p p χ(ax )|χi = |H | x ∈H |G | ˆ χ∈G ! 1 X χ(a) X p p χ(x ) |χi |G | ˆ |H | x ∈H χ∈G





Fourier transzformáció 2. |χi együtthatója χ(a)

p

|G

1 X χ(x ) = : H | |H | x ∈H

(

√χ(a) |G :H | 0

ha χH = 1, egyébként.

Biz.: 1H és χH ortogonalitása: 1 ha χH = 1, 1 P x ∈H χ(x ) = 0 egyébként |H |

χ valószín¶sége:

1

|G :H |

0


ha χ ∈ H ⊥ , egyébként. Rejtett részcsoportok és kvantum-számítógépek



H kiszámítása

H ⊥ = {χ ∈ Gˆ | χH = 1} a Gˆ egy részcsoprtja. Várhatóan O (log |G |) ismétléssel H ⊥ egy Γ generátorrendszere

gy¶lik össze. Ekkor

H = {x ∈ G

| χ(x ) = 1 for every χ ∈ Γ}.

(∼ lineáris egyenletrendszer)




Nemkommutatív Fourier-transzformáció A standard módszer a szimmetrikus csoportban Pozitív eredmények - rekordok






Nemkommutatív Fourier-transzformáció

g Gb : G dρ :

dρ p dρ XX dρ X p 7→ ρ(g )ij |ρ, i , j i |G | i ,j =1 i , j = 1 b ρ∈G

komplex irreducibilis unitér mátrixreprezentációi minden ekvivalencia-osztályból egy

ρ foka

a transzformáció unitér, függ ρ választásától elég sok csoportra ismert hatékony kvantum-implementáció





Gyenge standard Fourier-módszer a kommutatív esetet követi csak ρ-t használja a mérés után d P ρ valószín¶sége: |Gρ| h∈H χρ (h). H C G esetén 0 valószín¶ség, ha H 6≤ ker ρ, "eléggé egyenletes" a H ≤ ker ρ tulajdonságúakra H -t polinom sok próba után valszeg egyért. meghat. Er®s standard módszer: i , j -t is méri csak egy ismert esetben jobb bizonyítottan nem jó gráf-izomorzmusra!





A szimmetrikus csoport gyenge módszerrel polinom id®ben érzékelhet® részcsoportjai Ezek a konstans minimális fokú permutációcsortok H minimális foka: H \ {1}-be tartozó permutációk által mozgatott elemek min. száma. Polinom sok konstans elemet mozgató permutáció van ⇒ ilyen H az 1-t®l megkülönböztethet® klasszikus módszerrel is polinom id®ben.

Kempe és Shalev sejtette és bizonyította spec. esetekre Pyber László bizonyította általánosan f® eredménye: egy, a permutációcsoportok rendje és minimális fokszáma közötti aszimptikus összefüggés igazolása Ivanyos Gábor MTA SZTAKI




Pozitív eredmények rekordok a lekérdezési bonyolultság polinomiális Ettinger, Hoyer, Knill 2004 ⇒ a negatív eredmények jellege Ez vagy az a konkrét megközelítés nem m¶ködik...

Dn diéder csoportra

p log n-ben exponenciális Kuperberg 2005 Fontos indukciós eszköz lenne feloldható csoportokra korlátos exponens¶, korlátos hosszú feloldható csoportokra polinomiális módszer Friedl, ∼, Magniez, Sántha, Sen 2003 Znp o Z2 -n (konstans p ) alapuló rekurzió





Rekordok 2.

Polinomiális idej¶ módszerek vannak még

p3 rend¶ csoportokra

Bacon, Childs, van Dam 2005 Az ún. Pretty Good Measurement hatékony implementációja Extraspeciális p -csoportokra ∼, Sántha, Sanselme 2007 Nem az el®z® módszer kiterjesztése! Ötlet: reprezentációk hangolása automorzmusokkal. 2 osztályú csoportokra általánosítható ???





Reprezentációk hangolása

G = p exponens¶, p2m+1 rend¶ extraspeciális csoport √ z = Z (G ) generátora, ω = p 1 j = 1, . . . , p − 1: φj pm dim. irrep.: φj (z ) = ωj I . 1-dimenziós reprezentációk ∼ φi ⊗ φj = φi +j egy direkt hatványa ∃ α0 , . . . αp−1 ∈ End (G ), amelyekre αk ◦ φj = φk 2 j Adott j1 , j2 , j3 -ra keresend® k1 , k2 , k3 , amelyekre k12 j1 + k22 j2 + k32 j3 = 0, így αk1 ◦ φj1 ⊗ αk2 ◦ φj2 ⊗ αk3 ◦ φj3 ∼ = a φ0 egy hatványa

φ0 =

L

φ0 -ból

G /G 0 Fourier trafójával H Ivanyos Gábor MTA SZTAKI

modulo

G 0.


Rejtett részcsoportok és kvantum-számítógépek

Recommend Documents