Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk

Figures & Tables

Algorithms	Model	Initial state	Success probability
Wong et al. [28]	CG framework for Laplacian walk	∑i=0m+n−1\|i〉 \sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle	1 (m, n → ∞)
Wong et al. [28]	CG framework for adjacency walk	12m∑i∈V1\|i〉+12n∑i∈V2\|i〉 {1 \over {\sqrt {2m}}}\sum\nolimits_{i \in {V_1}} \|i\rangle + {1 \over {\sqrt {2n}}}\sum\nolimits_{i \in {V_2}} \|i\rangle	1 (m, n → ∞)
Rhodes and Wong [29]	Coined DTQW	1m+n(∑i∈V1\|i〉⊗1n∑j∈V2\|j〉+∑i∈V2\|i〉⊗1m∑j∈V1\|j〉) {1 \over {\sqrt {m + n}}}\left({\sum\nolimits_{i \in {V_1}} \|i\rangle \otimes {1 \over {\sqrt n}}\sum\nolimits_{j \in {V_2}} \|j\rangle +} \right.\left. {\sum\nolimits_{i \in {V_2}} \|i\rangle \otimes {1 \over {\sqrt m}}\sum\nolimits_{j \in {V_1}} \|j\rangle} \right)	mm+n {m \over {m + n}} or nm+n {n \over {m + n}} (and 1 for a special case)
Rhodes and Wong [29]	Coined DTQW	12mn(∑i=0m+n−1\|i〉⊗∑j∼i\|j〉) {1 \over {\sqrt {2mn}}}\left({\sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle \otimes \sum\nolimits_{j \sim i} \|j\rangle} \right)	12 {1 \over 2} (and 1 for a special case)
Xu et al. [30]	Coined DTQW	12mn(∑i=0m+n−1\|i〉⊗∑j∼i\|j〉) {1 \over {\sqrt {2mn}}}\left({\sum\nolimits_{i = 0}^{m + n - 1} \|i\rangle \otimes \sum\nolimits_{j \sim i} \|j\rangle} \right)	≥ 1 − ɛ for any adjustable parameter ɛ
Our work	CTQW	1m∑i∈V1\|i〉 {1 \over {\sqrt m}}\sum\nolimits_{i \in {V_1}} \|i\rangle or 1n∑i∈V2\|i〉 {1 \over {\sqrt n}}\sum\nolimits_{i \in {V_2}} \|i\rangle	1

Algorithm 2 : Quantum Phase Estimation (QPE).
Input: A unitary U, initial state \|0〉^⊗p\|ϕ₀ (p is the number of qubits in the first register and \|ϕ₀〉 is an arbitrary state of the second register).
Output: An estimate θ̃ of one of the eigenphases of U.
1: Apply Hadamard gate H to each qubit in the first register.
2: Apply U^{2^j} on the second register controlled by qubit j, 1 ≤ j ≤ p in the first register.
3: Apply inverse quantum Fourier transform to the first register.
4: Measure the first register in the computational basis and get the result l.
5: Return θ˜=2πlM(M=2p) \tilde \theta = 2\pi {l \over M}(M = {2^p}) .

Algorithm 3 : Quantum counting for search on complete bipartite graphs.
Input: Unitary U(t₀), initial state\|0〉^⊗p\|ψ〉 ( p=⌈log2 5nπ2δ⌉ p = \left\lceil {{{\log}_2}\,{{5n\pi} \over {2\delta}}} \right\rceil is the number of qubits in the first register and δ is the desired precision).
Output: Estimation k̃ of the number of marked vertices k with precision δ.
1: Call Algorithm 2 and get the result θ̃.
2: if θ̃ = π
then discard;
else
k˜=(sinθ˜2)2n \tilde k = {\left({\sin {{\tilde \theta} \over 2}} \right)^2}n .
3: Return k̃.

Algorithm 1 : Deterministic search algorithm on complete bipartite graphs.
Input: A complete bipartite graph K_m,n with k marked vertices on the order-n part whose adjacency matrix is A, an oracle O that satisfies equation (5).
Output: A marked vertex.
1: Calculate parameters l=⌈π4nk−12⌉ l = \left\lceil {{\pi \over 4}\sqrt {{n \over k}} - {1 \over 2}} \right\rceil and t=2mnarcsin[nksin(π2(2l+1))] t = {2 \over {\sqrt {mn}}}\arcsin \left[ {\sqrt {{n \over k}} \sin ({\pi \over {2(2l + 1)}})} \right] .
2: Construct the initial state \|s〉=1m∑i=0m−1\|i〉 \|s\rangle = {1 \over {\sqrt m}}\sum\nolimits_{i = 0}^{m - 1} \|i\rangle .
3: Perform quantum walk search Ul(t)e−iAt2\|s〉=(e−iAtO)le−iAt2\|s〉 {U^l}(t){e^{- iA{t \over 2}}}\|s\rangle = {({{\rm{e}}^{- iAt}}O)^l}{{\rm{e}}^{- iA{t \over 2}}}\|s\rangle .
4: Measure the final state and get \|i〉.
5: Return vertex i.

Algorithms	Graph	Model	Number of marked vertices
Marsh and Wang [21]	2 × n Rook graph	Alternating CTQW	Single
Qu et al. [22]	Star graph	Alternating CTQW	Single
Wang et al. [23]	Integer Laplacian spectra	Alternating CTQW	Multiple
Peng et al. [24]	Complete bipartite graph	Coined DTQW	Multiple
Our work	Complete bipartite graph	CTQW	Multiple