Hasil mana yang membuat ruang kuantum menarik?

17

Perhitungan kuantum terikat waktu jelas sangat menarik. Bagaimana dengan perhitungan kuantum yang dibatasi ruang?

Saya tahu banyak hasil menarik untuk komputasi kuantum dengan batas ruang sublogaritmik dan berbagai jenis model quantum automata.

Di sisi lain, itu menunjukkan bahwa probabilistik dan ruang kuantum unbounded-error adalah setara untuk setiap ruang yang dapat dikonstruksikan (Watrous, 1999 dan 2003 ).s(n)∈Ω(catatan⁡(n))

Saya bertanya-tanya apakah ada beberapa hasil spesifik yang membuat ruang kuantum menarik (dengan mengecualikan model sublogaritmik-ruang dan automata).

(Saya mengetahui entri ini: Analog kuantum kelas kompleksitas SPACE .)

quantum-computing space-bounded Abuzer Yakaryilmaz
sumber
1
Maaf atas ketidaktahuan. Apa hubungan antara komputasi kuantum ruang-dibatasi dan model sirkuit kuantum?
Alex 'qubeat'
1
@ Alex'qubeat ': Lebih mudah menggunakan mesin Turing untuk perhitungan yang dibatasi ruang. Model sirkuit sesuai untuk perhitungan yang dibatasi waktu.
Abuzer Yakaryilmaz
1
Mengapa lebih nyaman? Apakah nyaman dalam kasus kuantum atau klasik? Dari sudut pandang naif, ini adalah ruang tanpa batas yang lebih nyaman untuk mesin Turing (klasik).
Alex 'qubeat'
1
@ Alex'qubeat ': Lebih mudah untuk kasus klasik dan kuantum. Saya bisa sangat merekomendasikan Anda makalah mendasar tentang masalah ini oleh Stearns, Hartmanis, dan Lewis: "Hierarki memori terbatas perhitungan" ( computer.org/portal/web/csdl/doi/10.1109/FOCS.1965.11 ). Anda juga dapat memeriksa kedua makalah Watrous (disebutkan di atas) dan makalah terbaru oleh Melkebeek dan Watson ( theoryofcomputing.org/articles/v008a001 ).
Abuzer Yakaryilmaz
1
Terima kasih, saya telah melihat itu, tetapi ada juga pekerjaan menggunakan sirkuit kuantum arxiv.org/abs/0908.1467 bahwa, setidaknya tidak menderita karena keharusan untuk mengelola dengan beberapa definisi QTM yang berbeda.
Alex 'qubeat'

Jawaban: