양자 튜링 기계

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

양자 튜링 기계(quantum Turing machine, QTM)는 양자 컴퓨터의 효과를 모델링 하기 위한 추상적 기계이다. 이 모델은 양자 전산의 특징을 잡아내는 간단한 모형을 제시하며, 어떤 양자 알고리즘도 양자 튜링 기계의 연산으로 표현할 수 있다. 이 튜링 기계 는 1985년 옥스포드대학교의 물리학자 데이비드 도이치양자 게이트가 통상적인 이진 시스템의 논리 게이트와 비슷한 방식으로 동작할 수 있다는 사실을 지적한 논문에서 처음 제시되었다.[1]

양자 튜링 기계 모델만이 양자 전산만을 분석하는 데 쓰이지는 않는다. 양자 회로가 양자 전산을 모사하는 데 더 많이 쓰이고 있으나, 두 모델은 동등하다는 것이 알려져 있다.[2]

Lance Fortnow 에 의하면, 양자 튜링 기계는 전이 행렬을 이용해 고전적이고 확률적인 튜링 기계를 대응 시킨 것에 해당한다.[3]

Iriyama, Ohya, Volovich 는 기존 양자 튜링 기계를 일반화한 선형 양자 튜링 기계 모델을 개발했는데, 이는 일반 양자 튜링기계에 mixed state 를 사용할 수 있게 하여, 비가역적인 전이 함수를 대응시킬 수 있게 했고, 이를 통해 고전적인 결과를 얻지 않으면서 양자 측정을 행할 수 있게 했다.[4]

Scott Aaronsonpostselection 의 개념이 들어간 양자 튜링 기계를 정의했는데, 이 기계에서 다항함수 수준의 복잡도를 가진 연산(PostBQP)은 고전적인 복잡도 연산(PP)에 대응한다는 것을 보였다.[5]

각주[편집]

  1. Deutsch, David (July 1985). “Quantum theory, the Church-Turing principle and the universal quantum computer” (PDF). 《Proceedings of the Royal Society of London; Series A, Mathematical and Physical Sciences》 400 (1818): pp. 97–117. Bibcode:1985RSPSA.400...97D. doi:10.1098/rspa.1985.0070. 2008년 11월 23일에 원본 문서 (PDF)에서 보존된 문서. 2008년 6월 1일에 확인함. 
  2. Andrew Yao (1993). 《Quantum circuit complexity》. 352–361쪽. 
  3. Lance Fortnow (2003). “One Complexity Theorist's View of Quantum Computing”. 《Theoretical Computer Science》 292: 597–610. doi:10.1016/S0304-3975(01)00377-2. 
  4. Simon Perdrix; Philippe Jorrand (2007년 4월 4일). 《Classically-Controlled Quantum Computation》. 87쪽. arXiv:quant-ph/0407008 [quant-ph].  also Simon Perdrix and Philippe Jorrand (2006). “Classically-Controlled Quantum Computation” (PDF). 《Math. Struct. In Comp. Science》 16: 601–620. doi:10.1017/S096012950600538X. 
  5. Aaronson, Scott (2005). “Quantum computing, postselection, and probabilistic polynomial-time”. 《Proceedings of the Royal Society A》 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546.  Preprint available at [1]

더 읽기[편집]