Επειδή ένας αλγόριθμος είναι στην πραγματικότητα η «συνταγή» για να φτάσουμε σε κάποιο αποτέλεσμα, θα κάνουμε όπως γίνεται και με τις συνταγές. Πρώτα θα παραθέσουμε έναν κατάλογο με τα απαραίτητα υλικά και θα ακολουθήσει η εκτέλεση της συνταγής. Που είναι κάπως απλοποιημένη εδώ, αλλά απόλυτα κατανοητή με προαπαιτούμενες γνώσεις απλώς Γυμνασίου, και επιτρέπει μεγαλύτερη κατανόηση για το πόσο πιο αποτελεσματικοί θα είναι κάποτε οι κβαντικοί υπολογιστές.

Προαπαιτούμενα υλικά

• Αρχίζουμε από τον Μέγιστο Κοινό Διαιρέτη (ΜΚΔ). Είναι ο μεγαλύτερος ακέραιος που διαιρεί ακριβώς δυο άλλους ακεραίους. Π.χ. ΜΚΔ (15, 30) = 5. Ο καλύτερος τρόπος να βρεθεί ο ΜΚΔ είναι ο αλγόριθμος του Ευκλείδη που θα τον δούμε στη συνέχεια.
• Θα μας χρειαστούν επίσης κάποιες πολύ απλές ιδιότητες των υπολοίπων της διαίρεσης ακέραιων αριθμών (παλαιότερα είχαμε αναλύσει με λεπτομέρειες το θέμα). Π.χ. η ακέραια διαίρεση 17:5 δίνει υπόλοιπο 2 και αυτό το συμβολίζουμε ως εξής: 17 mod 5 = 2.
• Μας ενδιαφέρουν οι μεγάλοι ακέραιοι θετικοί αριθμοί, δηλαδή με εκατοντάδες έως και χιλιάδες ψηφία, που μπορούν να αναλυθούν σε γινόμενο δυο άλλων πρώτων αριθμών με περίπου ίδιο αριθμό ψηφίων. Ψάχνουμε τον τρόπο να βρίσκουμε τέτοιους αριθμούς. Ο προς ανάλυση αριθμός σε δυο άλλους πρώτους πρέπει να μην είναι προφανώς πρώτος και να μην είναι της μορφής Ν^χ .

Αυτά προς το παρόν ως προς τα υλικά.

Τα πρώτα βήματα

Ο Πίτερ Σορ, καθηγητής Εφαρμοσμένων Μαθηματικών στο ΜΙΤ, γεννημένος το 1959, επινόησε τον παρακάτω αλγόριθμο που θα τον παρακολουθήσουμε με τη βοήθεια του Ν = 15, του αριθμού που του έγινε η ανάλυση σε έναν από τους πρώτους κβαντικούς υπολογιστές.

Βήμα 1: Για την ανάλυση διαλέγουμε στην τύχη, θα λέγαμε, έναν θετικό ακέραιο που βρίσκεται μεταξύ του 1 και του Ν. Ας συμβολίζεται με το γράμμα κ. Στο συγκεκριμένο παράδειγμα διαλέγουμε κ = 7.

Βήμα 2: Αναζητούμε τον ΜΚΔ των (Ν, κ), εδώ των 15 και 7 (με τον αλγόριθμο του Ευκλείδη). Θεωρούμε εδώ, για τις ανάγκες του παραδείγματος, ότι ο ΜΚΔ δεν θα είναι άλλος από τη μονάδα.

Βήμα 3: Πρέπει να βρούμε τον μικρότερο θετικό ακέραιο ρ τέτοιον ώστε αν φ(χ) = κ^χ mod N, τότε φ(α) = φ(α+ρ). Αυτό μην μας τρομάζει, θα γίνει κατανοητό σε λίγο.

Βήμα 3.1.: Στη σκηνή βγάζουμε άλλον έναν πρωταγωνιστή. Με το όνομα λ, που ξεκινάει να παίζει τον ρόλο του με την τιμή λ = 1.

Βήμα 3.2.: Βρίσκουμε το αποτέλεσμα της πράξης: (λ επί κ) mod N. Δηλαδή πολλαπλασιάζουμε πρώτα το λ με το κ, κάνουμε τη διαίρεση με το Ν και εξετάζουμε μόνο το ακέραιο υπόλοιπο. Αν είναι 1, προχωρούμε στο Βήμα 3.3. Αν όχι δίνουμε, στο λ την τιμή του υπολοίπου αυτού και κάνουμε πάλι τον πολλαπλασιασμό με το κ και την ακέραια διαίρεση. Επαναλαμβάνουμε μέχρι να προκύψει ακέραιο υπόλοιπο ίσον με 1.

