Quantum Bayesian Networks

August 29, 2009

Tulsi

Filed under: Uncategorized — rrtucci @ 4:35 pm

Check out:

“Indian prodigy boy completes PhD in physics at the age of 21”
Bombay News.Net
Friday 28th August, 2009 (ANI)

Excerpt:

“The young Indian scientist has an invite from the Institute for Quantum Computing at the University of Waterloo, Canada, for post- doctoral work.

But he wants to continue his research in software development for quantum computing, the super fast future of number crunching in India given a chance and proper funding.

He said that he hopes to set up his own quantum computing company someday and is working hard for it.”

Huh? This must be a misquote. Surely what Tulsi really said must have been that he wants to be a prestigious quantum complexity theorist, not a lowly quantum computer programmer. 🙂

Wikipedia on Tathagat Avatar Tulsi

Quantum Internet Snake Oil

Filed under: Uncategorized — rrtucci @ 6:27 am

Bizarre/Hilarious.
Caltech and MIT snake oil sale:

“Entangled Light, Quantum Money”
Technology Review, September/October 2009
by Mark Williams

Some excerpts:

…Kimble made one easily graspable assertion: “Our society’s technical base is information commerce. In the next 20 years, quantum information science–a fusion of computer science and quantum mechanics that didn’t exist 20 years ago–will radically change that commerce.”

The revolutionary technology that Kimble envisions is large quantum networks, resembling the Internet but relying on entanglement. What inherent advantages would promote the development and adoption of such networks?

Substantial ones….

MIT’s Seth Lloyd has given some thought to the design options for quantum networks.

So Kimble has a reasonable argument that quantum networks are feasible. And the advantages that he envisions–absolute data security, no latency, and a further exponential gain in computational power–would hardly be negligible in the world of information commerce.

Futures traders who use near-instantaneous quantum networks will have clear advantages over those who don’t.

Other commercial applications are possible as well. Scott Aaronson suggested one of them in a paper called “Quantum Copy-Protection and Quantum Money.”

The first generation of money emerged with the invention of coins in Lydia nearly 3,000 years ago, its second generation with the paper bills of exchange issued by the banks of Renaissance Italy, and its third with electronic money and the virtual economy of the modern era. If scientists like Kimble and Aaronson are correct, quantum networks may soon give rise to a further generation of money.

Replacing the classical internet by a quantum one is a really dumb idea; doing so would be phenomenally expensive and totally unnecessary. There are known classical cryptographic codes which cannot be broken by a classical or quantum computer, so there is no need for quantum cryptography, or a “quantum Internet”, or “quantum money”, ever. Why should a carpenter replace his perfectly adequate steel hammer (classical networks and classical encryption methods) by a pure gold one?

My previous blog posts on this subject:

August 28, 2009

xkcd comic on AI

Filed under: Uncategorized — rrtucci @ 4:22 pm

xkcd comics, “genetic algorithms” panel:
genetic_algo

Military Uses of Quantum Computers

Filed under: Uncategorized — rrtucci @ 3:55 pm

Both hawks and doves should be interested in this topic. We would be dangerously naive and irresponsible if we didn’t think about this topic, starting at the early stages of QC development.

Since the dawn of civilization, science has been used to design weapons, the instruments with which we defend our nation, wage war against other nations, kill and maim. Many highly successful, peaceful applications of science were initially invented or improved with warfare in mind. A modern example is the internet, which was initially funded by DARPA.

Unless humans learn to stop killing each other, which is highly unlikely, it’s inevitable that eventually, someone somewhere will use quantum computers to build weapons. So, what types of weapons could be built with quantum computers? Some obvious near term military applications of quantum computers are

cryptographic decoding – Thanks to Shor’s algorithm, quantum computers can decode efficiently certain types of cryptographic codes such are RSA, which is the backbone of our current commercial encryption systems. Luckily, there are other known classical cryptographic codes which cannot be decoded by a QC.

AI/pattern recognition – Bayesian network methods (a subset of which is MCMC (Markov Chain Monte Carlo) methods) have numerous, wonderful, peaceful applications. Nevertheless, Bayesian network methods have military applications too. For example, they are already in use (or their use is being tested) to discriminate between missiles and decoys in Star Wars defense systems. (I know this for a fact, since I was once interviewed (and rejected 🙂 ) for a defense job to write Bayesian net software for this purpose). We will soon know how to do B. net calculations on a quantum computer. (See my previous posts about quantum simulated annealing). QCs will perform such calculations much faster than classical computers. The speed at which one can perform discrimination is crucial for defensive systems like a Star Wars defense shield.

Bioinformatics – A frightful possibility in the not too distant future is bio-engineered terrorism or accidents. Suppose someone were to engineer a very harmful germ and unleash it upon us. Bioinformaticists might be enlisted to analyze this germ, as their findings might help to find an antidote. Clearly, how long it takes to analyze the germ is critical in this scenario. One common tool in bioinformatics is MCMC, so if MCMC can be performed faster with a quantum computer than a classical computer, that would help bioinformaticists do their job more quickly.

August 25, 2009

Quantum (Zeno, Anti-Zeno, Hamlet) Effects

Filed under: Uncategorized — rrtucci @ 8:54 pm

New fodder for quantum algorithm composers and quantum computer programmers:

“Quantum Hamlet Effect” by Vladan Panković, arXiv 0908.1301

Imagine a play in which:
As he stands near the edge of the quantum precipice,
Zeno hears voices saying: “Don’t jump!”,
Anti-Zeno hears voices saying: “Jump!”,
and poor Hamlet hears both.
Quite a drama!

Unfortunately, as already pointed out by Wolfgang, Vladan incorrectly assumes he can take, for his proposed Hamlet experiment, the limit of infinitely many measurements. (If you could take such a limit, then the sum of the time intervals between measurements would be infinite, so it would take an infinitely long time to perform the experiment).

By the way, the Wikipedia article on the standard quantum Zeno and anti-Zeno effects is excellent, even discussing experimental tests of the idea.

August 23, 2009

The X-Prize for Quantum Computing, Why Not?

Filed under: Uncategorized — rrtucci @ 11:47 am

In his latest blog post, Jack Woehr ponders about the factors that might determine when quantum computers will become practical, to the point where people like him “can play with them”.

In my opinion, quantum computing research is currently mostly a government funded, academic endeavor. Private sector investment in QCs is currently almost nil. It will take an eternity to develop a large scale quantum computer this way. If the private sector were more involved, that would certainly speed up the development of QCs. So the question in my mind is, how can we encourage more private investment in QCs. This reminded me of the great automobile and airplane contests of the early 20th century (Great auto race of 1908, Orteig aviation prize of 1919), and of the current X prizes.

The first X Prize was the Ansari X Prize, announced in 1996, $10 million to the first private company to fly a man to near space (100 km altitude) (twice in two weeks, in the same “reusable” vehicle). 26 teams from around the world participated. It has been estimated that 10 X $10 million was invested in pursuit of the prize. The prize was won in 2004 by SpaceShipOne.

An important goal of the Ansari X prize was to encourage private investment in the space industry, so participants were not allowed to have any government funding.

Since the Ansari X prize, 4 more X prizes have been announced and still lay unclaimed (Google Lunar, Progressive Automotive, Archon Genomics, Northrop Grumman Lunar Lander) and 4 more are in the planning stages (Energy and Environment, Exploration, Education & Global Development, Life Sciences).

As of today, a search of the official X Prize website yields no hits for the keyword “quantum computer”. However, note that there is a very enticing “Propose an X Prize” button on the home page.

Other similar contemporary prizes: DARPA Grand Challenge, etc.

I end with an inspiring quote which I got from this news article. In an interview, Peter Diamandis, co-founder of the X prize, paid tribute to his friend and mentor, Arthur C. Clarke, by relating the following story about Clarke:

“He told me something once that I thought was incredibly valuable. He said, ‘Peter, there are three phases of a good idea. The first phase is, people tell you it’s a crazy idea, it’ll never work. The next phase is, they say, it might work but it’s not worth doing. And the third phase is when people tell you, “I told you that was a great idea all along.”‘

“The X Prize has definitely gone through those three phases, and I think of Arthur every time I talk about that. I’m thankful for his support … and also for his absolute passion regarding the need of the human race to evolve beyond the earth.”

August 19, 2009

Tocqueville

Filed under: Uncategorized — rrtucci @ 5:09 pm

In 1831, a 25 year old French aristocrat named Alexis de Tocqueville toured the young U.S. nation for 9 months. After this, he published his insightful thoughts and observations about the U.S. in a book entitled “Democracy in America”.

Jack Woehr, a long time denizen of the world of Computer Programming, has been recently touring the new world of Quantum Computing. He has just posted in his blog a 3 part series (Aug 11, 12, 19) on the ion trappers of the Colorado-NIST.

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.

August 13, 2009

Have a Hot Dog at the Ballpark of Quantum Computing

Filed under: Uncategorized — rrtucci @ 12:06 am

bogartA 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.

hot dog

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)

August 5, 2009

Why Quantum Computers–Galileo’s Telescope

Filed under: Uncategorized — rrtucci @ 12:42 pm

Check out:

Galileo’s Vision
Four hundred years ago, the Italian scientist looked into space and changed our view of the universe, By David Zax, Smithsonian magazine, July 2009

A beautifully written paean to the spirit of scientific discovery. Like Galileo’s telescope, quantum computers, once they are built, will open for us vast new vistas of the universe (into a new type of quantum devices, q. algorithms, q. computer programming, q. measurement theory, q. entanglement, q. decoherence, q. simulation, q. error correction, q. information theory, maybe even AI and q. gravity). Hopefully, QCs will make mankind wiser, kinder and stronger.

Blog at WordPress.com.

%d bloggers like this: