Quantum IsoRank: Efficient Alignment of Multiple Protein-Protein Interaction
Networks
Anmer Daskin∗

arXiv:1506.05905v2 [cs.CE] 14 Apr 2016

Department of Computer Engineering, Istanbul Medeniyet University, Uskudar, Istanbul, Turkey
Comparative analyses of protein-protein interaction networks play important roles in the understanding of biological processes. However, the growing enormity of available data on the networks
becomes a computational challenge for the conventional alignment algorithms. Quantum algorithms
generally provide greater efficiency over their classical counterparts in solving various problems. One
of such algorithms is the quantum phase estimation algorithm which generates the principal eigenvector of a stochastic matrix with probability one.
Using the quantum phase estimation algorithm, we introduce a quantum computing approach for
the alignment of protein-protein interaction networks by following the classical algorithm IsoRank
which uses the principal eigenvector of the stochastic matrix representing the Kronecker product
of the normalized adjacency matrices of networks for the pairwise alignment. We also present a
greedy quantum measurement scheme to efficiently procure the alignment from the output state of
the phase estimation algorithm where the eigenvector is encoded as the amplitudes of this state.
The complexity of the quantum approach outperforms the classical running time.

I.

INTRODUCTION

Comparative analyses of protein-protein interaction
(PPI) networks play important roles in the understanding of biological processes. Alignments of PPI networks
drawn from different species provide invaluable information to catalog conserved network regions and identify functional similarities across species. Using different
formulations, many network alignment algorithms have
been proposed such as the ones in [1–5] and others [6].
However, the growing enormity of available data on the
networks raises computational challenges for implementations of these algorithms. In analogous to ranking algorithms, e.g. PageRank [7], one of the global alignment
algorithms, IsoRank [8], uses the intuition that the score
of aligning two nodes should depend on the alignment
of their neighbours in the global alignment of two PPI
networks. It formulates the network alignment as an
eigenvector problem where coefficients of the principal
eigenvector of a stochastic matrix, the stationary state,
represent the functional similarity scores between pairs of
the nodes. Using a greedy algorithm, it then generates
the network alignment from the eigenvector. In the case
of multiple networks, IsoRank is applied to every pair
of the networks and a global alignment is retrieved from
the pairwise network alignment results [9]. While IsoRank is one of the successful algorithms and fast enough
to handle the alignment of large sparse graphs [10], the
exponential scaling of its running time with the number
of networks still impedes applications of the algorithm to
multiple networks (the running time of the algorithm is
O(E m ) where E is the number of edges in a network and
m is the number of networks) [11].
In [12], it has been discussed that aligning networks
on quantum computers may provide greater efficiency.

∗

email:anmerdaskin@yahoo.com

In particular, it is shown that the quantum phase estimation algorithm can be used for stochastic matrices to
find their principal eigenvector with the success probability one. However, it has not been shown how to procure
a solution from the quantum state representing the principal eigenvector. It is also not shown how to simulate
ranking matrices which are not Hermitian in most of the
cases in the phase estimation algorithm.
Here, we first show explicitly how the eigenvector of a
stochastic matrix can be obtained by using the quantum
phase estimation algorithm by following mostly Ref.[12].
To construct the alignment from the final quantum state,
we then give a greedy quantum algorithm based on a
quantum measurement scheme. In addition, we present
an approximate simulation approach for non Hermitian
ranking matrices and present simple examples with numerical results which can be experimented on quantum
computers (The capacities of the current quantum computers are very limited. Thus, they can only run for small
sized problems.). In the end, the complexity analysis
shows that the multiple network
alignment bythis quan

tum approach requires O m × poly log(|V |) computa
tional running time for sparse matrices while O m|V |2
for dense matrices. This is an exponential speedup over
the classical running time.

II.

CLASSICAL ISORANK

A PPI network is generally represented as an undirected graph, G(V, E) where the set of nodes V represents the set of proteins and the set of edges (vi , vj ) ∈ E
describes interactions between proteins vi and vj . To observe conserved similarities across species, PPI networks
for different species are comparatively analyzed by maximizing an objective function to indicate correspondences
between the nodes. One of the most common strategies to observe the similarities between networks is the

III

QUANTUM PHASE ESTIMATION ALGORITHM FOR NETWORK ALIGNMENT

network alignment. Network alignment is the process to
globally compare two or more networks to identify the regions where these networks are similar and dissimilar. In
general terms, network alignment can also be considered
as a more general variant of the subgraph isomorphism
problem which is an NP-complete problem of determining whether a finite larger graph contains a smaller graph
as an exact subgraph [13]. However, in the network alignment, it is important to find the most similar and dissimilar parts between two graphs even if the larger graph does
not contain the smaller one as an exact subgraph.[14]
Singh et al.[8] have presented a global alignment algorithm, viz. IsoRank, by using the intuition that the score
of aligning two nodes should depend on the alignment of
their neighbors. This intuition is formulated as follows:
Rij =

X

X

u∈N (i) v∈N (j)

1
Ruv ,
|N (u)||N (v)|

A.

Quantum Phase Estimation Algorithm

For a given approximate eigenvector encoded as the
amplitudes of the quantum state |µj i and the eigenvalue
equation U |µj i = ei2πφj |µj i; the phase estimation algorithm (PEA) [16] tries to find the phase φj in this equation. PEA mainly requires two quantum registers, |reg1 i
and |reg2 i, consisting of sufficient number of qubits to
hold the eigenvector and the phase, respectively. In the
initial setting, |reg1i is set to zero state and |reg2 i is
assigned to hold a vector which is the best known approximation of |µj i. With the help of quantum Fourier
transform and the sequential controlled unitary operations, |reg1 i becomes holding the Fourier transform of
the phase. Then, the application of the inverse quantum
Fourier transform turns |reg1i into the binary value of
the phase: |reg1i = |φj i. Consequently, the value of the
phase is obtained by measuring |reg1i in the standard
basis. Here, if the unitary operator U is the time evolution operator of a Hermitian matrix H, U = ei2πH , then
one also obtains the eigenvalue of H.

(1)

where, N (a) is the set of neighbors of the node a; |N (a)|
is the size of this set; V1 and V2 are the set of the nodes
for the networks G1 and G2 ; and i ∈ V1 and j ∈ V2 .
R defines the functional similarity matrix whose stationary state is used to find the solution for the alignment
problem. Eq.(1) can be rewritten also in matrix form as:
R = AR,
n
1
if (i, u) ∈ E1 and (j, v) ∈ E2 ,
A[i, j][u, v] = |N (u)||N (v)|
0
otherwise.
(2)

B.

Application to Stochastic Matrices

The success of the phase estimation algorithm is directly related to the closeness of the input vector to the
actual eigenvector. This can be defined by the dot product. The dot product of an equal superposition state and
a vector is the normalized sum of the vector elements. On
the other hand, the eigenvectors of a stochastic matrix
has the property that the sum of the vector elements is
one for the principal eigenvector and zero for the rest of
the eigenvectors. In [12], it has been showed that when
PEA is given an equal superposition input state, it then
finds the principal eigenvector of U and so the principal
eigenvector of the stochastic matrix H with the success
probability equal to one.

In the above equation, A is a |V1 ||V2 |x|V1 ||V2 | stochastic
matrix and can be defined from the Kronecker product
of the column-wise normalized adjacency matrices of the
input graphs: A = A1 ⊗ A2 , where Ai is the normalized
adjacency matrix for the graph Gi and also a stochastic
matrix. Eq.(2) describes an eigenvalue problem where
the principal eigenvector corresponding to the eigenvalue
one of the matrix A is the stationary distribution of the
random walk on the Kronecker product graph. On classical computers, this equation can be solved by using
different iterative methods such as the power iteration.

In our case, we find the principal eigenvector of the matrix A which is the Kronecker product of the column-wise
normalized adjacency matrices (normalized in the sense
to have stochastic matrices) for the input networks: i.e.,
A = A1 ⊗ A2 ⊗ · · · ⊗ Am . Because of the Kronecker
product, A defines a separable system and so quantum
circuits for each Ai can be constructed separately. This
eases the difficulty of finding quantum circuits for the
simulation. However, in general, quantum computing is
based on unitary gates associated with time evolution operators of Hermitian quantum systems. This dictates the
stochastic matrix used in the algorithm to be Hermitian,
in which case the principal eigenvector is already known
to be a vector of all ones. In the following subsection, we
shall describe how to approach non-Hermitian matrices.

III. QUANTUM PHASE ESTIMATION
ALGORITHM FOR NETWORK ALIGNMENT

