Strenger Sicherheitsnachweis für Wiesners Quantengeld?

50

Stephen Wiesner schlug in seiner berühmten Zeitung "Conjugate Coding" (geschrieben um 1970) ein Schema für Quantengeld vor, das bedingungslos nicht zu fälschen ist, vorausgesetzt, die ausstellende Bank hat Zugang zu einer riesigen Tabelle von Zufallszahlen, und Banknoten können mitgebracht werden zurück zur Bank zur Überprüfung. In Wiesner Schema, jede Banknote besteht aus einer klassischen „Seriennummer“ zusammen mit einem Quanten Geld Zustand | ψ s bestehend aus n unverflochtene Qubits, entweder jedess|ψsn

|0, |1, |+=(|0+|1)/2, or |=(|0|1)/2.

Die Bank erinnert sich an eine klassische Beschreibung von für alle s . Und deshalb, wenn | ψ s zurück an die Bank zur Überprüfung gebracht, die Bank jedes Qubit der messen | ψ s in der richtigen Basis (entweder { | 0 , | 1 } oder | + , | - ) und prüfen, ob sie die richtigen Ergebnisse erhalten.|ψss|ψs|ψs{|0,|1}|+,|

Andererseits ist es aufgrund der Unsicherheitsbeziehung (oder alternativ des No-Cloning-Theorems) "intuitiv offensichtlich", dass ein Fälscher, der die richtigen Grundlagen nicht kennt, versucht, zu kopieren ψ s , dann ist die Wahrscheinlichkeit , dass beide der Ausgangszustände der Fälscher den Verifizierungstest der Bank passieren höchstens sein kann , c n für eine Konstante c < 1 . Darüber hinaus sollte die wahr sein , unabhängig davon , welche Strategie der Fälscher Anwendungen, im Einklang mit der Quantenmechanik (zB auch wenn die Fälscher Anwendungen Phantasie verstrickt Messungen an | & psgr; s ).|ψscnc<1|ψs

Als mein Mitautor und ich jedoch eine Abhandlung über andere Quantengeldsysteme verfassten, stellten wir fest, dass wir niemals einen strengen Beweis für die oben genannte Behauptung oder eine explizite Obergrenze für : weder in Wiesners Originalarbeit noch in einer späteren gesehen hatten .c

So hat ein solcher Beweis (mit einer oberen auf gebunden ) veröffentlicht? Wenn nicht, kann man dann einen solchen Beweis auf mehr oder weniger einfache Weise aus (etwa) ungefähren Versionen des No-Cloning-Theorems oder aus Ergebnissen über die Sicherheit des BB84-Quantenschlüsselverteilungsschemas ableiten?c

Update: Angesichts der folgenden Diskussion mit Joe Fitzsimons sollte klargestellt werden, dass ich mehr als nur eine Reduzierung der Sicherheit von BB84 anstrebe. Ich suche vielmehr eine explizite Obergrenze für die Wahrscheinlichkeit einer erfolgreichen Fälschung (dh für ) - und im Idealfall auch ein Verständnis dafür, wie die optimale Fälschungsstrategie aussieht. Dh, misst die optimale Strategie einfach jedes Qubit von | ψ s unabhängig, sagen wir in der Basisc|ψs

{cos(π/8)|0+sin(π/8)|1,sin(π/8)|0cos(π/8)|1}?

Oder gibt es eine verwickelte Fälschungsstrategie, die es besser macht?

Update 2: Im Moment sind die besten Fälschungsstrategien, die ich kenne, (a) die oben genannte Strategie und (b) die Strategie, die einfach jedes Qubit in misst 0 , | 1 } Basis und „Hoffnungen auf das Beste.“ Interessanterweise erzielen beide Strategien eine Erfolgswahrscheinlichkeit von (5/8) n . Meine derzeitige Vermutung ist, dass (5/8) n die richtige Antwort sein könnte. In jedem Fall ist die Tatsache, dass 5/8 eine niedrigere ist{|0,|1} gebunden an c schließt jedes Sicherheitsargument für Wiesners Schema aus, das "zu" einfach ist (zum Beispiel jedes Argument, das besagt, dass ein Fälscher nichts Nicht-Triviales tun kann, und daher lautet die richtige Antwort c = 1/2).

Update 3: Nein, die richtige Antwort ist (3/4) n ! Siehe den Diskussionsthread unter der Antwort von Abel Molina.

