Bukti keamanan yang ketat untuk uang kuantum Wiesner?

Dalam makalahnya yang terkenal "Conjugate Coding" (ditulis sekitar tahun 1970), Stephen Wiesner mengusulkan skema untuk uang kuantum yang tanpa syarat mustahil untuk dipalsukan, dengan asumsi bahwa bank penerbit memiliki akses ke meja raksasa angka acak, dan bahwa uang kertas dapat dibawa kembali ke bank untuk verifikasi. Dalam skema Wiesner, masing-masing uang kertas terdiri dari klasik "nomor seri" , bersama-sama dengan uang negara kuantum yang terdiri dari qubit unentangled, masing-masing baik $s$ $|\psi_s\rangle$ $n$

| 0 ⟩, | 1 ⟩, | + ⟩ = (| 0 ⟩ + | 1 ⟩) / \sqrt{2}, or | - ⟩ = (| 0 ⟩ - | 1 ⟩) / \sqrt{2} .

$|0\rangle,\ |1\rangle,\ |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2},\ \text{or}\ |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}.$

Bank mengingat deskripsi klasik untuk setiap . Dan karena itu, ketika dibawa kembali ke bank untuk verifikasi, bank dapat mengukur setiap qubit dari di dasar yang benar (baik atau ), dan memeriksa bahwa itu mendapat hasil yang benar. $|\psi_s\rangle$ $s$ $|\psi_s\rangle$ $|\psi_s\rangle$ $\{|0\rangle,|1\rangle\}$ ${|+\rangle,|-\rangle}$

Di sisi lain, karena hubungan ketidakpastian (atau alternatifnya, Teorema Tanpa Kloning), "jelas secara intuitif" bahwa, jika pemalsu yang tidak tahu basis yang benar mencoba untuk menyalin , maka probabilitas bahwa kedua negara output pemalsu ini lulus tes verifikasi bank dapat paling , untuk beberapa konstan . Selanjutnya, ini harus benar terlepas dari apa strategi penggunaan pemalsu, konsisten dengan mekanika kuantum (misalnya, bahkan jika penggunaan pemalsu mewah terjerat pengukuran pada ). $|\psi_s\rangle$ $c^n$ $c<1$ $|\psi_s\rangle$

Namun, ketika menulis makalah tentang skema uang kuantum lainnya, rekan penulis saya dan saya menyadari bahwa kami belum pernah melihat bukti yang kuat dari klaim di atas di mana pun, atau batas atas eksplisit pada : baik di koran asli Wiesner maupun di kemudian hari . $c$

Jadi, memiliki bukti seperti (dengan batas atas ) telah diterbitkan? Jika tidak, maka dapatkah seseorang memperoleh bukti semacam itu dengan cara yang lebih atau kurang langsung dari (katakanlah) versi perkiraan Teorema Tanpa Kloning, atau hasil tentang keamanan skema distribusi kunci kuantum BB84? $c$

Pembaruan: Sehubungan dengan diskusi dengan Joe Fitzsimons di bawah ini, saya harus mengklarifikasi bahwa saya mencari lebih dari sekadar pengurangan dari keamanan BB84. Sebaliknya, saya mencari batas atas eksplisit pada kemungkinan pemalsuan yang berhasil (yaitu, pada ) --- dan idealnya, juga beberapa pemahaman tentang seperti apa strategi pemalsuan yang optimal. Yaitu, apakah strategi optimal cukup mengukur setiap qubit dari independen, mengatakan di dasar $c$ $|\psi_s\rangle$

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

$\{ \cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle, \sin(\pi/8)|0\rangle-\cos(\pi/8)|1\rangle \}?$

Atau ada strategi pemalsuan terjerat yang lebih baik?

Pembaruan 2: Saat ini, strategi pemalsuan terbaik yang saya tahu adalah (a) strategi di atas, dan (b) strategi yang hanya mengukur setiap qubit di dasar dan "harapan untuk yang terbaik." Menariknya, kedua strategi ini ternyata mencapai probabilitas keberhasilan (5/8) ⁿ . Jadi, dugaan saya saat ini adalah (5/8) ⁿ mungkin jawaban yang tepat. Bagaimanapun, fakta bahwa 5/8 lebih rendah $\{|0\rangle,|1\rangle\}$ terikat pada c mengesampingkan setiap argumen keamanan untuk skema Wiesner yang "terlalu" sederhana (misalnya, setiap argumen yang menyatakan bahwa tidak ada yang tidak dapat dilakukan oleh seorang pemalsu, dan oleh karena itu jawaban yang tepat adalah c = 1/2).

