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

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

Table 2.

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	$\sum_{i = 0}^{m + n - 1} \| i 〉$	1 (m, n → ∞)
Wong et al. [28]	CG framework for adjacency walk	$\frac{1}{\sqrt{2 m}} \sum_{i \in V_{1}} \| i 〉 + \frac{1}{\sqrt{2 n}} \sum_{i \in V_{2}} \| i 〉$	1 (m, n → ∞)
Rhodes and Wong [29]	Coined DTQW	$\frac{1}{\sqrt{m + n}} (\sum_{i \in V_{1}} \| i 〉 \otimes \frac{1}{\sqrt{n}} \sum_{j \in V_{2}} \| j 〉 + \sum_{i \in V_{2}} \| i 〉 \otimes \frac{1}{\sqrt{m}} \sum_{j \in V_{1}} \| j 〉)$	$\frac{m}{m + n}$ or $\frac{n}{m + n}$ (and 1 for a special case)
Rhodes and Wong [29]	Coined DTQW	$\frac{1}{\sqrt{2 mn}} (\sum_{i = 0}^{m + n - 1} \| i 〉 \otimes \sum_{j \sim i} \| j 〉)$	$\frac{1}{2}$ (and 1 for a special case)
Xu et al. [30]	Coined DTQW	$\frac{1}{\sqrt{2 mn}} (\sum_{i = 0}^{m + n - 1} \| i 〉 \otimes \sum_{j \sim i} \| j 〉)$	≥ 1 − ɛ for any adjustable parameter ɛ
Our work	CTQW	$\frac{1}{\sqrt{m}} \sum_{i \in V_{1}} \| i 〉$ or $\frac{1}{\sqrt{n}} \sum_{i \in V_{2}} \| i 〉$	1

Quantum circuit implementation for the oracle in (5)

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 = ⌈ \frac{π}{4} \sqrt{\frac{n}{k}} - \frac{1}{2} ⌉$ and $t = \frac{2}{\sqrt{mn}} arcsin [\sqrt{\frac{n}{k}} sin (\frac{π}{2 (2 l + 1)})]$ .
2: Construct the initial state $\| s 〉 = \frac{1}{\sqrt{m}} \sum_{i = 0}^{m - 1} \| i 〉$ .
3: Perform quantum walk search $U^{l} (t) e^{- iA \frac{t}{2}} \| s 〉 = {(e^{- iAt} O)}^{l} e^{- iA \frac{t}{2}} \| s 〉$ .
4: Measure the final state and get \|i〉.
5: Return vertex i.

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 $\tilde{θ} = 2 π \frac{l}{M} (M = 2^{p})$ .

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

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

Algorithm 3 : Quantum counting for search on complete bipartite graphs.
Input: Unitary U(t₀), initial state\|0〉^⊗p\|ψ〉 ( $p = ⌈ {log}_{2} \frac{5 n π}{2 δ} ⌉$ 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
$\tilde{k} = {(sin \frac{\tilde{θ}}{2})}^{2} n$ .
3: Return k̃.

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

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

State counts of the measurement result of the simulation.

References

Authors

Metrics

Articles in this issue

DOI: https://doi.org/10.2478/qic-2024-0001 | Journal eISSN: 3106-0544 (formerly 1533-7146) | 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:

Computer sciences,

Computer sciences in the humanities,

Computer sciences in natural sciences,

Mathematics,

Applied mathematics,

Physics,

Quantum physics

© 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)

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

Figures & Tables

Table 1.

Table 2.

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Paradigm

My account