Apa peran yang tepat dari verifikasi dalam pengambilan sampel kuantum, simulasi, dan pengujian extended-Church-Turing (ECT)?

9

Karena tidak ada jawaban yang diberikan, bendera telah ditetapkan yang meminta agar pertanyaan ini dikonversi ke wiki komunitas.

Komentar oleh Aaron Sterling, Sasho Nikolov, dan Vor telah disintesis menjadi resolusi berikut, yang terbuka untuk diskusi wiki komunitas:

Terselesaikan:    Sehubungan dengan algoritma klasik yang menghasilkan angka, sampel, atau lintasan simulasi, logika matematika yang ketat mengharuskan keempat proposisi berikut diterima, atau tidak satupun dari mereka:

  1. Kita dapat mengesampingkan algoritma klasik polinomial-waktu untuk menghasilkan angka acak.  [1]
  2. "Kita dapat mengesampingkan algoritma klasik polinomial-waktu untuk sampel distribusi keluaran komputer kuantum, dengan asumsi tunggal bahwa hierarki polinom tidak terbatas."  [2]
  3. "Kami tidak dapat mensimulasikan [lintasan mekanika kuantum] dengan cara yang biasa ... ada terlalu banyak variabel." ψ(t) [3]
  4. Diperpanjang Church-Turing-Thesis (ECT) dikesampingkan, karena alasan ketat bahwa algoritma klasik tidak dapat menghasilkan angka acak.  [4]

Untuk memulai diskusi, berikut adalah tanggapan positif dan afirmatif yang, meskipun masing-masing dapat dipertahankan, sengaja dinyatakan berlebihan. Argumen yang sangat afirmatif mungkin:

Afirmatif:   Keempat pernyataan ini mencerminkan teorema bahwa, untuk menghormati ketelitian, mengharuskan kita untuk tidak pernah berbicara tentang algoritma klasik yang menghasilkan bilangan acak, sampel acak, atau simulasi kuantum, melainkan berbicara hanya tentang algoritma klasik yang menghasilkan bilangan pseudo-acak dan (oleh ekstensi) sampel pseudo-acak, dan simulasi pseudo-kuantum.

Dengan pemahaman ini, keempat pernyataan itu benar. Selain itu, untuk menghindari ambiguitas dan mencegah kebingungan, matematikawan harus mendorong ilmuwan dan insinyur untuk membubuhkan awalan "pseudo-" ke hampir semua penggunaan "acak", "sampel", dan "simulasi kuantum".

Argumen yang sangat negatif mungkin:

Negatif:   Pernyataan-pernyataan ini (dan teorema formal yang terkait) adalah tanda-posting yang mengarahkan kita ke distrik "lampu merah" gaya-Lakatos di mana kita dipanggil untuk secara antusias merangkul (apa yang disebut) disiplin ilmu pseudo-randomness , pseudo-sampling, dan pseudo-simulasi ... praktik matematika yang menyenangkan untuk alasan berdosa yang nikmat: mereka mencapai efek matematika yang menurut logika formal tidak mungkin. Oleh karena itu, apa yang bisa lebih ajaib, dan lebih menyenangkan, daripada kesimpulan ini: masing-masing pernyataan empat resolusi secara resmi benar, tetapi praktis salah?

Karena dipahami, keempat pernyataan itu salah. Selain itu, karena sebagian besar pelukan praktis "keacakan", "pengambilan sampel", dan "simulasi kuantum" terjadi di lingkungan magis ini — di mana masalah yang terkait dengan kompleksitas Kolmogorov dan penilaian orokal dengan sengaja diabaikan - para ahli matematikalah yang harus mengubah penggunaannya.

Namun, secara realistis, bagaimana seharusnya para ahli teori kompleksitas mengutarakan temuan mereka terkait dengan keacakan, sampel, dan simulasi ... di satu sisi, dengan pandangan untuk mempertahankan keseimbangan yang jernih, kejelasan, ketelitian, dan kekakuan ... dan di sisi lain, dengan pandangan menuju mempertahankan komunikasi dengan kebisingan rendah dengan disiplin STEM lainnya? Tujuan yang terakhir ini sangat penting, karena kemampuan praktis terus meningkat dalam bidang-bidang seperti kriptografi, pengujian statistik, pembelajaran mesin, dan simulasi kuantum.

Akan sangat membantu (dan menyenangkan juga) untuk membaca jawaban yang beralasan, baik afirmatif atau negatif.

Pertanyaan yang diajukan adalah

Apa peran verifikasi yang diterima secara umum dalam definisi kompleksitas-teoretis yang terkait dengan pengambilan sampel, simulasi, dan pengujian tesis extended-Church-Turing (ECT)?

Jawaban yang disukai adalah referensi ke artikel, monograf, atau buku teks yang membahas masalah ini secara mendalam.

Jika literatur ini terbukti jarang atau tidak memuaskan, maka (setelah dua hari) saya akan mengonversi pertanyaan ini ke wiki komunitas yang bertanya:

Apakah peran yang masuk akal dan pantas verifikasi dalam definisi kompleksitas-teoretis yang terkait dengan pengambilan sampel, simulasi, dan pengujian tesis extended-Church-Turing (ECT)?

Latar Belakang

Pertanyaan yang diajukan dimotivasi oleh utas baru-baru ini, "Apa artinya menyangkal tesis Church-Turing?" , khususnya jawaban (IMHO sangat baik) yang diberikan oleh Gil Kalai dan oleh Timothy Chow

Dalam pertanyaan yang diajukan, frasa "definisi teoretis kompleksitas-yang tepat dan / atau diterima" harus ditafsirkan sebagai menahan Alice dari klaim tidak masuk akal seperti berikut:

Alice:   Ini adalah sampel percobaan saya dari angka biner acak yang dihitung oleh jaringan optik linear (satu-foton) saya.

Bob:   Ini adalah sampel simulasi saya dari angka pseudo-acak yang dihitung oleh mesin Turing klasik.

Alice:   Maaf Bob ... sampel Anda secara algoritmik dapat dikompresi, dan milik saya tidak. Karenanya data eksperimental saya menunjukkan bahwa ECT salah! "

Dengan tidak adanya asosiasi verifikasi pengambilan sampel, alasan Alice sangat sempurna. Dengan kata lain, harus teori kompleksitas menganggap ECT sebagai memiliki sudah secara resmi dibantah ... dekade yang lalu?

Dari sudut pandang praktis, metode simulasi yang terkait dengan pengambilan sampel lintasan kuantum pada ruang keadaan variabel mulai digunakan secara luas di banyak disiplin ilmu dan teknik. Itulah sebabnya definisi kompleksitas-teoretis dari sampel yang menghormati peran sentral verifikasi (yang tidak dapat dipisahkan dari keterulangan) dalam sains dan teknik akan sangat disambut baik oleh para ilmuwan dan insinyur yang mempraktekkannya ... terutama jika definisi ini disertai oleh teorema yang menggambarkan kompleksitas komputasi dari pengambilan sampel yang diverifikasi.

Edit Ditambahkan: Berkat kolaborasi antara University of Geneva dan perusahaan id Quantique , sangat mungkin untuk menyelesaikan latihan ini dalam kenyataan.

Berikut adalah 1024 bit acak yang disertifikasi oleh id Quantique sebagai algoritme yang tidak dapat dimampatkan :

0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011

Haruskah kita sekarang menerima klaim: "Tesis ECT ditolak"?

Jika tidak, alasan apa yang harus kita berikan?

quantum-computing program-verification sample-complexity John Sidles
sumber
1
1000nnlog2⁡nL2/3n
3
Saya pikir ini adalah pertanyaan yang bagus. Tetapi, dalam contoh Anda, bagaimana Alice tahu bahwa digit-digitnya tidak dapat dikompresi secara algoritmik?
Aaron Sterling
1
Pada sampling ekuivalensi / pencarian: scottaaronson.com/papers/samprel.ps
Marzio De Biasi
1
@ John: hanya klarifikasi (saya menggarisbawahi bahwa saya bukan ahli): " ... disertifikasi oleh id Quantique sebagai algoritmik yang tidak dapat dimampatkan ", tetapi bagaimana mereka dapat mengesahkannya? Jelasnya kompleksitas Kolmogorov dari suatu string tidak dapat dihitung sehingga kalimat tersebut keliru. Bahkan jika mereka hanya mengatakan " kami menyatakan bahwa urutannya adalah (kuantum) acak " Saya memiliki beberapa keraguan: proses fisik (perangkat keras) sulit untuk diseimbangkan sehingga mereka menggunakan Von Neumann unbiasing yang baik, tetapi tidak menjamin bahwa hasilnya benar-benar acak .
Marzio De Biasi
2
@ John Sidles: saat Anda melakukan pengamatan yang menarik dan suara, saya tidak mengerti apa yang Anda cari. Sudah jelas apa yang dimaksud oleh Aaronson dan rekan penulis dengan "mengesampingkan": jika PH tidak terbatas, tidak ada algoritma tertentu dalam model tertentu. Saya kira Anda bertanya apakah asumsi pemodelan dapat diverifikasi. perhatikan bahwa tujuan dari model ini adalah untuk memverifikasi hanya asumsi pemodelan, alih-alih menguji algoritma / teorema yang mungkin
Sasho Nikolov

Jawaban:

2

Inti pertanyaannya adalah, mengingat bahwa probabilitas kuantum adalah sumber keacakan yang sebenarnya, bagaimana hal itu memengaruhi tesis Church-Turing yang diperpanjang (atau efisien, atau waktu polinomial)?

Jawabannya adalah, per dugaan, itu tidak mempengaruhi itu. Orang-orang menduga bahwa BPP = P, yaitu, bahwa algoritma acak dapat diderandomisasi dengan generator pseudo-random-number dengan overhead polinomial. Iman pada PRNG sebagai pengganti keacakan benar adalah salah satu alasan bahwa orang akan percaya tesis Gereja-Turing diperpanjang jika bukan untuk perhitungan kuantum.

Greg Kuperberg
sumber