In den letzten Jahrzehnten haben sich Rechentempo und Zuverlässigkeit von Computern drastisch erhöht. Moderne Chips packen fast eine Milliarde Transistoren auf eine zentimetergroße Siliziumscheibe, und künftig werden Computerelemente noch weiter schrumpfen, bis hinunter zur Größe einzelner Moleküle. Solche Rechner dürften höchst ungewohnt anmuten, denn sie werden nach quantenmechanischen Regeln arbeiten – gemäß den physikalischen Gesetzen, die das Verhalten von Atomen und Elementarteilchen erklären. Daran knüpft sich die große Erwartung, dass Quantencomputer bestimmte wichtige Aufgaben wesentlich schneller auszuführen vermögen als herkömmliche Rechner.

Die wohl bekannteste dieser Aufgaben ist das Faktorisieren einer großen Zahl, die das Produkt zweier Primzahlen ist. Zwei Primzahlen zu multiplizieren fällt Computern leicht, selbst wenn die Zahlen hunderte Ziffern lang sind, aber der umgekehrte Prozess – das Herleiten der Primfaktoren – ist so schwierig, dass er die Grundlage fast aller heute gebräuchlichen Verschlüsselungstechniken bildet, vom Onlinebanking bis zur Übertragung von Staatsgeheimnissen. Im Jahr 1994 zeigte Peter Shor an den Bell Laboratories in Murray Hill (New Jersey), dass ein Quantencomputer diese Kodes theoretisch leicht knacken könnte, weil das Tempo, in dem er Zahlen zu faktorisieren vermag, exponentiell höher ist als das jedes bekannten klassischen Algorithmus. Und 1997 zeigte Lov K. Grover, damals ebenfalls an den Bell Labs, dass ein solches Gerät das Durchsuchen einer unsortierten Datenmenge erheblich beschleunigen würde – beispielsweise das Auffinden einer Person in einem Telefonbuch, von der man nur die Telefonnummer kennt.

Doch einen Quantencomputer tatsächlich zu bauen wird gar nicht leicht sein. Seine Hardware – die Atome, Photonen oder künstlichen Mikrostrukturen, welche die Daten als...