Open Access

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

Honghong Lin

Honghong Lin

  • Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of SciencesBeijing, China
  • School of Mathematical Sciences, University of Chinese Academy of SciencesBeijing, China
Search for this author on
Sciendo|Google Scholar
Lin, Honghong
 and 
Yun Shang

Yun Shang

  • Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of SciencesBeijing, China
  • NCMIS, MDIS, Academy of Mathematics and Systems Science, Chinese Academy of SciencesBeijing, China
Search for this author on
Sciendo|Google Scholar
Shang, Yun
  
Oct 14, 2024
Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk's Cover Image
About this article
Previous Article
Next Article
Cite
Download Cover
Article Category: Article
Published Online: Oct 14, 2024
Page range: 1 - 15
Received: Jun 21, 2024
Accepted: Sep 10, 2024
DOI: https://doi.org/10.2478/qic-2024-0001
Keywords
© 2024 Honghong Lin et al., published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Figure 1.

Quantum circuit implementation for the oracle in (5)
Quantum circuit implementation for the oracle in (5)

Figure 2.

The possible phase set returned by Algorithm 1 for M = 16. The best estimation for an angle θ is either θ+ or θ−.
The possible phase set returned by Algorithm 1 for M = 16. The best estimation for an angle θ is either θ+ or θ−.

Figure 3.

The eigenphase distribution of U(t0) on the unit circle.
The eigenphase distribution of U(t0) on the unit circle.

Figure 4.

Quantum circuit for implementation of e−iÃt.
Quantum circuit for implementation of e−iÃt.

Figure 5.

Graph K8,4 with vertex |8〉 marked.
Graph K8,4 with vertex |8〉 marked.

Figure 6.

Circuit simulation of the oracle for graph K8,4 with vertex |8〉 marked.
Circuit simulation of the oracle for graph K8,4 with vertex |8〉 marked.

Figure 7.

State counts of the measurement result of the simulation.
State counts of the measurement result of the simulation.

Comparison of previous results and our work on spatial search on complete bipartite graphs_

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 → ∞)
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)
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

j_qic-2024-0001_tab_004

Algorithm 2 : Quantum Phase Estimation (QPE).
Input: A unitary U, initial state |0〉⊗p|ϕ0 (p is the number of qubits in the first register and |ϕ0〉 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 U2j 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}) .

j_qic-2024-0001_tab_005

Algorithm 3 : Quantum counting for search on complete bipartite graphs.
Input: Unitary U(t0), 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̃.

j_qic-2024-0001_tab_003

Algorithm 1 : Deterministic search algorithm on complete bipartite graphs.
Input: A complete bipartite graph Km,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.

Comparison of previous results and our work on deterministic spatial search_

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
Language:
English
Publication timeframe:
1 times per year
Journal Subjects:
Physics, Quantum Physics
Journal RSS Feed