Finding a Perfect Matching of a Balanced
Bipartite Graph by Quantum Search Algorithm
Hideaki OTSUKI
∗Abstract
Finding maximal matchings of graphs is a well-studied problem. Some deterministic algorithms solve this problem by polynomial time. We apply Grover’s quantum search algorithm to find a perfect matching of balanced bipartite graphs. We show that in some restricted cases, this problem can be solved by O(1) queries to an oracle. We investigate the dependencies of the size of the answer on the computational complexity of this problem.
1
Introduction
Finding maximal matchings of graphs is a well-studied problem. Some deter-ministic algorithms solve this problem by polynomial time [1] [2]. Bipartite perfect matching is in Quasi-NC [3]. For d-regular bipartite graphs, perfect matching is solved in O(n log n)-time by randomized algorithm [4]. We apply Grover’s quantum search algorithm to find a perfect matching of balanced bi-partite graphs. We show that in some restricted cases, this problem can be solved by O(1) queries to an oracle.
In this article, we use Grover’s algorithm for finding a perfect matching of balanced bipartite graphs as follows. We encode a bipartite graph into an inte-ger. Next, we introduce a function that finds perfect matchings of a bipartite graph. We investigate dependencies of the size of the answer on the computa-tional complexity.
Some quantum algorithms compute particular problems faster than classical algorithms ever known. Grover’s algorithm is the search algorithm using an oracle. The complexity of the algorithm is measured by the number of queries to its oracle. For the size N database, Grover’s algorithm runs with O(√N )
queries, while simple sequential search needs O(N ) queries.
2
A Perfect Matching of a Balanced Bipartite
Graph
Throughout this article, we treat only simple and balanced bipartite graphs. Let B = (X, Y, E) be a balanced bipartite graph. Then |X| = |Y | ≡ n holds. Let X ={x1, . . . , xn} and Y = {y1, . . . , yn}. A perfect matching M of B is a
subgraph of B such that for all xi and yj, there is only one edge E(xi, yj)∈ M.
∗Department of Software Engineering, Nanzan University
Figure 1: B for b(B) = 22·3· 33· 52·5
x
1y
1x
2y
2x
3y
32
2
3
3
5
5
Let pibe the i-th prime begin with p1= 2. That is, p1= 2, p2= 3, p3= 5, . . .
and so on. For each xi∈ X, we assign an integer qi and ri as follows
qi=
∏
(xi,yj)∈E pj
ri= pqii.
For a graph B, we assign an integer b(B) which is the product of ri for all
i∈ {1, . . . , n}, that is, b(B) = n ∏ r=1 ri= n ∏ r=1 pqi i .
(See Figure 1.) From the uniqueness of prime factorization, if B is not isomor-phic to B′ then b(B)̸= b(B′) holds.
For sets of vertices X and Y , we give an expression of a perfect matching as follows. Let Σ be the set of permutations of {p1, p2, . . . , pn}. Let N ≡ n!.
For k∈ {1, . . . , N}, let σk ∈ Σ be the k-th permutation of {p1, p2, . . . , pn}. Let
σk(i) be the i-th prime of σk.
Let Mk be a graph such that b(Mk) =
∏n i=1p
σk(i)
i . Then from the definition
of b, Mk is a perfect matching of B.
Lemma 2.1. If qimod σk(i) = 0 for all i ∈ {1, . . . , n}, then B has Mk as a
subgraph.
Proof. If qimod σk(i) = 0 then there is an edge E(xi, yj) such that the i-th
prime of σk is pj. Thus, for each i, there is an edge E(xi, yj). Therefore B has
Mk as a subgraph.
Define a function fB(k) such that
fB(k) =
{
1 ∑ni=1(qimod σk(i)) = 0
0 otherwise. Then next proposition holds.
Proposition 2.2. If and only if there exists k∈ {1, . . . , N} such that fB(k) = 1,
B has a perfect matching.
3
Grover’s Search Algorithm for Finding a
Per-fect Matching of B
For simplifing our discussion, we suppose that log N is an integer. Add e extra variables to N variables such that log(N + e) is an integer. Introduce a function
f′(k′) such that for any values of these e extra variavles, f′(k′) = 1 if and only if fB(k) = 1, otherwise f′(k′) = 0. Instead of fB(k) for N variavles, let this
new function f′ be fB and suppose N + e variables as new N variables in the
following.
Let m = log N . Then fB(k) is a function from{0, 1}mto{0, 1}. Let Uf be
an oracle that answers wether k satisfies fB(k) = 1. Assume that the number
of answers is t. Then Grover’s algorithm outputs an answer with probability at least 1/2 using at most 2√N/t queries to Uf. We briefly overview this
algorithm.
Prepare m + 1 qubits |0m⟩ |1⟩. Apply the Hadamard transform H⊗m+1 to all m + 1 qubits where
H = √1 2 ( 1 1 1 −1 ) .
Apply Uf to the resulted qubits. At last, apply the matrix DN to the first m + 1
qubits where DN = −1 + 2 N 2 N · · · 2 N 2 N −1 + 2 N · · · 2 N . .. 2 N · · · −1 + 2 N.
LetK be the set of answers of fB(k) = 1. Note that|K| = t. Then the qubits
are transformed as follows.
|0m⟩ |1⟩ → √1 2 ∑ k∈{0,1}m |k⟩ ⊗√1 2(|0⟩ − |1⟩) → (∑ k∈K 3− (4/N) √ N |k⟩ + ∑ k /∈K 1− (4/N) √ N |k⟩) ⊗ 1 √ 2(|0⟩ − |1⟩) where ⊗ is the tensor multiplication. These transformation amplify the proba-blity of mesurements of the answers of fB(k) = 1. Applying Uf to these qubits
r times, the probability that we measure one of the answers is sin2((2r + 1)θt)
where sin θt =
√
t/N . See standard textbook for the detail of estimation [5].
Repeating the query 2√N/t times, we can amplify this probablity at least to
1/2.
3 Hideaki OTSUKI
4
Discussion
If t = Ω(N ) then using the oracle O(1) times, the algorithm outputs the correct answer with probability at least 1/2. Because N = n!, the number of perfect matchings is very large in this case. Thus, in contrast to the deterministic algorithm, the problem can be solved efficiently by this quantum algorithm, if the input graph is sufficiently dense.
We did not consider the complexity of the oracle in this article. It is impor-tant to investigate how to construct the circuit of the oracle. This is a subject for future analysis.
References
[1] John E. Hopcroft and Richard M. Karp. An n 5/2 algorithm for maximum matchings in bipartite graphs, 1973.
[2] K. Fukuda and T. Matsui. Finding all the perfect matchings in bipartite graphs. Applied Mathematics Letters., 7(1):15–18, 1994. PRO 94.13. [3] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect
matching is in quasi-nc. CoRR, abs/1601.06319, 2016.
[4] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Perfect matchings in o(n log n) time in regular bipartite graphs. CoRR, abs/0909.3346, 2009. [5] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and
Quan-tum Information. Cambridge University Press, 2000.
