Adakah bukti bahwa Linial, Shraibman, yang terikat dengan kompleksitas komunikasi kuantum tidak ketat?

Sejauh yang saya tahu, norma faktorisasi batas bawah yang diberikan oleh Linial dan Shraibman pada dasarnya adalah satu-satunya batas bawah yang dikenal dengan kompleksitas komunikasi kuantum (atau paling tidak itu mencakup semua yang lain). Apakah ada bukti bahwa ikatan ini ketat?

Norma faktorisasi terikat (juga disebut terikat) yang saya bicarakan adalah Teorema 13 dari Linial, Shraibman 2008 . Bahkan, ikatan ini mengikuti dari pengurangan dari kompleksitas komunikasi kuantum menjadi bias dalam game 2-pemain XOR Degorre, dkk. 2008 . Untuk alasan ini, itu bisa diharapkan menjadi ikatan yang buruk karena game XOR bahkan tidak ada hubungannya dengan komunikasi. Untuk yang tidak sabar, ikhtisar singkat diberikan dalam beberapa slide oleh Troy Lee . $\gamma_2$

Teks pengantar Jain, Klauck 2010 mengatakan bahwa teknik teori informasi mungkin menawarkan beberapa kompetisi tetapi tidak diketahui apakah ini mengalahkan . Jadi sepertinya, setidaknya beberapa tahun yang lalu, adalah teknik terbaik. Tetapi saya ingin tahu apakah ada contoh spesifik dari suatu fungsi yang diyakini memiliki kompleksitas komunikasi kuantum yang jauh lebih besar daripada batas . $\gamma_2$ $\gamma_2$ $\gamma_2$

quantum-information communication-complexity norms Dan Stahlke
sumber

untuk kelengkapan, dapatkah Anda memberikan tautan ke hasilnya?

Suresh Venkat

@ SureshVenkat: Saya telah menambahkan beberapa tautan dan konteks.

Dan Stahlke

+1. Ini adalah jenis pertanyaan yang sebenarnya tidak akan saya tanyakan di mana jika CSTheory tidak ada.

Robin Kothari

Jawaban:

Saya tidak tahu fungsi apa pun dengan komunikasi yang jauh lebih tinggi dari batas . Namun, intuisi saya mengapa tidak ketat adalah karena -norm juga merupakan batas bawah untuk komunikasi QCMA. Lihat makalah ini oleh Klauck untuk definisi komunikasi QCMA. $\gamma_2$ $\gamma_2$

Untuk membuktikan batas bawah pada komunikasi QCMA menggunakan -norm Anda dapat menggunakan reduksi yang sama untuk game XOR seperti dalam bukti Teorema 14 dari makalah ini . Ini juga berlaku untuk jenis keterjeratan tertentu. $\gamma_2$

Marcos Villagra
sumber

Terima kasih. Saya belum pernah mendengar tentang aspek ini.

Dan Stahlke

γ_{2}

$\gamma_2$

@RobinKothari, ya, itu benar. Karena biaya komunikasi QCMA lebih rendah dari komunikasi BQP, kami membutuhkan batas atas QCMA dan batas bawah BQP (yang lebih ketat).

Marcos Villagra

atau mungkin mereka sama?

Marcos Villagra

@MarcosVillagra: Saya tidak mengerti. Komplemen Disjointness adalah dalam NP, dan karenanya dalam QCMA. Namun, Disjointness (atau komplemennya) memiliki batas bawah eksponensial yang kuat dalam kompleksitas komunikasi kuantum. Bukankah itu memisahkan BQP dan QCMA?

Robin Kothari