Εδώ θα βοηθήσει σίγουρα το παράδειγμα με τα Ν = 15, κ = 7 και λ = 1. Προκύπτουν τα εξής κατά σειρά:

1 x 7 mod 15 = 7

7 x 7 mod 15 = 4

4 x 7 mod 15 = 13

13 x 7 mod 15 =1

Οταν φτάσουμε σε υπόλοιπο 1 είναι ώρα για το επόμενο βήμα.

Βήμα 3: Πόσες διαιρέσεις χρειάστηκαν μέχρι να βρούμε υπόλοιπο 1; Τέσσερις; Αυτή είναι και η τιμή του ρ. Εδώ ρ = 4, δηλαδή άρτιος. Αν είχε προκύψει περιττός, θα έπρεπε να πάμε πίσω στο Βήμα 1, στην επιλογή του κ και να ξεκινήσουμε με άλλο κ.

Βήμα 4: Χρειάζεται να είναι άρτιος το ρ γιατί θα πάρουμε το μισό του, εδώ το 2. Αλλος ένας πρωταγωνιστής μπαίνει στη σκηνή. Είναι ο υ και αυτός έχει τιμή ίση με το υπόλοιπο στη δεύτερη προσπάθεια (επειδή ρ/2 ήταν ίσο με 2), δηλαδή υ = 4. Εδώ ελέγχουμε μήπως υ + 1 = Ν. Αν αυτό συμβαίνει, πηγαίνουμε πάλι πίσω σε νέα επιλογή τιμής για το κ. Αν όχι, όπως εδώ (υ+1 = 4+1 = 5 διάφορο του Ν = 15), προχωρούμε στο τελευταίο βήμα.

Βήμα 5: Οι αριθμοί που σε αυτούς αναλύεται ο Ν δίνονται από τον ΜΚΔ των (υ+1, Ν) και (υ-1, Ν). Εδώ έχουμε ΜΚΔ (4+1, 15) και ΜΚΔ (4-1, 15) που είναι τα 3 και 5 αντίστοιχα.

Τις ημέρες των εορτών πραγματοποιήθηκε μια τετράωρη παρουσίαση, απαθανατισμένη πλέον στο YouTube στις 17.12.2022, του κ. Στέφανου Τραχανά, καθηγητή Κβαντομηχανικής στο Πανεπιστήμιο Κρήτης, έπειτα από παράκληση της Ενωσης Φυσικών Κρήτης για να συζητήσουν σχετικά με την ύλη της Κβαντομηχανικής στο Λύκειο. Επειδή βρίσκουμε πως κάποια στοιχειώδη θέματα αναλύθηκαν με πολύ κατανοητό τρόπο και βρίσκονται στην περιφέρεια του υλικού που παρουσιάζεται εδώ, το συνιστούμε στους αναγνώστες της σειράς.

Πνευματική Γυμναστική

Δυο τρένα ξεκινούν στις 7 το πρωί το ένα από τον σταθμό Α για να φτθάσει στον σταθμό Β και το άλλο από τον σταθμό Β για να φτάσει στον Α. Οι σταθμοί είναι σε ευθεία γραμμή και τα τρένα κινούνται με σταθερές ταχύτητες. Το πρώτο τρένο φτάνει στον προορισμό του σε 8 ώρες και το δεύτερο σε 12 ώρες. Ποια χρονική στιγμή συναντά το ένα το άλλο;

Οι λύσεις των προηγούμενων κουίζ

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

Αντί για την κλασική προσέγγιση όπου θα πάρουμε τις δύο διαμέτρους D και D+2X10 = D+20 και από τον τύπο για το μήκος της περιφέρειας του κύκλου θα έχουμε πxD και πx(D+20), άρα η διαφορά τους θα είναι 20π, θα σκεφτούμε ως εξής: Οι ακτίνες των κύκλων δεν μας δίνονται, άρα μπορούμε να πάρουμε όποιες θέλουμε, αρκεί οι διάμετροί τους να έχουν διαφορά 20. Για τον εσωτερικό λοιπόν παίρνουμε ακτίνα ίση με 0, οπότε η διάμετρος του εξωτερικού κύκλου είναι 20 και το μήκος της περιφέρειάς του 20π. Αρα και η διαφορά τους 20π – 0 = 20π.

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

Έντυπη έκδοση Το Βήμα