Pembaruan 3: Tidak, jawaban yang tepat adalah (3/4) ⁿ ! Lihat utas diskusi di bawah jawaban Abel Molina.

quantum-computing Scott Aaronson
sumber

Selamat Datang di TP.SE Scott! Senang melihatmu di sini.

Joe Fitzsimons

Sepertinya skema Wiesner sesuai persis dengan BB84 di mana Anda memposting pilih pada Bob telah memilih basis pengukuran yang sama persis seperti yang dimiliki Alice untuk persiapan (karena bank adalah Alice dan Bob). Jelas bahwa bank dapat memilih basis pengukuran secara acak, dan mensimulasikan BB84, yang akan menghasilkan keamanan yang sangat lemah (karena Anda akan mempertimbangkan pengukuran yang persis sama tetapi hanya pada subset dari qubit), sehingga Anda pasti dapat menggunakan bukti BB84 untuk menurunkan mengikat keamanan skema uang kuantum. Mungkin aku melewatkan sesuatu.

Joe Fitzsimons

Terima kasih atas sambutan dan jawabannya, Joe! FWIW, saya membagikan intuisi Anda bahwa bukti keamanan untuk skema Wiesner seharusnya "lebih mudah" daripada bukti keamanan untuk BB84. Namun, dengan argumen itu (seperti halnya argumen lainnya), saya terus kembali ke pertanyaan yang sama: "jadi lalu apa batas atas c?"

Scott Aaronson

Tentunya itu dibatasi oleh probabilitas menentukan kunci di BB84.

Joe Fitzsimons

Juga, sementara itu boleh saja untuk menyimpulkan keamanan skema Wiesner dari keamanan BB84 jika itu satu-satunya / alternatif terbaik, saya bertahan dengan harapan bahwa harus ada bukti yang lebih langsung dan informatif. Selain itu, tampaknya masuk akal bahwa bukti langsung akan diperlukan untuk mendapatkan batas atas eksplisit pada c, atau untuk mendapatkan batas yang "masuk akal" tersebut (lebih seperti 0,9 daripada seperti 0,99999).

Scott Aaronson

Jawaban:

Sepertinya interaksi ini dapat dimodelkan dengan cara berikut:

