우리는 종종 Turing 머신이 사용할 수있는 공간의 양에 한계가있는 복잡성 클래스를 고려합니다 (예 :
DSPACE(f(n))또는 . 복잡도 이론 초기에는 공간 계층 정리와 및 와 같은 중요한 클래스를 만드는 등의 클래스에서 많은 성공을 거둔 것으로 보입니다 . 양자 계산에 대한 유사한 정의가 있습니까? 또는 양자 유사체가 흥미롭지 않은 명백한 이유가 있습니까?L의 PSPACE
NSPACE(f(n))L
PSPACE
— 양자 버전의 과 같은 클래스를 갖는 것이 중요 할 것 같습니다 .L
QLL
답변
John Watrous의 Space-Bounded Quantum Complexity 를 확인하고 싶을 수도 있습니다 .
당신은 어떤을 위해, 그 결과가이 , 공간에서 실행되는 양자 튜링 기계 의는 억제 할 수없는 오류가 우주에서 실행하는 확률 적 튜링 기계에 의해 시뮬레이션 할 수 있습니다 O ( 들 ) . 또한 공간에서 실행되는 양자 튜링 기계가 있다고 들 에서 시뮬레이션 할 수 N C (2) ( 2 개 의 ) ⊆ D S P C E ( S 2 ) ∩ D T I M E (
에스=Ω(로그엔)에스
영형(에스)
에스
엔씨2(2에스)⊆디에스피ㅏ씨이자형(에스2)∩디티나는미디엄이자형(2영형(에스))
답변
비 로그 공간 경계의 경우, 양자가 고전보다 더 강력한 것으로 입증되었습니다.
Abuzer Yakaryılmaz, AC Cem Say,“작은 공간 한계를 갖는 무한 오류 양자 계산”, Information and Computation, Vol. 209, pp.873-892, 2011. ( arXiv의 약간 오래된 버전 : 1007.3624 )
과
Abuzer Yakaryılmaz, AC Cem Say, “비결정론 적 양자 유한 오토마타에 의해 인식되는 언어”, Quantum Information and Computation, Vol. 10, pp. 747-770, 2010. ( arXiv : 0902.2081 )
무한 오류의 경우. 종이
A. Ambainis와 J. Watrous. 양자 및 고전적 상태를 갖는 양방향 유한 오토마타. 이론적 컴퓨터 과학, 287 (1) : 299–311, 2002, ( arXiv : cs / 9911009v1 )
회문 공간이있는 확률 론적 튜링 기계는 회문 언어를 인식 할 수 없다는 사실 과 함께, 경계 오류의 경우에도 동일하게 적용됩니다.