Gibt es eine allgemeine Aussage darüber, welche Arten von Problemen mit einem Quantencomputer effizienter gelöst werden können?
Ganz allgemein gilt, dass ein Quantencomputer keine Probleme lösen kann, die ein klassischer Computer nicht lösen kann. Es ist lediglich eine Frage der Komplexität des Lösungsalgorithmus.
Bei klassischen Computern teilen wir Probleme im Wesentlichen in zwei Klassen ein:
P: Probleme, die in polynomieller Zeit gelöst werden können
NP: Probleme, für die das eben nicht gilt, also im Wesentlichen eine exponentielle Komplexität haben
Im Rahmen der Quantencomputingtheorie haben Wissenschaftler eine neue Klasse definiert, BQP (bounded-error quantum polynomial time). Es kann theoretisch nachgewiesen werden, dass P eine Teilmenge von BQP ist, andererseits vermuten Wissenschaftler, dass es Probleme in BQP gibt, die nicht in P liegen. Da wir andererseits aber bis heute nicht einmal nachweisen können, ob P != NP ist, ist das erst mal nur eine Vermutung. Theoretisch könnte auch gelten dass P = BQP = NP.
Wenn wir also fragen, welche Problem in BQP liegen könnten, aber nicht in P, bei denen also Quantencomputer gegenüber klassischen Computern Vorteile bringen könnten, dann schauen wir als erstes auf solche Probleme, die wir bis heute nicht effizient in polynomieller Zeit lösen können.
Eines der meistuntersuchten Probleme dabei ist die Primfaktorzerlegung, also die Frage aus welchen Primfaktoren eine Zahl besteht. Die Tatsache, dass wir dieses Problem bis heute nicht effizient lösen können, ist eine zentrale Grundlage der Public Key Kryptographie, weshalb daran so intensiv geforscht wird.