Περίληψη:
Η κλάση πολυπλοκότητας QMA, που ορίσθηκε από τον Watrous, το 2000, είναι το κβαντικό ανάλογο
της MA, που ορίσθηκε από τον Babai, το 1985, και η οποία είναι μία γενίκευση της κλάσης NP. Η
κλάση MA γενικεύει την NP με την εξής έννοια: η επαληθευτική διαδικασία στην κλάση MA είναι
πιθανοκρατική, ενώ στην NP είναι πλήρως ντετερμινιστική.
Το 2014, οι Grilo, Kerenidis και Sikora, απέδειξαν ότι η κβαντική απόδειξη που ανακύπτει στον
ορισμό της QMA μπορεί, σε κάθε περίπτωση, να αντικατασταθεί από μία, κατάλληλα ορισμένη,
κβαντική κατάσταση-υποσύνολο. Οι Grilo κ.ά. ονόμασαν την κλάση αυτή SQMA, για ‘subset-state
quantum Merlin-Arthur.’ ΄Αρα QMA ⊆ SQMA, και κάποιος θα μπορούσε να γράψει ότι QMA =
SQMA, μιά και ο εγκλεισμός SQMA ⊆ QMA ισχύει τετριμμένα.
Μετά από αυτό το αποτέλεσμα, από τους Grilo κ.ά., οι Fefferman και Kimmel, το 2015, απέδει-
ξαν ότι υπάρχει κάποιο κβαντικό μαντείο A—παρόμοιο με αυτό που εισήγαγαν οι Aaronson και
Kuperberg, το 2006, για να δείξουν ότι υπάρχει μαντείο A τέτοιο ώστε QMAA
1
6⊆ QCMAA—το
οποίο είναι τέτοιο ώστε QMAA = SQMAA 6⊆ QCMAA. Σημειώνουμε εδώ ότι η QCMA είναι αυτή
η έκδοση της QMA, που ορίσθηκε από τους Aharonov και Naveh, το 2002, σύμφωνα με την οποία
η προς επαλήθευση απόδειξη είναι πλήρως κλασσική, π.χ. μία συμβολοσειρά 0-1-χαρακτήρων, και
η QMA1 είναι η έκδοση τέλειας πληρότητας της QMA, δηλαδή είναι η έκδοση της QMA κατά την
οποία για κάθε ΝΑΙ απάντηση, στο εξεταζόμενο πρόβλημα απόφασης, υπάρχει μία απόδειξη που κά-
νει τον επαληθευτή να απαντήσει ΝΑΙ με πιθανότητα ίση με ένα. Στον μαντειακό τους διαχωρισμό
οι Fefferman και Kimmel, εισήγαγαν, και χρησιμοποίησαν, μία ενδιαφέρουσα διαδικασία κατά την
οποία κάποιος μπορεί να αποδείξει ότι L ∈/ QCMA, για κάποια γλώσσα L που ικανοποιεί κάποιες
συγκεκριμένες ιδιότητες.
Χρησιμοποιώντας αυτό το αποτέλεσμα των Fefferman και Kimmel, αποδεικνύουμε ότι υπάρχει
κάποιο κβαντικό μαντείο τέτοιο ώστε SQMAA
1
6⊆ QCMAA. Σημειώνουμε εδώ ότι η κλάση SQMA1
είναι η έκδοση τέλειας πληρότητας της SQMA. Στην απόδειξή μας χρησιμοποιήσαμε την εν λόγω
διαδικασία των Fefferman και Kimmel, μία εκδοχή των βασικών μαντειακών τους κατασκευών,
όπως και το πρόβλημα απόφασης που χρησιμοποίησαν για την απόδειξη του διαχωρισμού τους.
Σημειώνουμε εδώ ότι το αποτέλεσμά μας συνεπάγεται αυτό των Fefferman και Kimmel, μιά και
ισχύει ότι SQMA1 ⊆ SQMA.
Αφού διατυπώσουμε και αποδείξουμε το αποτέλεσμά μας, κάνουμε μία παράκαμψη για να εξερευνή-
σουμε τον κόσμο των μαντειακών διαχωρισμών τόσο στον κλασσικό όσο και τον κβαντικό κόσμο.
Εξερευνούμε κάποια αποτελέσματα, και τις υποβόσκουσες μεθόδους τους, που είναι σχετικά με την
χρήση κλασσικών ή κβαντικών μαντείων σε μαντειακούς διαχωρισμούς που αφορούν σε κλασσικές
ή κβαντικές κλάσεις πολυπλοκότητας. ΄Αρα εξερευνούμε κάποιες πολύ ενδιαφέρουσες πτυχές των
διαχωριστικών αποτελεσμάτων που είναι σχετικά με σχετικιστικούς κόσμους.
Τελικά, επιστρέφουμε, στο ερευνητικό τοπίο, ώστε να προσεγγίσουμε την ερώτηση σχετικά με την
υποτιθέμενη ύπαρξη, ή όχι, ενός μαντείου A που είναι τέτοιο ώστε QMAA
1
6⊆ SQMAA
1
. Καταγρά-
φουμε τις πρώτες μας προσπάθειες, και ιδέες, μέχρι τώρα.
Λέξεις-κλειδιά:
Θεωρία κβαντικής υπολογιστικής πολυπλοκότητας, θεωρία υπολογιστικής πολυπλοκότητας, σχε- τικιστικοί κόσμοι, μαντειακοί διαχωρισμοί, μαντεία, QMA, QCMA, SQMA, SQMA1, κβαντικές καταστάσεις, κβαντικές καταστάσεις-υποσύνολα, κβαντικές αποδείξεις, επαληθευτικές διαδικασίες, επαληθευτικά πρωτόκολα, διαγωνοποίηση, και πολυπλοκότητα ερωτήσεων.
