양자 보행 탐색

양자 컴퓨팅의 맥락에서 양자 보행 검색은 그래프에서 표시된 노드를 찾기 위한 양자 알고리즘입니다.^[1]

양자 보행의 개념은 보행기가 그래프나 격자를 통해 무작위로 움직이는 고전적인 무작위 보행에서 영감을 받았습니다. 고전적인 무작위 보행에서 보행기의 위치는 그래프의 여러 노드에 대한 확률 분포를 사용하여 설명할 수 있습니다. 반면에 양자 보행에서 보행기는 양자 상태로 표현되며, 이는 동시에 여러 위치의 중첩 상태에 있을 수 있습니다.^[1]

양자 보행에 기반한 검색 알고리즘은 최적화, 기계 학습, 암호학, 네트워크 분석 등 다양한 분야에서 응용 프로그램을 찾을 수 있는 잠재력을 가지고 있습니다.^[2] 양자 보행 탐색의 효율성과 성공 확률은 탐색 공간의 구조에 크게 좌우됩니다. 일반적으로 양자 보행 탐색 알고리즘은 Grover의 알고리즘과 유사한 점근적 2차 속도 향상을 제공합니다.^[3]^[4]

양자 보행을 검색 문제에 적용하는 첫 번째 작업 중 하나는 닐 셴비, 줄리아 켐페 및 K에 의해 제안되었습니다. 버기타 웨일리.^[5]

고전적인 문제 설명

표시된 요소를 포함하는 검색 공간 $X$ ${\displaystyle$ X $}$ 및 부분 $M\subseteq X$ M $M\subseteq X$ ⊆ X ${\displaystyle$ M $\subseteq$ X}가 주어지면 확률적 검색 알고리즘은 M ${\$ displaystyle M}에서 $M$ 된요소를 찾을 때까지 $x\in X$ 각 단계에서 $x$ ∈ $X {\displaystyle$ x\in X}를 무작위로 균일하게 샘플링합니다. ϵ = $\epsilon =|M|/|N|$ / N {\ $displaystyle$ \epsilon = M / N}을 표시된 요소의 비율로 정의하면 해당 종류의 절차를 O(1 / ϵ) {\displaystyle O(1/\epsilon)}번 반복하여 표시된 요소를 찾아야 합니다.

If we have information about the structure of $X$ we can model it as a graph $G(V,E)$ , where every vertex $V=\{v_{1},\dots ,v_{n}\}$ represents a sample from the search space with $X =n$ , 가장자리는 현재 표본에서 시작하는 다음 요소를 표본으로 추출할 조건부 확률을 나타냅니다.^[6]

임의의 정점 $v_{2}$ 1 ${\$ 에서 시작하여 검색을 수행하고 $v_{1}$ $M$ ${\displaystyle$ M $}$ 에 속하지 않으면 $M$ $v_{1}$ $v_{1}$ ${\$ 에 연결된 정점 v $v_{2}$ ${\$ 를 $v_{{2}}$ 샘플링합니다 $v_{1}$ 이 절차를 랜덤 워크 검색이라고 합니다. 표시된 노드를 찾을 $1$ 이 1 ${\displaystyle$ 1 $}$ 에 가깝도록 하려면 그래프에서 점근적으로 O $($ / $O(1/\epsilon \delta )$ ϵ δ) {\ $displaystyle$ O( $1/\epsilon$ \delta)} 단계를 수행해야 합니다. 여기서 $\delta$ 변수 δ ${\displaystyle$ \delta}는 그래프의 $확률$ $행렬$ P ${\displaystyle$ P}와 관련된 스펙트럼 갭입니다.

랜덤 워크 알고리즘의 계산 비용을 평가하기 위해 일반적으로 절차를 설정, 확인, 업데이트의 세 가지 하위 단계로 나누어 비용을 분석합니다.^[6]

세우다

설정 비용 $S$ $S$ 은 그래프의 정점에 대한 정지 분포의 초기화를 의미합니다 $S$ .^[6]

갱신하다

업데이트 비용 $U$ $U$ 는 $u$ $P$ $P$ 에 정의된 전이 확률에 따라 그래프의 전이를 시뮬레이션하기 위한 비용입니다 $P$ ^[6]

확인.

체크 비용 $C$ $C$ 는 $c$ 현재 요소가 집합 $M {\displaystyle$ M $}$ 에 속하는지 확인하기 위한 비용입니다 $M$

랜덤 워크 검색 알고리즘의 총 비용은 $S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}$ + $S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}$ ϵ $S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}$ δ U + C) ${\displaystyle$ S+{\ $frac {$ 1}{\ $epsilon}}{\biggl(}{\frac {1$ }{\ $delta$ U+C{\biggr )}}입니다. 그래프의 모든 단계 후에 검사가 수행되는 그리디 버전의 알고리즘은 S $S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}$ + 1 $S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}$ ϵ δ( $S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}$ + $S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}$ ) {\displaystyle S $+{\$ frac {1 $}{\$ epsilon \delta }}{\biggl(}U+C{\biggr )}}의 복잡도를 가집니다. 비용 공식에서 스펙트럼 갭 항 $\delta$ δ {\displaystyle $\delta$ \delta }의 존재는 보행기가 정지 분포에 도달하기 위해 수행해야 하는 최소 단계 수로 생각할 수 있습니다. 이 수량은 혼합 시간이라고도 합니다.^[8]

