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)

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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: