Quantum walk, a quantum version of random walk, has been studied as a useful tool for quantum algorithms. We study two applications of quantum walks. The first one is the quantum search algorithm. We examine quantum walk on a star graph. We find that it can reproduce the standard Grover search when there are two types of vertices. And we investigate the search with many different types of unmarked vertices and an equivalent oracle search problem with multivalued function. We find that the search can still be achieved in quadratic speedup, despite decreased probability and increased number of steps.
The other application is entanglement generation. We consider the quantum walk of two walkers on one-dimensional graphs. It was reported that two walkers with general two-dimensional coins become entangled when there is a simple interaction between them. We introduce a three-dimensional coin instead of a two-dimensional coin to enhance entanglement. A three-dimensional coin allows the walker to stay in addition to moving left and right, which provides a solution to the parity problem. By numerical simulation, we show that walkers with three-dimensional coins generate a larger amount of entanglement in a faster time than walkers with two-dimensional coins. The generated amount of entanglement on a cycle is over 85\% of the maximal entanglement; that is, walkers are highly entangled in a large spatial dimension.
양자 마구걷기는 양자 전산 분야에서 새로운 알고리듬을 개발하기 위한 방법 중 하나로 주목받아 많은 연구가 이루어지고 있다. 우리는 양자 마구걷기를 이용한 두 가지 응용 방법에 대하여 연구하였다. 첫 번째는 $N$개의 데이터가 한 개의 중심이 되는 데이터와 연결된 구조의 그래프에서의 검색 알고리듬을 연구하였다. 이 그래프에서의 검색 방법은 잘 알려진 Grover의 알고리듬을 그대로 재현해 낼 수 있음을 보였다. 더 나아가 여러 가지 값을 갖는 함수에 대한 검색 알고리듬으로 확장해도 고전적인 검색 알고리듬보다 제곱으로 빠른 속도로 구현될 수 있음을 보였다. 하지만 문제가 복잡해짐에 따라 검색에 필요한 시간이 증가하고 성공 확률이 낮아지는 것을 확인하였다.
또한 우리는 얽힘 상태 생성에 대해서도 연구하였다. 우선 여러 개의 원자들의 얽힘 상태를 생성하는 방법으로 광자 공진기에 갇힌 원자들을 한 개의 광자와 상호작용시키는 방법을 소개하였다. 양자 마구걷기를 이용한 얽힘 상태를 생성하는 방법으로는 Berry에 의해 제안된 방법이 있다. 그들은 두 개의 입자가 마구걷기를 하면서 같은 위치에 있을 때 위상변화를 갖게 됨으로써 두 입자 사이에 고차원적인 얽힘 상태가 생성이 되는 것을 보였다. 우리는 여기서 입자가 왼쪽 또는 오른쪽으로 움직이는 것뿐만 아니라 제자리에 멈춰있을 수 있는 가능성을 더하였을 때 더 좋은 얽힘 상태를 얻을 수 있다는 것을 제안하였다. 입자가 3가지의 자유도를 가질 때 주로 사용되는 DFT 연산과 Grover 연산을 이용하여 컴퓨터 시뮬레이션한 결과 더 많은 양의 얽힘 정도를 더 빠른 시간에 얻을 수 있다는 것을 확인하였다.
