Των κβαντικών υπολογιστών: ένα φροντιστήριο

Home

Περίληψη:
Φανταστείτε έναν υπολογιστή, του οποίου η μνήμη είναι εκθετικά μεγαλύτερο από το προφανές φυσικό μέγεθος, ένα υπολογιστή που μπορεί να χειριστεί μια εκθετική σύνολο εισροών ταυτόχρονα * έναν υπολογιστή που υπολογίζει στη ζώνη του λυκόφωτος του Hilbert space. Θα πρέπει να σκέφτεται ενός κβαντικού υπολογιστή. Σχετικά λίγες και απλές έννοιες της κβαντικής μηχανικής απαιτούνται να κάνουν οι κβαντικοί υπολογιστές είναι μια πιθανότητα. Η λεπτότητα έχει στη μάθηση για να χειριστείτε αυτές τις έννοιες. Είναι όπως ένας υπολογιστής αναπόφευκτη ή θα είναι πάρα πολύ δύσκολο να χτίσεις;

Στην εργασία αυτή θα δώσει ένα tutorial για το πώς η κβαντική μηχανική μπορεί να χρησιμοποιηθεί για να βελτιώσει τον υπολογισμό. Η πρόκληση για μας: την επίλυση ενός εκθετικά δύσκολο πρόβλημα για ένα συμβατικό υπολογιστή—factoring ένα μεγάλο αριθμό. Ως προοίμιο, θα επανεξετάσει το πρότυπο εργαλεία υπολογισμού, καθολική πύλες και μηχανές. Οι ιδέες αυτές στη συνέχεια να εφαρμοστεί πρώτα σε κλασσική, dissipationless υπολογιστές και, στη συνέχεια, να κβαντικούς υπολογιστές. Ένα μοντέλο ενός κβαντικού υπολογιστή που περιγράφονται, καθώς και μερικές από τις λεπτές αποχρώσεις του προγραμματισμού. Ο αλγόριθμος Shor [1,2] για αποτελεσματικά factoring αριθμούς σε ένα κβαντικό υπολογιστή παρουσιάζεται σε δύο μέρη: την κβαντική διαδικασία εντός του αλγορίθμου και ο κλασικός αλγόριθμος που καλεί την κβαντική διαδικασία. Η μαθηματική δομή factoring που κάνει ο αλγόριθμος Shor είναι δυνατόν να συζητηθούν. Θα ολοκληρώσω με μια προοπτική για τη σκοπιμότητα και τις προοπτικές των κβαντικών υπολογιστών τα επόμενα χρόνια.

Ας ξεκινήσουμε με την περιγραφή του προβλήματος: παραγοντοποίηση ενός αριθμού N σε πρωταρχικούς παράγοντες (π. χ., ο αριθμός 51688 μπορεί να αποσυντεθεί ως ). Ένα βολικό τρόπο για να ποσοτικοποιήσει πόσο γρήγορα ένα συγκεκριμένο αλγόριθμο μπορεί να λύσει ένα πρόβλημα είναι να ζητήσει από το πώς τον αριθμό των βημάτων για να ολοκληρωθεί ο αλγόριθμος κλίμακες με το μέγεθος της `εισαγωγής” ο αλγόριθμος είναι της fed. Για το factoring πρόβλημα, αυτή η είσοδος είναι ο αριθμός N θέλουμε να παράγοντα, ως εκ τούτου, το μήκος της εισόδου . (Η βάση του λογαρίθμου καθορίζεται από μας σύστημα αρίθμησης. Συνεπώς μια βάση του 2 δίνει το μήκος σε δυαδική; βάση του 10 σε δεκαδικό.) “Λογικό” αλγόριθμοι είναι αυτοί που την κλίμακα ως μια μικρή βαθμού πολυώνυμο το μέγεθος της εισόδου (με ένα βαθμό ίσως 2 ή 3).

Σε συμβατικούς υπολογιστές, το πιο γνωστό αλγόριθμος τρέχει σε βήματα [3]. Αυτός ο αλγόριθμος, ως εκ τούτου, κλίμακες εκθετικά με το μέγεθος της εισόδου . Για παράδειγμα, το 1994 129 ψήφιο αριθμό (γνωστή ως RSA129 [3′]) επιτυχώς συνυπολογίζονται χρησιμοποιώντας αυτόν τον αλγόριθμο σε περίπου 1600 θέσεις εργασίας διάσπαρτα σε όλο το κόσμο, όλο το παραγοντοποίηση πήρε οκτώ μήνες [4]. Χρησιμοποιώντας αυτό για την εκτίμηση της prefactor τα παραπάνω εκθετική κλιμάκωση, θα βρείτε ότι θα λάβει περίπου 800.000 χρόνια σε παράγοντα 250 ψήφιο αριθμό με τον ίδιο υπολογιστή δύναμη ομοίως, 1000-ψήφιο αριθμό που θα απαιτούσε χρόνια (σημαντικά lon ger από την ηλικία του σύμπαντος). Η δυσκολία παραγοντοποίηση μεγάλων αριθμών, είναι ζωτικής σημασίας για το δημόσιο-κλειδί κρυπτοσυστήματα, όπως αυτά που χρησιμοποιούνται από τις τράπεζες. Εκεί, οι κώδικες αυτοί βασίζονται στη δυσκολία του factoring αριθμούς με περίπου 250 ψηφία.

Πρόσφατα, ένας αλγόριθμος που αναπτύχθηκε για το αριθμούς σε ένα κβαντικό υπολογιστή που τρέχει στα βήματα που είναι μικρό [1]. Αυτό είναι περίπου τετραγωνικές με το μέγεθος της εισόδου, έτσι ώστε factoring 1000 ψήφιο αριθμό με έναν τέτοιο αλγόριθμο απαιτεί μόνο μερικά εκατομμύρια βήματα. Το συμπέρασμα είναι ότι το δημόσιο κλειδί κρυπτοσυστήματα βασίζονται σε factoring μπορεί να είναι εύθραυστα.

Για να σας δώσω μια ιδέα του πώς αυτή η εκθετική βελτίωση μπορεί να είναι δυνατόν, θα επανεξετάσει μια στοιχειώδης κβαντική μηχανική πείραμα που μας δείχνει πού τέτοια δύναμη μπορεί να βρίσκονται κρυμμένα [5]. Οι δύο σχισμών πείραμα prototypic για την παρατήρηση κβαντική μηχανική συμπεριφορά: Μια πηγή εκπέμπει φωτόνια, ηλεκτρόνια ή άλλα σωματίδια που φτάνουν σε ένα ζευγάρι σχισμών. Τα σωματίδια αυτά υποβάλλονται σε ενιαίο εξέλιξη και το τέλος της μέτρησης. Θα δείτε ένα μοτίβο παρεμβολής, με τις δύο σχισμές, που wholely εξαφανίζεται αν είτε σχισμή καλύπτεται. Κατά κάποιο τρόπο, τα σωματίδια περνούν μέσα από τις δύο σχισμές παράλληλα. Αν μια τέτοια ενιαία εξέλιξη ήταν να εκπροσωπεί έναν υπολογισμό (ή μια λειτουργία εντός υπολογισμού), τότε το κβαντικό σύστημα θα πρέπει να εκτελεί υπολογισμούς παράλληλα. Κβαντική παραλληλισμό έρχεται για δωρεάν. Η παραγωγή αυτού του συστήματος θα δίνεται από την εποικοδομητική παρέμβαση μεταξύ των παράλληλων υπολογισμών.
Αρχικά στο http://www-users.cs.york.ac.uk/~schmuel/comp/comp.html