양자 튜링 기계

튜링 기계
기계.
튜링 기계 등가물 튜링 기계 예시 튜링 기계 갤러리
변종
교대 튜링 기계 신경 튜링 기계 비결정론적 튜링 기계 양자 튜링 기계 포스트튜어링 머신 확률론적 튜링 기계 멀티테이프 튜링 머신 멀티트랙 튜링 머신 대칭 튜링 기계 토탈 튜링 머신 명확한 튜링 기계 범용 튜링 기계 제노 기계
과학
앨런 튜링 카테고리:튜링 기계
v t

양자 튜링 기계(QTM) 또는 범용 양자 컴퓨터는 양자 컴퓨터의 효과를 모델링하는 데 사용되는 추상 기계입니다.이것은 양자 계산의 모든 힘을 포착하는 단순한 모델을 제공한다. 즉, 양자 알고리즘은 특정 양자 튜링 기계로서 공식적으로 표현될 수 있다.그러나 계산상 등가 양자회로가 더 일반적인 ^{[1][2]: 2} 모델이다.

양자 튜링 기계는 전이 행렬에 기초한 프레임워크에서 고전적이고 확률적인 튜링 기계와 관련될 수 있다.즉, 매트릭스는 고전적 또는 확률적 기계를 나타내는 매트릭스를 가진 제품이 양자 기계를 나타내는 양자 확률 매트릭스를 제공하는지 지정할 수 있다.이것은 랜스 포트노우에 ^[3]의해 보여졌다.

비공식 스케치

양자튜링기계(QTM)를 이해하는 방법은 양자유한오토마톤(QFA)이 결정론적 유한오토마톤(DFA)을 일반화하는 것과 같은 방법으로 고전적인 튜링기계(TM)를 일반화하는 것이다.본질적으로, 고전적인 TM의 내부 상태는 힐베르트 공간의 순수 또는 혼합 상태로 대체되며, 전이 함수는 힐베르트 공간을 자신에게 ^[4]매핑하는 단일 행렬의 모음으로 대체됩니다.

즉, 고전적인 튜링 머신은 7 $태플{\displaystyle }$ M${\displaystyle =}$ ${\displaystyle q}$ Q${\displaystyle }$、${\displaystyle \gamma }$ 、 b${\displaystyle 、}$ ${\displaystyle \mathrm{0}}$ 、${\displaystyle {0\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$、 ${\$ { $display$ M = \ $langle$ Q 、 \ $Gamma$ , b 、 \ Sigma$、$、$$$q$ { 0 , F $}$로 기술됩니다.

3테이프 양자 튜링 머신(입력 유지 테이프 1개, 중간 계산 결과 유지 테이프 2개, 출력 유지 테이프 3개)의 경우:

• $상태{\displaystyle }$ 집합$$Q(\$displaystyle$ Q$)$는 Hilbert 공백으로 대체됩니다.
• 테이프 알파벳 기호$\gamma {\displaystyle \mathrm{}}$(\$style \Gamma)$도 마찬가지로 힐베르트 공간(보통 상태 집합과는 다른 힐베르트 공간)으로 대체됩니다.
• ${\displaystyle \mathrm{공백}}$ $기호{\displaystyle }$ b $∈$ space element \ $displaystyle$ b$\in$\ Gamma$$}
• 입력 및 출력 기호$\delta {\displaystyle \mathrm{}}$(\$displaystyle \Sigma)$는 일반적으로 기존 시스템과 마찬가지로 이산 집합으로 간주되므로 양자 기계에 대한 입력 및 출력은 양자 시스템 자체일 필요가 없습니다.
• $전이함수{\displaystyle }$ ${\displaystyle :}$ :${\displaystyle \mathrm{\sigma }}$ × ${\displaystyle Q}$ ${\displaystyle \otimes }$ → ${\displaystyle \to }$ → → → ${\displaystyle \to }$ $γ$ × {${\displaystyle }$L , ${\displaystyle R}$ $}$ { $displaystyle \Sigma \times$ Q $\otimes \Gamma \to \Sigma \times$Q \$otimes \Gamma$\times \$tes$ \{$L$ }$$}는$$ $A$의 일반화이다.
• 초기 $상태{\displaystyle {}_{}}$ ${\displaystyle {q\mathrm{}}_{}}$ 0$(\displaystyle q_{0}\in$ Q$)$는 혼합 상태 또는 순수 상태 중 하나입니다.
• 최종 상태 또는 수용 상태의 집합$$F(\$displaystyle$ F$)$는 힐베르트 $공간{\displaystyle }$Q(\$displaystyle$ Q$)$의 부분 공간입니다.

위는 양자 튜링 기계의 공식적인 정의라기 보다는 단지 양자 튜링 기계의 스케치일 뿐이다. 예를 들어, 얼마나 자주 측정이 수행되는지, 예를 들어, 측정 한 번과 측정 다수의 QFA의 차이를 참조한다.이 측정 문제는 출력 테이프에 대한 쓰기의 정의 방법에 영향을 미칩니다.

역사

1980년과 1982년, 물리학자 폴 베니오프는 튜링 기계의 양자역학 모델을 최초로 설명한 논문을 발표했다^[5][6].옥스퍼드 대학의 물리학자 데이비드 도이치가 1985년에 쓴 논문은 양자 게이트가 전통적인 디지털 컴퓨팅 이진 논리 ^[4]게이트와 유사한 방식으로 기능할 수 있다는 것을 제안함으로써 양자 컴퓨터의 아이디어를 더욱 발전시켰다.

이리야마, 오야, 볼로비치는 LQTM(Linear Quantum Turing Machine) 모델을 개발했는데, 이는 혼합 상태를 가지며 불가역적인 전이 함수를 가능하게 하는 고전적인 QTM의 일반화이다.이를 통해 고전적인 ^[7]결과 없이 양자 측정을 표현할 수 있습니다.

후선택이 있는 양자 튜링 기계는 스콧 아론슨에 의해 정의되었으며, 그는 그러한 기계의 다항식 시간 클래스가 고전적인 복잡도 클래스 ^[8]PP와 같다는 것을 보여주었다.

「 」를 참조해 주세요.

• 양자 시뮬레이터 ① 물리 문제 해결

레퍼런스

추가 정보

• Molina, Abel; Watrous, John (2018). "Revisiting the simulation of quantum Turing machines by quantum circuits". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 475 (2226). arXiv:1808.01701. doi:10.1098/rspa.2018.0767. PMC 6598068. PMID 31293355.
• Iriyama, Satoshi; Ohya, Masanori; Volovich, Igor (2004). "Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm". arXiv:quant-ph/0405191.
• Deutsch, D. (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 400 (1818): 97–117. Bibcode:1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382. doi:10.1098/rspa.1985.0070. JSTOR 2397601. S2CID 1438116.

외부 링크

• 양자 컴퓨터 – 역사