Kvantum-számítástudomány (gyorstalpaló)
2024 Őszi kurzus az Eötvös Loránd Turományegyetemen
(Neptun kurzuskód -- EJC-INFO-SZ/02)
Az előadások szerdánként 14:30-16:00 között az ELTE Déli Tömb Soó Rezső termében (LD 0-818) vannak.
Az előadások jórészt Ronald de Wolf (angol nyelvű) jegyzetét követik. Rövid ismertető:
A mai számítógépek --- mind elméletben (Turing-gépek), mind gyakorlatban (PC-k és okostelefonok) --- a klasszikus fizikán alapulnak. A modern kvantumfizika alapján azonban tudjuk, hogy a világ mélyen egészen másképp viselkedik. Egy kvantumrendszer egyszerre lehet több különböző állapot szuperpozíciójában, és interferencia-jelenségeket mutathat. Ráadásul a térben elkülönült kvantumrendszerek összefonódhatnak egymással, és a műveletek emiatt "nem-lokális" hatásokat fejthetnek ki. A kvantumszámítás az a terület, amely a kvantummechanikai elveken alapuló számítógépek számítási teljesítményét és egyéb tulajdonságait vizsgálja. Fő építőeleme a qubit, amely a klasszikus bitekkel ellentétben egyszerre veheti fel a 0 és az 1 értéket, így egyfajta párhuzamosságot tesz lehetővé. A kvantummechanika törvényei korlátozzák, hogy hogyan végezhetünk számítási műveleteket ezeken a qubiteken, és így meghatározzák, hogy milyen hatékonyan oldhatunk meg egy adott számítási problémát. A kvantumszámítógépek általánosítják a klasszikus számítógépeket, így legalább olyan hatékonyak. A valódi cél azonban olyan számítási problémák megtalálása, ahol a kvantumszámítógép sokkal hatékonyabb a klasszikus számítógépeknél. Peter Shor például 1994-ben talált egy kvantumalgoritmusmust, amely hatékonyan képes nagy egész számokat prímtényezőkre bontani. Ezt a problémát általában exponenciális időigényűnek tartják még a legjobb klasszikus számítógépeken is, és feltételezett nehézsége a modern kriptográfia (különösen az elterjedt RSA-rendszer) alapját képezi. Shor algoritmusa feltöri az összes ilyen kriptográfiát. Egy másik fontos kvantumalgoritmus Grover keresési algoritmusa, amely egy rendezetlen keresési térben kvadratikusan gyorsabban keres mint az klasszikusan lehetséges. Ezeken az algoritmusokon kívül számos más alkalmazás is ismert: kvantumkriptográfia, kvantumkommunikáció, fizikai rendszerek szimulációja és még sok más területen.
A kurzus matematikai és elméleti számítástudományi szemlélettel van felépítbe, de fizikusok számára is követhető.
Előfeltételek: Alapvető lineáris algebra, valószínűségszámítás, diszkrét matematika és algoritmusok ismerete, mindegyik egy alapszintű BSc kurzus szintjén. Emellett általános matematikai érettség: bizonyítások helyes és teljes leírására való képesség. További részletek Józsa Richárd ismétlő jegyzetében találhatók.
További háttéranyagok:
Az első előadás magyar nyelvű jegyzete itt található
Gyorstalpaló csak középiskolai matematikai háttérre témaszkodva: https://www.quantum-quest.org/material.html
Józsa Richárd bevezető kurzusa, amely kicsit több fizikai motivációt tartalmaz: https://www.qi.damtp.cam.ac.uk/files/PartIIIQC/Part 2 QIClecturenotes.pdf
Ashley Montanaro kiegészítő jegyzetei Józsa Richárd kurzusához: https://people.maths.bris.ac.uk/~csxam/partiii/qc-partiii.pdf
Andrew Childs előadásjegyzetei, amelyek haladóbb témákat fednek le (beleértve az algebrai algoritmusokat, kvantumos bolyongásokat, query komplexitást stb.): https://www.cs.umd.edu/~amchilds/qa/
John Preskill előadásjegyzetei, amelyek haladóbb témákat fednek le (beleértve a hibajavítást és hibatűrő számításokat stb.): http://theory.caltech.edu/~preskill/ph229/
Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information, Cambridge University Press, 2000.
Minden előadás előtt beadható az előző héten (Ronald
jegyzetéből) feladott házi feladat, amire helyes megoldás esetén 10 pont jár.
Az év végi jegy az összesített eredmények alapján az alábbiak szerint fog alakulni:
085 pont ≤ 5
070 pont ≤ 4
055 pont ≤ 3
040 pont ≤ 2
A házifeladatokon lehet közösen ötletelni, de mindenki saját maga kell leírja a végső kidolgozott megoldást. Akik közösen dolgoztak egy feladaton írják rá, hogy kikkel ötleteltek.