# Quantum Bayesian Networks

## August 13, 2009

### Have a Hot Dog at the Ballpark of Quantum Computing

Filed under: Uncategorized — rrtucci @ 12:06 am

A conversation overheard at Rick’s Café Américain-

So why would anyone be interested in using a quantum computer, shweetheart?

-Cigarettes, gum, cryptography, anyone?

-No cryptography thank you. Just cigarettes, shweetie.

Let’s face it Miss, most people (including most scientists and engineers) are not interested in understanding cryptography. They want to use cryptography to protect their data (e.g., in monetary transactions), but that’s about it. They don’t give a hill of beans about the underlying theory, or Shor factorization or RSA. Understanding the arcane details of cryptography is just not necessary or important to their disciplines (Is cryptography part of the curriculum of a physicist or biologist or chemist, like calculus and linear algebra are? Nope.). Besides, quantum computers can break RSA, but there are other known cryptographic codes, not breakable by a QC, that could easily replace RSA.

So what’s left for a poor QC prospector down on his luck? Grover’s algorithm?

Most people who have given a curshory look at Grover’s algo are totally baffled by the claim that it can be used to search a database. Not the type of databases (e.g., a telephone directory) I am familiar with. Not unless you first know how to express your “database” as an efficient oracle (that is, as an algorithm that is computable with polynomial efficiency), and how do you do that for a telephone directory? Beats me.

So…to recap, the average Joe thinks that there are only two known, important algorithms for a quantum computer, see, and those two algorithms sound quite lame to him.

Now, now. It ain’t that bad kid. Just remember darling, we’ll always have Paris, and… quantum simulated annealing and other applications of MCMC (Markov Chain Monte Carlo) for a quantum computer.

While most scientist and engineers and businessmen don’t give a hill of beans about breaking RSA or searching a misnomer-ed database, they are keenly interested in minimizing functions. They are confronted with such problems on a daily basis. And quite often, function minimization cannot be performed with polynomial efficiency. In those difficult cases, classical simulated annealing enables them to get an answer that is fairly close to the true minimum, using a thermodynamic method that Nature herself loves and uses frequently.

And… Somma et al. (arXiv:0712.1008) and Wocjan et al. (arXiv:0804.4259) have proven that one can do simulated annealing much faster on a quantum computer than on a classical one. (More precisely, for any $\epsilon>0$, their quantum algorithm requires order $1/\sqrt{\delta}$ elementary operations to find, with probability greater than $1-\epsilon$, the minimum of a function. Here $\delta$ is the distance between the two largest eigenvalue magnitudes of the transition probability matrix for the Metropolis Markov chain. Their quantum algorithm outperforms the classical simulated annealing algorithm, which requires order $1/\delta$ elementary operations to do the same thing.)

Relax. No need to fear the Germans while you’re here at Rick’s Cafe. Have a drink at the bar and play our new Monte Carlo roulette game, QuSAnn. QuSAnn outputs a quantum circuit for doing simulated annealing on a quantum computer. The quantum circuit implements the algorithm of Wocjan et al., which improves on the original algorithm of Somma et al.

Appendix

Bogie quotes:

“A hot dog at the ball park is better than steak at the Ritz.”(his own words)

“I was born when you kissed me. I died when you left me. I lived a few weeks while you loved me.”(In A Lonely Place)

“help a poor American down on his luck”(Treasure of the Sierra Madre)

“The stuff that dreams are made of.”(Maltese Falcon)

Casablanca:

“Of all the gin joints in all the towns in all the world, she walks into mine.”(Casablanca)

Ilsa: Play it once, Sam. For old times’ sake.

Sam: [lying] I don’t know what you mean, Miss Ilsa.

Ilsa: Play it, Sam. Play “As Time Goes By.”

Sam: [lying] Oh, I can’t remember it, Miss Ilsa. I’m a little rusty on it.

Ilsa: I’ll hum it for you. Da-dy-da-dy-da-dum, da-dy-da-dee-da-dum…

[Sam begins playing]

Ilsa: Sing it, Sam.

Sam: [singing] You must remember this / A kiss is still a kiss / A sigh is just a sigh / The fundamental things apply / As time goes by. / And when two lovers woo, / They still say, “I love you” / On that you can rely / No matter what the future brings-…

Rick: [rushing up] Sam, I thought I told you never to play-…

[Sees Ilsa. Sam closes the piano and rolls it away]

“It doesn’t take much to see that the problems of three little people doesn’t add up to a hill of beans in this crazy world. Someday you’ll understand that. Now, now… Here’s looking at you kid.”(Casablanca)

“If that plane leaves the ground and you’re not with him, you’ll regret it. Maybe not today. Maybe not tomorrow, but soon and for the rest of your life.”(Casablanca)

“We’ll always have Paris.”(Casablanca)

“Louis, I think this is the start of a beautiful friendship.”(Casablanca)