양자 튜링 기계는 양자역학의 원리를 적용한 이론적 계산 모델로, 전통적인 튜링 기계의 양자 버전이라고 할 수 있다. 이는 1985년 물리학자 데이비드 도이치(David Deutsch)가 제안한 Quantum Turing Machine(QTM) 개념을 한국어로 번역한 것으로, 양자 컴퓨팅 이론의 기초적 프레임워크 중 하나이다.
정의 및 구조
- 기본 구성: 고전 튜링 기계와 동일하게 무한히 긴 테이프, 헤드, 상태 레지스터 등을 갖는다. 그러나 각 요소는 양자 비트(큐비트)로 표현되며, 시스템 전체는 복소수 계수의 선형 결합(양자 상태)으로 기술된다.
- 연산 규칙: 상태 전이 함수가 유니터리 연산으로 정의되어, 시스템의 진화가 양자역학의 선형성 및 보존법칙을 만족한다. 이것은 고전 튜링 기계의 결정론적 전이와 달리, 중첩과 얽힘을 활용한 비결정적 연산을 가능하게 한다.
- 측정: 계산이 완료된 후에 테이프와 헤드의 양자 상태를 측정함으로써 고전적인 출력 값을 얻는다. 측정 과정은 확률적이며, 측정 결과에 따라 여러 가능한 출력 중 하나가 선택된다.
주요 특징
- 보편성: 양자 튜링 기계는 모든 양자 알고리즘을 형식화할 수 있는 보편적 모델이다. 이는 양자 회로 모델과 계산 능력 면에서 동등함이 증명되었다.
- 복잡도 이론: 양자 튜링 기계 기반의 복잡도 클래스인 BQP(Bounded‑Error Quantum Polynomial time)는 고전적인 클래스 P와 NP 사이의 관계를 탐구하는 데 사용된다.
- 이론적 의의: 양자 튜링 기계는 양자 컴퓨터가 실제 물리적 구현 여부와 무관하게 이론적 한계를 분석하는 도구로 활용된다. 특히 양자 알고리즘의 최적성 및 양자 오류 정정 이론 연구에 기여한다.
역사적 배경
- 제안 시점: 1985년, 데이비드 도이치가 “Quantum theory, the Church‑Turing thesis and the universal quantum computer” 논문에서 최초로 제시하였다.
- 후속 연구: 이후 에드워드 피트스(Edward F. P. Feynman), 피터 숀(Peter Shor) 등 여러 학자가 양자 튜링 기계의 형식적 정의와 계산 능력에 대한 연구를 진행하였다.
실제 적용 및 한계
- 현재 양자 튜링 기계 자체가 물리적으로 구현된 사례는 없으며, 실제 양자 컴퓨터는 주로 양자 회로 모델(양자 게이트)로 설계된다.
- 양자 튜링 기계는 주로 이론적 분석, 복잡도 구분, 알고리즘 설계 원리 설명 등에 이용된다.
어원 및 사용 맥락
- 양자(Quantum): 물리학에서 에너지와 물질이 불연속적인 최소 단위로 존재한다는 개념.
- 튜링(Turing): 영국의 수학자 앨런 튜링(Alan Turing)으로, 튜링 기계는 현대 컴퓨터 과학의 기초 모델.
- 기계(Machine): 자동화된 계산 장치를 의미한다.
따라서 “양자 튜링 기계”라는 용어는 양자와 튜링 기계를 결합한 표현으로, 양자 컴퓨팅 이론 분야에서 공식적인 학술 용어로 사용된다.
