Editorial Ilmu Komputer & AI
Open AccessOA2026
Batas bawah baru untuk CDS dan f-routing
Ringkasan Hasegawa & Mataraarachchi (2026) tentang biaya keterkaitan kuantum, CDS yang robust, dan f-routing yang sempurna satu sisi
Atsuya Hasegawa; Ranitha Mataraarachchiยท 2026ยท DOI 10.48550/arXiv.2609.24291
Masalah inti
Memahami biaya entanglement dari non-local quantum computation (NLQC) relevan bagi teori kompleksitas, kriptografi, gravitasi kuantum, dan bidang terkait. Kasus khusus yang sentral adalah -routing, yang dimotivasi sebagian oleh verifikasi posisi kuantum. Membuktikan batas bawah pada biaya entanglement-nya dalam pengaturan yang sepenuhnya robust telah menjadi masalah terbuka utama dalam NLQC. Termotivasi oleh masalah ini, penulis menetapkan dua batas bawah yang saling terkait. Pertama, mereka mempelajari biaya shared randomness dari conditional disclosure of secrets (CDS) yang robust. Keterkaitan antara CDS dan -routing yang ditetapkan oleh Allerstorfer dkk. (Quantum 2024) menjadikan pemahaman kompleksitas randomness dari CDS yang robust sebagai langkah alami menuju batas bawah untuk masalah routing yang sepenuhnya robust. Kedua, mereka mempertimbangkan -routing yang sempurna satu sisi, di mana protokol bersifat eksak pada satu kelas input dan memiliki galat konstan pada kelas lainnya.
Inovasi
Makalah ini menyajikan dua hasil utama. Pertama, untuk CDS yang robust, biaya shared randomness dibatasi bawah oleh logaritma dari kompleksitas komunikasi SMP deterministik. Secara formal, untuk setiap protokol CDS yang robust untuk fungsi , biaya shared randomness memenuhi:
di mana
adalah kompleksitas komunikasi SMP deterministik dari . Batas ini berlaku bahkan ketika komunikasi dan private randomness tidak dibatasi. Batas ini ketat untuk fungsi equality. Kedua, untuk -routing yang sempurna satu sisi, biaya entanglement dibatasi bawah oleh sign rank dari matriks terkait. Secara khusus, untuk fungsi hasil kali dalam, hal ini menghasilkan batas bawah linear pada biaya entanglement di kedua pengaturan sempurna satu sisi, yang cocok dengan batas atas yang diketahui. Secara spesifik, untuk fungsi hasil kali dalam pada string -bit, biaya entanglement adalah ebits, yang cocok dengan batas atas yang diketahui sebesar ebits.
Memahami biaya entanglement dari non-local quantum computation (NLQC) relevan bagi teori kompleksitas, kriptografi, gravitasi kuantum, dan bidang terkait. Kasus khusus yang sentral adalah -routing, yang dimotivasi sebagian oleh verifikasi posisi kuantum. Membuktikan batas bawah pada biaya entanglement-nya dalam pengaturan yang sepenuhnya robust telah menjadi masalah terbuka utama dalam NLQC. Termotivasi oleh masalah ini, penulis menetapkan dua batas bawah yang saling terkait. Pertama, mereka mempelajari biaya shared randomness dari conditional disclosure of secrets (CDS) yang robust. Keterkaitan antara CDS dan -routing yang ditetapkan oleh Allerstorfer dkk. (Quantum 2024) menjadikan pemahaman kompleksitas randomness dari CDS yang robust sebagai langkah alami menuju batas bawah untuk masalah routing yang sepenuhnya robust. Kedua, mereka mempertimbangkan -routing yang sempurna satu sisi, di mana protokol bersifat eksak pada satu kelas input dan memiliki galat konstan pada kelas lainnya.
Penulis menggunakan dua teknik yang berbeda. Untuk CDS yang robust, mereka menunjukkan bahwa biaya shared randomness dibatasi bawah oleh logaritma dari kompleksitas komunikasi SMP deterministik, bahkan ketika komunikasi dan private randomness tidak dibatasi. Batas bawah ini ketat untuk fungsi equality. Untuk -routing yang sempurna satu sisi, mereka memanfaatkan kepositifan matriks berperingkat rendah yang muncul dalam metode Asadi, Culf, dan May (ITCS 2025) untuk menurunkan batas bawah umum pada biaya entanglement dalam bentuk sign rank. Sign rank dari matriks didefinisikan sebagai:
Mengapa penting
Hasil-hasil ini memberikan kemajuan signifikan pada masalah terbuka pembuktian batas bawah untuk -routing yang sepenuhnya robust. Keterkaitan antara CDS yang robust dan -routing menunjukkan bahwa pemahaman kompleksitas randomness dari CDS yang robust merupakan langkah alami menuju batas bawah untuk masalah routing yang sepenuhnya robust. Ketatnya batas CDS untuk fungsi equality menunjukkan bahwa batas tersebut optimal dalam beberapa kasus. Batas bawah sign rank untuk -routing yang sempurna satu sisi, khususnya batas linear untuk hasil kali dalam, cocok dengan batas atas yang diketahui, sehingga menyelesaikan biaya entanglement untuk fungsi ini dalam pengaturan sempurna satu sisi. Teknik yang diperkenalkan, seperti memanfaatkan kepositifan matriks berperingkat rendah, mungkin dapat diterapkan pada masalah lain dalam NLQC. Karya penulis juga menyoroti peran sign rank sebagai ukuran kompleksitas dalam informasi kuantum. Pekerjaan selanjutnya dapat memperluas batas bawah ini ke pengaturan yang sepenuhnya robust atau ke fungsi lain. Diagram berikut mengilustrasikan hubungan antar konsep:
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten memberโฆ