Distribusi probabilitas kedalaman terbatas

Dua pertanyaan terkait tentang komputasi kedalaman terbatas:

1) Misalkan Anda mulai dengan n bit, dan untuk memulai dengan bit saya bisa 0 atau 1 dengan beberapa probabilitas p (i), secara independen. (Jika itu membuat masalah lebih sederhana, kita dapat mengasumsikan bahwa semua p (i) s adalah 0,1, atau 1/2.~~atau bahkan semuanya adalah 1/2.~~)

Sekarang Anda membuat jumlah putaran perhitungan yang dibatasi. Di setiap putaran Anda menerapkan gerbang klasik reversibel pada set bit terpisah. (Perbaiki set gerbang reversibel klasik universal favorit Anda.)

Pada akhirnya Anda mendapatkan distribusi probabilitas pada string pada n bit. Apakah ada hasil pembatasan distribusi seperti itu?

Saya mencari sesuatu yang analog dengan Hastad switching biar, hasil Boppana bahwa pengaruh total kecil atau teorema LMN.

2) Pertanyaan yang sama seperti 1) tetapi dengan sirkuit kuantum kedalaman terbatas.

cc.complexity-theory quantum-computing circuit-complexity randomness circuit-depth Gil Kalai
sumber

Saya mungkin kehilangan sesuatu, tapi bukan pertanyaan 1 dengan semua

sama dengan

sepele? Anda mulai dengan distribusi yang seragam pada

, yang invarian dengan bijections.

p (i)

$p(i)$

1 / 2

$1/2$

{0, 1}^{n}

$\{0,1\}^n$

Klaus Draeger

Apakah berikut ini transformasi bermanfaat dari masalah Anda? Ubah input Anda (vektor

), menjadi vektor panjang

merepresentasikan distribusi probabilitas pada string biner dengan panjang

. Sekarang setiap perhitungan adalah matriks stokastik persegi yang bekerja pada (katakanlah) sebelah kiri untuk menghasilkan distribusi probabilitas atas string keluaran dengan panjang

. WLOG kita dapat menganggap semua entri adalah biner. Satu-satunya pertanyaan adalah apa kelas matriks biner stokastik yang dapat diproduksi melalui sejumlah perkalian matriks dari matriks basis kami (gerbang reversibel).

p_{0}, p_{1}, \dots

$p_0,p_1,\dots$

2^{n}

$2^n$

n

$n$

n

$n$

usul

Maaf, saya harus lebih tepat. Dengan matriks dasar di sini yang saya maksud bukan gerbang reversibel, melainkan beberapa set gerbang reversibel yang bekerja secara paralel, dan sepertinya tidak segera jelas bagi saya seperti apa matriks yang akan diberikan dengan seperangkat gerbang.

usul

Kedua jawaban itu layak mendapat hadiah, saya akan lihat apa yang bisa saya lakukan

Gil Kalai

apa yang Anda maksud dengan "set terpisah" bit?

vzn

Jawaban:

Ada beberapa makalah yang relatif baru oleh Emanuele Viola et al., Yang membahas kompleksitas distribusi sampel. Mereka fokus pada model komputasi yang dibatasi, seperti pohon keputusan kedalaman terbatas atau sirkuit kedalaman terbatas.

Sayangnya mereka tidak membahas gerbang yang dapat dibalik. Sebaliknya sering ada kerugian dalam panjang output. Namun demikian makalah ini mungkin merupakan titik awal yang baik.

Sirkuit Kedalaman Terikat Tidak Dapat Mencicipi Kode Baik

Kompleksitas Distribusi

MassimoLauria
sumber

Terima kasih banyak, Massimo! ini terlihat sangat relevan.

Gil Kalai

(Juga saya tertarik pada kasus yang tidak dapat dibalik.)

Gil Kalai

Jawaban singkat.

Untuk sirkuit kuantum, setidaknya ada satu hasil non- klimitasi: sirkuit kuantum kedalaman terikat sewenang-wenang tidak mungkin dapat disimulasikan dengan kesalahan multiplikasi kecil dalam probabilitas hasil, bahkan untuk sirkuit klasik polinomial -depth.

Ini, tentu saja, tidak memberitahu Anda resctrictions apa yang sirkuit benar-benar akan memiliki; terutama jika Anda tertarik pada masalah keputusan dengan kesalahan terbatas, bukan distribusi probabilitas. Namun, itu berarti bahwa analisis dalam hal pohon keputusan, seperti dengan Håstad's Switching Lemma , tidak mungkin berada di sebentar lagi untuk simulasi klasik dari sirkuit ini. $\mathsf{QNC^0}$

Detail

Kita dapat mempertimbangkan definisi sirkuit kuantum kedalaman polylog seperti yang diberikan oleh Fenner et al. (2005) :

Definisi. adalah kelas keluarga rangkaian kuantum yang terdapat polinomial di mana setiap berisi input qubit dan paling banyak ancilla segar, hanya menggunakan gerbang qubit tunggal dan gerbang yang dikontrol-bukan, dan memiliki kedalaman . $\mathsf{QNC^k}$ $\{C_n\}_{n\geqslant0}$ $p$ $C_n$ $n$ $p(n)$ $O(\log^k(n))$

Gerbang single-qubit harus dari himpunan berhingga tetap, meskipun ini cukup untuk mensimulasikan setiap kesatuan tetap pada jumlah qubit konstan ke presisi tetap apa pun. Kami juga mengizinkan subset qubit apa pun pada akhir sirkuit yang akan digunakan untuk mewakili output dari rangkaian keluarga (misalnya qubit tunggal untuk fungsi boolean).

$\mathsf{QNC^0}$ $\mathsf{PostBQP = PP}$ $\mathsf{QNC^0}$ $\sqrt 2$ $\mathsf{PH} \subseteq \Delta_3$

Niel de Beaudrap
sumber

Dear Niel, Sangat menarik! Terima kasih! Saya sangat tertarik dengan distribusi. Bisakah Anda menjelaskan mengapa "Ini, tentu saja, tidak memberi tahu Anda ..."?

Gil Kalai

Hasil faktor-konstan-ketidak-taksiranan bertahan melalui PostQNC⁰ = PostBQP = PP . Postselection digunakan di sini untuk "memaksa keberhasilan" dari serangkaian panjang teleportasi, untuk mensimulasikan distribusi kuantum-poli-kedalaman melalui distribusi kedalaman-konstan-kuantum yang dikondisikan pada peristiwa dengan probabilitas sangat rendah tetapi bukan nol. Setiap faktor perkiraan konstan akan berlaku juga untuk sirkuit poly-depth. Tetapi ini tidak memberi tahu Anda, misalnya batas atas pada seberapa banyak amplitudo, dalam istilah absolut (dan asimptotik), terkonsentrasi (atau dapat diproyeksikan ke) setiap subruang tertentu.

Niel de Beaudrap