Quantum Bayesian Networks

February 27, 2010

Quibbs, a Killer-App for Quantum Computers

Filed under: Uncategorized — rrtucci @ 6:00 am

If you are familiar with the famous computer program WinBUGS, imagine running WinBUGS on a quantum computer. A QC can run WinBUGS (or, more precisely, a program with similar inputs and outputs as WinBUGS) quadratically faster than a classical computer. That’s what the computer program that I am currently writing, called “Quibbs”, will allow you to do. The word “Quibbs” is a contraction of the words “Quantum” and “Gibbs”.

My last 3 papers

describe in full detail the algorithm that will be used by Quibbs. The algorithm uses a combination of techniques, including Grover’s algorithm, quantum multiplexors, Szegedy operators, and quantum phase estimation.

Given a probability distribution (i.e., a classical Bayesian network) as input, Quibbs will generate a quantum circuit diagram (i.e., a sequence of one and two-qubit operations) that can be used to sample the probability distribution. Hence, borrowing the terminology of this taxonomy of quantum computing software, Quibbs will be a quantum “code generator”. I’ve previously written a quantum code generator called QuSann. In fact, Quibbs will share a Java class library with QuSann.

Quibbs will be a truly commercially-viable application of QCs, unlike that other less well known algorithm due to Shor. Shor’s algorithm, the greatest QC algorithm that will never be used. I say that because by the time QCs are built, the world will have already switched from RSA to a post-quantum cryptography, a type of classical cryptography that cannot be broken by any QC algorithm, including Shor’s. Okay, maybe saying that Shor’s algorithm will never be used is an ever-so-slight exaggeration. Shor’s algorithm will probably be used for calibration and benchmarking purposes, but certainly not for most commercial, scientific or engineering QC applications.

In the past, I’ve written many blogposts about why an application like Quibbs will be useful:

I’ve also written blogposts about

February 17, 2010

Experimental Quantum Computing, State of the Art

Filed under: Uncategorized — rrtucci @ 6:59 am

Many QC hardware designs are being tried at the present time. Eventually, one of those will prevail over all the others. Luckily, as a writer of QC software, I don’t need to worry too much about which hardware design will win out. That’s because my software is to a large extent “platform independent”. By this I mean that, because it outputs a sequence of one and 2-qubit gates, my software is compatible with any QC hardware design that implements the “gate-circuit model”, and that includes most QC hardware designs that experimentalists are currently trying to build.

Even though as a QC programmer I don’t need to worry too much about the details of QC hardware design, I still enjoy learning about it.

Check out:
Natural and artificial atoms for quantum computation
by Iulia Buluta, Sahel Ashhab, Franco Nori

This excellent paper describes the current state of the art of QC hardware for implementing the gate-circuit model.

(The paper says nothing about topological QCs. For info about topological QCs, visit the website of Michael Freedman’s group, “Microsoft Station Q”, at UCSB.)

(The paper says nothing about adiabatic QCs. For info about adiabatic QCs, visit D-wave’s website. )

The paper is easy to understand (even if you are not an experimentalist), informative, well-written, and short (just 5 pages of actual text. The paper contains a total of 21 pages, but pages 6-21 are references and pictures.) Since the paper is short, I recommend that you read the whole thing yourself, but here is a preview to pique your interest.

As its title suggests, the paper groups QC experimental approaches into two kinds: those that use natural atoms, and those that use artificial atoms. As the paper itself warns the reader, the fact that one particular experimental approach is at the present time more advanced than another, doesn’t necessarily mean that it is simpler, or better than the other, or that it will go farther in the future. It might just mean that it has been around longer.

The paper is structured as follows:

  • Introduction
  • Natural Atoms:
    Sec.1-Neutral Atoms
    Sec.2-Ions

  • Artificial Atoms:
    Sec.3-Superconducting Circuits
    Sec.4-Spins in Semiconductors (quantum dots and NV centers in diamond)

  • Epilogue
    Secs.5-8 Comparisons/Photons/Hybrids/Prospects

  • References

The references section at the end is a wonderful list, a treasure trove of experimental QC papers. For convenience, I cut and pasted just the references section into a simple text document (see here). I also created a text document with the references grouped by chapters (see here).

So how does one compare the current state of the art of various QC experimental approaches? You’ll have to read the paper in order to find out! The paper has informative tables that compare the same characteristics (about 30 of them) for each of 4 approaches (neutral atoms, ions, superconducting circuits, and spins in semiconductors). Out of those 30 characteristics, 4 of them are:

T1 (relaxation time) is the average time that the system takes for its excited state to decay to the ground state.
T2 (decoherence time) represents the average time over which the qubit energy-level difference does not vary.
Q1 (quality factor) represents the number of one-qubit quantum gates that can be realized within the time T1.
Q2 (quality factor) represents the number of two-qubit quantum gates that can be realized within the time T1.

In the final “Prospects” section, the paper concludes that:

In both natural and artificial atoms, almost all the basic requirements for realizing QC [83] have been demonstrated (i.e., (i) a scalable system with well-characterized qubits; (ii) initialization of the qubits; (iii) reasonably long decoherence times; (iv) a universal set of quantum gates; (v) measurement of the qubits)… The current challenges are to attain increased controllability (and minimize decoherence) and scale the existing systems to tens and hundreds of qubits and many-gate operations.

Qubit Mixology (i.e., 2-qubit gates)
I am particularly interested in how advanced each of the 4 approaches is in producing good 2-qubit gates. So I cut and pasted those sentences in the paper that address this issue: (To find out what are the references being alluded to by number, look in here, or in a pdf version of the paper.)

  • NEUTRAL ATOMS
    Excerpt

    The effective spin-spin interaction between two atoms in a double-well potential was used to demonstrate a two-qubit SWAP gate [17]. Furthermore, with polar molecules [20] or Rydberg atoms [21, 22] dipole-dipole interactions could be exploited for realizing two-qubit gates. Very recently, a CNOT gate using Rydberg blockade interactions has been demonstrated [23].

  • IONS
    Excerpt

    …quantum algorithms [36, 37],…

  • SUPERCONDUCTING CIRCUITS
    Excerpt

    …one can now realize simple algorithms [43],…

  • SPINS IN SEMICONDUCTORS
    Excerpt

    While Rabi oscillations have already been observed [60, 61], two-qubit gates have not yet been demonstrated (although, a SWAP gate between logical states has been realized [62]). However, long coherence times [63, 64] have been measured for both quantum dots (~microsec) and NV centers (20 ms) [65]. Moreover, for NV centers the entanglement between the electron and nuclear spins has also been shown [66].

Websites of Some Key Players
From the references of the paper, you can get a good idea of which are the most productive QC experimental groups in the world. Here are the websites of some of those groups:

Hey, Where is China and India?


UPDATE:
I was looking up SOME of the references in the Buluta/Ashhab/Nori review paper. And before I knew it, I ended up finding web links for ALL of the references. What a nerd!* So others don’t have to redo all this google searching, I’ve posted the results on my website. Just drag and drop any url from this text document into your search engine’s url input box, and presto! Whenever there is an arXiv version of the paper, I give a link to that. Otherwise, I give a less suitable link.

*This turned out to be simpler to do than I thought. I used Google Scholar (just the basic interface, not the advanced one). I pasted the title of each reference into the search box of Google Scholar. If there is an arXiv version of the paper, Google Scholar always gives it as the top entry of the search results; then you just drag and drop the title of that top entry to an open text editor window, and voilà, you get on your text editor window a perfectly formed url for the paper .

February 8, 2010

Post-Quantum Crypto

Filed under: Uncategorized — rrtucci @ 6:05 pm

The term “Post-Quantum Cryptography” is increasingly being used to describe the growing body of work on classical encryption systems which appear to be unbreakable (in polynomial time) by quantum (or classical) computers. A google search of this term already yields thousands of hits. In particular, note that “PQCrypto” conferences were held in 2006, 2008, and a third one is scheduled on May 25-28, 2010. Also, a compendium of articles in book form, entitled “Post-Quantum Cryptography” (Springer, 2009), edited by Bernstein, Buchmann, and Dahmen, has already been published.

The existence of PQ encryption systems makes quantum cryptography, and a quantum internet, OBSOLETE technologies.

My previous posts on quantum cryptography

February 5, 2010

Likely: Wall Street Firms Will be Early Adopters of Quantum Computers

Filed under: Uncategorized — rrtucci @ 11:35 pm

Imagine an institution that

  • is waging war against its rivals
  • has deep pockets and does not shy away from buying any gadget that might give it even a slight advantage over its rivals
  • will gain a significant advantage over its rivals if it can speed up its response time
  • must predict the future in order to respond

Well, a very effective way of predicting the future is to use Bayesian statistical techniques. An important calculational tool of Bayesian statistics is Markov Chain Monte Carlo (MCMC). Quantum computers can do MCMC quadratically faster than classical computers. (See my post on the quantum computerization of MCMC).

Hence, any institution that fits the above bill will love QCs, because QCs will help it achieve its goals better.

One type of institution that fits the bill is the Department of Defense, when doing time-constrained target discrimination, as in, for instance, ballistic missile defense (Star Wars). (I’ve talked about this before in my post about military applications of QCs.)

But another type of institution that fits this bill just as well are Wall Street firms.

For evidence that financial engineers in Wall Street firms use Bayesian/MCMC techniques, see

  • A search of the wilmott.com domain for the keyword “MCMC”.
  • A search of the wilmott.com domain for the keyword “Bayesian”.
  • A search of the wilmott.com domain for the keyword “Monte Carlo”.
  • My previous post on Emanuel Derman’s book about quants.

Hence, it is not too far-fetched to predict that Wall Street firms will be early adopters of QCs.