In this section, we briefly explain the main intuition
of the quantum phase estimation algorithm (for an unfamiliar reader, we recommend Ref.[15]) and then show
how the stochastic matrices can be used in the phase estimation algorithm by following mostly Ref.[12]. Then,
we discuss how to simulate a non-Hermitian stochastic
matrix on quantum computers by using the closest Hermitian matrix. In the final subsection, we show how to
incorporate some other information used in the PPI networks.
2

C

Simulation of Non-Hermitian
III QUANTUM
OperatorsPHASE ESTIMATION ALGORITHM FOR NETWORK ALIGNMENT
C.

close to the ones of A. Hence, we expect the sums of the
coefficients of the eigenvectors of H to be very similar
to the ones of the eigenvectors of A and so the success
probability to be very close to one.

Simulation of Non-Hermitian Operators

A matrix A is called positive if the matrix elements
Aij > 0 and non-negative if Aij ≥ 0. It is normal if A† A−
AA† = 0, where A† describes the conjugate transpose of
A. Any matrix A can be decomposed into a Hermitian
and a skew-Hermitian matrices as:
A=H +S =

1
1
(A + A† ) + (A − A† ),
2
2

(3)

where H = 12 (A + A† ) and S = 12 (A − A† ) define the
nearest Hermitian and skew-Hermitian matrices to A, respectively [17]. The eigenvalues of H are all real and the
eigenvalues of S have only imaginary parts. Moreover,
when A is a normal matrix, there are a few additional
useful properties:
• H and S commute: [H, S] = HS − HS = 0.

D.

• Since AA† = A† A, H and S have the same eigenvectors.
• The imaginary part of the eigenvalues of A are
equal to the eigenvalues of S, and the real parts
are equal to the eigenvalues of H.

Incorporation of Other Information

As done in IsoRank [8], one can include further information, e.g. BLAST scores, into the quantum model as
well in the following form:

Because of the last property, one can simulate normal matrices and their corresponding non-Hermitian operators
on quantum computers by using two separate registers to
obtain the imaginary and the real parts of the eigenvalue
individually. In that case, one uses two unitary operators U1 = eiH and U2 = eS for the simulation. (Note
that U2 is a unitary matrix because the exponential of
a skew symmetric matrix is a unitary matrix.). However, if a stochastic matrix is normal, it turns out that
it is also doubly stochastic: i.e., its left and right principal eigenvectors are known to be a vector of all ones with
the eigenvalue one. Therefore, instead of an approximate
normal matrix, we shall use the closest Hermitian matrix
H = 12 (A + A† ) in our simulations. H defines a nonnegative matrix. If it is also irreducible, then there is a
well known theorem stating that H has a dominant positive eigenvalue equal to the spectral radius, ρ(H), of matrix H and corresponds to a real nonnegative eigenvector
unique up to a scalar
P of ρ(H) is
P multiple [18]. The value
bounded as: minj i hij ≤ ρ(H) ≤ maxj i hij , where
hij are the matrix elements of H. Using the stochastic
property of A, we also find ρ(H) > 0.5. PEA outputs
jth eigenvector with the probability:

Ã = H + B,

(5)

where B and H are to be assumed to commute: BH −
HB = 0. Therefore, the time evolution can be written
as:

eiÃ = eiH+B = eiH eiB

(6)

2

N
1 X
√
hi| |µj i .
N i

(4)

This is the normalized sum of the coefficients of the jth
eigenvector and is equal to one if |µij is the principal
eigenvector and zero for the rest of the eigenvectors.
Therefore, the success probability of PEA for stochastic
matrices is one. Moreover, since H is the best Hermitian approximation to A, the principal eigenpair of H

Note that the above equation does not change the sparsity of the matrix A; hence, it is still sparse and the
evolution operator and the corresponding quantum circuit require polynomial time for the implementation [19]
(see Sec.VI for the complexity analysis).
3

A Matching for a Pair of Networks

E.

IV

EXTRACTING NODE MAPPINGS FROM A QUANTUM STATE
we cannot apply classical matching algorithms directly.
Hence, engineering the order of the quantum registers in
the measurement, we describe the following greedy strategy for the alignment: Consider the eigenvector consists
of two registers as |xi |yi, where each register represents
a network:

Summary of the Method

• Prepare to quantum registers as: |reg1 i=0
PN
and |reg2 i = √1N i |ii defining an equal
superposition state.

1. Apply a conditional measurement: when the first
register is xi , measure the second register. For each
measured xi , this generates a yj ; therefore, xi s are
matched to yj s. Note that the measurement outcome is determined by the conditional probability
(The probability is conditional when additional information such as BLAST scores is included. Otherwise, it is disjoint.): the probability of measuring
yj in the second register while the first register is
xi .

†

• Find H = A+A
as the closest Hermitian
2
approximation to the stochastic matrix A.
• Find the quantum circuit simulating H by
using one of the methods described in [19,
20]. The number of gates in the resulted
circuit is polynomially bounded w.r.t. the
number of qubits for the sparse matrices.
• Apply the phase estimation algorithm with
the above initial settings.

2. If there are duplicities and still unmatched nodes;
then apply a second type of conditional measurement: if the second register yj , measure the first
register. This time for each yj an xi is obtained.

• For stochastic matrices; the PEA results the
correct answers with probability one: the
probability of seeing jth eigenvector is given
by the normalized square of the sum of its
coefficients:

This step is only useful when additional information is incorporated (A + B is used) because the
system is otherwise separable as A = A1 ⊗ A2 and
the conditional measurement outcome will be the
same as the outcome obtained in the first step.

2

N
1 X
√
hi| |µj i .
N i

(7)

Since the sum of the coefficients are one for
the principal eigenvector and zero for the
rest, PEA results the principal eigenvector
with probability one.

3. We combine these two different measurement outcomes obtained in the first and the second steps
and begin matching from nodes whose scores are
the highest.

• For the closest Hermitian matrix H; the
probability is not one. However, it is still
expected to be very close to one since H is
a nonnegative matrix with a principal eigenvalue and a positive eigenvector (this is due
to the Perron-Frobenious theorem) close to
the eigenvector of the original stochastic
matrix.

4. If there are still unmatched nodes, statistical information about the other possibilities obtained during the measurement is used to match the remaining nodes.
Since the main intuition of the algorithm gives a higher
similarity score to the nodes whose neighbours have
high scores; in the matching, the neighbours of the first
matched nodes are given priority so as to generate a solution which is also connected. In the end, we choose the
largest connected component as the best solution to the
alignment.
B.

IV.

In the case of multiple networks, as done in [9] an obvious approach is to align each possible pair of networks
and derive a common solution for the multiple networks
from these pairwise alignments. However, the complexity of this approach grows exponentially with the number
of networks. Here, we shall follow a different approach
which can be generalized easily to any number of networks: Assume we have three networks G1 , G2 , and G3
with nodes {a1 . . . am1 }, {b1 . . . bm2 } and {c1 . . . cm3 }, respectively. Let also |regG1 i, |regG2 i, and |regG3 i represent the networks G1 , G2 , and G3 , respectively:

EXTRACTING NODE MAPPINGS FROM A
QUANTUM STATE
A.

Matching for Multiple Networks

Matching for a Pair of Networks

Generating a discrete solution from the final quantum
state is known to be just solving a maximum weight
matching problem. However, since fully obtaining a
quantum state requires exponential time complexity [15],
4

B

Matching for Multiple Networks

V EXAMPLES

• Measuring |regG1 i alone and |regG2 i and |regG3 i
together, we draw the conditional probabilities to
see one of the nodes, ai , in |regG1 i and bj ck in
|regG1 i|regG3 i. In other words, when |regG1 i is
ai , the probability to see bj ck in |regG1 i|regG3 i is
obtained. This results in a matching of ai − bj ck .
Note that in the real implementation on a quantum
computer, one just assigns the nodes as a result of
the measurement outcome.

A.

