Quantum Bayesian Networks

March 28, 2013

Quantum Computers Do Primes Too

Filed under: Uncategorized — rrtucci @ 5:52 pm

Check out this recent ArXiv paper in which 2 Spaniards, José Latorre and Germán Sierra, give an n qubit circuit that produces a quantum superposition of all the prime numbers less than 2^n. They also show how further QC processing of this superposition of primes can be done to calculate the prime counting function \pi(N). Their QC algorithm can calculate \pi(N) quadratically more efficiently than a classical computer. This permits a QC to probe \pi(N) for much higher N values than a classical computer, if both computers have the same amount of time to calculate. Here is a decent, popular press article about their paper, courtesy of the website “I-Programmer”.

I am often asked for a practical example of the use of Grover’s algorithm. Well, this prime thingie is a very nice example, although it assumes some interest in Number Theory and familiarity with it.

Grover’s algorithm is near and dear to my heart, because I use it in my computer program called “Quibbs”(a QC circuit generator written in JAVA) . In Quibbs, I use my own, home-brewed, fixed-point version of Grover’s algorithm to sample any probability distribution inputted in the form of a classical Bayesian network.

Number Theory shows up infrequently in present day physical theories, but it does show up frequently in computer science algorithms and it has deep connections with group theory (Langlands program), and physicists are always interested in group theory. Hence, maybe in the future, physicists will use Number Theory much more often than they do today.

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

Create a free website or blog at WordPress.com.

%d bloggers like this: