Analog kuantum kelas kompleksitas SPACE

Kami sering mempertimbangkan kelas kompleksitas di mana kami dibatasi dalam jumlah ruang yang dapat digunakan mesin Turing kami, misalnya: atau . Tampaknya pada awal teori kompleksitas ada banyak keberhasilan dengan kelas-kelas ini seperti teorema ruang-hierarki dan penciptaan pada kelas-kelas penting seperti dan . Apakah ada definisi analog untuk perhitungan kuantum? Atau adakah alasan yang jelas mengapa kuantum analog tidak akan menarik? $\textbf{DSPACE}(f(n))$ $\textbf{NSPACE}(f(n))$ $\textbf{L}$ $\textbf{PSPACE}$

Sepertinya akan penting untuk memiliki kelas seperti --- versi quantum dari : memerlukan sejumlah logaritmik qubit (atau mungkin TM kuantum menggunakan ruang logaritmik). $\textbf{QL}$ $\textbf{L}$

cc.complexity-theory complexity-classes quantum-computing space-bounded Artem Kaznatcheev
sumber

wah, sepertinya analog kuantum PSPACE sudah didefinisikan: BQPSPACE dan itu sama dengan PSPACE.

Artem Kaznatcheev

Anda mungkin ingin memeriksa "Kompleksitas kuantum terikat ruang", oleh John Watrous ( cs.uwaterloo.ca/~watrous/Papers/… )

Abel Molina

@ Bel, ini bisa menjadi jawaban.

Suresh Venkat

Untuk kelas ruang di atas ruang polinomial, kelas kuantum dan klasik adalah sama. Adapun ruang log kuantum, saya tidak bisa bicara banyak. Saya kira semua yang bisa kita katakan adalah .

L \subseteq B Q L \subseteq D S P A C E (\log^{2} n)

$L \subseteq BQL \subseteq DSPACE(\log^2 n)$

Robin Kothari

@ Suresh Tentu, saya menambahkan tautan sebagai jawaban, dan memasukkan bagian dari informasi dalam abstrak juga.

Abel Molina

Jawaban:

Anda mungkin ingin memeriksa Kompleksitas Quantum Berbatasan-Ruang , oleh John Watrous.

Di sana Anda mendapatkan hasil bahwa untuk , Mesin Quantum Turing yang berjalan di ruang dapat disimulasikan oleh Mesin Turing probabilistik dengan kesalahan tanpa batas yang berjalan di ruang . Anda juga memiliki Mesin Quantum Turing yang berjalan di ruang dapat disimulasikan dalam $s=\Omega(\log n)$ $s$ $O(s)$ $s$ $NC^2(2^s) \subseteq DSPACE(s^2) \cap DTIME(2^{O(s)})$

Abel Molina
sumber

Apakah maksud Anda

? Juga, apa

Ω (\log n)

$\Omega(\log n)$

N C^{2} (2^{s})

$NC^2(2^s)$

Robin Kothari

@Robin:

adalah kelas masalah yang dapat diselesaikan oleh keluarga seragam ruang-

dari sirkuit Boolean, dengan ukuran

, kedalaman

, dan fan-in yang terikat.

N C^{2} (2^{s})

$NC^2(2^s)$

s

$s$

2^{O (s)}

$2^{O(s)}$

O (s^{2})

$O(s^2)$

Alessandro Cosentino

@Robin Ya, maksud saya, ubah jawaban saya. Saya percaya bahwa definisi Alessandro untuk

benar.

N C^{2} (2^{s})

$NC^2(2^s)$

Abel Molina

Untuk batas ruang sublogaritmik, kuantum telah terbukti lebih kuat daripada klasik, lihat

Abuzer Yakaryılmaz, AC Cem Say, "Komputasi kuantum tanpa kesalahan dengan batas ruang kecil," Informasi dan Komputasi, Vol. 209, pp.873-892, 2011. (versi yang sedikit lebih tua di arXiv: 1007.3624 )

dan

Abuzer Yakaryılmaz, AC Cem Say, “Bahasa yang dikenali oleh quantum automata hingga nondeterministic,” Quantum Information and Computation, Vol. 10, hlm. 747-770, 2010. ( arXiv: 0902.2081 )

untuk kasus kesalahan tidak terbatas. Kertas

A. Ambainis dan J. Watrous. Automata terbatas dua arah dengan keadaan kuantum dan klasik. Theoretical Computer Science, 287 (1): 299–311, 2002, ( arXiv: cs / 9911009v1 )

bersama dengan fakta bahwa bahasa palindrome tidak dapat dikenali oleh mesin Turing probabilistik dengan ruang sublogaritmik, menunjukkan bahwa hal yang sama juga berlaku untuk kasus kesalahan yang dibatasi.

Cem Say
sumber