Quantum Computer Programmers Get Some Respect from NIST

One of the best quantum computers currently in existence is the one built by the Colorado-NIST Ion Storage Group, headed by David Wineland. Multiple Beryllium ions are trapped in an electrostatic ion trap at very low temperature and pressure. Then the quantum states of the ions (=the qubits) are manipulated with laser beams. This QC design is very intricate and difficult to build and operate successfully. Hopefully, someday we will discover simpler QC designs. But, for now, this one is fine because, despite its complexity, it works! It is teaching us many valuable lessons that will probably be applicable to future designs. And, best of all for aspiring quantum computer programmers like me, the device with 2 qubits has been made to run 160 different (mind numbingly simple) quantum computer programs.

What the public is saying:

• Bery Cool
• No way! You mean you actually move ions around physically from chamber to chamber…Rube Goldberg would be proud of you.
• It’s ugly as hell, but it works, dammit
• What do you mean “programmable”? You mean you load proofs of complexity theorems into it?
• No backwards compatibility with Windows XP. Spooky, how well it works with Vista.
• MIT quantum computer = { }
• Caltech quantum computer = { }
• Perimeter Institute quantum computer = { }

More References:

• NIST press releases, here
• Jack Woehr’s prize winning report of his NIST visit, here
• arxiv publications with Wineland as coauthor, here

• home page of NIST Ion Storage Group, here

Solving Systems of Linear Equations With a Quantum Computer

Check out this blog post by Eric Drexler (nanotech guru, author of “Engines of Creation”)

Useful Quantum Computers Are 200 Years Away

When will quantum computers (with a useful number of qubits) be built? Depends. The time it takes to travel from location A to location B depends on how fast you are willing to drive.

Example of Fast Driving:
Look at this timeline of the Manhattan Project.
Excerpt:

• 1939 August 2: Albert Einstein signs a letter authored by physicist Leo Szilard addressed to President Franklin D. Roosevelt, advising him to fund research into the possibility of using nuclear fission as a weapon in the event that Nazi Germany may also be conducting such research.

• 1945 August 6: “Little Boy”, a gun-type uranium-235 weapon, is used against the city of Hiroshima, Japan.
• 1945 August 9: “Fat Man”, an implosion-type plutonium-239 weapon, is used against the city of Nagasaki, Japan.

That’s 6 years between the time when nobody had the faintest idea of how to build an atomic bomb, or purify U-235 or Plutonium-239 (Plutonium hadn’t even been discovered yet. That happened in Feb 1941), to the time when 2 very different bomb designs were demonstrated to work all too well.

To be honest, this is an unfair comparison. These people didn’t have transistors or integrated circuits or personal computers or the internet. Not even TVs. Their laboratory tools were quite primitive by today’s standards. Building a quantum computer with our modern tools should be much easier.

Example of Very Very Slow Driving:
The current global efforts to build a quantum computer, which are expected to take about 200 years to achieve a product.

Quantum Computing Primer for Spies

An alien space ship, no. An American sacred Kaaba, no. National Security Agency Headquaters at Fort Meade, Maryland, yes

You are an NSA analyst working at NSA headquarters, a sinister looking, shinny black box mega-building at Fort Meade, Maryland. Then, one day, you wonder…

“What should a master spy like me know about quantum computing?”

So you boot up your top secret ECHELON terminal, giving you instant access to Google++: all Google info (including 10 million digitized books), all public and confidential records of all US federal and state agencies including the FBI and CIA, and some foreign ones (Interpol, MI5) too, plus a large fraction of all the electronic communications (emails, internet searches, websites, cell and land line telephone calls, faxes, credit card transactions, radio and TV transmissions, cell phone GPS chip transmissions) of the entire planet for the last 5 years. Unfortunately, with so much data at hand, your ECHELON search takes 10 minutes and yields 5 million hits. You curse at the ECHELON software…

“The ECHELON search engine sucks. How can I possibly sift through 5 million records?”

But it’s your lucky day, and serendipity or a software glitch or a software Trojan has placed this blogpost at the top of the list. So here is what you need to know.

• Quantum computers can decode RSA coded messages quickly using something called Shor’s algorithm. There are known classical encryption systems that cannot be broken by a classical or quantum computer, so the NSA should shepherd the US commercial sector into switching to one of those encryption systems long before quantum computers become available. There is talk of a quantum internet, but that’s just snake oil.
• One popular technique used in data mining is called MCMC (Markov Chain Monte Carlo). MCMC can be done on both classical and quantum computers, but quantum computers are typically quadratically faster at MCMC than classical ones. (Some Nerd speak: The quantum computerized version of MCMC is an application of Grover’s algorithm, quantum phase estimation, and the Szegedy quantum walk operators). The bottom line: NSA can data-mine ECHELON much faster with quantum computers than with classical ones.

