Για τους επιστήμονες της πληροφορικής, η επίλυση προβλημάτων θυμίζει ορειβασία: πρώτα εντοπίζουν την «κορυφή» (το πρόβλημα) και στη συνέχεια αναπτύσσουν στρατηγικές για να την κατακτήσουν. Σε αυτόν τον αγώνα, οι ερευνητές των κλασικών και των κβαντικών υπολογιστών ανταγωνίζονται διαρκώς, με τους κβαντικούς να αναζητούν νέες κορυφές και τους κλασικούς να σπεύδουν να αποδείξουν ότι μπορούν να τις κατακτήσουν εξίσου ή καλύτερα.
Συνήθως, η «μάχη» αυτή καταλήγει σε ισοπαλία: κάθε φορά που παρουσιάζεται ένας κβαντικός αλγόριθμος που φαίνεται ταχύτερος, οι κλασικοί αλγόριθμοι ακολουθούν με αναβαθμίσεις που εξισώνουν την απόδοση. Μάλιστα, την περασμένη εβδομάδα, μια δημοσίευση στο Science για υποτιθέμενη υπεροχή κβαντικού υπολογισμού αμφισβητήθηκε αμέσως από δύο ερευνητικές ομάδες.
Ωστόσο, μια νέα εργασία φέρνει ελπίδα για μια πραγματική κβαντική υπεροχή. Οι ερευνητές παρουσίασαν έναν νέο κβαντικό αλγόριθμο, τον Decoded Quantum Interferometry (DQI), ο οποίος φαίνεται να λύνει πιο γρήγορα από οποιονδήποτε γνωστό κλασικό αλγόριθμο μια ευρεία κλάση προβλημάτων βελτιστοποίησης.
Μέχρι στιγμής, κανένας κλασικός αλγόριθμος δεν έχει καταφέρει να «εκθρονίσει» το DQI. Ο Gil Kalai, μαθηματικός στο Reichman University και γνωστός σκεπτικιστής των κβαντικών υπολογιστών, χαρακτήρισε το DQI «ορόσημο στους κβαντικούς αλγορίθμους». Τόσο οι καινοτομίες όσο και η προοπτική πρακτικής εφαρμογής αναζωπυρώνουν τον ενθουσιασμό γύρω από το μέλλον των κβαντικών μηχανών.
Ο Ronald de Wolf, θεωρητικός επιστήμονας πληροφορικής στο CWI της Ολλανδίας, υποστηρίζει ότι πρόκειται για μια πολλά υποσχόμενη ανακάλυψη, αν και δεν αποκλείει ότι στο μέλλον μπορεί να αναπτυχθεί κλασικός αλγόριθμος που να επιτυγχάνει παρόμοιες επιδόσεις. Το μεγαλύτερο πρόβλημα, ωστόσο, παραμένει: η έλλειψη κβαντικού hardware ικανού να υποστηρίξει άμεσα τη δοκιμή του DQI.
Ακόμα και αν δεν υπάρχει άμεση πρακτική εφαρμογή, το DQI έχει ήδη κινήσει το ενδιαφέρον της επιστημονικής κοινότητας. Η Ewin Tang, επιστήμονας πληροφορικής στο Πανεπιστήμιο της Καλιφόρνια, Μπέρκλεϊ, δήλωσε ότι η νέα εργασία είναι τόσο ενδιαφέρουσα που προτείνει στους συναδέλφους της να τη μελετήσουν εντατικά.
Ο αγώνας δρόμου στην βελτιστοποίηση
Το πεδίο της βελτιστοποίησης, όπου συχνά διασταυρώνονται οι κλασικοί και κβαντικοί αλγόριθμοι, αφορά την εύρεση της καλύτερης λύσης ανάμεσα σε αμέτρητες πιθανές επιλογές, όπως ο σχεδιασμός διαδρομών για φορτηγά ή η σωστή τοποθέτηση αντικειμένων σε έναν περιορισμένο χώρο.
Το συγκεκριμένο πρόβλημα που στοχεύει να λύσει το DQI περιλαμβάνει μια συλλογή σημείων σε ένα επίπεδο και την ανάγκη εύρεσης ενός πολυωνυμικού τύπου (μιας γραφικής καμπύλης) που περνάει από τα περισσότερα σημεία με περιορισμένη πολυπλοκότητα. Τέτοια προβλήματα συναντώνται σε τομείς όπως η κωδικοποίηση σφαλμάτων και η κρυπτογραφία.
Ο Stephen Jordan, φυσικός στην Google Quantum AI, και κύριος δημιουργός του DQI, περιγράφει την ανακάλυψη ως αποτέλεσμα «οπισθοδρομικής και κυκλικής πορείας». Όταν το 2023 εντάχθηκε στην ομάδα του Eddie Farhi– πρωτοπόρου στα κβαντικά αλγοριθμικά μοντέλα – ήθελε να ακολουθήσει μια διαφορετική προσέγγιση: να δει το πρόβλημα μέσω των κυμάτων, βασική έννοια της κβαντικής φυσικής.
Με τη βοήθεια του κβαντικού μετασχηματισμού Fourier, ο Jordan κατάφερε να μετατρέψει τις πιθανές λύσεις ενός προβλήματος σε κβαντικά κύματα, όπου το μέγεθος του κύματος αντιπροσωπεύει την ποιότητα της λύσης. Όμως το πρόβλημα δεν ήταν απλό: το να εντοπιστεί το μεγαλύτερο κύμα σε ένα κβαντικό σύστημα αποδείχθηκε εξαιρετικά περίπλοκο.
Η λύση ήρθε μέσω της θεωρίας κωδικοποίησης. Ο Jordan συνειδητοποίησε ότι η επιλογή της καλύτερης λύσης έμοιαζε με τη διαδικασία αποκωδικοποίησης μηνυμάτων με σφάλματα, μια γνωστή τεχνική στην πληροφορική. Μεταφράζοντας το πρόβλημα βελτιστοποίησης σε πρόβλημα αποκωδικοποίησης, κατάφερε να δημιουργήσει ένα νέο κβαντικό αλγόριθμο.Μαζί με τον συνάδελφό του, Noah Shutty, δοκίμασαν διαφορετικά μοντέλα αποκωδικοποίησης μέχρι να βρουν αυτό που προσφέρει πραγματικό πλεονέκτημα έναντι των κλασικών αλγορίθμων.
Για να επιβεβαιώσουν την ανθεκτικότητα της μεθόδου τους, οι ερευνητές συνεργάστηκαν με την ειδικό στη θεωρία κωδικοποίησης, Mary Waters, η οποία ερεύνησε αν κάποιος κλασικός αλγόριθμος μπορούσε να μιμηθεί την απόδοσή τους. Τα αποτελέσματα ήταν ενθαρρυντικά: η υπεροχή του DQI παρέμεινε.
Παρότι η παρούσα τεχνολογία δεν επιτρέπει την πρακτική εφαρμογή του DQI, οι ερευνητές συνεχίζουν να επεκτείνουν τη χρήση του σε περισσότερες κατηγορίες προβλημάτων βελτιστοποίησης. Ο Jordan εκτιμά ότι το DQI μπορεί να υπερισχύσει και σε άλλες περιπτώσεις, ενισχύοντας το ενδεχόμενο μιας νέας εποχής για τους κβαντικούς αλγορίθμους.
Στον κβαντικό κόσμο, κάθε τέτοια επιτυχία αποτελεί σημαντικό σταθμό. Όπως τόνισε ο Kalai, «η εύρεση κβαντικών αλγορίθμων που υπερέχουν σαφώς έναντι των κλασικών είναι σπάνια και πολύτιμη, κάθε νέα ανακάλυψη είναι αιτία γιορτής».
[via]
