Νέος αλγόριθμος κλείνει το παράθυρο της κβαντικής υπεροχής | Περιοδικό Quanta

[et_pb_section fb_built=”1″ admin_label=”section” _builder_version=”4.16″ global_colors_info=”{}”][et_pb_row admin_label=”row” _builder_version=”4.16″position background_size=”initial” ” global_colors_info=”{}”][et_pb_column type=”4_4″ _builder_version=”4.16″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_text admin_label=”Text” _builder_version=”4.16″ background_size=”initial” background_position=”top_left” background_repeat=”repeat” global_colors_info

Σε ποιες συγκεκριμένες περιπτώσεις οι κβαντικοί υπολογιστές ξεπερνούν τους κλασικούς αντίστοιχους; Αυτή είναι μια δύσκολη ερώτηση για να απαντηθεί, εν μέρει επειδή οι σημερινοί κβαντικοί υπολογιστές είναι περίεργα πράγματα, μαστίζονται από σφάλματα που μπορούν να συσσωρευτούν και να χαλάσουν τους υπολογισμούς τους.

Με ένα μέτρο, βέβαια, το έχουν ήδη κάνει. Το 2019, φυσικοί της Google ανακοίνωσε που χρησιμοποίησαν μηχανή 53 qubit για να επιτύχουν κβαντική υπεροχή, ένα συμβολικό ορόσημο που σηματοδοτεί το σημείο στο οποίο ένας κβαντικός υπολογιστής κάνει κάτι πέρα ​​από κάθε πρακτικό κλασικό αλγόριθμο. Παρόμοιος διαδηλώσεις από φυσικούς στο Πανεπιστήμιο Επιστήμης και Τεχνολογίας της Κίνας ακολούθησε σύντομα.

Αλλά αντί να επικεντρωθούν σε ένα πειραματικό αποτέλεσμα για μια συγκεκριμένη μηχανή, οι επιστήμονες υπολογιστών θέλουν να μάθουν εάν οι κλασικοί αλγόριθμοι θα είναι σε θέση να συμβαδίσουν καθώς οι κβαντικοί υπολογιστές γίνονται όλο και μεγαλύτεροι. «Η ελπίδα είναι ότι τελικά η κβαντική πλευρά θα απομακρυνθεί εντελώς μέχρι να μην υπάρχει πλέον ανταγωνισμός», είπε. Σκοτ Άαρσον, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Τέξας στο Ώστιν.

Αυτή η γενική ερώτηση εξακολουθεί να είναι δύσκολο να απαντηθεί, και πάλι εν μέρει λόγω αυτών των ενοχλητικών σφαλμάτων. (Οι μελλοντικές κβαντικές μηχανές θα αντισταθμίσουν τις ατέλειές τους χρησιμοποιώντας μια τεχνική που ονομάζεται κβαντική διόρθωση σφάλματος, αλλά αυτή η ικανότητα είναι ακόμα μακριά.) Είναι δυνατόν να αποκτήσουμε το αναμενόμενο μακρινό κβαντικό πλεονέκτημα ακόμη και με μη διορθωμένα σφάλματα;

Οι περισσότεροι ερευνητές υποψιάζονταν ότι η απάντηση ήταν αρνητική, αλλά δεν μπορούσαν να το αποδείξουν για όλες τις περιπτώσεις. Τώρα, σε ένα χαρτί Δημοσιεύτηκε στον διακομιστή προεκτύπωσης arxiv.org, μια ομάδα επιστημόνων υπολογιστών έκανε ένα σημαντικό βήμα προς την ολοκληρωμένη απόδειξη ότι η διόρθωση σφαλμάτων είναι απαραίτητη για ένα διαρκές κβαντικό πλεονέκτημα στην τυχαία δειγματοληψία κυκλωμάτων — το εξατομικευμένο πρόβλημα που χρησιμοποίησε η Google για να δείξει την κβαντική υπεροχή. Το πέτυχαν αναπτύσσοντας έναν κλασικό αλγόριθμο που μπορεί να προσομοιώσει πειράματα τυχαίας δειγματοληψίας κυκλωμάτων όταν υπάρχουν σφάλματα.

«Είναι ένα όμορφο θεωρητικό αποτέλεσμα», δήλωσε ο Aaronson, τονίζοντας παράλληλα ότι ο νέος αλγόριθμος δεν είναι πρακτικά χρήσιμος για την προσομοίωση πραγματικών πειραμάτων όπως αυτά της Google.

Σε πειράματα δειγματοληψίας τυχαίων κυκλωμάτων, οι ερευνητές ξεκινούν με μια σειρά από qubits ή κβαντικά bit. Στη συνέχεια χειρίζονται τυχαία αυτά τα qubits με πράξεις που ονομάζονται κβαντικές πύλες. Ορισμένες πύλες αναγκάζουν τα ζεύγη qubits να μπλέκονται, που σημαίνει ότι μοιράζονται μια κβαντική κατάσταση και δεν μπορούν να περιγραφούν ξεχωριστά. Επανειλημμένα στρώματα πυλών φέρνουν τα qubits σε μια πιο περίπλοκη κατάσταση εμπλοκής.

Για να μάθουν για αυτήν την κβαντική κατάσταση, οι ερευνητές μετρούν στη συνέχεια όλα τα qubits στον πίνακα. Αυτό προκαλεί την κατάρρευση της συλλογικής κβαντικής τους κατάστασης σε μια τυχαία συμβολοσειρά από συνηθισμένα bit — 0 και 1. Ο αριθμός των πιθανών αποτελεσμάτων αυξάνεται ραγδαία με τον αριθμό των qubits στον πίνακα: Με 53 qubits, όπως στο πείραμα της Google, είναι σχεδόν 10 τετράκις εκατομμύρια. Και δεν είναι όλες οι συμβολοσειρές εξίσου πιθανές. Η δειγματοληψία από ένα τυχαίο κύκλωμα σημαίνει επανάληψη τέτοιων μετρήσεων πολλές φορές για να δημιουργηθεί μια εικόνα της κατανομής πιθανοτήτων που διέπει τα αποτελέσματα.

Το ερώτημα του κβαντικού πλεονεκτήματος είναι απλώς το εξής: Είναι δύσκολο να μιμηθεί κανείς αυτήν την κατανομή πιθανοτήτων με κλασικό αλγόριθμο που δεν χρησιμοποιεί καμία εμπλοκή;

Στο 2019, ερευνητές αποδείχθηκε ότι η απάντηση είναι ναι για κβαντικά κυκλώματα χωρίς σφάλματα: Είναι πράγματι δύσκολο να προσομοιώσεις κλασικά ένα πείραμα δειγματοληψίας τυχαίου κυκλώματος όταν δεν υπάρχουν σφάλματα. Οι ερευνητές εργάστηκαν στο πλαίσιο της θεωρίας της υπολογιστικής πολυπλοκότητας, η οποία ταξινομεί τη σχετική δυσκολία διαφορετικών προβλημάτων. Σε αυτό το πεδίο, οι ερευνητές δεν αντιμετωπίζουν τον αριθμό των qubits ως έναν σταθερό αριθμό όπως το 53. «Σκεφτείτε το ως n, που είναι ένας αριθμός που πρόκειται να αυξηθεί», είπε Αράμ Χάροου, φυσικός στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης. «Τότε θέλετε να ρωτήσετε: Κάνουμε πράγματα όπου η προσπάθεια είναι εκθετική; n ή πολυώνυμο σε n;" Αυτός είναι ο προτιμώμενος τρόπος ταξινόμησης του χρόνου εκτέλεσης ενός αλγορίθμου — πότε n μεγαλώνει αρκετά, ένας αλγόριθμος που είναι εκθετικός n υστερεί πολύ σε σχέση με οποιονδήποτε αλγόριθμο που είναι πολυωνυμικός n. Όταν οι θεωρητικοί μιλούν για ένα πρόβλημα που είναι δύσκολο για τους κλασσικούς υπολογιστές αλλά εύκολο για τους κβαντικούς υπολογιστές, αναφέρονται σε αυτή τη διάκριση: Ο καλύτερος κλασικός αλγόριθμος απαιτεί εκθετικό χρόνο, ενώ ένας κβαντικός υπολογιστής μπορεί να λύσει το πρόβλημα σε πολυωνυμικό χρόνο.

Ωστόσο, αυτό το έγγραφο του 2019 αγνόησε τις επιπτώσεις των σφαλμάτων που προκαλούνται από ατελείς πύλες. Αυτό άφησε ανοιχτή την περίπτωση ενός κβαντικού πλεονεκτήματος για τυχαία δειγματοληψία κυκλώματος χωρίς διόρθωση σφαλμάτων.

Εάν φαντάζεστε ότι αυξάνετε συνεχώς τον αριθμό των qubits όπως κάνουν οι θεωρητικοί της πολυπλοκότητας και θέλετε επίσης να λάβετε υπόψη τα σφάλματα, πρέπει να αποφασίσετε εάν θα συνεχίσετε να προσθέτετε περισσότερα στρώματα πυλών — αυξάνοντας το βάθος του κυκλώματος, όπως λένε οι ερευνητές. Ας υποθέσουμε ότι διατηρείτε το βάθος του κυκλώματος σταθερό, ας πούμε, σε σχετικά ρηχά τρία επίπεδα, καθώς αυξάνετε τον αριθμό των qubits. Δεν θα μπερδευτείτε πολύ και η έξοδος θα εξακολουθεί να είναι επιδεκτική κλασικής προσομοίωσης. Από την άλλη πλευρά, εάν αυξήσετε το βάθος του κυκλώματος για να συμβαδίσετε με τον αυξανόμενο αριθμό των qubits, τα σωρευτικά αποτελέσματα των σφαλμάτων της πύλης θα ξεπλύνουν την εμπλοκή και η έξοδος θα γίνει και πάλι εύκολη στην κλασική προσομοίωση.

Αλλά ενδιάμεσα βρίσκεται μια ζώνη Goldilocks. Πριν από τη νέα δημοσίευση, εξακολουθούσε να υπάρχει πιθανότητα ότι το κβαντικό πλεονέκτημα θα μπορούσε να επιβιώσει εδώ, ακόμη και όταν ο αριθμός των qubits αυξανόταν. Σε αυτήν την περίπτωση ενδιάμεσου βάθους, αυξάνετε το βάθος του κυκλώματος εξαιρετικά αργά καθώς αυξάνεται ο αριθμός των qubits: Παρόλο που η έξοδος θα υποβαθμίζεται σταθερά από σφάλματα, μπορεί να είναι ακόμα δύσκολο να προσομοιωθεί κλασικά σε κάθε βήμα.

Το νέο χαρτί κλείνει αυτό το κενό. Οι συγγραφείς έβγαλαν έναν κλασικό αλγόριθμο για την προσομοίωση δειγματοληψίας τυχαίων κυκλωμάτων και απέδειξαν ότι ο χρόνος εκτέλεσης του είναι μια πολυωνυμική συνάρτηση του χρόνου που απαιτείται για την εκτέλεση του αντίστοιχου κβαντικού πειράματος. Το αποτέλεσμα σφυρηλατεί μια στενή θεωρητική σύνδεση μεταξύ της ταχύτητας των κλασικών και των κβαντικών προσεγγίσεων στη δειγματοληψία τυχαίων κυκλωμάτων.

Ο νέος αλγόριθμος λειτουργεί για μια μεγάλη κατηγορία κυκλωμάτων ενδιάμεσου βάθους, αλλά οι υποκείμενες υποθέσεις του καταρρέουν για ορισμένα πιο ρηχά, αφήνοντας ένα μικρό κενό όπου οι αποτελεσματικές κλασικές μέθοδοι προσομοίωσης είναι άγνωστες. Αλλά λίγοι ερευνητές διατηρούν την ελπίδα ότι η δειγματοληψία τυχαίου κυκλώματος θα αποδειχθεί δύσκολο να προσομοιωθεί κλασικά σε αυτό το εναπομείναν λεπτό παράθυρο. «Του δίνω πολύ μικρές πιθανότητες», είπε Μπιλ Φέφερμαν, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Σικάγο και ένας από τους συγγραφείς της θεωρητικής εργασίας του 2019.

Το αποτέλεσμα υποδηλώνει ότι η τυχαία δειγματοληψία κυκλωμάτων δεν θα αποφέρει κβαντικό πλεονέκτημα σύμφωνα με τα αυστηρά πρότυπα της θεωρίας υπολογιστικής πολυπλοκότητας. Ταυτόχρονα, καταδεικνύει το γεγονός ότι οι πολυωνυμικοί αλγόριθμοι, τους οποίους οι θεωρητικοί της πολυπλοκότητας αποκαλούν αδιακρίτως αποτελεσματικούς, δεν είναι απαραίτητα γρήγοροι στην πράξη. Ο νέος κλασικός αλγόριθμος γίνεται προοδευτικά πιο αργός καθώς μειώνεται το ποσοστό σφάλματος, και στα χαμηλά ποσοστά σφάλματος που επιτυγχάνονται σε πειράματα κβαντικής υπεροχής, είναι πολύ αργός για να είναι πρακτικός. Χωρίς σφάλματα, καταρρέει εντελώς, επομένως αυτό το αποτέλεσμα δεν έρχεται σε αντίθεση με τίποτα από όσα γνώριζαν οι ερευνητές σχετικά με το πόσο δύσκολο είναι να προσομοιωθεί κλασικά η τυχαία δειγματοληψία κυκλωμάτων στην ιδανική, χωρίς σφάλματα περίπτωση. Sergio Boixo, ο φυσικός που ηγείται της έρευνας για την κβαντική υπεροχή της Google, λέει ότι θεωρεί την εργασία «περισσότερο ως μια ωραία επιβεβαίωση της δειγματοληψίας τυχαίων κυκλωμάτων παρά οτιδήποτε άλλο».

Σε ένα σημείο, όλοι οι ερευνητές συμφωνούν: Ο νέος αλγόριθμος υπογραμμίζει πόσο κρίσιμη θα είναι η κβαντική διόρθωση σφαλμάτων για τη μακροπρόθεσμη επιτυχία του κβαντικού υπολογισμού. «Αυτή είναι η λύση, στο τέλος της ημέρας», είπε ο Fefferman.

[/ et_pb_text] [/ et_pb_column] [/ et_pb_row] [/ et_pb_section]