|
양자 튜링 기계양자 튜링 기계(Quantum Turing machine, QTM)는 양자 컴퓨터의 효과를 모델링 하기 위한 추상적 기계이다. 이 모델은 양자 전산의 특징을 잡아내는 간단한 모형을 제시하며, 어떤 양자 알고리즘도 양자 튜링 기계의 연산으로 표현할 수 있다. 이 튜링 기계는 1985년 옥스퍼드 대학교의 물리학자 데이비드 도이치가 양자 게이트가 통상적인 이진 시스템의 논리 게이트와 비슷한 방식으로 동작할 수 있다는 사실을 지적한 논문에서 처음 제시되었다.[1] 양자 튜링 기계 모델만이 양자 전산만을 분석하는 데 쓰이지는 않는다. 양자 회로가 양자 전산을 모사하는 데 더 많이 쓰이고 있으나, 두 모델은 동등하다는 것이 알려져 있다.[2] Lance Fortnow에 의하면, 양자 튜링 기계는 전이 행렬을 이용해 고전적이고 확률적인 튜링 기계를 대응 시킨 것에 해당한다.[3] Iriyama, Ohya, Volovich는 기존 양자 튜링 기계를 일반화한 선형 양자 튜링 기계 모델을 개발했는데, 이는 일반 양자 튜링기계에 mixed state를 사용할 수 있게 하여, 비가역적인 전이 함수를 대응시킬 수 있게 했고, 이를 통해 고전적인 결과를 얻지 않으면서 양자 측정을 행할 수 있게 했다.[4] Scott Aaronson은 postselection의 개념이 들어간 양자 튜링 기계를 정의했는데, 이 기계에서 다항함수 수준의 복잡도를 가진 연산(PostBQP)은 고전적인 복잡도 연산(PP)에 대응한다는 것을 보였다.[5] 각주
추가 문헌 |
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
