Quantum Bayesian Networks

November 27, 2009

Proposing to Spies

Filed under: Uncategorized — rrtucci @ 5:06 am

(thanks to Quantum Pontiff’s blog for alerting me to this story)
The US government agency known as DARPA (also named ARPA at various times during its history) was founded in 1958, as a response to the Soviet launching of Sputnik in 1957. DARPA’s mission is to develop defense related technologies. Its current budget is about 3.2 billion dollars/year. More recently, an agency called IARPA was founded in 2006 to develop technologies that might be of use to the intelligence community (i.e., to spies). The budget of IARPA is classified, although it is thought to be smaller than that of DARPA.

IARPA’s website here. From their website, we learn that:

In the recent past, IARPA has held two solicitations, now closed, having to do with quantum computer hardware: (BAA=Broad Agency Announcement)

  • Advanced Material and Fabrication for Coherent Superconducting Qubits Program
    BAA Release Date: July, 2008
    BAA Second Announcement Date: March, 2009
    Proposal Due Date: July 31, 2009

  • Multi-qubit Coherent Operations (MQCO) Program
    Release Date: August 14, 2009
    Proposal Due Date: October 13, 2009

Now IARPA seems to be mulling over a future program dedicated to quantum computer software. According to this page of their website, on December 17, 2009, IARPA will hold a so called Proposers’ Day for a future program called its Quantum Computer Science (QCS) Program, IARPA-BAA-10-02.

The goal of the QCS program is to develop “quantum programming environments, as well as tools for generating, analyzing and optimally selecting quantum error correction and control protocols.”

From the program number IARPA-BAA-10-02, one ventures to guess that proposals will be due sometime between the end of February and the “ides” of March, barring any unforseen delays or cancellation.

Up to now, quantum computer programming (not just pseudo-code but real code) has been largely neglected by federal funding agencies. As evidence of this, look at the Quantum Algorithm Zoo, or ask yourself how many conferences have been held to date, that were dedicated even partially to quantum computer programming: zero, compared to dozens dedicated to quantum complexity and hardware. This prejudice against software seems quite illogical, considering the fact that quantum computers will be useless without good software. Good software will no doubt play a major, fundamental role in the development of quantum computers, the same way that it has played a major, fundamental role in the development of personal computers and the Internet. I hope this QCS program is a sign that the attitude of federal funding agencies towards quantum computer programming has begun to change.

November 20, 2009

Quantum Computer Programmers Get Some Respect from NIST

Filed under: Uncategorized — rrtucci @ 4:28 pm

I thought I was ugly, but then I realized I could have been born with this man's face. Some people get no respect, even after they're dead.

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 ion trap at very low temperature and pressure. Then the quantum states of the ions 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?
  • 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

November 15, 2009

Solving Systems of Linear Equations With a Quantum Computer, Sort of

Filed under: Uncategorized — rrtucci @ 3:06 am

Check out this blog post by Eric Drexler (nanotech guru, author of the famous book “Engines of Creation”, author of the excellent blog Metamodern)

Dr. Drexler’s blog post concerns the paper

“Quantum algorithm for solving linear systems of equations”(v1 title)
“Quantum algorithm for linear systems of equations”(v3 title)
by Aram W. Harrow, Avinatan Hassidim, Seth Lloyd

November 10, 2009

Useful Quantum Computers Are 200 Years Away

Filed under: Uncategorized — rrtucci @ 6:33 pm

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.

  • 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 lasers or 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.

November 6, 2009

Quantum Computing Primer for Spies

Filed under: Uncategorized — rrtucci @ 7:37 pm


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

November 4, 2009

Experimental Physics Informatics and Quantum Computing

Filed under: Uncategorized — rrtucci @ 7:11 pm

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.


  • 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


(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.”

November 2, 2009

China and India, Quantum Computing’s Two Slumbering Giants

Filed under: Uncategorized — rrtucci @ 4:40 am

Addendum: I’ve written a new, updated edition of this post. Click here to see it.

AP= 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.

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.

Blog at WordPress.com.

%d bloggers like this: