Apa cara paling efisien untuk menghasilkan permutasi acak dari probabilistic pairwise swaps?

Pertanyaan yang saya tertarik terkait dengan menghasilkan permutasi acak. Diberikan gerbang swap berpasangan probabilistik sebagai blok bangunan dasar, apa cara paling efisien untuk menghasilkan permutasi acak yang seragam dari elemen? Di sini saya mengambil "probabilistic pairwise swap gate" untuk menjadi operasi yang mengimplementasikan swap gate antara elemen terpilih dan dengan beberapa probabilitas yang dapat dipilih secara bebas untuk setiap gerbang, dan identitas sebaliknya. $n$ $i$ $j$ $p$

Saya menyadari ini biasanya bukan cara seseorang menghasilkan permutasi acak, di mana biasanya seseorang mungkin menggunakan sesuatu seperti shuffle Fisher-Yates, namun, ini tidak akan berfungsi untuk aplikasi yang ada dalam pikiran saya karena operasi yang diizinkan berbeda.

Jelas ini bisa dilakukan, pertanyaannya adalah seberapa efisien. Berapa jumlah minimum probabilistic swap yang diperlukan untuk mencapai tujuan ini?

MEMPERBARUI:

Anthony Leverrier menyediakan metode di bawah ini yang memang menghasilkan distribusi yang benar menggunakan gerbang , dengan Tsuyoshi Ito memberikan pendekatan lain dengan penskalaan yang sama dalam komentar. Namun, batas bawah terbaik yang saya lihat sejauh ini adalah , yang berskala sebagai . Jadi, pertanyaannya masih tetap terbuka: Apakah yang terbaik yang bisa dilakukan (yaitu apakah ada batas bawah yang lebih baik)? Atau sebagai alternatif, apakah ada rangkaian keluarga yang lebih efisien? $O(n^2)$ $\lceil \log_2(n!) \rceil$ $O(n\log n)$ $O(n^2)$

MEMPERBARUI:

Beberapa jawaban dan komentar telah mengusulkan rangkaian yang seluruhnya terdiri dari swap probabilistik di mana probabilitasnya tetap pada . Sirkuit seperti itu tidak dapat menyelesaikan masalah ini karena alasan berikut (diangkat dari komentar): $\frac{1}{2}$

Bayangkan sebuah sirkuit yang menggunakan gerbang tersebut. Lalu ada jalur komputasi yang dapat disetel, dan dengan demikian permutasi apa pun harus terjadi dengan probabilitas untuk beberapa bilangan bulat k. Namun, untuk distribusi yang seragam, kami meminta , Yang dapat ditulis ulang sebagai . Jelas ini tidak dapat dipenuhi untuk nilai integer untuk , karena(untuk , tetapi . $m$ $2^m$ $k 2^{−m}$ $k 2^{−m}=\frac{1}{n!}$ $k n! = 2^m$ $k$ $n\geq3$ $3|n!$ $n\geq 3$ $3\nmid 2^m$

UPDATE (dari mjqxxxx yang menawarkan hadiah):

Karunia yang ditawarkan adalah untuk (1) bukti bahwa diperlukan, atau (2) sirkuit kerja, untuk setiap , yang menggunakan kurang dari gerbang. $\omega(n \log n)$ $n$ $n(n-1)/2$

co.combinatorics randomness probabilistic-circuits Joe Fitzsimons
sumber

@Anthony: Mungkin tidak jelas, tetapi Anda dapat: Bayangkan bahwa sirkuit menciptakan distribusi permutasi yang seragam dari elemen pertama . Kemudian diikuti oleh pertukaran probabilistik (dengan probabilitas 0,5) antara posisi dan posisi akan menghasilkan pilihan acak yang seragam untuk posisi . Jika Anda mengikuti ini dengan menerapkan lagi ke elemen pertama , Anda harus mendapatkan distribusi acak yang seragam.

C

$C$

n - 1

$n-1$

C

$C$

n - 1

$n-1$

n

$n$

n

$n$

C

$C$

n - 1

$n-1$

Joe Fitzsimons

ok terima kasih untuk penjelasannya! Perhatikan bahwa pertukaran probabilistik harus memiliki proba antara posisi dan posisi .

(n - 1) / n

$(n-1)/n$

n - 1

$n-1$

n

$n$

Anthony Leverrier

Dalam hal diperlukan entropi, algoritme membutuhkan bit acak di mana adalah fungsi entropi biner. Saya tidak dapat menghitung jumlah itu dengan tepat tetapi itu adalah menurut ... sedangkan yang optimal adalah setidaknya .

(n - 1) h (1 / 2) + (n - 2) h (1 / 3) + \dots + (n - k) h (1 / (k + 1)) + \dots + h (1 / n)

$(n-1) h(1/2) + (n-2) h(1/3) + \cdots + (n-k) h(1/(k+1)) + \cdots + h(1/n)$

h (.)

$h(.)$

O (n \log_{2} (n)^{2})

$O(n \log_2(n)^2)$

O (n \log_{2} (n))

$O(n \log_2(n))$

Anthony Leverrier

Ini berbeda dari yang Anda inginkan, tetapi ada keluarga rangkaian ukuran O (n log n) yang menghasilkan setiap permutasi dengan probabilitas setidaknya 1 / p (n!) Untuk beberapa polinomial p: pertimbangkan jaringan sortir dengan ukuran O (n log n) dan ganti masing-masing pembanding dengan probabilitas-1/2 swap gate. Karena ketepatan jaringan penyortiran, setiap permutasi harus muncul dengan probabilitas nol, yang harus setidaknya 1/2 ^ {O (n log n)} = 1 / poly (n!).

Tsuyoshi Ito

Kembali ke masalah semula. Perhatikan bahwa solusi O (n ^ 2) yang dideskripsikan oleh Anthony dapat dilihat sebagai menggantikan setiap komparator dalam jaringan penyortiran yang mewakili jenis seleksi dengan gerbang swap probabilistik dengan probabilitas yang sesuai. (selengkapnya)

Tsuyoshi Ito

Jawaban:

Algoritme kerja yang saya jelaskan dalam komentar di atas adalah sebagai berikut:

Pertama-tama mulailah dengan membawa elemen acak dengan probabilitas di posisi : bertukar posisi 1 dan 2 dengan proba , lalu 2 dan 3 dengan proba , ... kemudian dan dengan proba . $1/n$ $n$ $1/2$ $2/3$ $n-1$ $n$ $(n-1)/n$
Terapkan prosedur yang sama untuk membawa elemen acak di posisi : tukar posisi 1 dan 2 dengan prob ... lalu posisi dan dengan proba . $n-1$ $1/2$ $n-2$ $n-1$ $(n-2)/(n-1)$
Dll

Jumlah gerbang yang dibutuhkan oleh algoritma ini adalah . $(n-1)+(n-2)+ \cdots + 2+1 = n(n-1)/2 = O(n^2)$

Anthony Leverrier
sumber

Algoritma ini memiliki koneksi ke semacam gelembung. Secara khusus mempertimbangkan ruang keadaan semua permutasi ukuran n. Probabilitas bahwa elemen 1 lebih besar dari 2 adalah 1/2, bertukar dengan probabilitas itu. Asumsikan dua elemen pertama diurutkan, apa elemen ke-2 proba> elemen ke-3 2/3, dll. Oleh karena itu, tampaknya mungkin untuk mengubah algoritma pengurutan menjadi sirkuit swap gate, di mana setiap langkah berikut harus memperhitungkan probabilitas kondisional akun, yang timbul dari sebelumnya Langkah. Yang dalam arti menyarankan metode tidak efisien eksplisit untuk membangun sirkuit seperti itu.

mkatkov

Ini bukan jawaban atau informasi baru. Di sini saya akan mencoba merangkum diskusi yang terjadi dalam komentar tentang hubungan antara masalah ini dan jaringan penyortiran . Dalam posting ini, semua waktu dalam UTC dan "komentar" berarti komentar pada pertanyaan kecuali dinyatakan sebaliknya.

Sebuah sirkuit yang terdiri dari gerbang swap probabilistik (yang menukar dua nilai secara acak) secara alami mengingatkan kita pada jaringan sortir, yang tidak lain adalah sirkuit yang terdiri dari komparator (yang menukar dua nilai tergantung pada urutan di antara mereka). Memang, sirkuit untuk masalah saat ini dan penyortiran jaringan terkait satu sama lain dengan cara berikut:

The solusi dengan Anthony Leverrier dengan n ( n -1) / 2 gerbang Swap probabilistik dapat dipahami sebagai jaringan menyortir untuk bubble sort dengan pembanding digantikan oleh gerbang pertukaran probabilistik dengan probabilitas yang sesuai. Lihat komentar mkatkov pada 10 Maret 4:53 tentang jawaban itu untuk perincian. Jaringan penyortiran untuk pemilihan semacam juga dapat digunakan dengan cara yang sama. (Dalam komentar pada 7 Maret 23:04, saya menggambarkan sirkuit Anthony sebagai jenis seleksi, tetapi itu tidak benar.)
Jika kita hanya ingin setiap permutasi dengan probabilitas bukan nol dan tidak peduli tentang distribusi yang seragam, maka setiap jaringan penyortiran melakukan pekerjaan ketika semua pembanding diganti dengan probabilitas-1/2 swap gerbang. Jika kita menggunakan jaringan penyortiran dengan komparator O ( n log n ), sirkuit yang dihasilkan menghasilkan setiap permutasi dengan probabilitas setidaknya 1/2 ^{O ( n log n )} = 1 / poly ( n !), Seperti yang diamati dalam komentar saya pada bulan Maret 7 22:59.
Dalam masalah ini, diperlukan bahwa gerbang pertukaran probabilistik menyala secara independen. Jika kita menghapus batasan ini, setiap jaringan penyortiran dapat dikonversi ke sirkuit yang menghasilkan distribusi seragam, seperti yang saya sebutkan di komentar pada 7 Maret 23:08 dan user1749 dijelaskan secara lebih rinci pada 8 Maret 14:07.

Fakta-fakta ini tampaknya menunjukkan bahwa masalah ini berkaitan erat dengan jaringan sortir. Namun, Peter Taylor menemukan bukti bahwa hubungannya mungkin tidak terlalu dekat. Yaitu, tidak setiap jaringan penyortiran dapat dikonversi ke sirkuit yang diinginkan dengan mengganti komparator dengan gerbang pertukaran probabilistik dengan probabilitas yang sesuai. Jaringan pengurutan lima pembanding untuk n = 4 adalah contoh tandingan. Lihat komentarnya pada 10 Maret 11:08 dan 10 Maret 14:01.

Tsuyoshi Ito
sumber

@mkatkov: Saya telah melihat tiga atau empat jawaban yang dihapus dan saya tidak ingat yang mana, maaf. Jika Anda telah menemukan solusi dengan gerbang kurang dari n (n − 1) / 2, saya ingin mengetahui seluruh konstruksi (dan itu bukan untuk mencuri karunia mjqxxxx dari Anda :)).

Tsuyoshi Ito

@mkatkov: Saya masih skeptis. Seperti yang saya tulis dalam paragraf terakhir dari posting ini, Peter Taylor menemukan bahwa jaringan penyortiran lima komparator untuk n = 4 tidak dapat dikonversi menjadi solusi untuk masalah saat ini dengan mengganti komparator dengan gerbang pertukaran probabilistik. Ini menyiratkan bahwa logika Anda tidak dapat bekerja untuk setiap jaringan penyortiran, meskipun tidak mengesampingkan kemungkinan bahwa itu entah bagaimana bekerja untuk, katakanlah, ganjil genap genap.

Tsuyoshi Ito

@mkatkov: Alasan jenis solusi ini tampaknya tidak berfungsi (atau setidaknya tidak ada contoh yang berfungsi telah ditunjukkan) adalah bahwa gerbang swap dalam api pengurutan jaringan berpasangan secara sangat berkorelasi. Dalam masalah ini, semua gerbang kebakaran secara independen, yang mengarah ke ruang sirkuit yang sangat berbeda.

mjqxxxx

@mkatbov, setiap langkah dalam jaringan Anthony memilih salah satu dari input m (di mana m berkisar dari n ke 2). Anda tidak dapat memilih salah satu dari input m dengan gerbang kurang dari m-1, jadi khususnya Anda tidak dapat melakukannya dengan gerbang m. Mengalahkan mungkin akan membutuhkan semacam pendekatan divide-and-conquer.

O (n^{2})

$O(n^2)$

Peter Taylor

@Tsuyoshi, Yuval dan saya telah menganalisis semua kemungkinan solusi 5-gerbang untuk dan menghilangkan semuanya, yang memperkuat hasil bahwa tidak semua jaringan penyortiran dapat dikonversi menjadi jaringan permutasi yang seragam menjadi hasil bahwa terdapat ukuran masalah yang jaringan permutasi seragam yang optimal membutuhkan lebih banyak gerbang daripada jaringan sortasi optimal.

n = 4

$n=4$

Peter Taylor

Ini bukan jawaban lengkap dengan cara apa pun, tetapi ini mencakup hasil yang mungkin berguna dan menerapkannya untuk mendapatkan beberapa kendala pada case yang membatasi kemungkinan solusi 5-gerbang hingga 2500 kasus yang mudah dihitung. $n=4$

Pertama hasil umum: dalam setiap solusi yang memungkinkan objek, harus ada setidaknya swap yang memiliki probabilitas . $n$ $n-1$ $\frac{1}{2}$

Bukti: pertimbangkan representasi permutasi dari permutasi urutan . Ini adalah matriks memuaskan . Pertimbangkan swap antara dan dengan probabilitas : ini memiliki representasi (menggunakan notasi siklus untuk mewakili permutasi). Anda dapat menganggap perkalian dengan matriks ini dalam hal teori representasi atau dalam istilah Markov sebagai penerapan permutasi dengan probabilitas dan membiarkan segala sesuatu tidak berubah dengan probabilitas . $n$ $n\times n$ $A_\pi$ $(A_\pi)_{i,j} = [i = \pi(j)]$ $i$ $j$ $p$ $(1-p)I + pA_{(i j)}$ $(i j)$ $p$ $1-p$

Oleh karena itu jaringan permutasi merupakan rantai perkalian matriks tersebut. Kita mulai dengan matriks identitas dan hasil akhirnya akan menjadi matriks mana , jadi kita akan dari matriks peringkat ke matriks peringkat dengan penggandaan - yaitu pangkat menurun dengan . $U$ $U_{i,j} = \frac{1}{n}$ $n$ $1$ $n-1$

Mempertimbangkan peringkat dari matriks , maka, kita melihat bahwa mereka pada dasarnya adalah matriks identitas selain dari minor , sehingga mereka memiliki peringkat penuh kecuali , dalam hal ini mereka memiliki peringkat . $(1-p)I + pA_{(i j)}$ $\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}$ $p=\frac{1}{2}$ $n-1$

Menerapkan ketimpangan matriks Sylvester oleh karena itu kami menemukan bahwa setiap swap mengurangi peringkat hanya jika , dan ketika kondisi ini terpenuhi, ia menguranginya tidak lebih dari 1. Oleh karena itu kami memerlukan setidaknya swap probabilitas . $p=\frac{1}{2}$ $n-1$ $\frac{1}{2}$

Perhatikan bahwa ikatan ini tidak dapat diperketat karena jaringan Anthony Leverrier mencapainya.

Aplikasi untuk kasing . Kami sudah memiliki solusi dengan 6 gerbang, jadi pertanyaannya adalah apakah solusi dengan 5 gerbang itu mungkin. Kita sekarang tahu bahwa setidaknya 3 gerbang harus 50/50 swap, jadi kami memiliki dua probabilitas "bebas", dan . Ada 32 kemungkinan acara (masing-masing 5 acara independen dengan dua hasil) dan ember yang masing-masing harus mengandung setidaknya satu peristiwa. Peristiwa dibagi menjadi 8 dengan probabilitas , 8 dengan probabilitas , 8 dengan probabilitas , dan 8 dengan probabilitas . $n=4$ $p$ $q$ $4! = 24$ $\frac{pq}{8}$ $\frac{\overline{p}q}{8}$ $\frac{p\overline{q}}{8}$ $\frac{\overline{p}\overline{q}}{8}$

32 kejadian menjadi 24 ember tanpa ember kosong menyiratkan bahwa setidaknya 16 ember berisi tepat satu peristiwa, jadi setidaknya dua dari empat probabilitas yang diberikan di atas sama dengan . Dengan mempertimbangkan simetri, kami memiliki dua kasus: atau . $\frac{1}{24}$ $pq = \overline{p}q = \frac{1}{3}$ $pq = \overline{p}\overline{q} = \frac{1}{3}$

Kasus pertama memberikan , ( koreksi atau , membuka gulungan simetri). Kasus kedua memberikan , jadi , yang tidak memiliki solusi nyata. $p=\overline{p}=\frac{1}{2}$ $q=\frac{2}{3}$ $q=\frac{1}{3}$ $pq=1-p-q+pq$ $pq = p(1-p) = \frac{1}{3}$

Oleh karena itu jika ada solusi 5-gerbang kami memiliki empat gerbang dengan probabilitas dan satu gerbang dengan probabilitas baik atau . Wlog swap pertama adalah , dan yang kedua adalah atau ; tiga lainnya masing-masing memiliki (tidak lebih dari) lima kemungkinan, karena tidak ada gunanya melakukan swap yang sama dua kali berturut-turut. Jadi kami memiliki urutan swap untuk dipertimbangkan dan 10 cara menetapkan probabilitas, mengarah ke 2500 kasus yang dapat dihitung dan diuji secara mekanis. $\frac{1}{2}$ $\frac{1}{3}$ $\frac{2}{3}$ $0\leftrightarrow 1$ $0\leftrightarrow 2$ $2\leftrightarrow 3$ $2\times 5^3$

Pembaruan: Yuval Filmus dan saya telah menghitung dan menguji kedua kasus dan tidak menemukan solusi, sehingga solusi optimal untuk melibatkan 6 gerbang, dan contoh solusi 6-gerbang ditemukan dalam jawaban lain. $n=4$

Peter Taylor
sumber

Pencacahan kasus saya gagal menghasilkan contoh yang lebih pendek.

Yuval Filmus

... bahkan setelah koreksi.

Yuval Filmus

Bagus sekali, itu pengamatan yang sangat bagus.

Joe Fitzsimons

@ mjqxxxx, saya menghitung bahwa dalam mencari solusi 9-gerbang ke Anda harus mempertimbangkan sekitar 104 juta kasus (walaupun ini dapat dikurangi sedikit dengan kepintaran), tetapi untuk setiap kasus Anda akan menghitung 120 persamaan dalam 5 variabel dengan cross-terms dan kemudian memeriksa solusinya. Ini mungkin dapat dilakukan dengan komputer desktop standar, tetapi membutuhkan sedikit usaha lebih karena Anda tidak dapat dengan mudah membatasi nilai kemungkinan dari probabilitas.

n = 5

$n=5$

Peter Taylor

Saya memberikan hadiah ini di sini, meskipun jawabannya tidak memberikan peningkatan asimptotik atas batas bawah atau perbaikan apa pun pada batas atas , karena setidaknya itu membuktikan bahwa optimal dalam satu kasus nontrivial.

Ω (n \log n)

$\Omega(n \log n)$

n (n - 1) / 2

$n(n-1)/2$

n (n - 1) / 2

$n(n-1)/2$

mjqxxxx

Berikut ini sepertinya informasi yang baru dan relevan:

Makalah [CKKL99] menunjukkan bagaimana mendapatkan 1 / n dekat dengan permutasi yang seragam dari n elemen menggunakan jaringan switching kedalaman O (log n), dan karenanya total komparator O (n log n).

Konstruksi ini tidak eksplisit, tetapi dapat dibuat eksplisit jika Anda meningkatkan kedalaman ke polylog (n). Lihat petunjuk di kertas [CKKL01], yang juga berisi informasi lebih lanjut.

Komentar sebelumnya sudah menunjukkan hasil yang mengatakan bahwa O (n log n) switch sudah cukup, tetapi perbedaannya adalah bahwa dalam switching jaringan elemen yang dibandingkan diperbaiki.

