Skip to main content
Have a personal or library account? Click to login
Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk Cover

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

Quantum Information & Computation
Volume 24 (2024): Issue 1 (October 2024)
By:  and    
Open Access
|Oct 2024
Figures & tables

Figures & Tables

Figure 1.

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 θ−.

Figure 3.

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

Figure 4.

Quantum circuit for implementation of e−iÃt.

Figure 5.

Graph K8,4 with vertex |8〉 marked.

Figure 6.

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

Figure 7.

State counts of the measurement result of the simulation.

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

AlgorithmsModelInitial stateSuccess 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 workCTQW 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_

AlgorithmsGraphModelNumber of marked vertices
Marsh and Wang [21]2 × n Rook graphAlternating CTQWSingle
Qu et al. [22]Star graphAlternating CTQWSingle
Wang et al. [23]Integer Laplacian spectraAlternating CTQWMultiple
Peng et al. [24]Complete bipartite graphCoined DTQWMultiple
Our workComplete bipartite graphCTQWMultiple
DOI: https://doi.org/10.2478/qic-2024-0001 | Journal eISSN: 3106-0544 | Journal ISSN: 1533-7146
Journal RSS Feed
Language: English
Page range: 1 - 15
Submitted on: Jun 21, 2024
Accepted on: Sep 10, 2024
Published on: Oct 14, 2024
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
spatial search,
deterministic quantum algorithm,
quantum counting,
continuous-time quantum walk,
complete bipartite graph
Related subjects:
Physics,
Quantum physics,
Mathematics,
Applied mathematics,
Computer sciences,
Computer sciences in the humanities,
Computer sciences,
Computer sciences in natural sciences

© 2024 Honghong Lin, Yun Shang, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

Volume 24 (2024): Issue 1 (October 2024)
Next article