$|000\rangle$ $|101\rangle$ $(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$ $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$
Bob melakukan saluran kuantum arbitrer yang mengirimkan qubitnya ke dua qubit, yang kemudian dikembalikan ke Alice.
Alice melakukan pengukuran proyektif pada empat qubit yang dimilikinya.

Jika saya tidak salah tentang ini (dan maaf jika saya salah), ini termasuk dalam formalisme dari Gutoski dan Watrous yang disajikan di sini dan di sini , yang menyiratkan bahwa:

Dari Teorema 4.9 dalam yang kedua, adalah optimal bagi Bob untuk bertindak secara independen ketika Alice mengulangi proses ini dengan beberapa qubit secara independen, jika tujuan Bob adalah untuk selalu membodohi Alice.
Dimungkinkan untuk mendapatkan nilai c dari program semidefinite kecil. Anda dapat menemukan rincian lebih lanjut tentang cara mendapatkan program ini di Bagian 3 di sini . Lihat komentar untuk kode cvx untuk program dan nilainya.

Abel Molina
sumber

Mengikuti saran Abel, tampak bahwa nilai optimalnya adalah c = 3/4.

Saya baru saja mendapatkan nilai yang sama yaitu 3/4. Kekuatan penjelasnya kecil, tetapi kode komputernya ada di cs.uwaterloo.ca/~amolinap/scriptWeisner.m dan cs.uwaterloo.ca/~amolinap/prtrace.m .

Abel Molina

Strategi ini diberikan oleh saluran kuantum yang perwakilan Choi-Jamielkowski adalah solusi optimal untuk program semidefinite. Lihat cs.uwaterloo.ca/~amolinap/optSolution.txt untuk tautan ke solusi semacam itu (qubit yang paling tidak signifikan adalah yang diterima oleh Bob, dan dua lainnya adalah yang ia kirimkan ke Alice). Jika perhitungan saya benar, saluran yang sesuai mengirimkan | 0> ke (| 01> + | 10>) / √2 dengan probabilitas 1/6, dan ke (3 | 00> + | 11>) / √10 dengan probabilitas 5 / 6. | 1> dikirim ke (| 01> + | 10>) / √2 dengan probabilitas 1/6, dan ke (| 00> +3 | 11>) / √10 dengan probabilitas 5/6

Abel Molina

Demikian pula, (| 0> + | 1>) / √2 dikirim ke (| 11> - | 00>) / √2 dengan probabilitas 1/6, dan ke (| 00> +1/2 | 01> +1 / 2 | 10> + | 11>) / √ (5/2) dengan probabilitas 5/6. Demikian pula, (| 0> - | 1>) / √2 dikirim ke (| 11> - | 00>) / √2 dengan probabilitas 1/6, dan ke (| 00> -1/2 | 01> -1 / 2 | 10> + | 11>) / √ (5/2) dengan probabilitas 5/6.

Abel Molina

Karena jawaban @ AbelMolina telah dikonversi juga menjadi makalah arXiv, arxiv.org/abs/1202.4010 , saya menambahkan tautan untuk pembaca masa depan.

Frédéric Grosshans

$\alpha |0\rangle + \beta |1\rangle$ $\alpha$ $\beta\in \mathbb{R}\:$

{(\frac{1}{2} + \frac{1}{\sqrt{8}})}^{2 n} \approx {.72855}^{n}

$\left(\frac{1}{2}+ \frac{1}{\sqrt{8}}\right)^{2n} \approx .72855^n$

n

$n$

(\frac{5}{8})^{n}

$(\frac{5}{8})^n$

$\sum_{i=1}^2 A_i \rho A_i^\dagger$

A_{1} = (\begin{array}{cc} \frac{1}{2} + \frac{1}{\sqrt{8}} & 0 \\ 0 & \frac{1}{\sqrt{8}} \\ 0 & \frac{1}{\sqrt{8}} \\ \frac{1}{2} - \frac{1}{\sqrt{8}} & 0 \end{array}) A_{2} = (\begin{array}{cc} 0 & \frac{1}{2} - \frac{1}{\sqrt{8}} \\ \frac{1}{\sqrt{8}} & 0 \\ \frac{1}{\sqrt{8}} & 0 \\ 0 & \frac{1}{2} + \frac{1}{\sqrt{8}} \end{array}) .

$A_1 = \left( \begin{array}{cc} \frac{1}{2}+\frac{1}{\sqrt{8}} & 0\\ 0 & \frac{1}{\sqrt{8}}\\ 0 & \frac{1}{\sqrt{8}}\\ \frac{1}{2}-\frac{1}{\sqrt{8}} & 0 \end{array} \right) \ \ \ \ A_2 = \left(\begin{array}{cc} 0& \frac{1}{2}-\frac{1}{\sqrt{8}} \\ \frac{1}{\sqrt{8}}&0\\ \frac{1}{\sqrt{8}}&0\\ 0&\frac{1}{2}+\frac{1}{\sqrt{8}} \end{array} \right) .$

$\sum_{i=1}^2 A_i \rho A_i^\dagger$

A_{1} = \frac{1}{\sqrt{12}} (\begin{array}{cc} 3 & 0 \\ 0 & 1 \\ 0 & 1 \\ 1 & 0 \end{array}) A_{2} = \frac{1}{\sqrt{12}} (\begin{array}{cc} 0 & 1 \\ 1 & 0 \\ 1 & 0 \\ 0 & 3 \end{array}) .

$A_1 = \frac{1}{\sqrt{12}}\left( \begin{array}{cc} 3 & 0\\ 0 & 1\\ 0 & 1\\ 1 & 0 \end{array} \right) \ \ \ \ A_2 = \frac{1}{\sqrt{12}}\left(\begin{array}{cc} 0& 1 \\ 1&0\\ 1&0\\ 0&3 \end{array} \right) .$

Ini jelas berasal dari keluarga transformasi yang sama, tetapi telah dioptimalkan untuk memenuhi fungsi tujuan yang berbeda. Keluarga transformasi kovarian ini tampaknya diberikan oleh

A_{1} = \frac{1}{\sqrt{2 x^{2} + 4 y^{2}}} (\begin{array}{cc} x + y & 0 \\ 0 & y \\ 0 & y \\ x - y & 0 \end{array}) A_{2} = \frac{1}{\sqrt{2 x^{2} + 4 y^{2}}} (\begin{array}{cc} 0 & x - y \\ y & 0 \\ y & 0 \\ 0 & x + y \end{array}) .

$A_1 = \frac{1}{\sqrt{2x^2+4y^2}}\left( \begin{array}{cc} x+y & 0\\ 0 & y\\ 0 & y\\ x-y & 0 \end{array} \right) \ \ \ \ A_2 = \frac{1}{\sqrt{2x^2+4y^2}}\left(\begin{array}{cc} 0& x-y \\ y&0\\ y&0\\ 0&x+y \end{array} \right) .$

Peter Shor
sumber

Terima kasih, Peter! Akan sangat bagus untuk menunjukkan optimalitas atau bahkan mendekati optimalitas cloner mereka. Untuk itu, saya kira langkah pertama akan menunjukkan bahwa serangan optimal adalah individual daripada kolektif.

Scott Aaronson

Jika pendekatan Abel Molina berhasil, itu harus menunjukkan ini. Jika tidak, Anda harus dapat menggunakan teknik-teknik dalam makalah cloner optimal untuk mendapatkan batas atas, tetapi saya tidak segera tahu apa yang akan terjadi.

Peter Shor

(| 0 ⟩ + i | 1 ⟩) / \sqrt{2}

$(|0\rangle + i |1\rangle)/\sqrt{2}$

(| 0 ⟩ - i | 1 ⟩) / \sqrt{2}

$(|0\rangle - i |1\rangle)/\sqrt{2}$

c = 2 / 3

$c = 2/3$

x = y = 1

$x = y = 1$

x = y = 1

$x=y=1$

Saya tidak tahu bukti keamanan yang dipublikasikan. Saya akan berpikir cara paling sederhana dan batas terkuat akan datang dari perkiraan tidak ada kloning, tapi saya kira Anda akan memerlukan versi khusus untuk negara-negara BB84. Bahkan pengurangan dari BB84 tidak jelas, karena kondisi keamanan untuk BB84 berbeda.

Saya pikir Anda bisa mendapatkan bukti secara langsung sebagai konsekuensi dari bukti keamanan enkripsi yang tidak dapat dikloning ( quant-ph / 0210062 ). Ini tidak akan mendapatkan batas atas yang ketat pada probabilitas kecurangan, tetapi setidaknya memberikan keamanan.

$\rho_k$

Ini dapat digunakan untuk membuat skema uang kuantum: Bank A menggunakan enkripsi yang tidak dapat dikloning untuk mengenkripsi string acak "pesan". Ada skema enkripsi yang tidak dapat dikloning yang pada dasarnya adalah BB84, jadi ini bisa memberikan skema Weisner. Eve mencegat uang, berinteraksi dengannya, dan mengirimkan orisinal yang dimodifikasi itu ke Bank B. Dia juga mencoba membuat salinan, yang masuk ke Bank C. Bank B dan C menerima jika negara yang diberikan kepada mereka melewati tes menguping enkripsi yang tidak dapat dikloning , dan jika mereka men-decode string "message" yang benar. Properti enkripsi yang tidak dapat dikloning b mengatakan bahwa, dengan probabilitas tinggi, salinan B gagal dalam tes menguping atau salinan C hampir tidak berisi informasi tentang pesan tersebut. Ini lebih kuat dari yang dibutuhkan, tetapi cukup untuk membuktikan keamanan.

Untuk serangan asimptotik terbaik, saya bayangkan, karena quantum de Finetti, bahwa serangan kolektif terbaik sama dengan serangan individu terbaik.

sumber

Terima kasih banyak, Daniel! Saya akan terus mencari argumen yang memberikan batasan eksplisit pada c, tetapi sementara itu, ini sangat membantu. Saya melanjutkan dan menandai jawaban Anda sebagai "diterima."

Scott Aaronson