Spurred by this blog post, an important thought now crosses your mind:

“I’m hungry. It’s 4 o’clock. Time to go home.”

Maybe you’ll try tomorrow to convince your boss to fund this quantum data-mining stuff. Oh, you forgot where you parked today, and the parking lot outside has a daunting 18,000 parking spaces. No problem. Just ask ECHELON. She regularly monitors the transmissions from the GPS chip in your car. A second later, she responds:

“Agent 156 car at parking space 51ew of NSA Meade facility”

Secret agent man, secret agent man
They’ve given you a number and taken away your name

Experimental Physics Informatics and Quantum Computing

Some important ongoing and future physics experiments have to deal with VERY LARGE data sets. I give some examples below, for Astronomy and Particle Physics. Companies like Google, Microsoft and Facebook, are very interested in such experiments, because they too are users of large data sets, and they realize that scientists often invent brilliant tools and techniques in order to accomplish their scientific goals (like Berners Lee at CERN did when he invented the World Wide Web).

My usual mantra: These large data sets beg analysis by parallel processors, using the tools of probability and statistics. Quantum computers, because of their intrinsically parallel processing and probabilistic nature, are ideally suited to meet this challenge. One specific way in which quantum computers can aid in the analysis of large data sets is MCMC (Markov Chain Monte Carlo). Methods are already known (this is not a pipe dream) for doing MCMC on a quantum computer, much faster than on a classical computer.

---

ASTRONOMY

• Earth Telescopes

  (1)Pan-STARRS An array of 4 telescopes located in Hawaii. Its expected completion date is 2012. Will photograph 3/4 of celestial sphere (fraction visible from Hawaii) every four days. Will compare observations at different times to detect differences. The project is expected to generate 10 Terabytes data/day (assuming 10 hrs. of operation/day)

• Space Telescopes

  (1)NASA missions involving space based telescopes (with region of electromagnetic spectrum and launch date): Hubble (Visible)1990-, Compton (Gamma-ray)1991-, Chandra (X-Ray)1999-, Spitzer (IR)2003-, WMAP (Microwave)2001-

Other relevant links

• Excellent blog called The AstroStat Slog, about uses of Statistics in Astronomy.
• A paper that surveys AstroInformatics up to now, and makes recommendations for the future: The Astronomical Information Sciences: A Keystone for 21st-Century Astronomy

---

PARTICLE PHYSICS

(1)LHC Computing Grid LHC = Large Hadron Collider, part of CERN laboratory, located near Geneva, Switzerland. Hopefully will start operating this year. Wikipedia quote: “The project is expected to generate 27 Terabytes of raw data per day, plus 10 Terabytes of “event summary data”, which represents the output of calculations done by the CPU farm at the CERN data center.”

---

China and India, Quantum Computing’s Two Slumbering Giants

YAP= Yearly ArXiv Production
I did the following simple experiment.

Experimental procedure:
I used Google Scholar with the following parameters:
Keywords: India “quantum computer”
Publication: arxiv
Date: 2000 to 2000
Then I recorded the number of hits, calling this number a YAP.
I repeated this with “India” replaced by “China”, “Japan”, no nation specified, and for years other than 2000. This yielded GRAPH 1. (Today is Sat. Oct.31, 2009 so the 2009 numbers do not include the whole year.). I also did searches with “quantum computer” replaced by “string theory”. This yielded GRAPH 2.

Conclusions:
For quantum computing, worldwide YAP peaked on 2004, waned for the next 4 years, but has gone back to its 2004 level this year. 2009 has been a pretty good year.

In 2009, for quantum computing, Chinese YAP was slightly higher than Japan’s, and twice that of India, but still relatively small (only 1/7 of total).

My Opinions:
Chinese and Indian performance in the QC race is, so far, very low spirited. Considering that both countries have about 1.3 billion inhabitants, quantum computing YAPs (for this year, up to Oct 31) of 31 papers for China and 15 papers for India, are indefensibly low. Also, some of the Chinese YAP is of poor quality because it involves their efforts to build a boondoggle quantum Internet and quantum cryptography.

