"Εισαγωγή στον κβαντικό υπολογισμό (πρόγραμμα της Σχολής Φυσικής)" - μάθημα 12.160 RUB. από το MSU, εκπαίδευση 15 εβδομάδων. (4 μήνες), Ημερομηνία: 30 Νοεμβρίου 2023.
μικροαντικείμενα / / December 03, 2023
Ο κύριος στόχος του μαθήματος είναι να εισαγάγει τους φοιτητές στο ταχέως αναπτυσσόμενο πεδίο της επιστήμης και της τεχνολογίας στη διασταύρωση της φυσικής και της επιστήμης των υπολογιστών - κβαντικοί υπολογιστές. Το μάθημα θα καλύψει το μοντέλο πύλης του κβαντικού υπολογισμού και τα καθολικά σύνολα κβαντικών λογικών πυλών. Θα μιλήσουμε για τους κύριους τύπους κβαντικών αλγορίθμων όπως ο αλγόριθμος εκτίμησης φάσης, ο αλγόριθμος Shor και άλλοι αλγόριθμοι που βασίζονται στον κβαντικό μετασχηματισμό Fourier. Ο αλγόριθμος του Grover και οι κβαντικοί αλγόριθμοι αναζήτησης. κβαντικοί αλγόριθμοι μεταβολής. Θα συζητήσουμε λεπτομερώς τα προβλήματα της καταπολέμησης της αποσυνοχής και των σφαλμάτων στις κβαντικές πύλες και τα ζητήματα κατασκευής κβαντικών κωδίκων διόρθωσης σφαλμάτων. Θα ληφθούν υπόψη επιλογές για την αρχιτεκτονική ενός κβαντικού υπολογιστή που είναι ανθεκτικός σε σφάλματα. Θα συζητήσουμε τη θεμελιώδη δυνατότητα δημιουργίας ενός κβαντικού υπολογιστή ανθεκτικού σε σφάλματα και την πραγματική κατάσταση πραγμάτων στο τρέχον επίπεδο ανάπτυξης της τεχνολογίας.
Διάλεξη 1. Εισαγωγή. Ιστορική προοπτική και σημερινή κατάσταση της περιοχής. Η γέννηση της βιομηχανίας των κβαντικών υπολογιστών. Μια ιδέα για τα χαρακτηριστικά του κβαντικού υπολογισμού χρησιμοποιώντας το παράδειγμα του απλούστερου αλγορίθμου Deutsch.
Διάλεξη 2. Απαραίτητες πληροφορίες από τη θεωρία της υπολογιστικής πολυπλοκότητας των αλγορίθμων. Η έννοια ενός αλγορίθμου, μηχανή Turing, καθολική μηχανή Turing. Υπολογίσιμες και μη υπολογίσιμες συναρτήσεις, πρόβλημα διακοπής. Προβλήματα επιλυσιμότητας, μια ιδέα τάξεων υπολογιστικής πολυπλοκότητας. Τάξεις Π και ΝΠ. Πιθανολογική μηχανή Turing, κατηγορίας BPP. Προβλήματα επανυπολογισμού του αριθμού των λύσεων, κατηγορία δυσκολίας #P. Το πρόβλημα της επίδειξης κβαντικής υπεροχής χρησιμοποιώντας το πρόβλημα BosonSampling ως παράδειγμα.
Διάλεξη 3. Μοντέλο πύλης κλασικού υπολογισμού, καθολικές πύλες. Μοντέλο πύλης κβαντικών υπολογιστών. Στοιχειώδεις κβαντικές λογικές πύλες, πύλες ενός qubit και δύο qubit. Υπό όρους πύλες δύο qubit, αναπαράσταση πυλών πολλαπλών qubit υπό όρους σε πύλες δύο qubit. Περιγραφή μετρήσεων στην κβαντική θεωρία, περιγραφή μετρήσεων σε κβαντικά κυκλώματα.
Διάλεξη 4. Η ευελιξία των πυλών ενός qubit και της πύλης CNOT. Διακριτικοποίηση πυλών ενός qubit, καθολικά διακριτά σύνολα πυλών. Η δυσκολία προσέγγισης ενός αυθαίρετου ενιαίου μετασχηματισμού.
Διάλεξη 5. Κβαντικός μετασχηματισμός Fourier. Αλγόριθμος εκτίμησης φάσης, εκτίμηση απαιτούμενων πόρων, απλοποιημένος αλγόριθμος Kitaev. Πειραματικές εφαρμογές του αλγορίθμου εκτίμησης φάσης και εφαρμογές στον υπολογισμό μοριακών όρων.
Διάλεξη 6. Αλγόριθμος για την εύρεση της περιόδου μιας συνάρτησης. Παραγοντοποίηση αριθμών σε πρώτους παράγοντες, αλγόριθμος Shor. Πειραματικές υλοποιήσεις του αλγορίθμου Shor. Άλλοι αλγόριθμοι που βασίζονται στον κβαντικό μετασχηματισμό Fourier.
Διάλεξη 7. Κβαντικοί αλγόριθμοι αναζήτησης. Αλγόριθμος Grover, γεωμετρική απεικόνιση, εκτίμηση πόρων. Μετρώντας τον αριθμό των λύσεων σε ένα πρόβλημα αναζήτησης. Επιτάχυνση επίλυσης προβλημάτων NP-complete. Κβαντική αναζήτηση σε μη δομημένη βάση δεδομένων. Βελτιστοποίηση αλγορίθμου Grover. Αλγόριθμοι που βασίζονται σε τυχαίους περιπάτους. Πειραματικές υλοποιήσεις αλγορίθμων αναζήτησης.
Διάλεξη 8. Κλασικοί κωδικοί διόρθωσης σφαλμάτων, γραμμικοί κωδικοί. Σφάλματα στον κβαντικό υπολογισμό, σε αντίθεση με την κλασική περίπτωση. Κωδικός τριών qubit που διορθώνει το σφάλμα X. Κωδικός τριών qubit που διορθώνει το σφάλμα Z. Κώδικας Shor εννέα bit.
Διάλεξη 9. Γενική θεωρία διόρθωσης σφαλμάτων, δειγματοληψία σφαλμάτων, ανεξάρτητο μοντέλο σφάλματος. Κλασικοί γραμμικοί κώδικες, κώδικες Hamming. Κωδικοί Quantum Calderbank-Shor-Steen.
Διάλεξη 10. Φορμαλισμός σταθεροποιητών, κατασκευή κωδικών KSH στον φορμαλισμό σταθεροποιητών. Ενιαίοι μετασχηματισμοί και μετρήσεις στον φορμαλισμό των σταθεροποιητών. Η έννοια των υπολογισμών ανεκτικών σφαλμάτων. Κατασκευή ενός καθολικού συνόλου πυλών ανοχής σε σφάλματα. Μετρήσεις ανεκτικές σε σφάλματα. Θεώρημα κατωφλίου. Πειραματικές προοπτικές για την εφαρμογή κβαντικής διόρθωσης σφαλμάτων και υπολογισμών ανεκτικών σφαλμάτων.
Διάλεξη 11. Κβαντικοί υπολογιστές σε συσκευές NISQ. Κβαντικοί αλγόριθμοι μεταβολής: QAOA και VQE. Εφαρμογές σε προβλήματα κβαντικής χημείας. Δυνατότητες υλοποίησης σε σύγχρονους κβαντικούς επεξεργαστές, προοπτικές ανάπτυξης.