알고리즘설명

양자 보행 탐색 알고리즘은 MNRS 알고리즘으로도 알려진 Magniez et al.^[7] 에 의해 처음 제안되었으며 Mario Szegedy 가 제안한 양자 보행 공식을 기반으로 합니다. 그래프의 방향 에지에 대해 워크를 수행하여 검색 공간과 관련된 양자 상태를 나타내기 위해 $vi {\$ $v_{j}$ v_{i}에서 $vj$ v_{j $}$ 까지의 $v_{i}$ 에 해당하는 두 개의 양자 $레지스터 i$ ⟩ ⟩ {\ $displaystyle$ i $|i\rangle |j\rangle$ rangle }가 필요합니다. 알고리즘이 어떻게 작동하는지 쉽게 이해할 수 있도록 기하학적 해석을 통해 알고리즘을 설명할 수 있습니다. $저희$ 는 $|p_{i}\rangle =\sum _{j}{\sqrt {P_{ij}}}|j\rangle$ $|p_{i}\rangle =\sum _{j}{\sqrt {P_{ij}}}|j\rangle$ ⟩ {\ $displaystyle$ $p_{i}\rangle$ =\ $sum$ _{ $j}{\$ sqrt {P_{ij}} j\rangle }를 i ⟩ {\displaystyle i\rangle $|i\rangle$ }의 이웃에 대한 균일한 $중첩$ 으로 정의합니다. 저희는 $|i\rangle$ 된 상태와 표시되지 않은 상태에 대한 중첩을 추가로 정의합니다. 종종 좋은 상태와 나쁜 상태로 일컬어지는 것, 즉

$G\rangle ={\frac {1}{\sqrt { M }}}\sum _{i\in M} i\rangle p_{i}\rangle$ and ${\displaystyle B\rangle ={\frac {1}{\sqrt {X- M }}}\sum _{i\n$ $ot \in M} i\rangle p_{i}\rangle }$

여기서 $M$ ${\displaystyle$ M $}$ 은 $M$ 표시된 요소 집합입니다. 모든 간선 $U$ $U$ 에 대한 균일한 중첩은 좋은 상태와 나쁜 상태의 조합으로 볼 수 있습니다 $U$ .

$U\rangle ={\frac {1}{\sqrt {X}}}\sum _{i\in X} i\rangle p_{i}\rangle =\sin(\theta ) G\rangle +\cos(\theta ) B\rangle$ with $\theta =\arcsin({\sqrt {\epsilon }})$ .^[9]

알고리즘은 다음 단계로 구성됩니다.

$U$ ⟩ {\ $displaystyle U$ rangle}을 사용하여 양자 상태를 초기화합니다. 일반적으로 어떤 상태 준비 루틴에 의해 수행됩니다.
$O(1/{\sqrt {\epsilon }})$ / $O(1/{\sqrt {\epsilon }})$ ϵ) {\displaystyle $O$ (1 $/{\sqrt {\$ epsilon $O(1/{\sqrt {\epsilon }})$ 에 대해 반복합니다.
- $B$ ⟩ {\ $displaystyle B\$ rangle}을(를) 통해 반사를 수행합니다.
- $U$ ⟩ {\ $displaystyle U\$ rangle}을(를) 통해 반사를 수행합니다.
1차 퀀텀 레지스터 측정 후 표시 여부 확인

알고리즘이 표시된 요소를 찾는 방법은 진폭 증폭 기술을 기반으로 ^[10]하므로 정확성의 증명은 Grover의 알고리즘과 유사합니다(완전 연결된 그래프에서 양자 보행의 특수한 경우로도 볼 수 있음). $U$ ⟩ {\ $displaystyle U\$ $}$ 과 B ⟩ ${\displaystyle$ B\rangle }을 통한 두 반사는 양자 상태를 양호한 상태로 이동시키는 효과가 있습니다. after $k$ applications of the reflections the state can be written as $\sin((2k+1)\theta ) G\rangle +\cos((2k+1)\theta ) B\rangle$ and by setting ${\displaystyle k\thickapprox {\frac {\pi$ $}{4\theta$ }} $=O(1/{\sqrt {\epsilon }}}$ $\sin((2k+1)\theta )\thickapprox 1$ 는 높은 확률로 좋은 상태를 산출하는 sin $⁡$ $\sin((2k+1)\theta )\thickapprox 1$ + $\sin((2k+1)\theta )\thickapprox 1$ 1 $θ$ $)$ $≈$ 1 ${\displaystyle$ \sin(((2k + 1))\theta )\ $thick$ 근사 1}을 가지고 있습니다.

1차반사

첫 번째 반사는 현재 정점이 표시되어 있는지 확인하고, 표시되어 $-1$ 있으면 $-1$ $-1$ 과 동일한 위상 이동을 적용하는 효과가 있습니다. 이는 진폭 증폭을 기반으로 하는 많은 양자 알고리듬에서 일반적인 절차이며 $|i\rangle \in M$ $|i\rangle \in M$ ⟩ ∈ M ${\displaystyle i\rangle$ \in $|i\rangle \in M$ M}을 검증하는 양자 오라클 기능을 통해 실현할 수 있습니다.

두번째 반사

두 번째 반사는 탐색 중인 그래프의 구조를 반영해야 하는 보행 $W$ 연산자 $W$ $W$ 에 대한 양자 위상 추정으로 구현됩니다. The walk operator can be defined as $W=ref({\mathcal {B}})ref({\mathcal {A}})$ where $ref({\mathcal {B}})$ and $ref({\mathcal {A}})$ are two reflections through the subspaces ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ $pi$ ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ ⟩ } ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ ${\displaystyle {\$ mathca ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ {A}} $=span\{i\$ rangle, p_{ $i}\$ rangle \ ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ 및 B =spa ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ {pj ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ , j ⟩ } {\displaystyle {\mathc ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ l {B}=span\{p_{j}\rangle, j\rangle \}}. Since the eigenvalues of $W$ are on the form $e^{\pm 2i\theta }$ and the operator has a unique eigenvalue equal to $1$ corresponding to $U\rangle$ given by $\theta =0$ , 정밀도 $O(1/{\sqrt {\delta }})$ ( $O(1/{\sqrt {\delta }})$ / $O(1/{\sqrt {\delta }})$ δ $O(1/{\sqrt {\delta }})$ ${\displaystyle O$ (1 / {\ $sqrt {\$ delta }})}로 위상 추정을 수행하여 고유 고유 고유 값을 찾을 수 있습니다. 반사의 정밀도는 위상을 추정하는 데 사용되는 큐비트 수에 따라 달라집니다.^[9]

복잡성

고전적 랜덤 워크 알고리즘의 비용을 추정하는 데 사용되는 것과 동일한 형식론을 사용하여 양자 비용은 다음과 같이 요약할 수 있습니다.

S: $중첩$ U ⟩ {\ $displaystyle U\$ rangle}을(를) 초기화하기 위한 비용입니다.
U: 비용은 그래프에서 중첩(즉, $U$ ⟩ {\ $displaystyle U\$ rangle}을 통한 반사) 단계를 수행합니다.
C: 양자 오라클을 구현하기 위한 비용, 즉 $B$ ⟩을 통한 반사 {\ $displaystyle$ B $\$ rangle}

$S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}$ 워크 검색의 총 비용은 S $S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}$ + 1 $S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}$ ϵ $S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}$ δ U + C) ${\displaystyle S+{\$ frac { $1}{\$ sqrt {\ $epsilon}}}{\biggl(}{\frac$ {1 $}{\sqrt$ {\ $delta$ U+C{\biggr)}}이며, 이는 고전 버전에 비해 2차 속도 상승을 초래합니다. Grover의 알고리즘에 비해 양자 보행은 각 양자 상태와 관련된 대규모 데이터 구조가 있는 경우 유리해집니다. 첫 번째 경우에는 각 반복마다 완전히 재구성되는 반면 보행에서는 각 단계에서 부분적으로만 업데이트되기 때문입니다.^[11]

하이퍼큐브 예제

이것은 하이퍼큐브 그래프에서 양자 보행 탐색을 적용하는 방법의 예입니다.^[12]

원래 설명에서 Szegedy 퀀텀 워크가 사용되지만, 이 예에서 우리는 이해하기가 더 직관적이기 때문에 조어된 퀀텀 워크의 사용을 보여줍니다. 어쨌든, 두 형식화는 특정 가정 하에서 동등한 것으로 밝혀졌습니다.^[13]

검색 공간은 $n=4$ = 4 ${\$ $displaystyle$ n=4}인 {\displaystyle $n}$ - hypercube이며 V = 24 {\displaystyle V = 2^{4}} 정점을 가지며 차수는 4 {\displaystyle 4}입니다. 각 노드 $v_{i}$ ${\$ 는 4 ${\displaystyle$ 4 $}$ 의 $4$ 이진 문자열로 레이블을 지정할 $v_{i}$ 수 있으며 두 노드는 $해밍$ 거리가 $1$ {\ $displaystyle$ 1 $}$ 인 경우 에지로 연결됩니다 $1$ 양자 보행 검색을 설정하려면 보행기가 선택할 수 있는 모든 방향을 인코딩하는 ${\mathcal {H}}^{n}$ 차원 ${\mathcal {H}}^{n}$ ${\mathcal {H}}^{n}$ ${\$ 의 코인 레지스터와 정점을 나타내는 ${\mathcal {H}}^{2^{n}}$ 차원 H ${\mathcal {H}}^{2^{n}}$ ${\mathcal {H}}^{2^{n}}$ ${\$ 의 정점 레지스터가 필요합니다.^[12]

$|d\rangle |v\rangle$ 기준은 { $\{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}$ ∈ $|d\rangle |v\rangle$ $\{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}$ = { $00$ , 01, 10, 11}, v ∈ V = {00, 0001, …, 1111 } {\displaystyle \in D =\{00, 01, 10 $,$ 11\}, v\in V =\{00, 0001, \dots $\{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}$ $\{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}$ 입니다.

보행은 다음 두 가지 조작자에 의해 수행됩니다.

코인 연산자 $C$ $C$ 을 $C$ (를) 사용하여 가능한 방향에 대한 중첩을 만듭니다.
Shift 연산자 $S$ $S$ 은 $S$ (는) 한 방향에 따라 그래프의 한 단계를 밟는 데 사용됩니다.

따라서 워크 연산자는 $W=SC$ = ${\$ displaystyle W = SC}입니다.

하이퍼큐브 그래프의 경우, 우리는 효율적인 시프트 연산자를 구성하기 위해 인접한 노드의 두 개에 대해 정점의 이진 인코딩이 한 비트만 다르다는 사실을 활용할 수 있습니다. 시프트 연산자는 다음과 같이 쓸 수 있습니다.

$S=\sum _{d=1}^{n}\sum _{v=1}^{n} d\rangle v\opplus e_{d}\rangle \langle v$

$e_{d}$ 서 $e_{d}$ 는 $d$ 의 d ${\displaystyle$ d $}$ - basis입니다( $n=4$ = $4$ {\displaystyle n= 4}인 경우 기본값은 {0001, 0010, 0100, 1000} {\displaystyle \{0001, 0010, 0100, 1000\}입니다). 그로버 동전이나 푸리에 동전과 같은 여러 가지 선택 사항이 있는 동전의 경우, 모든 방향에 대해 동일한 중첩을 갖도록 그로버 동전을 선택할 수 있습니다.^[12]

알고리즘은 다음과 같이 작동합니다.

$O(1/{\sqrt {\epsilon }})$ / $O(1/{\sqrt {\epsilon }})$ ϵ) {\displaystyle $O$ (1 / {\ $sqrt {\$ epsilon}})}에 대해 반복합니다.
- 중첩된 위상에 대한 카운팅 레지스터를 초기화합니다.
- $O(1/{\sqrt {\delta }})$ / $O(1/{\sqrt {\delta }})$ δ) ${\displaystyle$ O(1 $/{\sqrt {\$ delta}})} 정밀도로 $W$ $W$ 에 대한 위상 추정을 수행합니다.
- 추정 위상이 ${\tilde {\theta }}=0$ θ ~ = 0 ${\displaystyle {\theta$ }} = 0}인 경우 보조 큐비트를 표시합니다.
- 비연산 보조데이터 구조
정점 레지스터 측정

시프트 연산자는 효율적인 양자 보행을 구현하는 데 핵심 요소인 반면, 토로이드 및 격자와 같은 특정 그래프 계열의 경우 시프트가 알려져 있으며 비정규 그래프의 경우 효과적인 똥 연산자의 설계는 여전히 미해결 과제입니다.^[14]

적용들

다음 응용 프로그램은 Johnson 그래프 $J(n,k)$ $J(n,k)$ ${\displaystyle J(n,$ k $)}$ 의 양자 보행을 기반으로 합니다 $J(n,k)$ ^[15]

원소의 구별

$\{n\}$ $\{n\$ 에 정의된 $함수$ f ${\displaystyle$ f $}$ 가 주어졌을 때 $\{n\}$ f( $f(i)=f(j)$ ) $f(i)=f(j)$ = f $(j)$ {\displaystyle f(i)= f(j)}와 $f(i)=f(j)$ 쌍이 존재할 경우 두 개의 별개의 요소 $,$ $\in$ \{n\}를 찾으라고 요청합니다.

매트릭스 제품검증

Given three $n\times n$ matrices $A,B$ and $C$ , the problem asks to verify if $AB=C$ or otherwise find the indices $i,j$ such that ${\displaystyle (AB)_{i,j}\n$ $eq C_{i,j$ ^[6]

삼각형

삼각형은 방향이 없는 $그래프$ G{\ $displaystyle$ G}의 세 꼭짓점 부분 위에 있는 완전한 부분 그래프입니다 $G$ 그래프의 인접 행렬이 주어지면 문제는 삼각형이 존재할 때 삼각형을 찾으라고 요구합니다.^[6]

참고 항목

참고문헌

^ ^a ^b Portugal, Renato, ed. (2013). Quantum walks and search algorithms. Quantum science and technology. New York Heidelberg: Springer. pp. 17–37. ISBN 978-1-4614-6335-1.
^ Kadian, Karuna; Garhwal, Sunita; Kumar, Ajay (2021-08-01). "Quantum walk and its application domains: A systematic review". Computer Science Review. 41: 100419. doi:10.1016/j.cosrev.2021.100419. ISSN 1574-0137. S2CID 238207718.
^ Grover, Lov K. (1996-07-01). "A fast quantum mechanical algorithm for database search". Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. New York, NY, USA: Association for Computing Machinery. pp. 212–219. doi:10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID 207198067.
^ Santos, Raqueline A. M. (2016-08-26). "Szegedy's quantum walk with queries". Quantum Information Processing. 15 (11): 4461–4475. arXiv:1603.05473. Bibcode:2016QuIP...15.4461S. doi:10.1007/s11128-016-1427-4. ISSN 1570-0755. S2CID 254989663.
^ Shenvi, Neil; Kempe, Julia; Whaley, K. Birgitta (2003-05-23). "A Quantum Random Walk Search Algorithm". Physical Review A. 67 (5): 052307. arXiv:quant-ph/0210064. Bibcode:2003PhRvA..67e2307S. doi:10.1103/PhysRevA.67.052307. ISSN 1050-2947. S2CID 8688989.
^ ^a ^b ^c ^d ^e ^f ^g ^h Santha, Miklos (2008), Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng (eds.), "Quantum walk based search algorithms", Theory and Applications of Models of Computation, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 4978, pp. 31–46, arXiv:0808.0059, doi:10.1007/978-3-540-79228-4_3, ISBN 978-3-540-79227-7, S2CID 47163843, retrieved 2023-07-05
^ ^a ^b Magniez, Frederic; Nayak, Ashwin; Roland, Jeremie; Santha, Miklos (2007-06-11). "Search via quantum walk". Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. STOC '07. New York, NY, USA: Association for Computing Machinery. pp. 575–584. doi:10.1145/1250790.1250874. ISBN 978-1-59593-631-8. S2CID 1918990.
^ Levin, David Asher; Peres, Yuval (2017). Markov chains and mixing times. Elizabeth L. Wilmer, James G. Propp, David Bruce Wilson, American Mathematical Society (Second ed.). Providence, Rhode Island: American Mathematical Society. pp. 8–15. ISBN 978-1-4704-2962-1.
^ ^a ^b ^c ^d ^e de Wolf, Ronald (2019). "Quantum Computing: Lecture Notes". arXiv:1907.09415 [quant-ph].
^ Brassard, Gilles; Hoyer, Peter; Mosca, Michele; Tapp, Alain (2002), "Quantum Amplitude Amplification and Estimation", Quantum Computation and Information, Contemporary Mathematics, vol. 305, pp. 53–74, arXiv:quant-ph/0005055, doi:10.1090/conm/305/05215, ISBN 9780821821404, S2CID 54753
^ Jaques, Samuel (2019-05-01). Quantum Cost Models for Cryptanalysis of Isogenies (Master Thesis thesis). University of Waterloo.67-68쪽.
^ ^a ^b ^c ^d "Quantum Walk Search Algorithm". learn.qiskit.org. Retrieved 2023-07-05.
^ Wong, Thomas G. (2017). "Equivalence of Szegedy's and Coined Quantum Walks". Quantum Information Processing. 16 (9): 215. arXiv:1611.02238. Bibcode:2017QuIP...16..215W. doi:10.1007/s11128-017-1667-y. ISSN 1570-0755. S2CID 254985379.
^ Douglas, B. L.; Wang, J. B. (2007). "Efficient quantum circuit implementation of quantum walks". arXiv:0706.0304 [quant-ph].
^ Agong, Louis Anthony; Amarra, Carmen; Caughman, John S.; Herman, Ari J.; Terada, Taiyo S. (2018-01-01). "On the girth and diameter of generalized Johnson graphs". Discrete Mathematics. 341 (1): 138–142. arXiv:2304.02864. doi:10.1016/j.disc.2017.08.022. ISSN 0012-365X. S2CID 257985351.
^ Ambainis, Andris (2007). "Quantum Walk Algorithm for Element Distinctness". SIAM Journal on Computing. 37 (1): 210–239. CiteSeerX 10.1.1.251.5460. doi:10.1137/S0097539705447311. ISSN 0097-5397.

외부 링크

[:3-1] Portugal, Renato, ed. (2013). Quantum walks and search algorithms. Quantum science and technology. New York Heidelberg: Springer. pp. 17–37. ISBN 978-1-4614-6335-1.

[2] Kadian, Karuna; Garhwal, Sunita; Kumar, Ajay (2021-08-01). "Quantum walk and its application domains: A systematic review". Computer Science Review. 41: 100419. doi:10.1016/j.cosrev.2021.100419. ISSN 1574-0137. S2CID 238207718.

[3] Grover, Lov K. (1996-07-01). "A fast quantum mechanical algorithm for database search". Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. New York, NY, USA: Association for Computing Machinery. pp. 212–219. doi:10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID 207198067.

[4] Santos, Raqueline A. M. (2016-08-26). "Szegedy's quantum walk with queries". Quantum Information Processing. 15 (11): 4461–4475. arXiv:1603.05473. Bibcode:2016QuIP...15.4461S. doi:10.1007/s11128-016-1427-4. ISSN 1570-0755. S2CID 254989663.

[5] Shenvi, Neil; Kempe, Julia; Whaley, K. Birgitta (2003-05-23). "A Quantum Random Walk Search Algorithm". Physical Review A. 67 (5): 052307. arXiv:quant-ph/0210064. Bibcode:2003PhRvA..67e2307S. doi:10.1103/PhysRevA.67.052307. ISSN 1050-2947. S2CID 8688989.

[:0-6] ^ ^a ^b ^c ^d ^e ^f ^g ^h Santha, Miklos (2008), Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng (eds.), "Quantum walk based search algorithms", Theory and Applications of Models of Computation, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 4978, pp. 31–46, arXiv:0808.0059, doi:10.1007/978-3-540-79228-4_3, ISBN 978-3-540-79227-7, S2CID 47163843, retrieved 2023-07-05

[:1-7] Magniez, Frederic; Nayak, Ashwin; Roland, Jeremie; Santha, Miklos (2007-06-11). "Search via quantum walk". Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. STOC '07. New York, NY, USA: Association for Computing Machinery. pp. 575–584. doi:10.1145/1250790.1250874. ISBN 978-1-59593-631-8. S2CID 1918990.

[8] Levin, David Asher; Peres, Yuval (2017). Markov chains and mixing times. Elizabeth L. Wilmer, James G. Propp, David Bruce Wilson, American Mathematical Society (Second ed.). Providence, Rhode Island: American Mathematical Society. pp. 8–15. ISBN 978-1-4704-2962-1.

[:2-9] ^ ^a ^b ^c ^d ^e de Wolf, Ronald (2019). "Quantum Computing: Lecture Notes". arXiv:1907.09415 [quant-ph].

[10] Brassard, Gilles; Hoyer, Peter; Mosca, Michele; Tapp, Alain (2002), "Quantum Amplitude Amplification and Estimation", Quantum Computation and Information, Contemporary Mathematics, vol. 305, pp. 53–74, arXiv:quant-ph/0005055, doi:10.1090/conm/305/05215, ISBN 9780821821404, S2CID 54753

[11] Jaques, Samuel (2019-05-01). Quantum Cost Models for Cryptanalysis of Isogenies (Master Thesis thesis). University of Waterloo.67-68쪽.

[:4-12] "Quantum Walk Search Algorithm". learn.qiskit.org. Retrieved 2023-07-05.

[13] Wong, Thomas G. (2017). "Equivalence of Szegedy's and Coined Quantum Walks". Quantum Information Processing. 16 (9): 215. arXiv:1611.02238. Bibcode:2017QuIP...16..215W. doi:10.1007/s11128-017-1667-y. ISSN 1570-0755. S2CID 254985379.

[14] Douglas, B. L.; Wang, J. B. (2007). "Efficient quantum circuit implementation of quantum walks". arXiv:0706.0304 [quant-ph].

[15] Agong, Louis Anthony; Amarra, Carmen; Caughman, John S.; Herman, Ari J.; Terada, Taiyo S. (2018-01-01). "On the girth and diameter of generalized Johnson graphs". Discrete Mathematics. 341 (1): 138–142. arXiv:2304.02864. doi:10.1016/j.disc.2017.08.022. ISSN 0012-365X. S2CID 257985351.

[16] Ambainis, Andris (2007). "Quantum Walk Algorithm for Element Distinctness". SIAM Journal on Computing. 37 (1): 210–239. CiteSeerX 10.1.1.251.5460. doi:10.1137/S0097539705447311. ISSN 0097-5397.

[1]

[2]

[3]

[4]

[5]

[6]

[8]

[7]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search