양자 튜링 기계

3. 양자 튜링 기계 (QTM)

양자 튜링 기계(QTM)는 고전적인 튜링 기계를 양자 유한 오토마톤이 결정적 유한 오토마톤을 일반화하는 것과 같이 일반화한 것이다. 고전적 튜링 기계의 내부 상태는 힐베르트 공간의 순수 상태 또는 혼합 양자 상태로 대체되며, 전이 함수는 힐베르트 공간을 자신에게 매핑하는 일련의 유니타리 행렬로 대체된다.^[6]

이는 양자 튜링 기계의 형식적 정의라기보다는 개략적인 설명이며, 양자 측정이 얼마나 자주 수행되는지와 같은 몇몇 중요한 세부 사항들은 모호하게 남겨져 있다.

3. 1. 고전적 튜링 기계와의 비교

• 상태 집합 $Q$는 힐베르트 공간으로 대체된다.
• 테이프 알파벳 기호 $\backslash Gamma$ 역시 힐베르트 공간(일반적으로 상태 집합과는 다른 힐베르트 공간)으로 대체된다.
• 빈 기호 $b\; \backslash in\; \backslash Gamma$는 힐베르트 공간의 요소이다.
• 입력 및 출력 기호 $\backslash Sigma$는 일반적으로 고전적 시스템과 마찬가지로 이산 집합으로 간주된다. 따라서 양자 기계의 입력이나 출력은 양자 시스템 자체가 될 필요가 없다.
• 전이 함수 $\backslash delta\; :\; \backslash Sigma\; \backslash times\; Q\; \backslash otimes\; \backslash Gamma\; \backslash to\; \backslash Sigma\; \backslash times\; Q\; \backslash otimes\; \backslash Gamma\; \backslash times\; \backslash \{L,\; R\backslash \}$는 전이 모노이드의 일반화이며, 힐베르트 공간 $Q$의 자기 동형 사상인 일련의 유니타리 행렬로 이해된다.
• 초기 상태 $q\_0\; \backslash in\; Q$는 혼합 양자 상태 또는 순수 상태일 수 있다.
• '최종' 또는 '수용 상태' 집합 $F$는 힐베르트 공간 $Q$의 부분 공간이다.

3. 2. 양자 측정

4. 관련 연구 및 기술

폴 베니오프는 1980년과 1982년에 튜링 기계의 양자 역학적 모델을 설명하는 논문을 최초로 발표했다.^[4][5] 1985년 데이비드 도이치는 양자 게이트가 기존의 디지털 컴퓨팅 이진 논리 게이트와 유사하게 작동할 수 있다고 제안하며 양자 컴퓨터에 대한 아이디어를 더욱 발전시켰다.^[6]

이리야마, 오야, 볼로비치는 선형 양자 튜링 기계(LQTM) 모델을 개발했다. 이는 고전적인 QTM을 일반화한 것으로, 혼합 상태를 가지고 비가역적 전이 함수를 허용한다. 이를 통해 고전적 결과 없이 양자 측정을 표현할 수 있다.^[7]

스코트 아론슨은 사후 선택을 가진 양자 튜링 기계를 정의했으며, 이러한 기계에서 다항 시간 내에 계산 가능한 문제의 집합(PostBQP)이 고전적인 복잡도 클래스 PP와 같음을 보였다.^[8]

5. 같이 보기

• 양자 컴퓨터
• 튜링 기계
• 양자 유한 오토마톤

6. 참고 문헌

• 도이치의 논문 초록
• 양자 컴퓨터 – 역사

참조

_[1] 학회인용 Quantum circuit complexity
_[2] 학술지 Revisiting the simulation of quantum Turing machines by quantum circuits 2018
_[3] 학술지 One Complexity Theorist's View of Quantum Computing
_[4] 학술지 The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
_[5] 학술지 Quantum mechanical hamiltonian models of turing machines
_[6] 학술지 Quantum theory, the Church-Turing principle and the universal quantum computer http://www.ceid.upat[...] 1985-07
_[7] 학술지 Classically Controlled Quantum Computation 2007-04-04
_[8] 학술지 Quantum computing, postselection, and probabilistic polynomial-time
_[9] 저널 Quantum theory, the Church-Turing principle and the universal quantum computer http://www.ceid.upat[...] 2008-06-01
_[10] 서적 Quantum circuit complexity
_[11] 저널 One Complexity Theorist's View of Quantum Computing
_[12] 서적 Classically-Controlled Quantum Computation 2007-04-04
_[13] 저널 Quantum computing, postselection, and probabilistic polynomial-time