Quantum circuit of n.n. G(A,B) gates and its classical simulation

Abstract

계산 복잡성은 계산문제를 풀기위해서 필요한 시간과 공간에 대해 연구한다. 고전 컴퓨터에서 효율적으로 풀리지 않는 많은 문제들이 있다. 따라서 우리는 순수한 계산에서 양자 계산법이 고전 계산법보다 강력하길 기대한다. 그러나 현재까지 BPP=BQP 인지는 알려지지 않았다. 이런 관점에서 우리는 양자 계산법과 고전 계산법이 같아지는 특별한 상황을 관찰할것이다. 더 나아가 무엇이 둘 사이의 차이를 가져올수 있는지를 확인할것이다.

Computational complexity is the study of the time and space resources required to solve computational problems. In classical computation there are many problems which are not efficiently solved. So we expect that quantum computation is more powerful than classical computation for pure computation. However, it is not known so far whether BPP=BQP. This implies that it is still possible that efficient classical and quantum computational power might be equal. In this sense we will investigate a special situation in which quantum and classical computational power are equal. Furthermore, in this circumstance we will observe what makes the differences between the two parts if it exists.