Since many of the quants in Wall Street are physics or mathematics Ph.D.s well acquainted with the power and beauty of quantum mechanics, and since QCs will greatly increase a quant’s effectiveness, one hopes that quants will be keen on QCs. Just think of it: “Quants, the Next Generation”, or “Make Way For the QuQus (Quantum Quants)”. Okay, maybe it’s better not to think of it too much. I wonder if quants can help to persuade investors to invest in quantum computing.

At the present time, there is only one private company, D-Wave, doing full-time QC research, so more private QC research and development is sorely needed. It will take much more than one measly company to reach the critical mass of QC companies that will be needed to launch a self-sustaining QC industry.

Our Man in Havana, or a Physicist Working in Wall Street

Filed under: Uncategorized — rrtucci @ 3:24 am

Category: book report 🙂

Check out this autobiographical book:

My Life as a Quant: Reflections on Physics and Finance
by Emanuel Derman
(Wiley, 2004)
Amazon link for book (high Amazon rating of 4 out of 5 stars, 80+ reviews)

This memoir recounts the professional history (also a smattering of technical stuff and philosophy but very little about his personal, family life) of a person who ended up in a career quite different from the one he had originally intended. (As many of us do!) It was a painful journey, but he ultimately found a comfortable niche for himself. Along the way, he learned an important lesson in humility; that he is no Feynman, but that you can live a fulfilling, productive life without being one.

If you are currently an undergraduate or graduate student in physics, this book will be particularly illuminating to you. It will give you an idea of what life is like as a physics postdoc, what are your chances of getting a tenured academic position in physics, and what to expect if you give up on your quest for such a position and decide instead to pursue a career as a quant in Wall Street.

Reading this book will give you a flavor of the day to day life of a quant. A quant (quantitative analyst) is a highly paid “financial engineer” that invents and codes computer models that aid a Wall Street firm manage risk and assign prices to its financial products (especially options and the more general derivatives). A pinnacle of financial engineering math is the Black-Scholes-Merton model, which uses “Ito stochastic calculus” to derive an algorithm for pricing options. Sholes and Merton got the 1997 Nobel Prize in Economics for this model. Black, with whom Derman collaborated, would have shared in the Nobel prize, but he died a few years before 1997.

Derman is a very clear writer and explainer. Moreover, he has an exceptional memory, so he is able to recall many interesting details about events that occurred to him decades ago. For example, even after having worked in finance for more than two decades, he still remembers his physics very well, and he can recall a wealth of detail about the people that he encountered during his former life as a physicist.

Derman was born in 1946. He was raised in South Africa and did his undergraduate studies at the University of Cape Town. The book starts on the day he arrived at Columbia University (New York City) to do graduate studies in Physics. Here are the stages in Derman’s life that he touches upon in this book

1966-1973: graduate student at Columbia University.
1973-1975: postdoc at University of Pennsylvania
1975-1977: postdoc at Oxford University
1977-1979: postdoc at Rockefeller University
1979-1980: assistant professor at University of Colorado at Boulder
1980-1985: Bell Labs
1985-1988: Goldman Sachs
1988-1989: Salomon Brothers
1990-2002: Goldman Sachs
2002-present: Professor of financial engineering at Columbia University. Also partner of a hedge fund (Prisma Capital Partners)

Derman’s Ph.D. thesis and post-doctoral work was in High Energy Physics, Phenomenology (Deep Inelastic Scattering, Weinberg Salam Model).

He found Bell-Labs to be very bureaucratic. At Bell Labs, he worked for a group (Area 90) whose leader was a doltish bully. Area 90 was quite different from the legendary nirvana, Area 10, that garnered all the Nobel prizes. Even though Derman found his stint at Bell Labs stifling and depressing for the most part, at least he was able to use that time to learn much about programming, and to initiate a love affair with this art form that continues to this day.

Derman started his quant career relatively late in life, at age 40. As a physicist, he endured the stressful, uncertain, nomadic life style of a postdoc, and he witnessed fierce, seething rivalries between physics professors. But Wall Street was not a harmonious paradise either. Especially cut-throat were the people at Salomon brothers. Most people that work in Wall Street are extremely ambitious, so it’s common for them to change jobs very frequently (e.g., every 6 months) in order to move upwards. Quants and other technical geeks are looked down on by traders and executives.

The book was published in 2004. It’s not particularly prescient about the 2008 economic disaster, although it does repeatedly point out the limitations of financial models. In my opinion, Quants should have rung the alarm bells more forcefully. However, I doubt that this action alone would have prevented the disaster. Most quants have only very limited decision making power in Wall Street firms. Even if the power wielding executives at the top had been warned more forcefully by the quants, I doubt that the execs would have listened.

  • Wikipedia on Derman
  • Derman’s blog at wilmott.com
    (Paul Wilmott, mathematics Ph.D., is another practitioner and pedagogue of financial engineering. From Wikipedia article: “Wilmott magazine has the distinction of having the highest subscription price of any magazine” 🙂 )

Blog at WordPress.com.

%d bloggers like this: