교토대학 등의 연구그룹은 1양자비트밖에 사용할 수 없는 '약한' 양자컴퓨터에서도 고전컴퓨터보다 '강한' 것을 처음으로 이론적으로 증명했다.
양자 컴퓨터란, 마이크로의 세계를 설명하는 물리 이론 「양자 역학」에 근거해 동작하는 컴퓨터를 말한다.현재 우리가 사용하고 있는 「고전 컴퓨터」를 훨씬 능가하는 초고속 계산이 가능하다고 한다.
그러나, 대량의 양자 비트를 자유자재로 취급할 수 있는 거대한 만능 양자 컴퓨터의 실현은, 아직 먼 미래의 일.그래서 가까운 장래에 실현할 수 있는 수준의 '약한' 양자 컴퓨터에서도 고전 컴퓨터에 대한 우위성(양자 스프레마시)을 가지는 것을 보여주기 위한 연구가 활발히 이루어지고 있다.
예를 들어, "one-clean qubit 모델"은 1998년에 제안된 가장 오래된 "약한" 양자 계산 모델 중 하나이다. XNUMX 양자 비트 밖에 사용할 수 없고, 약하게 보이는 한편, Jones 다항식의 계산 등, 고전 컴퓨터로 효율적으로 계산하는 방법이 알려지지 않은 양을 효율적으로 계산할 수 있는 것이 나타나고 있다.그러나, Jones 다항식을 계산하는 효율적인 고전 알고리즘이 발견되면, one-clean qubit 모델의 고전에 대한 우위성은 없어지기 때문에, 확실한 양자 스프레마시라고는 할 수 없다.
이러한 가운데, 연구 그룹은 새로운 수법을 이용해 one-clean qubit 모델의 우위성의 이론적 증명에 처음으로 성공.게다가 이번에 발견한 수법은 다른 타입의 약한 양자 계산 모델에도 응용 가능하고, 이들 모델에 대해서도 종래보다 견고한 계산량 이론적 기반으로 양자 스프레마시를 증명하는 데 성공했다.
본 성과는 전세계에서 진행되는 양자 스프레마시 연구의 이론적 기반을 정비하는 것으로, 향후 양자 계산 연구의 발전에 크게 기여할 것으로 기대되고 있다.