[CKKL99] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, dan Krzysztof Loys. Jalan tunda yang tertunda dan menghasilkan permutasi acak melalui proses stokastik terdistribusi. Dalam Simposium tentang Algoritma Diskret (SODA), halaman 271 {280, 1999.

[CKKL01] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, dan Krzysztof Loys. Berpindah jaringan untuk menghasilkan permutasi acak, 2001.

— Manu
sumber

Terima kasih, itu tentu bermanfaat untuk diketahui. Namun saya masih tertarik untuk mengetahui tentang nomor gerbang untuk menghasilkan distribusi yang tepat.

— Joe Fitzsimons

Ini solusi yang agak menarik untuk . Gagasan yang sama juga berlaku untuk . $n=4$ $n=6$

Mulailah dengan sakelar dengan probabilitas . Mengurangi ke dan ke , kita berada dalam situasi . Terapkan sakelar dengan probabilitas . Hasilnya adalah Langkah kita selanjutnya adalah dengan probabilitas . Dengan demikian kami benar-benar hanya peduli jika hasil dari tahap sebelumnya adalah dari bentuk (kasus A) atau dari formulir $(0,1),(2,3)$ $1/2$ $0,1$ $X$ $2,3$ $Y$ $XXYY$ $(0,3),(1,2)$ $p$

\begin{aligned} X X Y Y & w.p. (1 - p)^{2}, \\ Y Y X X & w.p. p^{2}, \\ X Y X Y & w.p. p (1 - p), \\ Y X Y X & w.p. p (1 - p) \end{aligned}

$\begin{align*} XXYY &\text{ w.p. } (1-p)^2, \\ YYXX &\text{ w.p. } p^2, \\ XYXY &\text{ w.p. } p(1-p), \\ YXYX &\text{ w.p. } p(1-p) \end{align*}$

(0, 2), (1, 3)

$(0,2),(1,3)$

1 / 2

$1/2$

X X Y Y / Y Y X X

$XXYY/YYXX$

X Y X Y / Y X Y X

$XYXY/YXYX$ (kasus B). Dalam kasus A, sakelar-sakelar ini akan menghasilkan probabilitas yang seragam di atas . Dalam kasus B mereka tidak akan efektif. Karena itu harus memenuhi Mengingat itu, hasilnya seragam.

X X Y Y / X Y Y X / Y X X Y / Y Y X X

$XXYY/XYYX/YXXY/YYXX$

p

$p$

p (1 - p) = 1 / 6 ⟹ p = \frac{3 \pm \sqrt{3}}{6} .

$p(1-p) = 1/6 \Longrightarrow p = \frac{3 \pm \sqrt{3}}{6}.$

Gagasan serupa berlaku untuk - Anda pertama-tama mengurutkan masing-masing setengah, dan kemudian "menggabungkan" mereka. Namun, bahkan untuk saya tidak bisa melihat cara menggabungkan separuh dengan benar. $n=6$ $n=8$

Poin menarik tentang solusi ini adalah probabilitas aneh . $p$

Sebagai catatan tambahan, himpunan probabilitas yang dapat membantu kita diberikan oleh , di mana membahas semua nilai eigen dari semua representasi di semua transposisi. $p$ $1/(1-\lambda)$ $\lambda \leq 0$ $S_n$

— Yuval Filmus
sumber

Nilai aneh untuk memang menggembirakan, karena saya pikir ada bukti yang cukup sederhana bahwa jika kita membatasi probabilitas ke untuk integer maka yang terbaik yang dapat Anda lakukan adalah .

p

$p$

1 / k

$1/k$

k

$k$

O (n^{2})

$O(n^2)$

— Joe Fitzsimons

Cara yang sedikit berbeda untuk elemen 2n, yang masih aneh dalam arti yang sama, adalah dengan mengocok elemen n pertama, mengocok elemen n terakhir, menukar (i, i + n) dengan probabilitas p_i untuk i = 1,…, n , kocok n elemen pertama, dan kocok n elemen terakhir. Probabilitas p_i harus dipilih sehingga probabilitas bahwa tepat k dari api n swap gerbang sama dengan dan probabilitas p_i tersebut diberikan oleh ( 1 + x_i) / 2 di mana x_1, ..., x_n adalah akar dari Pyn polinomial Legendre . (selengkapnya)

{(\binom{n}{k})}^{2} / (\binom{2 n}{n})

$\binom{n}{k}^2/\binom{2n}{n}$

— Tsuyoshi Ito

(cont'd) Suatu hal yang mengecewakan tentang variasi yang saya jelaskan adalah bahwa ia memerlukan n (n − 1) / 2 probabilistik bertukar ketika n adalah kekuatan dua, yaitu, jumlah gerbang yang persis sama dengan jenis gelembung. solusi oleh Anthony Leverrier.

— Tsuyoshi Ito

@ Tsuyoshi, konstruksi Anda jelas benar, tapi saya ingin tahu apakah itu melakukan lebih dari yang diperlukan. Saya tidak punya waktu untuk mengerjakan analisis saat ini, tetapi jika Anda melakukannya, Anda mungkin merasa layak mempertimbangkan apakah ada sehingga ; ; ; ; kemudian menerapkan permutasi yang sesuai dari akar Legendre (dan mengisi perempat lainnya) dapat bekerja.

p_{0}, p_{1}

$p_0, p_1$

0 \leftrightarrow 1, p = \frac{1}{2}

$0\leftrightarrow 1, p=\frac{1}{2}$

2 \leftrightarrow 3, p = \frac{1}{2}

$2\leftrightarrow 3, p=\frac{1}{2}$

0 \leftrightarrow 2, p = p_{0}

$0\leftrightarrow 2, p=p_0$

1 \leftrightarrow 3, p = p_{1}

$1\leftrightarrow 3, p=p_1$

— Peter Taylor

Pertimbangkan masalah pengocokan acak string , di mana setiap blok memiliki panjang , dengan sirkuit yang terdiri dari swap berpasangan probabilistik. Artinya, semua string dengan s dan s harus output sama-sama kemungkinan sirkuit, mengingat masukan ditentukan. Biarkan menjadi sirkuit optimal untuk masalah ini, dan biarkan menjadi sirkuit optimal untuk masalah asli (mengacak elemen secara acak ). Menerapkan permutasi acak cukup untuk secara acak interleave dan , jadi $XX..XY..YY$ $n$ $(2n)!/(n!)^2$ $n$ $X$ $n$ $Y$ $B_{2n}$ $C_{2n}$ $2n$ $X$ $Y$ $\lvert{B_{2n}}\rvert \le \lvert{C_{2n}}\rvert$ . Di sisi lain, kita dapat mengocok elemen dengan mengocok elemen pertama , mengocok elemen terakhir , dan akhirnya menerapkan rangkaian . Ini menyiratkan bahwa . Menggabungkan dua batasan ini, kita dapat memperoleh hasil berikut: $2n$ $n$ $n$ $B_{2n}$ $\lvert{C_{2n}}\rvert \le 2\lvert{C_{n}}\rvert + \lvert{B_{2n}}\rvert$

$\lvert{B_{2n}}\rvert$ dan keduanya adalah , atau keduanya adalah. $\lvert{C_{2n}}\rvert$ $o(n^2)$

Kita melihat bahwa kedua masalah itu sama sulitnya, paling tidak dalam pengertian ini. Hasil ini agak mengejutkan, karena orang mungkin berharap masalah pengocokan menjadi lebih mudah. Secara khusus, argumen entropik menunjukkan bahwa adalah , tetapi memberikan hasil yang lebih kuat bahwa adalah . $XY$ $\lvert{B_{2n}}\rvert$ $\Omega(n)$ $\lvert{C_{2n}}\rvert$ $\Omega(n \log n)$

— mjqxxxx
sumber

Diaconis dan Shahshahani 1981, "Menghasilkan Permutasi Acak dengan Transposisi Acak" menunjukkan bahwa 1/2 n log dan transposisi acak (catatan: tidak ada "O" di sini) menghasilkan permutasi yang dekat (dalam jarak total variasi) ke seragam. Saya tidak yakin apakah tepatnya apa yang diperbolehkan dalam aplikasi Anda memungkinkan Anda menggunakan hasil ini, tetapi cukup cepat, dan ketat karena itu adalah contoh dari fenomena cut-off. Lihat Acak Berjalan di Grup Hingga oleh Saloff-Coste untuk survei hasil yang sama.

— Jason Morton
sumber

Dan mungkin dua permutasi yang hampir acak dapat disusun untuk menghasilkan permutasi yang bahkan lebih hampir acak.

— mjqxxxx

... Namun, perlu dicatat bahwa ini sebenarnya bukan masalah yang sama (bahkan memungkinkan untuk solusi perkiraan dan bukan tepat), karena penulis mempertimbangkan transposisi pasangan elemen yang dipilih secara acak, bukan transposisi probabilistik dari pasangan elemen tertentu.

— mjqxxxx

Ini benar-benar komentar tetapi terlalu panjang untuk dikirim sebagai komentar. Saya menduga bahwa teori representasi dari kelompok simetris mungkin berguna untuk membuktikan batas bawah yang lebih baik. Meskipun saya hampir tidak tahu apa-apa tentang teori representasi dan saya mungkin melenceng, izinkan saya menjelaskan mengapa itu mungkin terkait dengan masalah saat ini.

Perhatikan bahwa perilaku rangkaian yang terdiri dari gerbang swap probabilistik dapat sepenuhnya ditentukan sebagai distribusi probabilitas p di atas S _n , kelompok permutasi pada elemen n . Permutasi g ∈S _n dapat dianggap sebagai peristiwa bahwa keluaran i adalah g ( i ) masukan untuk semua i ∈ {1,…, n }. Sekarang merepresentasikan distribusi probabilitas p sebagai jumlah formal ∑ _{g ∈S _n} p ( g ) g . Misalnya, pertukaran probabilistik antara kabel i danj dengan probabilitas p direpresentasikan sebagai (1− p ) e + p τ _ij , di mana e ∈S _n adalah elemen identitas dan τ _ij ∈S _n adalah transposisi antara i dan j .

Fakta menarik tentang penjumlahan formal ini adalah bahwa perilaku rangkaian dua rangkaian independen dapat secara resmi digambarkan sebagai produk dari penjumlahan formal ini. Yaitu, jika perilaku sirkuit C ₁ dan C ₂ direpresentasikan sebagai jumlah formal a ₁ = ∑ _{g ∈S _n} p ₁ ( g ) g dan a ₂ = ∑ _{g ∈S _n} p ₂ ( g ) g , masing-masing, maka perilaku sirkuit C ₁ diikuti oleh C ₂direpresentasikan sebagai ∑ _{g ₁ , g ₂ ∈S _n} p ₁ ( g ₁ ) p ₂ ( g ₂ ) g ₁g ₂ = a ₁a ₂ .

Oleh karena itu, rangkaian yang diinginkan dengan swap probabilistik m persis sesuai dengan cara penulisan jumlah (1 / n !) ∑ _{g ∈S _n} g sebagai produk dari m jumlah masing-masing yang berbentuk (1− p ) e + p τ _ij . Kami ingin mengetahui jumlah minimum m faktor.

Jumlah formal ∑ _{g ∈S _n} f ( g ) g , di mana f adalah fungsi dari S _n hingga ℂ, dilengkapi dengan penambahan dan perkalian yang didefinisikan secara alami, membentuk cincin yang disebut aljabar grup ℂ [S _n ]. Aljabar grup terkait erat dengan teori representasi grup, yang merupakan teori yang mendalam seperti yang kita semua ketahui dan takuti :). Ini membuat saya curiga bahwa sesuatu dalam teori representasi mungkin dapat diterapkan pada masalah saat ini.

Atau mungkin ini hanya dibuat-buat.

Tsuyoshi Ito
sumber

Inilah yang direduksi menjadi. Ada banyak representasi dari kelompok simetris, yang dapat dihitung secara eksplisit untuk transposisi, dengan beberapa pekerjaan (biasanya mereka hanya dihitung secara eksplisit untuk transposisi ). Nilai awal dari setiap representasi adalah matriks identitas yang sesuai. Menerapkan swap probabilistik mengalikan setiap representasi dengan , di mana adalah nilai representasi pada swap yang dilakukan . (lanjutan)

(k, k + 1)

$(k,k+1)$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

(i j)

$(ij)$

Yuval Filmus

Agar output menjadi seragam, kita perlu semua representasi selain representasi identitas menjadi nol. Jadi probabilitas harus dipilih sehingga setidaknya beberapa matriks singular. Matriks untuk setiap representasi memiliki vektor eigen yang berbeda, jadi tidak jelas kondisi apa yang akan membuat representasi tertentu menjadi nol. (lanjutan)

p

$p$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

Yuval Filmus

Namun, jika kita dapat membuktikan bahwa setiap transposisi mengurangi pangkat rata-rata representasi paling banyak , katakanlah, maka kita akan mendapatkan batas bawah . Batas seperti itu dapat dibuktikan jika kita mengetahui vektor eigen yang sesuai dengan masing-masing representasi dan setiap transposisi. Informasi ini dapat dikerjakan pada prinsipnya, tetapi tidak ada jaminan bahwa pendekatan ini akan menghasilkan sesuatu yang tidak sepele.

1 / n^{2}

$1/n^2$

n^{2}

$n^2$

Yuval Filmus

(cont'd) dan transformasi linier ini adalah persis matriks yang muncul dalam representasi S_n oleh n × n matriks permutasi. Meskipun n − 1 sepele karena batas bawah pada jumlah gerbang (argumen entropi sudah memberikan batas bawah yang lebih baik), harapan saya adalah mungkin untuk menggeneralisasikan argumen Anda ke representasi lain untuk menghasilkan batas bawah yang lebih baik pada total jumlah gerbang.

Tsuyoshi Ito

@Yuval, @Peter: Saya perhatikan bahwa untuk setiap representasi, (1 − p) I + pA_ {ij} nonsingular kecuali p = 1/2 (karena A_ {ij} ^ 2 = Saya menyiratkan bahwa nilai eigen dari A_ {ij } adalah ± 1). Oleh karena itu, menghitung pangkat hanya berguna untuk batas yang lebih rendah jumlah gerbang probabilitas-1/2, yang sudah dilakukan secara optimal oleh Peter. Dengan kata lain, jika teori representasi berguna dalam cara yang saya sarankan dalam posting ini, kita membutuhkan sesuatu selain menghitung pangkat matriks! Saya tidak yakin apakah itu realistis.

Tsuyoshi Ito

Algoritma Anthony Anthony dapat dijalankan secara paralel dengan memulai iterasi prosedur berikutnya setelah dua swap probabilistik pertama, menghasilkan runtime . $O(n^2)$ $O(n)$

Dave
sumber

Saya pikir ukuran kompleksitas yang relevan untuk pertanyaan ini adalah jumlah gerbang dan bukan runtime.

Anthony Leverrier

@Anthony benar bahwa yang saya minati hanyalah jumlah minimum gerbang yang diperlukan.

Joe Fitzsimons

Jika saya mengerti dengan benar, jika Anda ingin sirkuit Anda dapat menghasilkan semua permutasi, Anda memerlukan setidaknya gerbang probabilistik, meskipun saya tidak yakin bagaimana rangkaian minimal dapat dibangun. $\lceil \log_2(n!) \rceil$

MEMPERBARUI:

Saya berpikir bahwa jika Anda mengambil algoritma Mergesort dan mengganti semua perbandingan dengan pilihan acak dengan probabilitas yang sesuai, Anda akan mendapatkan rangkaian yang Anda cari.

Antonio Valerio Miceli-Barone
sumber

Saya tidak sepenuhnya yakin bagaimana Anda akan menerjemahkan ini ke dalam model swap gate probabilitsic yang saya berikan di atas. Saya tidak melihat bagaimana pertukaran probabilistik menggantikan perbandingan dan masih mencapai distribusi acak. Karenanya, saya juga tidak yakin mengapa ini akan optimal.

Joe Fitzsimons

Dan ya, adalah minimum, tetapi ini hanya .

⌈ \log_{2} (n!) ⌉

$\lceil \log_2(n!) \rceil$

O (n \log (n))

$O(n\log(n))$

Joe Fitzsimons

Asumsikan dan lanjutkan dengan induksi pada . Anda memiliki dua permutasi acak dengan panjang . Jika Anda menggabungkan ini secara acak (yaitu mengambil elemen berikutnya dari subpermutasi yang dipilih secara acak) maka hasil yang digabungkan tentu harus acak. Probabilitas posisi memiliki elemen dari subpermutasi "kiri" jelas 1/2 oleh simetri. Dan dikondisikan di atasnya memiliki elemen dari subpermutasi kiri, itu harus memiliki yang acak secara acak. Dengan cara ini Anda dapat melihat bahwa permutasi yang dihasilkan memang acak.

n = 2^{k}

$n=2^k$

k

$k$

2^{k - 1}

$2^{k-1}$

i

$i$

Andrew D. King

Itu juga garis pemikiran saya ketika saya mengusulkan mergesort, namun, pada pemikiran kedua, tampaknya bagi saya bahwa tidak mungkin untuk menerapkan operasi penggabungan hanya menggunakan jenis gerbang yang diperlukan, karena mereka tidak menghasilkan output untuk mengetahui apakah mereka melakukan permutasi dan mereka tidak memiliki input kontrol untuk mengkondisikan mereka.

Antonio Valerio Miceli-Barone

@ Andrew: Saya tidak melihat cara "menggabungkan ini secara acak" menggunakan gerbang yang dijelaskan dalam pertanyaan.

Joe Fitzsimons

Jawaban berikut salah (lihat komentar @joe fitzsimon), tetapi mungkin berguna sebagai titik awal

Saya punya proposal sketsa di . Saya telah memeriksanya dengan tangan untuk (!) Tapi saya belum punya bukti bahwa hasilnya seragam di luar . $O(n\log n)$ $n=4$ $n=4$

Misalkan Anda memiliki sirkuit yang menghasilkan permutasi acak seragam pada bit. Les probabilistic swap gate yang menukar bit dan dengan probabilitas 1/2 dan tidak melakukan apa-apa dengan probabilitas . Bangun sirkuit berikut bekerja pada bit: $C_n$ $n$ $S_{i,j}^{\frac 12}$ $i$ $j$ $1/2$ $C_{2n}$ $2n$

$\forall 1\le k\le n$ , terapkan gerbang ; $S_{k,k+n}^{1/2}$
Terapkan pada bit pertama ; $C_n$ $n$
Terapkan pada bit terakhir ; $C_n$ $n$
$\forall 1\le k\le n$ , terapkan gerbang . $S_{k,k+n}^{1/2}$

Langkah 1. diperlukan agar bit dan dapat mendarat di bagian yang sama dari permutasi, dan langkah 4. diperlukan oleh simetri: jika adalah solusi, begitu juga diperoleh dengan menerapkan gerbang dalam urutan terbalik juga merupakan solusi. $1$ $n+1$ $C_{2n}$ $C_{2n}^-1$

Ukuran rangkaian keluarga ini mematuhi relasi rekursi berikut: dengan, jelas, . Satu kemudian dengan mudah melihat bahwa .

| C_{2 n} | = 2 | C_{n} | + 2 n

$|C_{2n}| = 2|C_n|+2n$

| C_{1} | = 0

$|C_1|=0$

| C_{n} | = n \log n

$|C_n|=n\log n$

Kemudian tetap menjadi pertanyaan yang jelas: apakah sirkuit ini melakukan permutasi yang seragam? Tidak, lihat komentar pertama di bawah

Frédéric Grosshans
sumber

Saya tidak percaya bahwa ini melakukan permutasi yang seragam. Bahkan, saya pikir tidak mungkin untuk melakukan persis dengan gerbang seperti itu jika Anda memperbaiki probabilitas menjadi 1/2. Alasan untuk ini adalah sederhana: bayangkan sebuah sirkuit yang menggunakan gerbang tersebut. Lalu ada lintasan komputasi yang dapat disetel, dan dengan demikian permutasi apa pun harus terjadi dengan probabilitas untuk beberapa bilangan bulat . Namun, untuk distribusi yang seragam, kami membutuhkan . Jelas ini tidak dapat dipenuhi untuk nilai integer untuk .

m

$m$

2^{m}

$2^{m}$

k 2^{- m}

$k 2^{-m}$

k

$k$

k 2^{- m} = \frac{1}{n!}

$k 2^{-m} = \frac{1}{n!}$

k

$k$

n \geq 3

$n\geq 3$

Joe Fitzsimons

Memang. Saya lupa juga memeriksa keseragaman untuk ...

n = 4

$n=4$

Frédéric Grosshans