In the case of the alignment of two networks G1 -G2 ,
the possible probability outcomes are shown in Fig.2(c);
where it is first assumed that |regG1 i = ai , then probabilities in the collapsed state are found for each bj.
Note that since the collapsed state is not normalized,
it represents conditional probabilities: e.g., the probability of |regG2 i = b2 when |regG1 i = a1 . The same
approach is also applied to G2 -G3 and the probabilities
are shown in Fig.2(a). The matching algorithm applied
to the outcomes in Fig.2(a) and Fig.2(c) procures the exact alignments for the both pairs of the networks. To
make the method understood well, we shall go through
the alignment for G1 and G2 by assuming PEA is run
statistically enough times with the same setting: The
probabilities for |regG1 i in the final state of PEA are
[0.1176, 0.1176, 0.2647, 0.1176, . . ., 0.1176, 0.0294] where
we see a3 with the highest probability.
When
|regG1 i = a3 , the quantum state collapses to the following unnormalized state: [0.1213, 0.3638, 0.2425, 0.2425]
which produces to the following normalized probabilities
[0.0556, 0.5000, 0.2222, 0.2222]. From this state we see
|regG2 i = b2 with the highest probability. Hence, a3
is matched to b2 . In the next possible step, |regG1 i
can take the same probabilities for different states. In
the measurement, we give the priority to the neighbours of the matched nodes. When |regG1 i = a1 , which
is a neighbour of a3 , the quantum state collapses to
[0.08080.2425, 0.1617, 0.1617] producing the normalized
probabilities: [0.0556, 0.5000, 0.2222, 0.2222]. Since b2 is
already matched, the second highest possible outcome is
either b3 or b4 . Therefore, a1 is matched to either b3 or
b4 . In the final round, we match a2 to the remaining one
of b3 and b4 . The same but unnormalized probabilities
are also shown in Fig.2(c).
Fig.2(b) and Fig.2(d) also show the probability outcomes for the alignment of the same networks: G1 -G2
and G2 -G3 ; however, in these figures, instead of A, approximate Hermitian matrices found by H = 1/2(A+A† )
are used. While the probabilities slightly differ in comparison to Fig.2(a) and Fig.2(c), they still conclude with
the same alignments.

– We match nodes initiating from the largest
probability, or the most commonly seen measurement outcome.
– As done in the case of two networks, the priority given to the neighbours of the first matched
nodes.
• If the measurement is no longer provide valuable information to match further nodes, then we measure
|regG2 i alone and |regG1 i and |regG3 i together.
This gives the probabilities to see one of the nodes,
bj , in |regG2 i and ai ck in |regG1 i|regG3 i. Then we
combine this measurement result with the previous measurement result to match the unmatched
nodes.
One can also go further and draw probabilities for
ck − ai bj and combine them with the previous results.
However, while different measurement settings increase
the statistical confidence in the measurement results, it
increases the complexity of the algorithm. As noted before, if |reg2 i is separable at the beginning: i.e., |reg2 i =
|regG1 i ⊗ |regG2 i ⊗ · · · ⊗ |regGm i, then the other measurements also produce the same result as the first measurement setting, G1i − G2j . . . Gmk . Thus, only the first
measurement setting is used to conclude the matching of
the nodes.

V.

Example-1: Alignment of Network Pairs

EXAMPLES

Because of the computational difficulty in simulating
quantum computers on classical computers (The complexity grows exponentially with the number of qubits
involved in the simulation. PEA requires also sufficient
number of qubits on the first register to hold eigenvalue.),
here we only aim to show the capability of the algorithm
when a fully functional quantum computer is available.
Therefore, we shall use merely trivial examples given in
Fig.1 for which one can see optimal solutions easily. For
the large non-trivial networks, since both IsoRank and
the quantum approach are based on the principal eigenvector; we expect the success of the algorithm to be similar to IsoRank even though the matching algorithm defined here is different than the one in IsoRank.

B.

Example-2: Alignment of Multiple Networks

As an example for the multiple network alignment, we
use G1 , G2 and G3 shown in Fig.1 and follow a similar method to the alignment of two networks: First, we
assume |regG1 i = ai , then find the probability of seeing |regG2 regG2 i = bj ck in the unnormalized collapsed
state which represents the conditional probabilities. The
probabilities are shown in Fig.3(a), where the exact matrix is used. Fig.3(a) represents the probabilities when
the Hermitian matrix H = 1/2(A + A† ) is used. Giving
the priority to the neighbors of the first matched nodes
as explained in Sec.IV B, the exact same matching can
5

VI

(a)G1

THE OVERALL ALGORITHMIC COMPLEXITY

(b)G2

(c)G3

FIG. 1. Example Networks

0.2

Combined Probability

0.25
Combined Probability

0.2
0.15
0.1
0.05
0

0.15

0.1

0.05

0

b1

b1
b2
b2
c4
b3

c4

c3

b3

c3

c2
b4

c2
b4

c1

G

c1

G

2

2

G

G

3

3

(a)Probabilities for matching of the nodes of G2 and G3