Why are China and India under-performing? I don’t know enough about those countries to answer this question authoritatively. However, I would advise Chinese and Indian leaders to put more heart into their QC efforts, and NOT to repeat the flaws of the current American QC program; instead, look at the history of Bell Labs and Silicon Valley for inspiration. Also, a Chinese or Indian X-prize for quantum computing might work wonders for their countries.

The MCMC Revolution

Check out
The MCMC Revolution
Persi Diaconis, Bull. Amer. Math. Soc. 46 (2009), 179-205.

This paper was a lot of fun to read. Though Diaconis is a mathematician, a large fraction of the paper is written at a level understandable by most persons with an undergraduate degree in science or engineering. (Just skip those parts that lie beyond your level). The goal of the paper is to introduce its readers to MCMC (Markov Chain Monte Carlo), and to make them appreciate the enormous usefulness of MCMC in most scientific fields.

Those who read this blog know that the most efficient way of doing MCMC is with a quantum computer. Although the paper is only about s-l-o-w poke classical computers, I still recommend it, so you can see how our dads did things

The paper motivates the mathematical theory of Markov chains using two cool examples.

(1)(a Metropolis sampling example) A real life detective story. The California prison system asked the Stanford Statistics Department to help it decypher some coded messages that it had intercepted. The messages had been written by a prison inmate using non-standard symbols (in what is called a substitution cypher). A regiment of 2 Stanford students was assigned the task of changing this light bulb. The students used Metropolis sampling with a code “plausibility” measure equal to —censored—. I won’t give away the punchline.

(2)(Monte Carlo integration example) Consider possible placements of hard discs of radius inside the unit square. The discs must not overlap and must be completely contained in the unit square. The centers of the discs are described by a point . Let be the subset of containing all possible placements of discs of radius . The goal is to integrate some function over the region .

According to Diaconis

“To someone working in my part of the world, asking about applications of Markov chain Monte Carlo (MCMC) is a little like asking about applications of the quadratic formula. The results are really used in every aspect of scientific inquiry. The following indications are wildly incomplete. I believe you can take any area of science, from hard to social, and find a burgeoning MCMC literature specifically tailored to that area.”

The paper ends with a list of references suggested for further reading, references that describe the application of MCMC in the fields of (1)Chemistry and Physics (2)Biology (3)Statistics (4)Group Theory (5)Computer Science (theory).

Persi Diaconis is a distinguished professor in the Department of Statistics at Stanford University. Since his teens, he has been a skillful performer of magical card tricks. His wife, Susan P. Holmes, is also a distinguished professor in the same Stanford department, where she teaches, you guessed it, applications of MCMC to Biology.

New Quantum Computer Algorithm is So-so

Alas, my recent paper on Quantum Gibbs Sampling has so far failed to generate any interest in the scientific or programming worlds . However, it occurs to me that the paper might still have a successful career in the entertainment world, as a source of themes for comic book writers . Some possible themes that come to mind

• Mr. Spock, Vulcan, Devises New Gibbs Sampling Algorithm For Quantum Computers

• New Gibbs Sampling Algorithm Endows Quantum Computers with SuperPowers

• New Gibbs Sampling Algorithm Allows Quantum Computers to Think Like God

• New Gibbs Sampling Algorithm Created at Vulcan’s Forge

• New Gibbs Sampling Algorithm Created at Neptune’s Furnace

• One Quantum Computer Algorithm to Rule them All

• Lex Luthor Buys Exclusive Rights to New Gibbs Sampling Algorithm For Quantum Computers

• Prof. Moriarty Buys Exclusive Rights to New Gibbs Sampling Algorithm For Quantum Computers; Sherlock Holmes Said to be Depressed About Sale and Taking Laudanum

• Mycroft Holmes Buys Exclusive Rights to New Gibbs Sampling Algorithm For Quantum Computers; Beats His Brother, Sherlock Holmes, to the Sale

• Lex Luthor: “Fellow Super-villains, Solving Systems of Linear Equations is for Ninnies; Give Me Faster Gibbs Sampling, and I WILL CONQUER THE WORLD!” (yikes)

Quantum Computerization of MCMC

Typical Americans watch Apollo 11 moon walk on TV, real time (except for 2.5 second time delay needed for light signal to make earth-moon round trip)

1969- Apollo 11 mission, Neil Armstrong and Buzz Aldrin become the first and second man to walk on the surface of the moon.

Apollo 11 mission:
Duration- 8 days round trip.
Lunar Module (lunar lander)- the Eagle.
Touchdown site- Sea of Tranquility.
Neil Armstrong: “Houston, Tranquility Base here. The Eagle has landed.”
Neil Armstrong: “That’s one small step for [a] man, one giant leap for mankind”
Neil Armstrong has been quoted as saying that at the time he thought his chances of surviving the Apollo 11 mission were 50/50. Yet he did his job without flinching. Truly a man made of the right stuff!

Roaring Saturn V rocket propels Apollo 11 crew towards the heavens

2009 is the 40th anniversary of the Apollo 11 mission. It’s also the zeroth anniversary of my new paper on Quantum Gibbs Sampling. One small step for mankind, one giant leap for Bob (me).

My new paper (Ref. Tuc3 below) extends 2 previous papers of mine (Tuc1, Tuc2). Papers by other workers that particularly inspired me in this work are Refs. Som1 and Woc1 on quantum simulated annealing. All these papers fall under the general category of quantum computerizations of MCMC (Markov Chain Monte Carlo), a subject that I find extremely interesting. Why?, you ask (Okay, maybe you didn’t ask, but let me tell you anyway).

MCMC allows you to sample probability distributions. If you’ve ever needed to sample a simple probability distribution defined for in a real interval, you are probably familiar with the inverse transform method, Unfortunately, this method requires finding the cumulative probability distribution and inverting it, a task which is very difficult for many probability distributions. Suppose, for example, that your probability distribution is defined for , where each can assume values in a discrete set . (This can be described as a classical Bayesian network). Unfortunately, the inverse sampling method does not work for sampling most B. nets. One method that does work and is very popular is called MCMC (this includes Gibbs sampling, Metropolis-Hastings sampling and Simulated Annealing). If you are new to this subject, a wonderful introduction can be found in Chapter 4 (the section entitled “Monte Carlo Methods”) of David MacKay’s magnificent, highly intuitive book entitled “Information Theory, Inference, and Learning Algorithms” (available for free in electronic pdf form, or for money in paper form).

Why is sampling a probability distribution (i.e., a classical B. net), where lives in a multidimensional domain, so difficult? A domain with a large number of dimensions is huge. The majority of the samples come from those regions of the domain where the probability is high. But finding those regions requires that we explore the entire domain!

Why is sampling a probability distribution useful? If you have a sample of points for , distributed according to , then you can evaluate approximately the expected value of any function using

You can also approximate probability distributions , where is the subset of which constitutes your Hypothesis variables, and is the subset of which constitutes your Evidence variables. Such Bayesian probability distributions are very useful for making inferences (in AI, bioinformatics and data mining, for example).

Why is quantum computerization of MCMC useful? Speed! Typically, for any , a quantum computer can sample a B. net with precision in steps, whereas it takes a classical computer steps to achieve the same precision. Here is the distance between the two largest eigenvalue magnitudes of the Markov chain being used.

References:

• Tuc1- R.R Tucci, “Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network” arXiv:0811.1792

• Tuc2- R.R Tucci, “Code Generator for Quantum Simulated Annealing ” arXiv:0908.1633

• Tuc3- R.R Tucci, “Quantum Gibbs Sampling Using Szegedy Operators” arXiv:0910.1647

• Som1- R. Somma, S. Boixo, H. Barnum, “Quantum Simulated Annealing” arXiv:0712.1008

• Woc1- Pawel Wocjan, Anura Abeyesinghe, “Speed-up via Quantum Sampling” arXiv:0804.4259

Bioinformatics and Quantum Computing

Check out
“Your Chance to get Seriously Wealthy from the Next Wave of Computational Biology”
Penny Sleuth, Aug 28th, 2009, by Patrick Cox

An excerpt:

As more powerful computing comes online, the pace of bioinformatics discovery will accelerate. Quantum computing, because it is particularly suited to sorting out cell biology, will enable a “quantum” leap in understanding.

I totally agree with Mr. Cox’s prediction. We live in an era of large data sets. These large data sets beg analysis by parallel processors, using the tools of Probability and Statistics. Quantum computers, because of their intrinsically parallel processing and probabilistic nature, are ideally suited to meet this challenge. One specific way in which quantum computers can benefit bioinformatics: A commonly used tool in bioinformatics is MCMC (Markov Chain Monte Carlo). Methods are already known (this is not a pipe dream) for doing MCMC on a quantum computer, much faster than on a classical computer. (I will discuss this in more detail in my next post, entitled “Quantum Computerization of MCMC”). So using a QC will help bioinformaticists do their job more quickly.

Further reading for the bioinformatically challenged (like me):

• Bioinformatics Primer
• Books for Bioinformatics Beginners, from an excellent blog called Genetic Inference