Perkiraan masalah penghitungan menangkap BQP

Dalam model kotak hitam, masalah menentukan output mesin BPP pada input adalah masalah penghitungan perkiraan untuk menentukan dengan kesalahan aditif 1/3 (katakanlah) . $M(x,r)$ $x$ $E_r M(x,r)$

Apakah ada masalah serupa untuk BQP? Komentar Ken Regan ini menunjukkan masalah seperti itu

Anda dapat mengurangi pertanyaan BPP hingga mendekati fungsi #P tunggal, tetapi dengan BQP yang Anda dapatkan adalah perbedaan dari dua fungsi #P, sebut saja dan . Perkiraan dan secara terpisah tidak membantu Anda memperkirakan ketika mendekati nol! $f$ $g$ $f$ $g$ $f - g$ $f - g$

BQP memang memberi Anda sedikit bantuan: Ketika jawaban untuk pertanyaan BQP pada input adalah ya, Anda mendapatkan bahwa dekat dengan akar kuadrat , di mana predikat penghitungan mendefinisikan dan memiliki variabel biner m setelah Anda mengganti . (Tidak ada bilah nilai absolut; "ajaib" Anda selalu mendapatkan . Di bawah representasi umum dari sirkuit kuantum untuk BQP, $x$ $f(x) - g(x)$ $2^m$ $f$ $g$ $x$ $f(x) > g(x)$ $m$ menjadi jumlah gerbang Hadamard.) Ketika jawabannya tidak, perbedaannya mendekati 0.

Bisakah Anda dengan tepat merumuskan masalah sedekat mungkin dengan BQP? Saya berharap untuk sesuatu seperti: diberi akses kotak hitam ke fungsi pemetaan ke , dengan janji bahwa ..., perkirakan dalam . $f,g$ $X$ $Y$ $f-g$ $\varepsilon$

cc.complexity-theory quantum-computing black-box Manu
sumber

Saya pikir komentar Ken Regan mengacu pada hasil BQP⊆AWPP oleh Fortnow dan Rogers (JCSS 1999; people.cs.uchicago.edu/~fortnow/papers/quantum.pdf ).

Tsuyoshi Ito

Jawaban:

Emanuele: Sayangnya, kami tidak tahu ada masalah black-box menangkap BQP sesederhana yang Anda sebutkan menangkap BPP.

Secara intuitif, ini karena sulit untuk berbicara tentang BQP tanpa membawa kesatuan dalam satu atau lain bentuk. Kemampuan untuk menjumlahkan angka positif dan negatif adalah apa yang membuat BQP lebih kuat dari BPP, tetapi kemudian unitaritaslah yang membuat BQP lebih kuat dari #P! :-)

Karena itu, selain Dawson et al. makalah yang dihubungkan dengan Martin Schwarz, Anda pasti harus memeriksa ini dan ini oleh Janzing dan Wocjan, yang memberikan masalah janji "tampak klasik" yang menangkap BQP.

Juga, misalkan S ⊆ {0,1} ⁿ , dan pertimbangkan fungsi Boolean f: S → {0,1}. Kemudian saya memiliki dugaan dari tahun lalu yang mengatakan bahwa Q (f), kompleksitas kueri kuantum kesalahan-terikat dari f, secara polinomi terkait dengan derajat minimum dari polinomial nyata p: R ⁿ → R sedemikian rupa sehingga

(i) p (x) ∈ [0,1] untuk semua x∈ {0,1} ⁿ , dan

(ii) | p (x) -f (x) | ≤ ε untuk semua x∈S.

Jika dugaan ini berlaku, maka "perkiraan masalah penghitungan menangkap BQP" hanya akan mendekati nilai polylog (n) -degree polinomial p: R ⁿ → R, pada titik yang ditentukan pada kubus Boolean, mengingat bahwa p adalah dibatasi di mana-mana di kubus Boolean. Ini mungkin sedekat mungkin dengan jawaban untuk pertanyaan Anda.

Scott Aaronson
sumber

Terima kasih. Saya memeriksa jawaban ini karena "Ini mungkin sedekat mungkin dengan jawaban untuk pertanyaan Anda." Pertanyaan: apa peran "S" dalam dugaan Anda? Saya bingung dengan (i) berbicara tentang {0,1} ^ n dan sisanya berbicara tentang S.

Manu

Emanuele: Jika S = {0,1} ^ n, maka f adalah fungsi Boolean total. Dalam hal itu, sudah diketahui bahwa kompleksitas kueri kuantum secara polinomi terkait dengan tingkat perkiraan (serta kompleksitas deterministik dan acak). Jadi kasus yang menarik adalah ketika f adalah fungsi Boolean parsial : yaitu, algoritma kuantum hanya perlu bekerja pada input yang memenuhi janji bahwa x milik S. Itulah situasi di mana algoritma kuantum seperti Simon (yang secara eksponensial mengungguli algoritma klasik terbaik) menjadi mungkin.

Scott Aaronson

Perhatikan bahwa, sementara algoritma kuantum hanya perlu menghitung f pada input milik set S, probabilitas penerimaan algoritma pada input yang tidak dalam S masih termasuk dalam interval [0,1]! Kedengarannya konyol, yang sering menjadi pengamatan penting dalam membuktikan batas bawah kuantum melalui metode polinomial. Dan jika saya tidak meminta polinomial p untuk dibatasi dalam [0,1] untuk semua x dalam {0,1} ^ n (bahkan x tidak dalam S), maka dugaan saya akan secara sepele salah.

Scott Aaronson

Makalah ini menguraikan ide-ide yang ditentukan di atas secara rinci.

Martin Schwarz
sumber

Z_{2}

$Z_2$

@Emanuele Viola, @Martin Schwarz: Saya tidak benar-benar melihat bagaimana makalah ini menjawab pertanyaan awal. Pertama, makalah ini tidak membahas masalah kotak hitam sama sekali. Saya sepertinya tidak bisa mendapatkan rumusan masalah kotak hitam dari kertas, jenis yang ditanyakan dalam pertanyaan. Mungkin salah satu dari kalian bisa menjelaskan ini?

Robin Kothari

@Robin Kothari: Saya setuju, bahwa makalah itu tidak menghasilkan masalah kotak hitam, seperti yang ditanyakan semula. Itu menguraikan komentar Ken Regan. Saya seharusnya membuat ini "komentar" daripada "jawaban".

Martin Schwarz

Oh, baiklah. Tidak masalah. Jadi saya kira pertanyaannya masih belum terselesaikan saat itu.

Robin Kothari