We show that a quantum algorithm, quantum search by measurement, can be performed even more efficiently when a priori information about a target is provided. In a searching problem, it is known that circuit-based quantum algorithms, Grover’s algorithm can achieve a quadratic speedup compared to classical algorithms. Furthermore, it has been shown that quantum search by adiabatic evolution or measurement can also yield similar results. If priori information about a target is available, it has been shown that Grover’s algorithm and quantum search by adiabatic evolution can reduce the running time based on the prior probabilities. In this thesis, we show that quantum search by measurement can also reduce the running time based on the prior probabilities and the reduced running time is the same with the one in the quantum search by adiabatic evolution with prior probabilities. On the other hand, in the quantum search by measurement, we show that by modifying the measurement, we can reduce the running time of the algorithm and the proposed method in the original paper can be explained by the extreme case of the modified method. From results, we suggest that we can adapt the proposed modification into the other problems that can be solved by measurement method.
우리는 대상에 대한 사전 정보가 주어졌을 때, 탐색을 위한 양자 측정 기반의 양자 알고리즘이 더욱 효율 적으로 수행될 수 있음을 보인다. 탐색 문제에서 회로 기반 양자 알고리즘인 Grover’s algorithm은 기존 알고리즘에 비해 Quadratic Speedup 을 달성할 수 있는 것으로 알려져 있다. 그리고 adiabatic evolution 과측정 기반 양자 탐색도 유사한 결과를 얻을 수 있음이 알려져있다. 대상에 대한 사전 정보가 주어진 경우, Grover’s algorithm 과 adiabatic evolution 에서 대상을 찾기 위한 컴퓨팅 실행 시간을 사전 정보에 대한 확률에 따라 줄일 수 있음이 알려져있다. 본 연구에서는 양자 측정을 통한 양자 탐색도 사전 확률에 기반한 실행 시간을 감소시킬 수 있음을 증명한다. 또한, 줄어든 실행 시간은 사전 확률을 고려한 adiabatic evolution과 동일한 결과임을 보인다. 한편으로, 양자 측정을 통한 양자 탐색에서는 측정 방식을 수정함으 로써 알고리즘의 실행 시간을 감소시킬 수 있음을 보여줍니다. 또한, 원래 논문에서 제안된 방법은 수정된 방법의 극단적인 경우로 설명할 수 있음을 보인다. 이러한 결과를 통해 제안된 수정 방법을 측정 기반으로 해결 가능한 다른 문제에 적용할 수 있음을 제안한다.