(b)Probabilities for matching of the nodes of G2 and G3
when the approximate Hermitian matrix is used.

Combined Probability

Combined Probability

0.2
0.15
0.1
0.05
0

0.04

0.02

0
a8

b1

a8

a7

a7

b1

a6

b2

a6

a5

a5

b2
a4
b3

a4

b3

a3

a3
b4

a2

b4

a1

G

2

G

G

2

1

(c)Probabilities for matching of the nodes of G1 and G2

a2
a1

G

1

(d)Probabilities for matching of the nodes of G1 and G2
when the approximate Hermitian matrix is used.

FIG. 2. Expected probability outcome for the alignment of pairs of the networks

trices of the PPI networks sparse, they can be simulated
efficiently on quantum computers.
In the implementation of the operator A, quantum circuits for each graph can be generated separately since it is
the Kronecker product of the column-wise normalized adjacency matrices (normalized in the sense to make them
stochastic): A = A1 ⊗ A2 ⊗ · · · ⊗ Am , where m represents
the number of networks. Therefore, the total complexity
of implementing A can be defined as:




O poly log(|V1 |) + poly log(|V2 |) . . . poly log(|Vm |) ,

be obtained from both of the figures.

VI.

THE OVERALL ALGORITHMIC
COMPLEXITY

The computational complexity of a quantum algorithm
is measured by the number of fundamental quantum
gates-e.g. one and two qubit gates-in the circuit which
simulates the algorithm. The complexity of PEA is dominated by the complexity of the circuit implementing the
given operator A. Implementation of A order of N requires O(N 2 ) number of quantum gates [15]. However, it
is proven that the efficient (polynomial time in the number of qubits) simulation of a sparse operator on quantum
computers is possible when the number of entries in A is
bounded polynomially in the number of qubits and the
norm of the matrix is less than or equal to the degree
of this polynomial [21]. There have been also algorithms
presented to simulate such sparse operators in polynomial time [19, 20]. As a result, since the adjacency ma-

(8)

or more concisely:


O m × poly log(|Vmax |) ,

(9)

where |Vmax | defines the maximum number of nodes in a
graph. This indicates an exponentially faster evaluation
time for the implementation of A than the implementations on classical computers. Note that if the adjacency
matrices are not sparse, then the complexity for this part
6

VIII

becomes O m|Vmax |2 which still provides exponential
speed-up in comparison to O |E|m classical complexity.
Moreover, in the case of the incorporation of additional
data: i.e., using A+B instead of A; the above complexity
arguments hold by assuming A and B commute and B
is efficiently simulatable.

VII.

ACKNOWLEDGMENT

CONCLUSION

In this paper, we have presented a quantum approach
for the alignment of multiple networks by adapting quantum phase estimation algorithm. In particular, we have
showed that the principal eigenvector of a stochastic matrix used in IsoRank algorithm for the alignment can be
found exponentially more efficiently on quantum phase
estimation algorithm. Since the final quantum state representing the eigenvector in the phase estimation algorithm is not classically available, adapting a conditional
measurement scheme, we have also showed a matching
algorithm to obtain the alignment result from this state.
In addition, since the stochastic matrices are generally
not Hermitian, we have also discussed how to approximate them for the simulation on quantum computers.
Finally, we have used three simple networks and showed
the numerical alignment results for them. While the approach discussed here follows mainly IsoRank algorithm,
we believe it shall also pave the way for the applications
of other spectral alignment methods on quantum computers.

The complexity of the matching part of the algorithm
is related to the number of measurements applied to the
system. If only one kind of measurement setting (measure a register alone and the rest together to draw the
conditional probabilities) is used, then this part requires
polynomial time (polynomial by the number of qubits)
because it is related to the number of qubits. On the
other hand, if one also uses different combinations of the
registers in the measurements and consider them together
to match the nodes (This can be only useful when additional data is incorporated.), then the complexity to store
the statistical results of the measurement outcomes and
find matching from these outcomes may grow exponentially with the number of networks. However, as mentioned in Sec.IV B, if no additional data is used, then the
system is separable and all possible measurement settings
produce the same output. Therefore, only one measurement setting can be used.

This work is supported by TUBITAK under the
project number 115E747.

