Apakah ada persamaan Quantum dari teorema hierarki Waktu?

19

Teorema favorit saya dalam teori kompleksitas adalah teorema hierarki waktu. Namun, ini dilakukan pada tahun 1965.

Saya ingin tahu kalau ada sesuatu yang serupa dengan Quantum Computing.

Juga, jika bukan apa yang orang / kelompok bekerja di arah ini!

cc.complexity-theory quantum-computing Zelah 02
sumber
Entah bagaimana pertanyaan ini terdengar seperti tuduhan dan saya tidak suka itu.
Tsuyoshi Ito
12
Apa tuduhannya?
Zelah 02
2
Menarik, tetapi sepertinya jawabannya adalah tidak . Saya membaca di sini bahwa "teorema yang sama tidak dikenal untuk waktu probabilistik atau waktu kuantum."
MS Dousti
4
Saya pikir Tsuyoshi menafsirkan tanda seru dalam kalimat terakhir Anda sebagai tuduhan kepada peneliti kuantum karena tidak bekerja pada hasil penting. Saya yakin Anda hanya bermaksud untuk bertanya apakah orang bekerja menuju teorema hierarki kuantum atau tidak.
Alessandro Cosentino

Jawaban:

15

Kutipan yang lebih baru untuk teorema hierarki waktu adalah "Hierarki Waktu Generik untuk Model Semantik Dengan Satu Saran" oleh Dieter van Melkebeek dan Konstantin Pervyshev yang dapat Anda peroleh dari halaman web Dieter. Teknik-teknik di sana memberikan hierarki waktu dengan 1 bit saran untuk model semantik "apa pun yang masuk akal", termasuk algoritma kuantum.

Juga, biasanya relatif mudah untuk mendapatkan hierarki untuk masalah janji yang dihitung oleh model semantik. Masalah janji hanya membutuhkan algoritme untuk "berperilaku baik" (misalnya, memiliki kesalahan terikat) pada beberapa input - input yang dipilih untuk menjadi bagian dari masalah janji. Untuk input yang tidak dipilih untuk menjadi bagian dari janji, algoritma dapat berperilaku sewenang-wenang (mis., Tidak memiliki kesalahan terikat). Hierarki untuk masalah janji adalah hasil cerita rakyat; bukti untuk pengaturan BPP diberikan dalam "Space Hierarchy Results for Randomized and Other Semantic Models" oleh Dieter van Melkebeek dan Jeff Kinne (saya sendiri) yang bisa Anda dapatkan dari Dieter's atau halaman web saya. Ini juga berlaku untuk algoritma kuantum.

Jadi jawabannya adalah, teorema hierarki yang layak dikenal untuk algoritma kuantum yang mendapatkan 1 bit saran atau diizinkan untuk mengabaikan input yang bermasalah. Beberapa teknik untuk hasil ini bergantung pada sifat-sifat algoritma acak. Akan menarik untuk mencoba dan mengeksploitasi sifat-sifat algoritma kuantum di bidang teorema hierarki.

Area yang agak terkait di mana ada hasil khusus untuk algoritma kuantum adalah area batas waktu-ruang yang lebih rendah. Ada survei oleh Dieter van Melkebeek: "Sebuah Survei Batas Bawah untuk Kepuasan dan Masalah Terkait".

Jeff KInne
sumber
19

Jawabannya adalah tidak. Kami bahkan tidak memiliki teorema hierarki waktu untuk waktu polinomial probabilitas-kesalahan terbatas (yaitu, BPTIME). Teorema hierarki waktu deterministik dan non-deterministik memiliki argumen diagonalisasi, yang tampaknya tidak berfungsi untuk kelas semantik. Inilah sebabnya kami tidak memiliki teorema hierarki yang kuat untuk kelas semantik.

Hasil terbaik yang saya ketahui adalah teorema hierarki untuk BPTIME dengan 1 saran: Fortnow, L .; Santhanam, R. (2004). Teorema Hierarki untuk Waktu Polinomial Probabilistik .

Saya tidak tahu ada kelompok yang mengerjakan teorema hierarki waktu kuantum. Saya kira ini karena sepertinya masalah hierarki BPTIME lebih mudah, jadi para peneliti akan menyerang masalah itu sebagai gantinya.

(Beberapa pertanyaan terkait: Apakah ada karakterisasi sintaksis untuk BPP, BQP, atau QMA? Di MathOverflow dan Semantic vs. Classical Complexity Classes di cstheory.)

Robin Kothari
sumber
4

Kelas waktu-dan-ruang terbatas quantum non-deterministik adalah yang mana bahasa adalah set string yang diterima oleh mesin Turing kuantum yang beroperasi dalam batas terkait dengan probabilitas bukan nol.

Dalam Bagian 8 dari " membuktikan kekuatan pasca pemilihan ", kami menunjukkan bahwa hierarki yang ketat untuk kelas quantum waktu-dan-ruang-terikat nondeterministik.

Cem Say
sumber