Quanten-Fingerabdrücke

Klassisches Fingerabdrücken assoziiert mit jeder Zeichenkette eine kürzere Zeichenkette (ihren Fingerabdruck), sodass zwei verschiedene Zeichenketten mit kleiner Fehlerwahrscheinlichkeit allein durch den Vergleich ihrer Fingerabdrücke unterschieden werden können. Die Fingerabdrücke können nicht exponentiell kleiner gemacht werden als die ursprünglichen Zeichenketten, es sei denn, die Parteien, die die Fingerabdrücke vorbereiten, haben Zugang zu korrelierten Zufallsquellen. Wir zeigen, dass Fingerabdrücke, die aus Quanteninformation bestehen, exponentiell kleiner gemacht werden können als die ursprünglichen Zeichenketten, ohne dass es Korrelationen oder Verschränkungen zwischen den Parteien gibt. Dies impliziert eine exponentielle Quanten/klassische Kluft für das Gleichheitsproblem im simultanen Nachrichtenübertragungsmodell der Kommunikationskomplexität.