Τρίτη, 21 Μαΐου

Ύλη που καλύψαμε

Εισαγωγή στη Θεωρία Κβαντικής Πολυπλοκότητας

Οι κλάσεις BQP, QMA 

Το πρόβλημα k-local Hamiltonian και η απόδειξη του Kitaev ότι το k-local Hamiltonian είναι QMA-complete

Εκδοχές του quantum PCP conjecture

Προτεινόμενη μελέτη - ενδεικτική βιβλιογραφία

• Μια πολύ καλή περιγραφή της απόδειξης του Kitaev: http://theory.caltech.edu/~preskill/ph219/20_local_Hamiltonian_problem.pdf
• Ένα survey paper για διάφορες κλάσεις που αντιστοιχούν σε κβαντικά ανάλογα του NP : The 7 faces of quantum NP (https://arxiv.org/abs/2310.18010)
  
• Μια εισαγωγή στις διαφορετικές εκδοχές του quantum PCP conjecture: The status of the quantum PCP conjecture (games version) (https://arxiv.org/pdf/2403.13084v1)