Accès libre

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
Recherchez cet auteur sur
Sciendo|Google Scholar
Lin, Honghong
 et 
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
Recherchez cet auteur sur
Sciendo|Google Scholar
Shang, Yun
  
14 oct. 2024
Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk's Cover Image
À propos de cet article
Article précédent
Article suivant
Citez
Télécharger la couverture
Catégorie d'article: Article
Publié en ligne: 14 oct. 2024
Pages: 1 - 15
Reçu: 21 juin 2024
Accepté: 10 sept. 2024
DOI: https://doi.org/10.2478/qic-2024-0001
Mots clés
© 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
Langue:
Anglais
Périodicité:
1 fois par an
Sujets de la revue:
Physique, Physique quantique
RSS Feed de la revue