Quantum Bayesian Networks

February 21, 2009

Classical Reversible Computing and Quantum Computer Programming

Filed under: Uncategorized — rrtucci @ 8:14 am

Historically, discoveries in classical reversible computing (CRC) provided a strong inspiration for later discoveries in quantum computing. But the importance of CRC for quantum computing is much more than historical. Many results and software from CRC can still be used almost out of the box in quantum computer programming. For example, many quantum computing algorithms query an oracle one or more times.  (See my previous blog post for an introduction to quantum oracles.) Finding a quantum circuit for such oracles is essentially a problem in CRC programming. Indeed, these deterministic circuits can be expressed solely in terms of CNOTs and Toffoli gates (i.e., 2 and 3 body deterministic interactions)

For example, consider Monte Carlo integration, an application which is extremely useful in many areas of science and engineering. Quantum computers can do Monte Carlo integration quadratically faster than classical computers. Woo hoo! (This assumes that we know a polynomial complexity algorithm for calculating the function being integrated. For an excellent introduction to quantum Monte Carlo integration, see this paper by Abrams and Williams). Quantum algorithms for Monte Carlo integration use an oracle that loads the function being integrated. Writing a circuit for such an oracle will often require reversible circuits for doing the basic panoply of imperative language operations (arithmetic operations, trigonometric and exponential functions, do-loops and conditionals). CRC software that writes such circuits already exists(?)

CRC Researchers:

(1)Michael P. Frank
has been in the forefront of CRC for more than a decade. He got his Ph.D. from MIT in 1999, in the field of CRC. I especially like the fact that he does both theory and programming. With his student DoRon B. Motter (now at Microsoft?), he wrote a reversible Shroedinger equation simulator in Java (Can’t find a link to it). More recently, he and his collaborators at FSU have written a space-efficient simulator of quantum computers in C++. I found the following talk, an overview of some of his work, very interesting: “Quantum Computer Architectures for Physical Simulations,” invited talk presented by Frank at the Quantum Computation for Physical Modeling workshop sponsored by the Air Force research labs, held at Martha’s Vineyard, Wed., May 8, 2002.  PowerPoint  slides  here


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Blog at WordPress.com.

%d bloggers like this: