Shor-Algorithmus

Eines der eindrucksvollsten Ergebnisse der Quanteninformatik ist der von Peter Shor entwickelte Algorithmus zur Faktorisierung großer Zahlen. Herkömmlich benötigt man bei klassischen Verfahren – insbesondere für sehr große Zahlen – extrem viel Rechenzeit, um eine Zahl in ihre Primfaktoren zu zerlegen. Genau hier kommt der Shor-Algorithmus ins Spiel: In einer idealen Quantenmaschine schafft er es, das Problem in (vergleichsweise) polynomialer Zeit zu lösen.


Warum ist das Faktorisieren großer Zahlen wichtig?

Die Schwierigkeit, große Zahlen in ihre Faktoren zu zerlegen, ist das Fundament vieler heute gängiger Verschlüsselungsverfahren (z. B. RSA). Sobald ein effizientes Quantenverfahren existiert, das solche Zahlen schnell knackt, sind diese Verfahren nicht mehr sicher. In der Praxis ist das einer der Gründe, warum aktuell intensiv an „post-quantum Krypto“ geforscht wird.


Die Funktionsweise in Kurzform

  • Superposition: Im Shor-Algorithmus versetzt man einen Teil der Qubits in einen Überlagerungszustand, sodass „alle möglichen Exponenten“ gleichzeitig durchgespielt werden können.
  • Kontrollierte Multiplikation: Mithilfe von sogenannten Controlled-Operationen entsteht eine Verschränkung zwischen dem Exponenten und einem „Arbeitsregister“.
  • Quantum Fourier Transform (QFT): Anschließend wird auf das Exponentenregister eine QFT angewendet, die dafür sorgt, dass sich die Periodeninformationen in den Messwahrscheinlichkeiten ablesen lassen.
  • Ausmessen & Faktorisierung: Mit einer gewissen Wahrscheinlichkeit bekommt man aus diesem Periodenwert nichttriviale Faktoren des ursprünglichen NNN.

Auch wenn die Erfolgschance pro Durchlauf nicht garantiert ist, lässt sich das Verfahren mehrfach wiederholen, um fast sicher eine Faktorisierung zu erhalten. Auf echten Quantencomputern wäre das für hinreichend große Zahlen revolutionär.


Teste eine einfache Simulation

Wenn du neugierig bist, wie so eine (stark vereinfachte) Quanten-Simulation für kleine Zahlen aussieht, haben wir einen interaktiven Prototyp erstellt:
Shors Algorithmus Demo (Toy Version)


In der realen Forschung werden heute bereits kleine Quantenchips eingesetzt, um Shors Algorithmus testweise zu implementieren – wenn auch noch nicht in Dimensionen, die reale Verschlüsselung gefährden. Trotzdem zeigt der Shor-Algorithmus eindrücklich, wie Quantencomputer in der Zukunft fundamentale Teile unserer digitalen Sicherheitsarchitektur umkrempeln könnten.

Programmieren heute

Vor Jahren, habe ich hier einen Beitrag über das Spiel Kalaha gepostet. Eine Version, die von einem Microprozessor (SCMP) über ein C-Programm auf JavaScript im Browser gelandet ist.

Heute in 5 Minuten mit ChatGPT. Der Promt: Kannst du ein kurzes Python Programm schreiben, gegen welches man das Spiel Kalaha spielen kann?

import random

def initialize_board():
return [4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0] # Spieler 1 auf 0-5, Kalaha auf 6; Spieler 2 auf 7-12, Kalaha auf 13

def print_board(board):
print("\nAktuelles Spielfeld:")
print(f" {board[12]} {board[11]} {board[10]} {board[9]} {board[8]} {board[7]}")
print(f"{board[13]} {board[6]}")
print(f" {board[0]} {board[1]} {board[2]} {board[3]} {board[4]} {board[5]}\n")

def is_game_over(board):
return all(pit == 0 for pit in board[:6]) or all(pit == 0 for pit in board[7:13])

def make_move(board, pit, player):
stones = board[pit]
board[pit] = 0
index = pit

while stones > 0:
index = (index + 1) % 14
if (player == 1 and index == 13) or (player == 2 and index == 6):
continue # Überspringe gegnerisches Kalaha
board[index] += 1
stones -= 1

# Überprüfen, ob der letzte Stein in einem leeren Loch des eigenen Bereichs landet
if player == 1 and 0 <= index <= 5 and board[index] == 1:
board[6] += board[index] + board[12 - index]
board[index] = board[12 - index] = 0
elif player == 2 and 7 <= index <= 12 and board[index] == 1:
board[13] += board[index] + board[12 - index]
board[index] = board[12 - index] = 0

# Überprüfen, ob der Zug endet
if (player == 1 and index == 6) or (player == 2 and index == 13):
return True # Spieler bekommt einen weiteren Zug

return False

def collect_remaining_stones(board):
board[6] += sum(board[:6])
board[13] += sum(board[7:13])
for i in range(6):
board[i] = 0
board[i + 7] = 0

def kalaha():
board = initialize_board()
player = 1

while not is_game_over(board):
print_board(board)
if player == 1:
print("Dein Zug! Wähle eine Grube (0-5):")
while True:
try:
pit = int(input("Grube: "))
if 0 <= pit <= 5 and board[pit] > 0:
break
else:
print("Ungültige Wahl. Bitte wähle eine nicht-leere Grube (0-5).")
except ValueError:
print("Bitte gib eine Zahl ein.")
else:
pit = random.choice([i for i in range(7, 13) if board[i] > 0])
print(f"Computer wählt Grube {pit - 7}.")

additional_turn = make_move(board, pit, player)
if not additional_turn:
player = 2 if player == 1 else 1

print("\nSpiel beendet!")
collect_remaining_stones(board)
print_board(board)

if board[6] > board[13]:
print("Glückwunsch! Du hast gewonnen!")
elif board[6] < board[13]:
print("Der Computer hat gewonnen. Viel Glück beim nächsten Mal!")
else:
print("Unentschieden!")

if __name__ == "__main__":
kalaha()

OK, Zufallszüge sind nett, aber nicht ganz das, was man möchte. Deshalb noch ein Promt: Diese Version hätte ich gerne gesichert und jetzt eine Version, die eine einfache alpha-beta Suche statt der Zufallsversion implementiert

import random
import math

def initialize_board():
return [4, 4, 4, 4, 4, 4, 0, 4, 4, 4, 4, 4, 4, 0] # Spieler 1 auf 0-5, Kalaha auf 6; Spieler 2 auf 7-12, Kalaha auf 13

def print_board(board):
print("\nAktuelles Spielfeld:")
print(f" {board[12]} {board[11]} {board[10]} {board[9]} {board[8]} {board[7]}")
print(f"{board[13]} {board[6]}")
print(f" {board[0]} {board[1]} {board[2]} {board[3]} {board[4]} {board[5]}\n")

def is_game_over(board):
return all(pit == 0 for pit in board[:6]) or all(pit == 0 for pit in board[7:13])

def make_move(board, pit, player):
stones = board[pit]
board[pit] = 0
index = pit

while stones > 0:
index = (index + 1) % 14
if (player == 1 and index == 13) or (player == 2 and index == 6):
continue # Überspringe gegnerisches Kalaha
board[index] += 1
stones -= 1

# Überprüfen, ob der letzte Stein in einem leeren Loch des eigenen Bereichs landet
if player == 1 and 0 <= index <= 5 and board[index] == 1:
board[6] += board[index] + board[12 - index]
board[index] = board[12 - index] = 0
elif player == 2 and 7 <= index <= 12 and board[index] == 1:
board[13] += board[index] + board[12 - index]
board[index] = board[12 - index] = 0

# Überprüfen, ob der Zug endet
if (player == 1 and index == 6) or (player == 2 and index == 13):
return True # Spieler bekommt einen weiteren Zug

return False

def collect_remaining_stones(board):
board[6] += sum(board[:6])
board[13] += sum(board[7:13])
for i in range(6):
board[i] = 0
board[i + 7] = 0

def evaluate_board(board):
return board[6] - board[13]

def alpha_beta_search(board, depth, alpha, beta, maximizing_player):
if depth == 0 or is_game_over(board):
return evaluate_board(board)

if maximizing_player:
max_eval = -math.inf
for pit in range(7, 13):
if board[pit] > 0:
new_board = board[:]
additional_turn = make_move(new_board, pit, 2)
eval = alpha_beta_search(new_board, depth - 1, alpha, beta, additional_turn)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = math.inf
for pit in range(0, 6):
if board[pit] > 0:
new_board = board[:]
additional_turn = make_move(new_board, pit, 1)
eval = alpha_beta_search(new_board, depth - 1, alpha, beta, not additional_turn)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval

def best_move(board, depth):
best_value = -math.inf
move = -1
for pit in range(7, 13):
if board[pit] > 0:
new_board = board[:]
additional_turn = make_move(new_board, pit, 2)
eval = alpha_beta_search(new_board, depth - 1, -math.inf, math.inf, additional_turn)
if eval > best_value:
best_value = eval
move = pit
return move

def kalaha():
board = initialize_board()
player = 1

while not is_game_over(board):
print_board(board)
if player == 1:
print("Dein Zug! Wähle eine Grube (0-5):")
while True:
try:
pit = int(input("Grube: "))
if 0 <= pit <= 5 and board[pit] > 0:
break
else:
print("Ungültige Wahl. Bitte wähle eine nicht-leere Grube (0-5).")
except ValueError:
print("Bitte gib eine Zahl ein.")
else:
pit = best_move(board, 5) # Alpha-Beta-Suche mit Tiefe 5
print(f"Computer wählt Grube {pit - 7}.")

additional_turn = make_move(board, pit, player)
if not additional_turn:
player = 2 if player == 1 else 1

print("\nSpiel beendet!")
collect_remaining_stones(board)
print_board(board)

if board[6] > board[13]:
print("Glückwunsch! Du hast gewonnen!")
elif board[6] < board[13]:
print("Der Computer hat gewonnen. Viel Glück beim nächsten Mal!")
else:
print("Unentschieden!")

if __name__ == "__main__":
kalaha()

Und Fertig! Leider gibt es kleiner Fehler:

def evaluate_board(board):
return board[6] - board[13]

hat das falsche Vorzeichen, board[13]-board[6], und das Spielende wird auch nicht ganz richtig erkannt, wenn ein Spieler gezwungen ist dem Geger wieder Spielzüge zur Verfügung zu stellen, aber …