Baru-baru ini saya menemukan sebuah makalah oleh Coudron dan Yuen tentang ekspansi keacakan menggunakan perangkat kuantum. Hasil utama dari pekerjaan ini adalah bahwa dimungkinkan untuk menghasilkan keacakan "tak terbatas" dari sejumlah sumber yang konstan (yaitu, jumlah bit acak yang dihasilkan hanya bergantung pada jumlah putaran protokol dan bukan pada jumlah sumber. ).
Secara naif, bagi saya ini seperti hasil yang memungkinkan derandomisasi dari setiap algoritma acak dengan sumber kuantum, dan akan menyiratkan semacam penahanan kelas kompleksitas acak di dalam kelas kuantum yang sesuai.
Tetapi saya tidak begitu mengerti teori informasi kuantum, dan saya yakin ada banyak seluk-beluk yang saya lewatkan. Belum lagi bahwa jika klaim seperti itu mungkin, penulis akan membuatnya. Jadi pertanyaan saya adalah:
Apakah keberadaan "ekspansi keacakan tak terbatas" seperti yang dijelaskan dalam makalah (dan semua pekerjaan terkait) menyiratkan semacam pernyataan derandomisasi untuk kelas kompleksitas acak? Dan jika tidak, mengapa tidak?
Pembaruan: Saya diarahkan ke ikhtisar tingkat tinggi yang sangat baik dari area ini dan dari makalah di atas oleh Scott Aaronson. Sayangnya saya masih bingung :).
sumber
Jawaban:
Ini pertanyaan yang bagus, Suresh!
Hasil ekspansi keacakan kami tidak menyiratkan hasil teori kompleksitas. Berikut ini salah satu cara untuk memahami hasilnya: kami percaya bahwa mekanika kuantum mengatur dunia, dan di bawah asumsi ini, ada yang perangkat kuantum yang menghasilkan asli, benar, keacakan informasi-teori.
Namun, bayangkan Anda tidak mempercayai kotak-kotak ini yang mengklaim melakukan hal-hal kuantum yang aneh ini dan menghasilkan keacakan (bagi sebagian orang, ini mungkin tidak terlalu banyak membayangkan). Anda tidak ingin berurusan dengan qubit. Yang Anda mengerti adalah string bit klasik.
Ekspansi keacakan adalah protokol di mana Anda, sebagai verifier klasik, dapat berinteraksi dengan sekelompok kotak hitam (menganggapnya sebagai provers non-communicating ), dan setelah menjalankan protokol dengan kotak hitam ini, Anda telah memastikan bahwa outputnya mengandung entropi sangat tinggi - jika prover lulus. Selain itu, jumlah keacakan yang Anda mulai dengan jauh lebih sedikit daripada entropi output yang Anda sertifikasi.
Dengan kata lain, ini adalah bukti interaktif untuk generasi keacakan.
Jadi, satu-satunya aspek "derandomisasi" dari itu adalah untuk berpendapat bahwa protokol itu sendiri memerlukan keacakan startup kecil. Tetapi hasilnya sangat un-derandomized: output yang dihasilkan oleh kotak adalah keacakan yang sebenarnya, bukan pseudorandomness (yaitu tidak ada asumsi komputasi).
sumber