Scott Aaronson
quelle
3
Willkommen bei TP.SE Scott! Schön, dich hier zu sehen.
Joe Fitzsimons
1
Wie es scheint, entspricht Wiesners Schema genau BB84, bei dem Sie die Post-Select-Methode für Bob ausgewählt haben, indem Sie genau die Messgrundlagen ausgewählt haben, die Alice für die Vorbereitung hat (da die Bank sowohl Alice als auch Bob ist). Natürlich könnte die Bank stattdessen die Messbasis nach dem Zufallsprinzip auswählen und BB84 simulieren, was zu einer streng schwächeren Sicherheit führen würde (da Sie genau die gleichen Messungen berücksichtigen würden, jedoch nur für eine Teilmenge von Qubits), sodass Sie mit Sicherheit einen BB84-Beweis zum Verringern verwenden können gebunden die Sicherheit des Quantengeldschemas. Vielleicht fehlt mir aber etwas.
Joe Fitzsimons
Danke für die Begrüßung und die Antwort, Joe! FWIW, ich teile Ihre Intuition, dass ein Sicherheitsnachweis für Wiesners Schema "strikt einfacher" sein sollte als ein Sicherheitsnachweis für BB84. Mit diesem Argument (wie mit jedem anderen) komme ich jedoch immer wieder auf die gleiche Frage zurück: "Also, wie hoch ist dann die Obergrenze für c?"
Scott Aaronson
Sicherlich ist es durch die Wahrscheinlichkeit der Bestimmung des Schlüssels in BB84 begrenzt.
Joe Fitzsimons
Auch wenn es in Ordnung wäre, die Sicherheit von Wiesners Schema von der Sicherheit von BB84 abzuleiten, wenn dies die einzige / beste Alternative ist, hoffe ich, dass es einen direkteren und informativeren Beweis geben sollte. Darüber hinaus erscheint es plausibel, dass ein direkter Beweis erforderlich wäre, um eine explizite obere Schranke für c zu erhalten, oder um eine "vernünftige" solche Schranke zu erhalten (eher 0,9 als 0,99999).
Scott Aaronson

Antworten:

33

Anscheinend kann diese Interaktion folgendermaßen modelliert werden:

  1. Alice bereitet einen der Staaten vor |000|101(|0+|1)|10/2(|0|1)|11/2
  2. Bob führt einen beliebigen Quantenkanal aus, der sein Qubit an zwei Qubits sendet, die dann an Alice zurückgegeben werden.
  3. Alice führt eine projektive Messung an den vier Qubits durch, die sie besitzt.

Wenn ich mich nicht irre (und es tut mir leid, wenn ich mich irre), fällt dies in den Formalismus von Gutoski und Watrous, der hier und hier vorgestellt wurde , was impliziert, dass:

  1. Ab Satz 4.9 ist es für Bob optimal, unabhängig zu handeln, wenn Alice diesen Vorgang mit mehreren Qubits auf unabhängige Weise wiederholt, wenn es das Ziel von Bob ist, Alice immer zum Narren zu halten.
  2. Es ist möglich, den Wert von c aus einem kleinen semidefiniten Programm zu erhalten. Weitere Informationen zum Erwerb dieses Programms finden Sie in Abschnitt 3 hier . Siehe die Kommentare zum cvx-Code für das Programm und seinen Wert.
Abel Molina
quelle
10
Nach Abels Vorschlag scheint der optimale Wert c = 3/4 zu sein.
3
Ich habe gerade den gleichen Wert von 3/4 erhalten. Die Erklärungskraft ist gering, aber der Computercode befindet sich unter cs.uwaterloo.ca/~amolinap/scriptWeisner.m und cs.uwaterloo.ca/~amolinap/prtrace.m .
Abel Molina
4
Die Strategie wird durch einen Quantenkanal vorgegeben, dessen Choi-Jamielkowski-Darstellung eine optimale Lösung für das semidefinite Programm darstellt. Unter cs.uwaterloo.ca/~amolinap/optSolution.txt finden Sie einen Link zu einer solchen Lösung (das niedrigstwertige Qubit ist das von Bob empfangene und die anderen beiden sind diejenigen, die er an Alice sendet). Wenn meine Berechnungen korrekt sind, sendet der entsprechende Kanal | 0> mit einer Wahrscheinlichkeit von 1/6 an (| 01> + | 10>) / √2 und mit einer Wahrscheinlichkeit von 5 an (3 | 00> + | 11>) / √10 / 6. | 1> wird an (| 01> + | 10>) / √2 mit einer Wahrscheinlichkeit von 1/6 und an (| 00> +3 | 11>) / √10 mit einer Wahrscheinlichkeit von 5/6 gesendet
Abel Molina
4
In ähnlicher Weise wird (| 0> + | 1>) / √2 mit einer Wahrscheinlichkeit von 1/6 an (| 11> - | 00>) / √2 und an (| 00> +1/2 | 01> +1 gesendet / 2 | 10> + | 11>) / √ (5/2) mit der Wahrscheinlichkeit 5/6. In ähnlicher Weise wird (| 0> - | 1>) / √2 mit einer Wahrscheinlichkeit von 1/6 an (| 11> - | 00>) / √2 und an (| 00> -1/2 | 01> -1 gesendet / 2 | 10> + | 11>) / √ (5/2) mit der Wahrscheinlichkeit 5/6.
Abel Molina
3
Da @ AbelMolina Antwort hat auch ein arXiv Papier umgewandelt worden, arxiv.org/abs/1202.4010 , füge ich den Link für zukünftige Leser.
Frédéric Grosshans
19

Die Frage der Klonierung der BB84-Zustände wurde in der Arbeit "Phase covariant quantum cloning" von Dagmar Bruß, Mirko Cinchetti, G. Mauro d'Ariano und Chiara Macchiavello [ Phys Rev. A, 62, 012302 (2000), behandelt. 36]. Sie geben einen optimalen cloner für diese Zustände (die auch ein optimaler cloner für alle Staaten α|0+β|1αβR

(12+18)2n.72855n
n(58)n

i=12AiρAi

A1=(12+18001801812180)    A2=(01218180180012+18).

i=12AiρAi wobei:

A1=112(30010110)    A2=112(01101003).

Diese stammen eindeutig aus derselben Familie von Transformationen, wurden jedoch optimiert, um verschiedene Zielfunktionen zu erfüllen. Diese Familie der kovarianten Transformationen scheint gegeben zu sein durch

A1=12x2+4y2(x+y00y0yxy0)    A2=12x2+4y2(0xyy0y00x+y).
Peter Shor
quelle
Danke, Peter! Es wäre großartig, die Optimalität oder sogar nahezu die Optimalität ihres Kloners zu zeigen. Ich denke, der erste Schritt würde darin bestehen, zu zeigen, dass der optimale Angriff eher individuell als kollektiv ist.
Scott Aaronson
Wenn der Ansatz von Abel Molina funktioniert, sollte er dies demonstrieren. Wenn nicht, sollten Sie in der Lage sein, die Techniken in den optimalen Klonerpapieren zu verwenden, um eine Obergrenze zu erhalten, aber ich weiß nicht sofort, was es sein würde.
Peter Shor
(|0+i|1)/2(|0i|1)/2c=2/3x=y=1
x=y=1
16

Ich kenne keinen veröffentlichten Sicherheitsnachweis. Ich würde denken, dass der einfachste Weg und die stärkste Bindung vom ungefähren Nicht-Klonen herrühren, aber ich denke, Sie benötigen eine Version, die auf die BB84-Staaten spezialisiert ist. Auch eine Reduzierung gegenüber BB84 ist nicht ersichtlich, da die Sicherheitsbedingung für BB84 anders ist.

Ich denke, Sie können als Folge des Sicherheitsnachweises für nicht klonbare Verschlüsselung ( quant-ph / 0210062) problemlos einen Beweis erhalten ). Dies wird keine enge Obergrenze für die Betrugswahrscheinlichkeit erhalten, gibt aber zumindest Sicherheit.

ρk . Dies wird als Nicht-Klonen-Ergebnis interpretiert: Eva könnte den Chiffretext stehlen, aber sie kann ihn nicht kopieren, ohne Bobs empfangene Nachricht durcheinander zu bringen.

Dies kann verwendet werden, um ein Quantengeldschema zu erstellen: Bank A verwendet eine nicht klonbare Verschlüsselung, um eine zufällige Zeichenfolge der "Nachricht" zu verschlüsseln. Es gibt ein nicht klonbares Verschlüsselungsschema, das im Grunde genommen BB84 ist. Dies könnte Weisners Schema ergeben. Eve fängt das Geld ab, interagiert mit ihm und sendet das geänderte Original an die Bank B. Sie versucht auch, eine Kopie an die Bank C zu senden , und wenn sie die richtige zufällige "message" Zeichenfolge dekodieren. Die nicht klonbare Verschlüsselungseigenschaft b besagt, dass entweder die Kopie von B mit hoher Wahrscheinlichkeit den Abhörtest nicht besteht oder dass die Kopie von C fast keine Informationen über die Nachricht enthält. Dies ist stärker als nötig, aber ausreichend, um die Sicherheit zu beweisen.

Für die beste asymptotische Attacke stelle ich mir aufgrund von quantum de Finetti vor, dass die beste kollektive Attacke die gleiche ist wie die beste individuelle Attacke.


quelle
Vielen Dank, Daniel! Ich werde weiterhin nach einem Argument suchen, das eine explizite Bindung an c enthält, aber in der Zwischenzeit ist dies äußerst hilfreich. Ich ging voran und markierte Ihre Antwort als "akzeptiert".
Scott Aaronson