Bukti Interaktif melalui Postselection?

Tentukan model komputasi MPostBQP agar identik dengan PostBQP kecuali kami mengizinkan pengukuran qubit secara polinomial banyak sebelum pengukuran pasca-seleksi dan akhir.

Bisakah kita memberikan bukti yang menunjukkan bahwa MPostBQP lebih kuat daripada PostBQP?

Tentukan MPostBQP [k] untuk memungkinkan beberapa putaran pengukuran dan pasca pemilihan sebelum kita melakukan pengukuran akhir. Pilih pengindeksan jadi MPostBQP [1] = PostBQP dan MPostBQP [2] = MPostBQP dan seterusnya. (Pembaruan: Definisi formal diberikan di bawah ini.)

Pertimbangkan permainan Arthur-Merlin. Mungkin kita dapat mensimulasikannya dalam model perhitungan ini: Pemilihan pasca dapat mengambil peran Merlin menghasilkan pesan yang meyakinkan dan pengukuran menengah dapat mengambil peran lemparan koin publik Arthur. Kemungkinan ini membuat saya bertanya:

Apakah kita memiliki AM [k] $\subset$ MPostBQP [k]?

Ini memang dikenal untuk $k=1$ , yang mengatakan MA $\subset$ PP. Untuk menunjukkannya untuk $k=2$ berarti MPostBQP = PP hanya jika AM $\subset$ PP. Karena ada oracle relatif yang AM tidak terkandung dalam PP , ini bisa memberikan jawaban positif untuk pertanyaan pertama saya.

Akhirnya, untuk banyak kasus putaran polinomi,

Apakah kita memiliki PSPACE MPostBQP [poli]? Jika demikian, apakah ini kesetaraan? $\subset$

Ini akan menjadi filosofis menarik (setidaknya untuk saya) karena akan memberitahu kita bahwa "penurut" kelas masalah untuk "postselecting tukang sihir" termasuk (atau adalah ) semua PSPACE.

EDIT: Saya telah dimintai definisi formal MPostBQP. (Saya telah memperbarui yang berikut.)

MPostBQP [k] adalah kelas bahasa $L \subset \{0,1\}^*$ mana terdapat keluarga seragam dari sirkuit kuantum ukuran polinomial sehingga untuk semua input , prosedur di bawah ini menghasilkan true dengan probabilitas setidaknya jika , dan dengan probabilitas paling jika . Prosedur, yang memungkinkan untuk beberapa pilihan yang mungkin bergantung pada (tetapi tidak $\{C_n\}_{n \geq 1}$ $x$ $2/3$ $x \in L$ $1/3$ $x \notin L$ $L$ $x$ ), didefinisikan sebagai berikut:

Prosedur: Langkah 1. Terapkan operator kesatuan sesuai dengan ke negara input . Perhatikan panjang pertama register paling polinomial dalam panjang . Langkah 2.Untuk : Jika adalah genap, maka ukur jumlah qubit yang diinginkan dari register pertama (paling banyak secara polinomi, mengingat ukuran register). Jika $C_n$ $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$ $\left\vert0\cdots 0\right>$ $x$ $i = 1 \cdots k$ $i$ $i$ ganjil, lalu pilih-pilih jadi qubit tunggal yang dipilih dalam register pertama mengukur sebagai (dan memiliki jaminan bahwa probabilitas non-nol sehingga postselection tersebut valid, tentu saja). Langkah 3. Terakhir, ukur qubit terakhir pada register pertama, dan kembalikan true jika kita mengukur dan palsu sebaliknya. $\left\vert 0 \right>$ $\left \vert 1 \right>$

Kami memiliki MPostBQP [0] = BQP, MPostBQP [1] = PostBQP, dan MPostBQP: = MPostBQP [2]. Saya mencoba untuk mencerminkan kelas Arthur-Merlin di mana AM [0] = BPP, AM [1] = MA, dan AM [2] = AM.

EDIT (3/27/11 5 PM): Tampaknya ada perdebatan tentang bagaimana pasca pemilihan harus didefinisikan dalam konteks ini. Jelas, maksud saya untuk definisi yang tidak meremehkan pertanyaan saya! :) Definisi yang saya asumsikan adalah sebagai berikut: Postselecting pada bit kth berarti kita memproyeksikan negara ke subruang di mana bit kth adalah $0$ , dan menormalkan. Ternyata dalam skema di mana kita memilih sebelum kita melakukan pengukuran, maka kita dapat memperoleh statistik akhir dengan melihat probabilitas bersyarat dalam skema di mana pemilihan pasca diganti dengan pengukuran. Namun, saya mengklaim bahwa karakterisasi ini rusak ketika pengukuran dan pemilihan akhir diselingi. Saya pikir kebingungan berasal dari orang-orang yang menggunakan "definisi probabilitas kondisional" ini (yang bekerja dalam kasus khusus yang saya generalisasikan) sebagai definisi postselection, daripada definisi "pengukuran paksa" yang baru saja saya berikan, yang jelas tergantung pada memesan karena kurangnya komutatif. Saya harap ini membantu!

EDIT (3/27/11 9 PM): Saya sudah mendefinisikan pemilihan setelah formalisme murni-negara. Niel memberikan analisis dalam formalisme matriks kepadatan yang tidak setuju dengan tambang untuk contoh 3-qubit. Pelakunya adalah, sekali lagi, definisi postselection. Definisikan postselection dalam pengaturan matriks kerapatan sebagai berikut. Diberi matriks kepadatan , menulis ulang sebagai campuran negara dipisahkan. Biarkan menjadi hasil dari postselection (pada beberapa qubit) menggunakan formalisme murni-negara saya yang didefinisikan di atas. Tetapkan hasil dari postselection pada menjadi $M$ $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$ $\left\vert A_i \right>$ $M$ . $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$

Ini adalah definisi yang lebih masuk akal, karena tidak memberi kita hasil yang mengatakan bahwa setelah kita memilih, kita mengubah statistik peristiwa (pengukuran) yang sudah kita saksikan terjadi. Artinya, adalah probabilitas koin yang sudah "terbalik". Tidak masuk akal bagi saya untuk mengatakan bahwa kita akan kembali ke masa lalu dan bias flip koin yang sudah terjadi karena itu akan membuat pemilihan pasca saat ini lebih mungkin. $p_i$

EDIT (3/28/11 1 PM): Niel mengakui bahwa dengan definisi saya masalahnya masuk akal dan tidak meremehkan - tetapi dengan ketentuan bahwa saya tidak boleh menyebutnya postselection . Mengingat jumlah kebingungan, saya harus setuju dengannya. Jadi mari kita sebut apa yang saya definisikan sebagai seleksi , yang melakukan "pengukuran paksa". Saya mungkin harus mengubah nama kelas kompleksitas yang saya definisikan juga (untuk tidak memiliki "Posting" di dalamnya) jadi mari kita sebut mereka QMS [k] (kuantum-ukur-pilih).

cc.complexity-theory complexity-classes quantum-computing interactive-proofs Shaun Harker
sumber

Bisakah Anda mendefinisikan MPostBQP secara lebih formal? Jika Anda hanya bermaksud bahwa kelas ini memiliki kekuatan untuk memilih-pilih berdasarkan hasil dari beberapa bit, maka kelas ini harus dimuat dalam PostBQP.

Robin Kothari

Gagasan kuncinya adalah jangan memilih-pilih banyak bit sekaligus, karena seperti yang ditunjukkan Robin, ini tidak membantu. Ini untuk melakukan interspersi pengukuran dan pemilihan. Kami tidak bisa bepergian ini; pesanan itu penting. Misalnya tidak akan berfungsi di PostBQP untuk mengukur jawabannya, dan kemudian memilih.

Shaun Harker

Lihat komentar tentang jawaban Niel; kita bisa menunda pengukuran dan pasca seleksi sampai setelah evolusi kuantum. Saya sudah melakukan itu! Argumen yang sama tampaknya juga tidak menyusun ulang pemilihan setelah pengukuran juga, karena pengukuran tidak kesatuan. Secara khusus, saya katakan pengukuran dan pasca-pemilihan adalah operasi non-kesatuan pada keadaan kuantum yang tidak bolak-balik, sejauh yang saya tahu kita tidak bisa tanpa kehilangan menunda semua pemilihan setelah sampai semua pengukuran.

Shaun Harker

@Shaun Harker: fakta bahwa pengukuran dan pilihan akhir adalah non-kesatuan tidak benar-benar memberi kami informasi lebih lanjut tentang apakah mereka akan bepergian. Mungkin Anda bisa mengetahui mengapa menurut Anda mereka tidak bepergian?

Niel de Beaudrap

Karena keterikatan. Berikut ini sebuah contoh. Siapkan keadaan

. Pilih

. Jika kita pertama mengukur qubit pertama dan kemudian memilih pada qubit ketiga dan kemudian mengukur qubit kedua untuk hasil kita, maka kita memperoleh

atau

dengan probabilitas yang sama. Jika kita memilih dulu pada qubit ketiga, lalu mengukur qubit pertama, dan akhirnya mengukur qubit kedua untuk hasil kita, kita memperoleh

lebih jarang daripada kita mendapatkan

α | 000 ⟩ + \sqrt{1 / 2 - α^{2}} | 011 ⟩ + \sqrt{1 / 2 - β^{2}} | 101 ⟩ + β | 110 ⟩

$\alpha\left\vert 000 \right> + \sqrt{1/2 - \alpha^2} \left\vert 011 \right> + \sqrt{1/2 - \beta^2} \left\vert 101 \right> + \beta\left\vert 110 \right>$

0 < α < β < 1

$0 < \alpha < \beta < 1$

0

$0$

1

$1$

0

$0$

1

$1$

Shaun Harker

Jawaban:

Tampaknya dari komentar yang Shaun pikirkan sesuatu yang berbeda dari apa yang biasanya dipahami oleh pasca seleksi. Saya sekarang mengerti ini berarti bahwa statistik untuk setiap pengukuran yang dilakukan sebelum pemilihan pasca tertentu tidak boleh diubah oleh pasca pemilihan berikutnya. Ini mirip dengan memiliki operator proyeksi di mana normalisasi dilakukan pada setiap cabang dari fungsi gelombang yang sesuai dengan pengukuran pengukuran tertentu, daripada fungsi gelombang secara keseluruhan.

Dalam hal ini, argumen yang diberikan dalam jawaban lain oleh saya dan Neil tidak berlaku lagi. Memang mudah terlihat bahwa MPostBQP [k], karena MPostBQP $P^{PP[k]}\subseteq$ dapat dilihat sebagai mesin BQP yang dapat membuat query ke PP oracle, dan karenanya MPostBQP. $[k]$ $k$ $P^{\# P}\subseteq$

Jadi sekarang kita memiliki batas bawah non-sepele, bagaimana dengan batas atas? Ya, jelas masalahnya ada di PSPACE , tetapi bisakah kita melakukan yang lebih baik? Sebenarnya, saya pikir kita bisa.

Kita dapat menulis perhitungan apa pun dalam MPostBQP sebagai urutan lapisan bentuk: perhitungan kuantum diikuti oleh pemilihan-selingan, diikuti oleh pengukuran qubit tunggal. Memang, ini mungkin merupakan cara alternatif untuk merumuskan MPostBQP [k], karena perhitungan yang terdiri dari lapisan tersebut (ini sedikit berbeda dari definisi Shaun yang saya percaya dimaksudkan untuk menghitung hanya jumlah pilihan pasca), diikuti oleh lapisan akhir post-processing klasik. Saya akan menggunakan definisi MPostBQP [k] ini sebagai berikut, karena mengarah ke hasil yang lebih estetis. $k$

Di bawah ini diperbarui dari versi asli untuk memperbaiki lubang di buktinya.

Pertama, kami ingin menghitung hasil pengukuran qubit pertama yang diukur (tidak dipilih!). Untuk melakukan ini pertama-tama kita perhatikan bahwa setiap perhitungan kuantum dapat diekspresikan hanya menggunakan gerbang Hadamard dan gerbang Toffoli, dan amplitudo dari keadaan dasar komputasi tertentu dalam output dapat ditulis sebagai jumlah dari paling hal , di mana adalah jumlah total Hadamard gerbang, yang masing-masing berkorespondensi ke jalur komputasi yang unik. Jelas, $\alpha_w$ $|w\rangle$ $2^{H}$ $a_{j,w}$ $H$ $a_{j,w} = \pm 2^{-H/2}$ . Peluang untuk mendapatkan status akhir kemudian diberikan oleh . Kami ingin menghitung probabilitas total untuk mengukur 1. Misalkan adalah kumpulan keadaan dasar komputasi yang memenuhi kriteria pasca-seleksi (yaitu qubit pasca-pilih adalah 1) dan menghasilkan 0 untuk qubit yang diukur, dan biarkan $|w\rangle$ $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$ $S_0$ $S_1$ menjadi himpunan negara basis komputasi yang memenuhi kriteria pasca-seleksi dan menghasilkan 1 untuk qubit yang diukur. Kita dapat mendefinisikan dan

π_{0}^{\pm} = \sum w \in S_{0} \pm \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w}

$\pi_0^\pm = \sum{w \in S_0} \pm \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}$

π_{1}^{\pm} = \pm \sum_{w \in S_{1}} \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w} .

$\pi_1^\pm = \pm \sum_{w \in S_1} \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}.$

Dalam hal ini probabilitas untuk mengukur 1 dikondisikan pada 1 untuk qubit pasca-pilihan diberikan oleh . Seperti yang kita dapat menentukan ini dengan 4 panggilan ke oracle #P. Kami menggunakan ini untuk menghasilkan bit acakyaitu 1 dengan probabilitas, sama dengan pengukuran kuantum. JadiMPostBQP[1] ada dalam. $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$ $b_1$ $X_1$ $BPP^{\# P[4]}$

Selanjutnya kita menghitung hasil pengukuran qubit kedua. Untuk melakukan ini, kita menjalankan kueri #P yang sama seperti untuk lapisan pertama, tetapi pada sirkuit yang diperoleh dengan menyusun dua lapisan pertama, dan di mana kita memilih pada 1 untuk masing-masing qubit yang dipilih pasca, tetapi juga pada untuk output dari pengukuran 1. Perhatikan bahwa meskipun ini adalah pemilihan-pilih pada status 3 qubit daripada 1, ini adalah modifikasi sepele untukkueri , dengan hanya menambahkan ancilla yang ditetapkan hanya jika ketiga qubit memenuhi persyaratan yang diperlukan dan sebagai gantinya memilih di ancilla ini. Hal ini kemudian menghasilkan probabilitas output yang kondisional yang benar untuk hasil qubit diukur kedua, yang kami label $b_1$ $\# P$ $b_2$ . Perhatikan bahwa kami sekarang telah menggunakan 8 panggilan ke oracle #P .

Kami mengulangi proses ini secara iteratif, sehingga pada layer kami memilih pada 1 untuk semua sebelumnya qubit yang dipilih dan pada untuk semua pengukuran sebelumnya, dan memberi label hasil dari mesin sesuai $j$ $j$ $b_{i<j}$ $P^{\# P}$ . Secara total, ini membutuhkan permintaan oracle. $b_j$ $4j$

Dengan demikian kita memiliki MPostBQP [k] , yang dikombinasikan dengan hasil sebelumnya yang MPostBQP , menyiratkan bahwa MPostBQP [k] , dan karenanya MPostBQP $\subseteq P^{\# P[4k]}$ $P^{PP[k]}\subseteq$ $[k]$ $P^{PP[k]} \subseteq$ $\subseteq BPP^{\# P[4k]}$ . $= P^{\# P}$

Joe Fitzsimons
sumber

[Revisi.] Saya telah merevisi respons saya berdasarkan revisi Anda terhadap pertanyaan Anda, saya telah mempertahankan konten dari tanggapan asli saya, tetapi membuatnya lebih pendek. Deskripsi yang lebih terperinci dari proses "simulasi" telah diganti, tapi saya kira itu dapat dilihat dengan melihat riwayat edit posting ini.

Sebagian besar orang akan memahami "pemilihan akhir" dalam arti kemungkinan bersyarat. Memang, versi saat ini dari artikel Wikipedia saat ini di PostBQP menggambarkannya seperti itu; dan dipandang sebagai operasi pada operator kepadatan (di mana seseorang menerapkan jejak-tidak-meningkat peta yang benar-benar positif, sehingga Φ ² = Φ, dan kemudian memperbarui jejak) yang satu memulihkan definisi ini.

Dengan definisi postselection ini, definisi algoritma MPostBQP [ k ] Anda dapat disimulasikan oleh PostBQP algoritme , dengan menunda seleksi pasca dan melakukannya secara bersamaan, dengan cara yang sesuai. Ini dicatat kurang lebih secara eksplisit pada halaman 3 dari makalah Aaronson Quantum Computing, Postselection, dan Probabilistic Polynomial-Time yang memperkenalkan kelas PostBQP .

Ini dapat ditunjukkan secara eksplisit dengan mencatat bahwa, untuk urutan bit P ₁ , P ₂ , ... yang akan dipilih sebelumnya ( misalnya di 1negara, yang biasa), tidak ada perbedaan antara pendingin pada mereka berada 1di tengah-tengah perhitungan dan pengkondisian pada mereka berada 1di akhir perhitungan, selama nilai bit ini tidak diubah untuk sementara. Kemudian, daripada memilih pada masing-masing dari mereka secara individu 1, kita dapat menghitung logika mereka DAN sebelum pasca-seleksi dan kemudian memilih pada hubungan yang menjadi1. Lebih jauh lagi, menghitung AND dapat dilakukan pada titik mana pun antara transformasi bit terakhir dan pasca-pemilihannya. Ini sama sekali tidak akan mempengaruhi statistik gabungan dari salah satu properti negara.

Dengan demikian, dengan menggunakan definisi umum dari pemilihan-dalam hal probabilitas bersyarat, kita akan memiliki MPostBQP [ k ] = PostBQP untuk semua k > 0.

Seperti yang telah saya catat dalam komentar di atas, saya tidak berpikir bahwa operasi yang Anda gambarkan pada status vektor - khususnya, yang melibatkan renormalisasi vektor-negara secara independen di setiap cabang distribusi probabilitas atas hasil pengukuran- sesuai dengan pasca-seleksi, karena banyak orang di lapangan (terutama eksperimentalis) akan menggambarkan konsep tersebut. Bahkan dapat menimbulkan beberapa sifat 'tidak fisik', jika diperluas ke pemetaan pada operator kepadatan. Namun, itu adalah cara yang mungkin untuk membangun sesuatu seperti pohon keputusan yang simpulnya diberi label oleh vektor-vektor negara, dan karena itu pada prinsipnya merupakan proses studi yang masuk akal dalam dirinya sendiri. Saya hanya tidak akan menyebut proses itu 'pasca pemilihan'.

[Sunting.] Demi kerapian, saya telah menghapus contoh yang dihitung. Saya kira itu bisa dilihat dengan melihat riwayat edit posting ini.

Niel de Beaudrap
sumber

Argumennya tampak tidak lengkap. Komentar dalam makalah Aaronson menunjukkan bahwa kita tidak memperoleh kekuatan dengan menyelaraskan pilihan-pilihan dengan evolusi kesatuan, seperti halnya tidak membantu untuk menyelingi pengukuran dengan evolusi kesatuan. Tapi saya tidak melakukan keduanya; Saya menyelingi postselection dan pengukuran. Untuk menjawab pertanyaan saya dalam negatif dengan cara ini akan membutuhkan pembuktian kami selalu dapat memesan pasca-seleksi setelah pengukuran tanpa kehilangan daya. (Tidak jelas bagi saya sama sekali.) Sisa dari jawaban hanya menjelaskan mengapa saya mendefinisikan kelas untuk hanya memilih pada satu bit setiap putaran.

Shaun Harker

@Shaun Harker: Terlepas dari apakah kertas Aaronson menjawab pertanyaan Anda, tanggapan saya di atas harus. Efek dari postselection pada dasarnya adalah untuk memungkinkan pengukuran untuk mewujudkan probabilitas bersyarat daripada probabilitas "non-kondisional". Pasca memilih pada bit

pada dasarnya sama seperti memilih untuk konjungsi dari kondisi untuk probabilitas bersyarat. Mereka probabilitas bersyarat pada bit

tidak berubah, hanya dengan menunda evaluasi apakah kondisi memegang, asalkan bit

yang tersisa tanpa gangguan.

C_{j}

$C_j$

C_{j}

$C_j$

C_{j}

$C_j$

Niel de Beaudrap

Tampaknya Anda berargumen bahwa kami mendapatkan statistik yang sama jika kami menyusun ulang pos pemilihan dan pengukuran. Tetapi jika kita mengukur beberapa bit sebelum pemilihan, maka kita mengukur dari distribusi yang berbeda maka kita akan memiliki jika kita mengukur bit yang sama setelah pemilihan akhir. Jadi statistiknya tidak sama.

Shaun Harker

Untuk tujuan mengumpulkan statistik, pemilihan pasca dapat diimplementasikan secara fisik (walaupun tidak efisien) dengan hanya menolak uji coba di mana kondisi pasca yang diinginkan tidak berlaku. Status apakah suatu postcondition berlaku ( mis. "Bit tunggal ini dalam keadaan | 1⟩" atau "lima bit ini semuanya dalam keadaan | 1⟩") tidak dipengaruhi oleh urutan pengukuran, selama operasi tidak diterapkan untuk mengubah bit yang menyimpan hasilnya. Karena fakta apakah uji coba akan ditolak atau tidak tidak tergantung pada urutan pengukuran di PostBQP , kami dapat menunda pemilihan sampai akhir.

Niel de Beaudrap

Karakterisasi postselection ini hanya berlaku ketika kami melakukan postselection sebelum pengukuran. Tiga contoh qubit yang saya berikan sudah menunjukkan hal ini. Jika saya salah tentang hal ini, maka silakan balas dengan menyangkal langsung contoh ini yang memberikan statistik berbeda tergantung pada urutan pengukuran dan pemilihan akhir.

Shaun Harker

Tampaknya dari definisi Anda MPostBQP , bahwa ini hanyalah PostBQP dalam pakaian mewah. Daripada mencoba meyakinkan Anda bahwa pengukuran dapat disusun ulang, mungkin Anda akan merasa lebih meyakinkan untuk membuktikan MPostBQP = PP , karena diketahui bahwa PostBQP = PP (lihat quant-ph / 0412187 ). Untuk membuktikan ini, kami memisahkannya menjadi dua tugas:

$\subseteq$ MPostBQP dan
$\subseteq$

$\subseteq$ halaman Wikipedia di PostBQP untuk garis besar buktinya).

Berikut ini diadaptasi dari sketsa bukti Wikipedia untuk PostBQP = PP .

$|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$ $P_i^1$ $i$ $|1\rangle$ $A^{ij}$ $A^{ij}$ adalah nyata dengan mengorbankan sebuah qubit tambahan.

$\{p_i\}$ $q$ $\pi_0 = \sum_{w \in S_0} \psi_w^2$ $\pi_1 = \sum_{w \in S_1} \psi_w^2$ $S_0$ $S_1$ $p_i = 1 \forall i$ $q=0$ ( $q=1$ $\pi(1) \geq 2\pi(0)$ $\pi_0 \geq 2\pi_1$ $\pi_0$ $\pi_1$ $\psi_w$ $\psi$ $w$ $i$ $j$ $A^{ij}$ $k$ $G$ $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$

$\frac{1}{2}(1+C(\pi_1-\pi_0))$ $C>0$ $x \in L$ $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ $x \notin L$

$\alpha = \{\alpha_i\}$ $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$ $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$

Seperti PP mesin kemudian dapat didefinisikan sebagai berikut:

$w$
$w \notin S_0 \cup S_1$ $1/2$ , dan menolak sebaliknya.
$\alpha$ $\alpha'$ $G$ dasar komputasi secara seragam secara acak.
$X = F(A,w,\alpha,x)F(A,w,\alpha',x)$ .
$w\in S_1$ $\frac{1+X}{2}$ $w\in S_0$ $\frac{1-X}{2}$ , dan tolak sebaliknya.

$\subseteq$ $k$

Joe Fitzsimons
sumber

Argumen ini menunjukkan bahwa menyelingi banyak pilihan-pilihan dengan evolusi kesatuan tidak memberi kita lebih dari sekadar PP. Saya sangat setuju. Kita dapat tanpa kehilangan kekuatan menunda mereka sampai akhir dan kita hanya perlu satu. Saya tidak melihat bahwa argumen ini memberi tahu saya lebih dari itu. Tetapi pertanyaan saya menanyakan sesuatu yang berbeda; itu menganggap evolusi kesatuan diikuti oleh putaran pengukuran dan seleksi (dengan probabilitas akhir diperhitungkan melalui metode pohon keputusan ini). Jadi saya tidak melihat bahwa ini menjawab pertanyaan saya.

Shaun Harker

Bukan untuk mengatakan saya tidak (sangat) menghargai upaya yang Anda lakukan dalam respons Anda. Saya hanya tidak melihat bahwa itu membahas apa yang benar-benar saya coba capai, yang saya akui tidak terlalu hebat dalam pekerjaan menjelaskan.

Shaun Harker

@Shaun: Saya tidak melihat perbedaannya. Apakah Anda menyarankan bahwa menambahkan pengukuran mengubah daya? Ini tentu tidak demikian, karena pengukuran selalu setara dengan evolusi kesatuan pada ruang Hilbert yang lebih besar.

Joe Fitzsimons

@ Samun: Maksud saya adalah bahwa secara matematis situasi dengan pengukuran dan situasi tanpa (tetapi dengan ruang Hilbert yang sesuai diperbesar) adalah identik. Saya tidak mencoba untuk membuat titik filosofis apa pun, atau mendukung satu interpretasi mekanika kuantum, saya hanya menunjukkan bahwa menambahkan pengukuran tidak membuat perbedaan pada kekuatan komputasi karena hasil (matematika) yang mapan.

Joe Fitzsimons

@Shaun: Sepertinya saya salah menerapkan pemilihan pasca. Jika Anda menerapkannya dengan cara normal (yaitu mempertimbangkan statistik apa yang Anda dapatkan jika Anda hanya mempertimbangkan hasil yang sesuai dengan kriteria tertentu), maka Anda mendapatkan PostBQP = MPostBQP, seperti yang ditunjukkan oleh Niel dan saya. Anda juga mendapatkan statistik identik independen dari pemesanan untuk pengukuran negara yang Anda berikan di komentar. Yang penting qubit pertama tidak memberikan 0 dan 1 dengan probabilitas yang sama. (

Bersambung