[1] G. Klau, BMC Bioinformatics 10, S59 (2009).
[2] B. P. Kelley, B. Yuan, F. Lewitter, R. Sharan,
B.
R.
Stockwell,
and
T.
Ideker,
Nucleic Acids Research 32, W83 (2004).
[3] M. Koyutürk, Y. Kim, U. Topkara, S. Subramaniam,
W. Szpankowski, and A. Grama, Journal of Computational Biology 13, 182 (2006).
[4] Z. Li, S. Zhang, Y. Wang, X.-S. Zhang, and L. Chen,
Bioinformatics 23, 1631 (2007).
[5] M. Zaslavskiy,
F. Bach,
and J.-P. Vert,
Bioinformatics 25, i259 (2009).
[6] C. Clark and J. Kalita, Bioinformatics 30, 2351 (2014).
[7] L. Page, S. Brin, R. Motwani, and T. Winograd,
The PageRank Citation Ranking: Bringing Order to the
Web., Technical Report 1999-66 (Stanford InfoLab, 1999)
previous number = SIDL-WP-1999-0120.
[8] R. Singh,
J. Xu,
and B. Berger, in
Research in Computational Molecular Biology,
Lecture Notes in Computer Science, Vol. 4453, edited by
T. Speed and H. Huang (Springer Berlin Heidelberg,
2007) pp. 16–31.
[9] C.-S. Liao, K. Lu, M. Baym, R. S. 0001, and B. Berger,
Bioinformatics 25 (2009).
[10] M. Bayati, M. Gerritsen, D. Gleich, A. Saberi, and
Y. Wang, in Data Mining, 2009. ICDM ’09. Ninth IEEE
International Conference on (2009) pp. 705–710.

[11] Y. Nir, S. Roded, and N. William Stafford, Bioinformatics 24, i200 (2008).
[12] A. Daskin, A. Grama, and S. Kais, Quantum Information Processing 13, 2653 (2014).
[13] S. A. Cook, in Proceedings of the third annual ACM symposium on Theory of computing (ACM, 1971) pp. 151–
158.
[14] R. Sharan and T. Ideker, Nature biotechnology 24, 427
(2006).
[15] M. A. Nielsen and I. L. Chuang, Quantum computation
and quantum information (Cambridge university press,
2010).
[16] A. Kitaev, arXiv:quant-ph/9511026 (1995).
[17] J. B. Keller, Mathematics Magazine 48, pp. 192 (1975).
[18] A. Berman and R. J. Plemmons, “4. symmetric nonnegative matrices,” in Nonnegative Matrices in the Mathematical Sciences (1994) Chap. 4, pp. 87–111.
[19] D. Berry, G. Ahokas, R. Cleve,
and B. Sanders,
Communications in Mathematical Physics 270, 359 (2007).
[20] A. M. Childs and R. Kothari, in Theory of Quantum Computation, Communication, and Cryptography
(Springer, 2011) pp. 94–103.
[21] D. Aharonov and A. Ta-Shma, in Proceedings of the
thirty-fifth annual ACM symposium on Theory of computing, STOC ’03 (ACM, New York, NY, USA, 2003)
pp. 20–29.

VIII.

7

ACKNOWLEDGMENT

VIII

ACKNOWLEDGMENT

0.07
c

1

c

2

c

0.06

3

c

4

Combined Probability

0.05

0.04

0.03

0.02

0.01

0
a1b1

a1b3

a2b1

a2b3

a3b1

a3b3

a4b1

a4b3
a5b1
a5b3
G ⊗G ⊗G
1

2

a6b1

a6b3

a7b1

a7b3

a8b1

a8b3

3

(a)Probabilities for matching of the nodes of G1 , G2 , and G3 .
0.035
c

1

c

2

c

0.03

3

c

4

Combined Probability

0.025

0.02

0.015

0.01

0.005

0
a1b1

a1b3

a2b1

a2b3

a3b1

a3b3

a4b1

a4b3
a5b1
a5b3
G ⊗G ⊗G
1

2

a6b1

a6b3

a7b1

a7b3

a8b1

a8b3

3

(b)Probabilities for matching of the nodes of G1 , G2 , and G3 when the approximate Hermitian
matrix is used.

FIG. 3. Probabilities for matching of the nodes G1 , G2 , and G3 . While the x-axis represents the nodes, ai bj ck ; the y-axis is the
unnormalized conditional probabilities: if |regG1 i is in ai state, then the probability to measure |regG2 i |regG3 i in bj ck state
in the collapsed quantum state is shown.

8

