양자 컴퓨터는 양자 역학에 따라 작동하는 완전히 새로운 유형의 컴퓨터입니다.우리가 현재 사용하고 있는 컴퓨터(고전 컴퓨터)를 훨씬 능가하는 계산 성능을 가진다고 믿어지고, 그 실현에 큰 기대가 전해지고 있다.

　그 중에서도, 어떠한 양자 알고리즘으로도 달릴 수 있는 범용 양자 컴퓨터의 개발은 하나의 궁극의 골로 되어, 전세계에서 많은 연구자가 임하고 있다.그러나, 대량의 양자 비트를 취급할 수 있는 범용 양자 컴퓨터의 실현은 아직 어렵고, 최근에는 범용이 아니고, 특정의 문제에 대해서 뛰어난 계산을 가능하게 하는 비범용의 양자 컴퓨터 개발에 주목이 모이고 있다 .

　비범용 양자 컴퓨터의 예로서 가장 오래된 것에는 one-clean-qubit 모델이 있다. one-clean-qubit 모델은 임의의 양자 계산을 할 수 없지만, 매듭 불변량의 계산 등 특정의 문제에 한해서는, 현재의 고전의 베스트의 알고리즘보다 고속으로 풀 수 있다.이 사실은 one-clean-qubit 모델이 고전 컴퓨터보다 강력하다는 것을 시사하지만, 그 증명은 지금까지 이루어지지 않았다.

　본 연구에서는 이 one-clean-qubit 모델이 고전 컴퓨터보다 빠르다는 것을 계산량 이론에 기초하여 처음으로 이론적으로 증명하였다.이에 따라 복잡한 범용 양자 컴퓨터를 만들지 않아도 가까운 장래에 실현할 수 있는 기술로 양자 컴퓨터의 고전 컴퓨터에 대한 우위성을 실연할 수 있게 될 것으로 기대되고 있다.

논문 정보:【Physical Review A Rapid Communications】Hardness of classically sampling one clean qubit model with constant total variation distance error