# Quantum Bayesian Networks

## August 15, 2009

### Szegedy Ops

Filed under: Uncategorized — rrtucci @ 10:07 pm

Fig.1-Szegedy Operator W(M) when M acts on 2 bits (i.e., is 4 by 4 matrix)

QuSAnn implements in software some cool theoretical techniques, such as the quantum walk operators $W(M)$ invented by Mario Szegedy ( a two times Gödel prize winner). These are unitary operators which have the following highly desirable property.

Suppose you have a Markov chain with transition probability matrix $M(y|x)$ and stationary state $\pi(x)$, where $x,y\in\Omega$. Then the state $\sum_x \sqrt{\pi(x)} |x\rangle\otimes |0\rangle$ is a stationary state of $W(M)$. (Here $0$ is an arbitrary, fixed element of $\Omega$ ). Thus, if $M$ acts on $N_B$ bits (i.e., on a $2^{N_B}$ dimensional vector space), then $W(M)$ acts on $2N_B$ bits.

For example, Fig.1 shows a circuit diagram for $W(M)$ in case $N_B=2$. (For instructions on how to decipher Fig.1, see the QuSAnn documentation). Fig.1 uses multiplexor gates. If you want to express these in terms of simpler gates, like multiply controlled NOTs and qubit rotations, you can do this with Multiplexor Expander, an utility application that comes with QuSAnn.