Contoh Pertanyaan Quantum Finite Automata 1 arah

Saya mencoba untuk memperjelas pemahaman saya dalam contoh yang disajikan dalam Bagian 2.2 dari Quantum Finite Automata 1-arah: Kekuatan Kelemahan dan Generalisasi ( tautan alternatif ini juga mungkin berguna). Contoh ini memberikan contoh 1-QFA yang sangat terbuka dengan aturan transisi berikut:

$V_a|q_0\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle$ ,

$V_a|q_1\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle$ ,

$V_{\$}|q_0\rangle = |q_{rej}\rangle$ ,

$V_{\$}|q_1\rangle = |q_{acc}\rangle$

Misalnya, jika saya di dan saya memproses sebagai masukan, saya menerapkan aturan pertama. Pemahaman saya adalah bahwa saya akan memiliki kesempatan untuk tetap dalam keadaan , a peluang berkembang menjadi state dan kesempatan untuk mengakhiri perhitungan dan menolak string. $q_0$ $a$ $||\frac{1}{2}||^2 = \frac{1}{4}$ $|q_0\rangle$ $||\frac{1}{2}||^2 = \frac{1}{4}$ $|q_1\rangle$ $||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$

Saya akan membayangkan automata untuk ini terlihat seperti gambar berikut

masukkan deskripsi gambar di sini

Namun saya tidak sepenuhnya yakin apakah itu benar. Probabilitas yang disebutkan dalam makalah untuk penerimaan string adalah sedangkan probabilitas penolakan adalah . Hanya ingin tahu apakah seseorang dapat menunjukkan kesalahan atau memvalidasi apa yang ada dalam pikiran saya sebagai contoh. $aa$ $\frac{1}{4}$ $\frac{3}{4}$

Terima kasih.

Model automata yang dikerjakan ulang untuk mencerminkan probabilitas dengan lebih akurat: masukkan deskripsi gambar di sini

fl.formal-languages quantum-computing automata-theory grammars Vincent Russo
sumber

Saya sarankan Anda mencari "superposisi kuantum". Sepertinya Anda menafsirkannya murni probabilistik, yang mengabaikan kemungkinan interferensi, yang merupakan pusat komputasi kuantum.

funkstar

Yah, saya menganggap negara berada dalam superposisi pada setiap input. Diberikan input ke automata, itu berlanjut ke keadaan berikutnya berdasarkan runtuhnya superposisi dari pengukuran. Nilai runtuh ini diperoleh dari superposisi sebelumnya berfungsi sebagai bobot untuk transisi. Misalnya pada langkah pertama, probabilitas untuk beralih dari ke adalah . Setiap langkah perhitungan menginduksi pengukuran.

q_{0}

$q_0$

q_{r e j}

$q_{rej}$

| | \frac{1}{\sqrt{2}} | |^{2}

$||\frac{1}{\sqrt 2}||^2$

Vincent Russo

Perhatikan bahwa pengukurannya parsial - ini tidak memberi Anda keadaan yang pasti kecuali itu adalah keadaan akhir. Dengan begitu, Anda dapat melakukan pengukuran (parsial) setelah menerapkan transformasi kesatuan yang terkait dengan beberapa simbol, dan jika itu tidak runtuh ke kondisi akhir maka itu akan tetap berada di superposisi yang tepat, yang membuat kemungkinan interferensi tetap terbuka.

funkstar

Jadi hanya untuk memastikan saya mengerti: 1.) - Baca dulu : Tolak string dengan probabilitas , jika tidak, nyatakan bisa dalam atau dan superposisi runtuh menjadi . . 2) - Untuk kedua saya agak tidak yakin: Sejak negara bisa baik atau , baik aturan yang diterapkan untuk superposisi saat ini saya akan berasumsi sebagai:

a

$a$

\frac{1}{2}

$\frac{1}{2}$

q_{0}

$q_0$

q_{1}

$q_1$

\frac{1}{2} | q_{0} ⟩ + \frac{1}{2} | q_{1} ⟩

$\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle$

a

$a$

| q_{0} ⟩

$|q_0\rangle$

| q_{1} ⟩

$|q_1\rangle$

Vincent Russo

(\frac{1}{2} ⟨ q_{0} | + \frac{1}{2} ⟨ q_{1} |) (\frac{1}{2} | q_{0} ⟩ + \frac{1}{2} | q_{1} ⟩ + \frac{1}{\sqrt{2}} | q_{r e j} ⟩) ((\frac{1}{2} | q_{0} ⟩ + \frac{1}{2} | q_{1} ⟩ - \frac{1}{\sqrt{2}} | q_{r e j} ⟩))

$(\frac{1}{2}\langle q_0| + \frac{1}{2}\langle q_1|) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle) ((\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle))$

= (\frac{1}{4} ⟨ q_{0} | q_{0} ⟩ + \frac{1}{4} ⟨ q_{1} | q_{1} ⟩) (\frac{1}{2} | q_{0} ⟩ + \frac{1}{2} | q_{1} ⟩ - \frac{1}{\sqrt{2}} | q_{r e j} ⟩)

$= (\frac{1}{4}\langle q_0 | q_0 \rangle + \frac{1}{4} \langle q_1 | q_1 \rangle) (\frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle)$

= \frac{1}{8} | q_{0} ⟩ + \frac{1}{8} | q_{1} ⟩

$= \frac{1}{8}|q_0\rangle + \frac{1}{8}|q_1\rangle$

Vincent Russo

Jawaban:

Yang pasti, automata melakukan pengukuran setelah membaca setiap simbol "a" dan menerapkan kesatuan yang terkait . Namun, itu tidak benar-benar bermakna untuk menghitung amplitudo negara yang akan diukur lebih dan dan untuk menempatkan mereka pada diagram, untuk automata melakukan Neot mengukur proyektor, dan $V_a$ $|q_{0}⟩$ $|q_{1}⟩$ $|q_{0}⟩\langle q_{0}|$ $|q_{1}⟩\langle q_{1}|$ . Dengan kata lain, angka-angka ini tidak mewakili probabilitas, mereka tidak sesuai dengan hasil pengukuran yang akan dilakukan. Oleh karena itu, memberi tanda panah pada diagram dengan angka-angka ini akan memberikan ilustrasi yang berpotensi menyesatkan tentang bagaimana proses pengukuran bekerja.

Meskipun saya mungkin mengatakan hal-hal yang sudah Anda ketahui, izinkan kami menguraikan sedikit topik untuk memperjelas arti diagram transisi yang Anda gambarkan. Penting untuk digarisbawahi bahwa setelah membaca simbol dan menerapkan , automata tidak melakukan pengukuran dalam basis komputasi standar: Sebagai gantinya, automata mengukur serangkaian proyektor orthogonal yang lengkap ini: $a$ $V_a$

{| q_{0} ⟩, | q_{1} ⟩, | q_{a c c} ⟩, | q_{r e j} ⟩}

$\{|q_0⟩,|q_1⟩,|q_{acc}⟩,|q_{rej}⟩\}$

$P_{acc}=|q_{acc}⟩\langle q_{acc}|$
$P_{rej}=|q_{rej}⟩\langle q_{rej}|$
$P_{non}= |q_{0}⟩\langle q_{0}|+|q_{1}⟩\langle q_{1}|$

Dengan kata lain, pengukuran memiliki tiga kemungkinan hasil: ( acc ) automata mengukur keadaan penerimaan dan penghentian; ( rej ) automata mengukur negara yang menolak dan berhenti; ( non ) tindakan otomatis sesuatu yang lain, tidak berhenti, dan membaca simbol berikutnya (bukan negara untuk tidak berhenti).

Sekarang, ini adalah masalah yang saya lihat dalam diagram Anda: jika Anda memiliki keadaan sebelum beberapa pengukuran, dan Anda kebetulan mendapatkan hasil (non), negara akan tetap invarian setelah pengukuran (hanya berlaku dan periksa). Oleh karena itu, menggambarkan probabilitas transisi ke atau menciptakan kebingungan. $(|q_{0}⟩+|q_{1}⟩)/2$ $P_{non}$ $|q_{0}⟩$ $|q_{1}⟩$

Dengan memperhitungkan semua kata, mudah untuk mengikuti perhitungan yang diberikan dalam referensi utama Anda . Untuk menggambarkan semua yang dikatakan, dan, untuk kelengkapan, saya akan mengutipnya di sini dengan beberapa komentar kecil (meskipun saya menambahkan beberapa modifikasi, saya tidak tahu apakah jenis kutipan ini dapat diterima; jika tidak , tolong, izinkan saya ketahui atau edit jawabannya sendiri):

Otomat dimulai pada . $|q_0\rangle$

Baca "a" . diterapkan, memberikan . Ini diamati. Ada dua hasil yang mungkin. Dengan probabilitas , keadaan menolak diamati. Kemudian, superposisi runtuh menjadi , kata tersebut ditolak dan perhitungannya berakhir. Kalau tidak (dengan probabilitas ), keadaan non-halting diamati dan superposisi runtuh menjadi . Dalam hal ini, perhitungan berlanjut. $V_a$ $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle+ \frac{1}{\sqrt{2}} |q_{rej}\rangle$ $(1/\sqrt{2})^2=1/2$ $|q_{rej}\rangle$ $1/2$ $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$

Baca "a" lagi . Perhitungan sederhana (kami biarkan detailnya keluar) menunjukkan bahwa dipetakan ke dirinya sendiri oleh . Setelah itu, kondisi non-halting diamati. (Tidak ada negara yang menerima atau menolak dalam superposisi ini.) $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$ $V_a$

Baca simbol akhir $ . Transformasi sesuai dengan endmarker kanan selesai. Ini memetakan superposisi ke . Ini diamati. Dengan probabilitas keadaan menolak diamati. Dengan probabilitas , status penerima diamati. $V_{\$}$ $\$$ $\frac{1}{2} |q_{rej}\rangle+\frac{1}{2} |q_{acc}\rangle$ $(1/2)^2=1/4$ $q_{rej}$ $1/4$ $q_{acc}$

Probabilitas total penerimaan adalah , probabilitas penolakan adalah . $1/4$ $1/2+1/4=3/4$

Juan Bermejo Vega
sumber

Ah jawaban yang hebat, terima kasih banyak telah meluangkan waktu untuk menuliskannya dalam istilah yang lebih eksplisit. Juga, di samping catatan, apakah ada cara yang jelas atau mungkin referensi sebelumnya yang menggambarkan representasi visual dengan cara yang lebih akurat dan tidak menyesatkan? Tampaknya mungkin meletakkan evolusi dalam beberapa jenis struktur seperti pohon akan memungkinkan ilustrasi yang lebih baik dari percabangan yang terjadi di seluruh pelaksanaan automata. Sekali lagi terima kasih atas bantuan Anda.

Vincent Russo

@VincentRusso: Anda tidak bisa menggambarkannya dengan cara berbasis pohon. Intinya adalah bahwa ada gangguan destruktif antara amplitudo pada berbagai 'kondisi' otomat terbatas; ini menjadi perbedaan utama antara perhitungan stokastik dan kuantum. Penggambaran grafis dari automaton tidak benar-benar menyesatkan jika Anda menganggap serius itu menggambarkan amplitudo untuk vektor, daripada transisi probabilistik. Tentu saja, baik untuk kuantum atau automata stokastik, model ini sebenarnya tentang transformasi linier, sehingga gambar sebagian besar di samping intinya.

Niel de Beaudrap

Pada awal bab 6 dari Kaye, Laflamme, Mosca ada diskusi yang bagus tentang perbedaan antara komputasi klasik-probabilistik dan kuantum; penulis menggambarkan teks dengan diagram keadaan. Mereka benar-benar mendiskusikan bahwa diagram ini tidak sepenuhnya memadai untuk menggambarkan gangguan kuantum - seperti yang ditunjukkan oleh Niel de Beaudrap dan dijelaskan dengan baik -. Saya pribadi merekomendasikan referensi ini untuk bacaan lebih lanjut.

Juan Bermejo Vega

Juan Bermejo Vega telah memberikan ringkasan yang akurat tentang apa yang dikatakan di koran aslinya. Saya akan memberi Anda deskripsi tingkat yang lebih tinggi.

Dalam kasus Anda, saya akan merekomendasikan untuk tidak memikirkan amplitudo sebagai probabilitas sama sekali. Mereka terkait dengan probabilitas, tetapi ini tidak terlalu membantu untuk memikirkan automata terbatas ini. Saya menduga bahwa hal-hal akan jauh lebih jelas jika Anda menganggap ini sebagai resep yang agak abstrak untuk mengubah vektor-vektor bernilai kompleks.

Vektor apa yang kita ubah? Nah: misalkan Anda memiliki otomat terbatas dengan status n . Automaton mewakili model (ya, probabilistik) untuk mentransformasikan vektor, yang pada setiap saat langkah dapat menimbulkan keputusan menerima atau menolak.

Tentukan n sumbu (koefisien vektor yang sedang diubah). Beri label setiap sumbu dengan salah satu label negara. Secara khusus, ada sumbu terima dan sumbu tolak . Sebut ruang vektor ini . Vektor yang akan kita ubah adalah vektor satuan dalam , dan satu-satunya probabilitas yang akan kita pertimbangkan berkaitan dengan koefisien vektor di sepanjang sumbu terima atau tolak. $\mathcal H$ $\mathcal H$
Kami memiliki koleksi transformasi untuk setiap status q , sedemikian rupa sehingga ( yaitu mereka adalah kesatuan ). Kami juga memiliki transformasi awal (diabaikan dalam contoh yang Anda jelaskan; kami memiliki dalam kasus itu) dan transformasi akhir yang juga merupakan kesatuan. $V_q : \mathcal H \to \mathcal H$ $V_q^\dagger V_q = I$ $V_c$ $V_c = I$ $V_\$$
Kita mulai dengan vektor , di mana adalah transformasi awal dan adalah vektor satuan searah dengan sumbu sumbu status pertama ( pada Anda contoh). Kami kemudian melakukan transformasi berikut untuk setiap huruf:Vc e 1q0
1. Jika huruf berikutnya untuk dibaca adalah , kita melakukan transformasi pada vektor. $a$ $V_a$
2. Vektor dihasilkan mungkin memiliki koefisien sepanjang sumbu terima, dan sepanjang sumbu tolak. Jika demikian, kami segera menerima dengan probabilitas dan menolak dengan probabilitas . $\mathbf v$ $u_A$ $u_R$ $|u_A|^2$ $|u_R|^2$
3. Jika beberapa koefisien lainnya tidak nol, ada kemungkinan bahwa penghitungan berlanjut; jika demikian, kita mengalikan vektor dengan faktor , dan mengatur koefisien terima dan tolak ke nol. $(1 - |u_A|^2 - |u_R|^2)^{-1/2}$
4. Lanjutkan untuk surat berikutnya.
Kami melakukan transformasi ini untuk setiap huruf kata, dan juga untuk simbol penghentian $ yang kami tambahkan sampai akhir.

Satu-satunya probabilitas waktu yang berperan adalah dengan poros penerimaan dan penolakan . Walaupun model komputasi ini jelas diilhami oleh finite automata, sederhana saja tidak berguna untuk menginterpretasikan salah satu koefisien vektor lainnya, pada setiap titik waktu (bahkan di akhir!), Sebagai probabilitas.

Perhatikan bahwa probabilitas terima dan tolak pada setiap catatan waktu adalah probabilitas bersyarat , yaitu mereka bergantung pada perhitungan yang belum dihentikan; jika Anda ingin menghitung probabilitas total penerimaan / penolakan, Anda dapat dengan mudah melakukan ini dengan menghilangkan langkah "renormalisasi" dalam evolusi (bagian di mana kami mengalikan dengan nilai kuadrat-akar-akar, tetapi masih menetapkan penerimaan / tolak koefisien ke nol jika perhitungan berlanjut), dan sederhananya jumlah kontribusi probabilistik untuk menerima / menolak yang muncul di sepanjang jalan.

Niel de Beaudrap
sumber

Niel, terima kasih lagi atas komentar Anda juga. Sangat membantu untuk mendapatkan gambaran yang lebih intuitif tentang bagaimana perhitungan ini terjadi. Terima kasih banyak telah meluangkan waktu untuk menjelaskan, ini jauh lebih jelas bagi saya sekarang.

Vincent Russo

Anda salah berasumsi bahwa keadaan runtuh sepenuhnya (ke keadaan dasar komputasi) setelah membaca setiap simbol. Pengukuran pada setiap tahap hanya sebagian.

Shitikanth
sumber

Saya mendapat kesan bahwa karena ini menggunakan model "mengukur banyak" bahwa pengukuran dilakukan pada setiap langkah perhitungan, yang meruntuhkan superposisi ke nilai probabilistik yang pasti.

Vincent Russo

@Incent Russo Anda benar bahwa status diukur untuk setiap simbol yang dibaca.

funkstar

Saya berpikir bahwa QFA di mana keadaan otomaton diukur setelah setiap langkah akan sepenuhnya setara dengan Rantai Markov. Jadi apa yang menjadi motivasi untuk mempelajarinya?

Shitikanth

Saya hanya ingin menunjukkan mengapa "model robot yang dikerjakan ulang" nya tidak secara akurat menggambarkan sistem QFA. Ini, pada kenyataannya, karena otomat tidak sepenuhnya runtuh dalam dasar komputasi pada setiap langkah.

Shitikanth

Bagaimanapun, saya pikir pertanyaan itu sudah dijawab dengan cukup jelas. Jangan sampai tersesat dalam hal teknis.

Shitikanth