Quantum Bayesian Networks

March 22, 2019

Life in the time of the Bayesian Wars: Qubiter can now do Back-Propagation via Autograd

Filed under: Uncategorized — rrtucci @ 12:57 am

The main purpose of this blog post is to announce that the quantum simulator that I manage, Qubiter (https://github.com/artiste-qb-net/qubiter), can now do minimizations of quantum expected values, using Back-Propagation. These minimizations are a staple of Rigetti’s cloud based service (https://rigetti.com/qcs), which I am proud and grateful to have been granted an account to. Woohoo!

Technically, what Rigetti Cloud offers that is relevant to this blog post is

Hybrid Quantum Classical NISQ computing to implement the VQE (Variational Quantum Eigensolver) algorithms.

Phew, quite the mouth full!

The back-prop in Qubiter is currently done automagically by the awesome software Autograd (https://github.com/HIPS/autograd), which is a simpler version of, and one of the primary, original inspirations for PyTorch. In fact, PyTorch contains its own version of Autograd, which is called, somewhat confusingly, PyTorch Autograd, as opposed to the the earlier HIPS Autograd that Qubiter currently uses.

I also plan in the very near future to retrofit Qubiter so that it can also do back-prop using PyTorch and Tensorflow. This would enable Qubiter to do something that Autograd can’t do, namely to do back-prop with the aid of distributed computing using GPU and TPU. I consider enabling Qubiter to do back-prop via Autograd to be a very instructive intermediate step, the bicycle training wheels step, towards enabling Qubiter to do distributed back-prop via PyTorch and TensorFlow.

AI/Neural Network software libs that do back-propagation are often divided into the build-then-run and the build-as-run types. (what is being built is a DAG, an acronym that stands for directed acyclic graph). Autograd, which was started before Pytorch, is of the build-as-run type. PyTorch (managed by Facebook & Uber, https://en.wikipedia.org/wiki/PyTorch) has always been of the b-as-run type too. Tensorflow (managed by Google, https://en.wikipedia.org/wiki/TensorFlow) was originally of the b-then-run type, but about 1.5 years ago, Google realized that a lot of people preferred the b-as-run to the b-then-run, so Google added to Tensorflow, a b-as-run version called Eager TensorFlow. So now Tensorflow can do both types.

PyTorch and TensorFlow also compete in an area that is near and dear to my heart, bayesian networks. The original PyTorch and TensorFlow both created a DAG whose nodes were only deterministic. This is a special case of bayesian networks. In bnets, the nodes are in general probabilistic, but a special case of a probabilistic node is a deterministic one. But in recent times, the PyTorch people have added also probabilistic nodes to their DAGs, via an enhancement called Pyro (Pyro is managed mainly by Uber). The TensorFlow people have followed suit by adding probabilistic nodes to their DAGS too, via an enhancement originally called Edward, but now rechristened TensorFlow Probability (Edward was originally written by Dustin Tran for his PhD at Columbia Uni. He now works for Google.) And, of course, quantum mechanics and quantum computing are all about probabilistic nodes. To paraphrase Richard Feynman, Nature isn’t classical (i.e., based on deterministic nodes), damnit!

In a nutshell, the Bayesian Wars are intensifying.

It’s easy to understand the build-as-run and build-then-run distinction in bnet language. The build-then-run idea is for the user to build a bnet first, then run it to make inferences from it. That is the approach used by my software Quantum Fog. The build-as-run approach is quite different and marvelous in its own right. It builds a bnet automagically, behind the scenes, based on the Python code for a target function with certain inputs and outputs. This behind the scenes bnet is quite fluid. Every time you change the Python code for the target function, the bnet might change.

I believe that quantum simulators that are autograd-pytorch-tensorflow-etc enabled are the future of the quantum simulator field. As documented in my previous blog posts, I got the idea to do this for Qubiter from the Xanadu Inc. software Pennylane, whose main architect is Josh Izaac. So team Qubiter is not the first to do this. But we are the second, which is good enough for me. WooHoo!

PennyLane is already autograd-pytorch-tensorflow enabled, all 3. So far, Qubiter is only autograd enabled. And Pennylane can combine classical, Continuous Variable and gate model quantum nodes. It’s quite general! Qubiter is only for gate model quantum nodes. But Qubiter has many features, especially those related to the gate model, that PennyLane lags behind in. Check us both out!

In Qubiter’s jupyter_notebooks folder at:

https://github.com/artiste-qb-net/qubiter/tree/master/qubiter/jupyter_notebooks

all the notebooks starting with the string “MeanHamilMinimizer” are related to Qubiter back-prop

January 21, 2018

Life in the time of the Bayesian Wars: Clippy Strikes Back

Filed under: Uncategorized — rrtucci @ 7:42 pm

You can now add Clippy to any website, with his full panoply of adorable responses.

https://www.smore.com/clippy-js

(Thanks to Gavin Dekant for pointing this website to us.) First lines of website:

Clippy.js
Add Clippy or his friends to any website for instant nostalgia. Our research shows that people love two things: failed Microsoft technologies and obscure Javascript libraries. Naturally, we decided to combine the two.

So what does this have to do with Bayesian Networks?

In a previous blog post, I linked to a 1996 newspaper article that quotes Bill Gates revealing his strong interest in Bayesian Networks. But I didn’t mention in that blog post that this was not just a platonic love affair with Bnets which never went any further. By 1996, Gates was already actively channeling his love of B nets into backing real MS products, such as the Lumiere project, which brought to the world the first office assistant, in Office 97. Nowadays, Alexa, Siri, Google’s Office Assistant and Cortana are well known, commonplace office assistants, but MS was there first. Sadly, but characteristically, MS has fumbled the OA ball since then, and today, Cortana ranks last in usage among the big 4 OA’s. In fact, Cortana is almost dead today, now that MS has all but pulled out of the mobile phone OS and hardware businesses.

Next, I want to say more about the Lumiere project, a project remarkable for its great foresight, technical prowess and creativity, and for its instructive, amusing history with a dramatic, poignant ending.

Here is a nice article which backs up much of the history that I will recount next:

The Lumiere project: The origins and science behind Microsoft’s Office Assistant By Awesome-o | August 31, 2009

The office assistant created by the Lumiere project and first offered by MS in Office 97 was called Clippy. Clippy predicted its user’s next moves and needs so poorly that Office users soon started to hate and dread it, so much so that MS decided to turn it off starting with Office 2007. So poor Clippy was born about 20 years ago and he was killed when he was 10 years old.

Microsoft’s Lumiere project, headed by Eric Horovitz, produced the first in-house versions of Clippy, based on Bayesian Networks. This original Clippy learned from the user, it was trainable, so it was truly Bayesian. By all accounts, it worked really well. However, for the commercial version that appeared in Office 97 and thereafter, upper management insisted that the Bayesian heart of Clippy be replaced by a rule based system that could not learn from the user. The reason Clippy was crippled was not out of palace intrigue or corporate malice but simply that Office 97 already occupied too much space and the Office designers had to choose between including a full fledged Clippy or including some new, mundane word processing features, but not both, and they chose the latter. Hence, the original, by many accounts brilliant Clippy, was lobotomized before it was first released to the public.

But it gets better. Because of the Clippy fiasco, many people in 2007 considered the idea of an office assistant that could be trained by the user to be an impossible dream. How wrong they were! Look at the present. OA’s have not gone away. They keep getting better and more ubiquitous.

And, Clippy is back!

Bayesianism will never die. Author Sharon McGrayne has the same opinion and has written a wonderful popular science book explaining why:

“The Theory That Would Not Die: How Bayes’ Rule Cracked the Enigma Code, Hunted Down Russian Submarines, and Emerged Triumphant from Two Centuries of Controversy”, by Sharon Bertsch McGrayne

April 3, 2014

Life in the Time of the Bayesian Wars, Operation Lisbeth Unveiled

Filed under: Uncategorized — rrtucci @ 1:11 am

In previous blog posts, I described the race for Bayesian supremacy, the Bayesian Wars, that is currently rocking the computer world, especially in the areas that go by the buzz words of artificial intelligence, machine learning, big data, analytics, deep learning, etc. Since quantum computers can perform certain special but important tasks with a better time complexity than classical computers, it is inevitable that quantum computers will enter this fray as soon as they become available. Any empire that fails to acquire such quantum weaponry will surely succumb to its rivals. This blog post is a bird’s eye-view of Operation Lisbeth, my entrant into the quantum Bayesian weapons race.

Lisbeth is a software package, written in Java, for generating code that can be followed by a GATE MODEL quantum computer. The code generated by Lisbeth enables a QC to do certain AI related tasks, particularly those associated with classical BAYESIAN NETWORK calculations. The algorithms used by Lisbeth are all based on AFGA, a patented improvement of GROVER’S ALGORITHM. As with the original Grover’s algorithm, AFGA based algorithms are quadratically more efficient (measured by time complexity) than the best available counterpart classical algorithms.

SOFTWARE
Lisbeth comprises 5 Java applets. These applets are limited in the types of cases they can handle, but this is because they are meant for demonstration purposes only. The 5 applets are based on a Java class library that is much more general and malleable. The applets are:


  1. qSym-logo
    qSym calculates a symmetrized version of a given function.


  2. qMobius-logo
    qMobius calculates the Mobius Transform of a given function.


  3. qMargi-logo
    qMargi calculates a marginal probability distribution of a given probability distribution.


  4. qMean-logo
    qMean calculates the mean value of a given function.


  5. qJennings-logo
    qJennings allows one to discover from data the structure of a classical Bayesian network.


Source code can be found at my website www.ar-tiste.com

Check out my previous post entitled: “qJennings Thinks qWatson is a Moron“.

DOCUMENTATION
The algorithms used by the 5 Lisbeth applets and the interface of the applets are documented in the following 5 arXiv papers.

  1. “Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm”, by R.R. Tucci (abstract)
  2. “Quantum Circuit for Calculating Mobius-like Transforms Via Grover-like Algorithm”, by R.R. Tucci (abstract)
  3. “Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm”, by R.R. Tucci (abstract)
  4. “Quantum Circuit For Discovering from Data the Structure of Classical Bayesian Networks”, by R.R. Tucci (abstract)
  5. “qSym, qMobius, qMargi, qMean and qJennings, 5 Code Generators for Generating Quantum Circuits that Perform Some Artificial Intelligence Related Tasks”, by R.R. Tucci (Not in arXiv yet. You can download pdf here)


The Lisbeth software is protected by 4 pending patents, namely entries 8-11 in this list of patents owned by the Artiste company. Sorry for the patents, but my competitors are very dishonest and I have to protect myself.

Emblem for Operation Lisbeth, the goldfish with the dragon tattoo

Emblem for Operation Lisbeth, the goldfish with the dragon tattoo

October 12, 2013

Life in the Time of the Bayesian Wars, The Battle of PA Hill

Filed under: Uncategorized — rrtucci @ 11:46 pm

Secret message: Operation Lisbeth is going really well.

In a previous post entitled “Life in the Time of the Bayesian Wars“, I pointed out that “Companies like IBM, Google, Oracle, HP/Autonomy and SAP are in a fierce battle for the supremacy over the Bayesian sea lanes and trade routes to the New World.” and that “quantum computers have the potential to escalate that war significantly.” (I love quoting myself. I always agree with myself completely)

One particular battle in that war, a battle that is now raging at maximum intensity, is the one over personal assistants (PAs). PAs rely on a carefully curated database of facts called a knowledge base (KB). Some of the opening salvos of the Battle of PA Hill were made by Wolfram Research with its KB Wolfram Alpha, by IBM with its PA Watson and by Apple with its PA Siri. Since those initial volleys, the war has escalated. Now two search engine superpowers, Google and Microsoft/Bing, have joined the fray. Search engine (or social network) companies have a great advantage over IBM and other analytics giants, because they are in a better position to leverage the data of web pages plus user queries and personal data. Here is what these two search engine empires call their military operations:

KB PA
Google Knowledge Graph Android’s Now
Microsoft Bing Satori Cortana

Even though it might appear that Microsoft has just joined the fight, and doesn’t stand a chance against mighty Google, the truth is that MS has been involved in the PA battle longer than any other superpower. Google was founded in 1998, but as far back as 1996, Bill Gates was already telling everyone that someday B nets would be Microsoft’s secret weapon. Microsoft’s initial entry into the field was Clippy :), not the best of starts, although the story is that the B net part of Clippy was removed or badly crippled at the last moment, so Clippy is not a true representative of B net power, thank God. More recent PA attempts by Microsoft like their “Virtual Receptionist” are much more respectable.

Recently, the Redmond giant has uttered some battle cries that must be unnerving to their opponents. Microsoft has been bragging that their KB Satori (which means “understanding” and “enlightenment” in Japanese) and their PA Cortana (named after a holographic AI in the XBox video game Halo), both of which are soon to be unveiled in their full majesty, are more advanced Bayesian weapons, true death stars, than the weapons of their competitors.

Microsoft has faltered frequently and foolishly in the past ten years (with the exception of Kinetic which is pretty cool). Will Satori and Cortana finally take Microsoft out of the doldrums it’s been stuck in for the past decade and save cash hemorrhaging Bing? Or is it all bluster on their part and once again they will end up replaying the bungling role of the Brits in the charge of the light brigade? Stay tuned.

Cortana in video game Halo

Cortana in video game Halo

There are of course many elements to a KB and PA that have nothing to do with Bayesian analysis so some might say that us Bayesians take credit for everything. Okay, but you have to admit that important parts of the analysis done by PAs, either the current ones or the future versions, will be heavily based on Bayesian ideas.

Of course, I think a secret weapon that has the potential to change the outcome of this war is quantum computer AI. We’ll see.

Check out this nice war reportage from the front lines:

Microsoft’s Answer To Siri: Cortana, by Michael Endler (InformationWeek.com, September 13, 2013)

excerpts:

Cortana anticipation has been building again in recent days, after several purported Windows 8.1 images leaked online. Citing an inside source, ZDNet’s Mary Jo Foley subsequently reported that Microsoft is indeed readying a digital assistant technology, but that it will involve more than smartphones; rather, it will be a “shell” that harnesses the cloud to personalize and unify user experiences across Microsoft devices and services.

Apple’s Siri already follows voice commands and intelligently aggregates information in response to certain user queries. Android’s Google Now goes a step further in some ways; if the user chooses, it will scan emails, calendars and other data in order to learn more about the user and anticipate his or her needs. Cortana reportedly aims to outdo both competitors thanks to Microsoft’s Satori technology, which is currently used in Bing.

Bing senior developer Stefan Weitz added fuel to the fire in late July, telling CNET that Siri and Google Now “have a fairly shallow understanding of the world,” and that Microsoft will not ship a competitor until it can disrupt the market. “We could come out with something like [Siri and Google Now], but it wouldn’t be state of the art,” he said, noting that Satori’s brain is powered by more than 50,000 nodes in Microsoft’s cloud.

Microsoft founder Bill Gates and retiring Microsoft CEO Steve Ballmer also have chimed in with hints. In the memo that announced the “one Microsoft” restructuring plan, Ballmer wrote that the company’s technology “will understand people’s needs and what is available in the world, and will provide information and assistance.” He said Microsoft services will anticipate each user’s daily needs and provide insight when it’s needed.

Other great war reportage:

February 16, 2012

Life in the Time of the Bayesian Wars

Filed under: Uncategorized — rrtucci @ 8:23 pm

Check out this brief but excellent article

I.B.M.: Big Data, Bigger Patterns
By Quentin Hardy (New York Times, February 15, 2012)

Excerpts:

It’s not just about Big Data. For the big players in enterprise technology algorithms, it’s about finding big patterns beyond the data itself.

When it comes to algorithms, “if I can do a power grid, I can do water supply,

That kind of cross-pollination is reminiscent of the way Wall Street, starting in the 1990s, hired astrophysicists and theoretical mathematicians to design arcane financial products.

I.B.M., Mr. Mills said, is now the largest employer of Ph.D. mathematicians

In the last five years, I.B.M. has spent some $14 billion purchasing analytics companies, in the service of its Big Data initiative. “We look for adjacencies” between one business and another, said Mr. Mills. “If we can’t get an adjacency, we’ll never get a return.”

Bayesian Networks and MCMC (Markov Chain Monte Carlo) are some of the most important and powerful weapons for doing statistical analyisis of vast amounts of data, what the business world refers to as “data mining” or “analytics”. Companies like IBM, Google, Oracle, HP/Autonomy and SAP are in a fierce battle for the supremacy over the Bayesian sea lanes and trade routes to the New World.

As I have argued in many previous posts in this blog, quantum computers have the potential to escalate that war significantly. Quantum computers are ideal for doing the quantum version of Bayesian networks that gives this blog its name, and they can do MCMC much faster (see my software Quibbs) than classical computers.

July 3, 2014

Microsoft, the next Google?

Filed under: Uncategorized — rrtucci @ 6:47 pm

June must have been a rough month for the Google/D-Wave collaboration. A paper by Matthias Troyer et al which I quote below has been available at arXiv for a long time, in fact since January, but when it was published by Science magazine on June 19, all hell broke loose. The news media finally noticed the paper’s existence and came out in surprisingly large numbers to point out that the D-Wave computer had “flunked its first big test”. The Troyer et al paper concludes

“Using random spin glass instances as a benchmark, we find no evidence of quantum speedup when the entire data set is considered, and obtain inconclusive results when comparing subsets of instances on an instance-by-instance basis,”

Ouch, those words gotta hurt. Even cold hearted Scott Aaronson must feel a little sorry for D-Wave at this point.

To add Google-insult to Google-injury, the news media (including the NY Times, see here) has also started to trumpet the fact that, unlike doofus Google, Microsoft has been methodically subsidizing Gate Model QC research for about 15 years, and that research is beginning to bear fruit. Microsoft has a theoretical group called Station Q located at UCSB (Univ. of Calf. at Santa Barbara) doing research into anyonic QCs. They also have a small group of people writing generic gate model QC software. Also, for the last 15 years, they have been partially funding about a dozen experimental research groups throughout the world that are trying to build an anyonic QC. It appears that Robert Willet, working at the legendary Bell Labs in Murray Hill, N.J. (the little of it that still exists), is closest to building an anyonic qubit.

Last but not least, there is some evidence of civil Google-disobedience inside the very heart of Google country. Haker Dojo, the SETI Institute and the Googleplex (Google HQ) are all located in Mountain View CA (near San Francisco).

Haker Dojo has been hosting a MeetUp on quantum computing with roughly monthly events. For July 8, they have invited Nathan Wiebe from Microsoft, to speak about “Using quantum computers to learn physics”. This is a decidedly gate model talk, much to the consternation of Google. Like myself, Wiebe has written papers on using gate model QCs to do machine learning.

Meanwhile, SETI Institute is ringing another note of Google-disobedience by hosting on July 9 the first of what they hope will become an annual event, a FREE (as in beer) conference on Quantum Simulation. Their list of speakers for this year’s conference includes both gate-model and D-Wave partisans.

April 14, 2014

Can Quantum Computers Do Machine Learning in General in Polynomial Time?!!!

Filed under: Uncategorized — rrtucci @ 2:50 pm

In 2 recent papers (here and here), Seth Lloyd, Masoud Mohseni and Patrick Rebentrost have proposed a method for using a quantum computer to do “supervised machine learning”. Their papers have been trumpeted by Lloyd and the press as a significant breakthrough. On Jan 29, 2014, Lloyd gave a lecture about his algorithm at Google.

A nagging question that you might have upon browsing the 2 Lloyd papers is, how can this be? His algorithm has a sub-polynomial time complexity. Don’t the meatier machine learning problems have exponential time complexity, even on a quantum computer? After all, as Scott Aaronson states in the masthead to his blog, “quantum computers are not known to be able to solve NP-complete problems in polynomial time”.

An answer to this nagging question about Lloyd’s 2 papers was given in the following paper by a group of Microsoft researchers:

“Quantum Nearest-Neighbor Algorithms for Machine Learning”, by Nathan Wiebe, Ashish Kapoor, Krysta Svore (abstract)

The Microsoft paper points out in its introduction that the machine learning algorithm that Lloyd et al implement on a QC is known to perform poorly in many cases on a classical computer, so its quantum computerized version will perform just as poorly, except that it will produce the same crummy answer more quickly than a classical computer.

Let me explain briefly what the Microsoft paper says about the Lloyd et al algorithm.

Suppose you are given a point \vec{x}\in \mathbb{R}^N and 2 disjoint sets A and B of points in \mathbb{R}^N. The task solved by Lloyd et al is to assign \vec{x} to either A or B, the one which is “closest” to \vec{x}.
Two simple methods of doing this are:

  • Nearest centroid (NC) method: Calculate the centroid (i.e. mean) of A and of B. Then assign \vec{x} to the set whose centroid is closest to \vec{x}.
  • Nearest neighbor (NN) method: Find the point (called the nearest neighbor of \vec{x}) in A \cup B which is closest to \vec{x}. Assign \vec{x} to the set which contains that nearest neighbor.

Lloyd et al use the NC method, which often performs poorly, whereas the Microsoft group uses the NN method, which performs much better. The catch is that whereas the Lloyd NC method has a polynomial time complexity on a QC, the Microsoft NN method has an exponential time complexity on a QC. (In fact, the Microsoft NN method uses Grover’s algorithm. My Lisbeth software for doing AI on a QC also uses Grover’s algorithm.)

Assume that red data points are uniformly distributed over red areas and blue data points are uniformly distributed over blue areas. In these 3 examples, the Lloyd method would classify 50% of the red data points as blue whereas the Microsoft method would classify all red data points as red.

March 9, 2012

CMI, A Universal Translator Built by the SIT-ian Race

Filed under: Uncategorized — rrtucci @ 6:13 am

I am currently trying very hard to write a long, crazy paper on quantum SIT (Shannon Information Theory). So I’m thinking a lot about SIT these days. Here is a short “song” about the subject.

Sometimes two parties cannot understand each other without the help of an intermediary.

When the two parties involved are made of people, we human beings have invented clever devices and human professions whose goal is to intervene, and mediate a transaction between the two parties. For example,

  • devices – Rosetta stone, translation dictionaries, Google’s Translate, DARPA’s TRANSTAC, Universal Translator in “Star Trek” (and many other sci-fi stories), C3PO in “Star Wars”, dog2human translation devices in “Up”…
  • people – nearly simultaneous, human translators and interpreters of languages, sign language interpreters, marriage brokers and matchmakers, conflict mediators, divorce lawyers, judges…

When the two parties involved are objects instead of people, we often come up with devices to mediate transactions (e.g, electronic transistors, fluid valves, bridges,…)

Star Trek's Universal Translator (looks like a cordless microphone)

Since SIT (Shannon Information Theory) is an attempt to model in a very general way the communication of information between several parties, it’s not surprising that SIT has its own universal translator. Indeed, in SIT one defines a “universal translator function” called the CMI (Conditional Mutual Information), pronounced by me as “see-me”. CMI, denoted here by H(\underline{a}:\underline{b}|\underline{c}), is a real valued function with 3 slots filled by the random variables \underline{a}, \underline{b}, \underline{c}. (In what follows, we will indicate random variables by underlining.) In H(\underline{a}:\underline{b}|\underline{c}), \underline{a}, \underline{b} are the two parties that are having trouble understanding each other and \underline{c} is the mediator.

In classical SIT, one defines

  • the entropy (i.e., the variance or spread) of \underline{a} by
    H(\underline{a}) = \sum_a P(a) \log \frac{1}{P(a)},

  • the conditional spread (of \underline{a} given \underline{b}) by
    H(\underline{a} |\underline{b}) = \sum_{a,b} P(a,b) \log \frac{1}{P(a|b)},

  • the mutual information (MI) (i.e., the correlation) between \underline{a} and \underline{b} by
    H(\underline{a}:\underline{b}) = \sum_{a,b} P(a,b) \log \frac{P(a,b)}{P(a)P(b)},

  • the CMI by
    H(\underline{a}:\underline{b}|\underline{c}) = \sum_{a,b,c} P(a,b,c) \log \frac{P(a,b|c)}{P(a|c)P(b|c)}.

But note that H(\underline{a}), H(\underline{a}|\underline{b}) and H(\underline{a}:\underline{b}) can all be expressed in terms of the CMI. Indeed,

H(\underline{a}) = H(\underline{a}:\underline{a}|empty)

H(\underline{a}|\underline{b}) = H(\underline{a}:\underline{a}|\underline{b})

H(\underline{a}:\underline{b}) = H(\underline{a}:\underline{b}|empty)

So the spread, conditional spread and MI are all just special cases of CMI.

CMI has many nice properties, by which I mean that it satisfies some cool equalities (a.k.a. identities) and inequalities.

One identity that I find really neat is

H(\underline{a}|\underline{c}) = H(\underline{a}:\underline{x}|\underline{c}) + H(\underline{a}|\underline{x},\underline{c}).

I usually remember this one by the mnemonic :\underline{x} + |\underline{x} = 1. Basically, this identity is saying to me that the spread of \underline{a} can be decomposed into a correlation (of \underline{a} and \underline{x}) plus a conditional spread (of \underline{a} given \underline{x}).

Another cool identity satisfied by CMI is the chain rule, which says basically that the “:” operator behaves sort of like a differential operator.

CMI also satisfies a slew of cool inequalities; for instance, CMI >= 0, the data processing inequalities, Fano’s inequality, and subadditivity (a.k.a. the independence bound).

This blog post is just a quick introduction to CMI. For a more complete discussion of CMI, you might consult the SIT textbooks mentioned below.

Almost every statement in both Cover&Thomas’ book and Papa the Camel’s book, two great books on classical SIT, involves CMI (or one of the aforementioned special cases of CMI). Thus, CMI is pretty universal!

So far we have discussed classical CMI. One can also define a quantum version of CMI. The quantum version of CMI again shows up almost everywhere in Mark Wilde’s very complete book on quantum SIT. (By the way, Mark’s book is excellent and free.)

Quantum CMI can even be used to define quantum entanglement.

There are, however, correlations between 4 or more random variables that cannot be expressed in terms of CMI. (or can they be?) So the fact that most of the classical and quantum SIT books talk almost exclusively about CMI does not mean that CMI is the most general SIT function possible, and that all others can be expressed in terms of CMI. It just means that most of our current SIT-ing knowledge involves correlations of <= 3 random variables, because that is the lowest fruit in the tree of SIT. So there are limits to the universality of CMI. Our universal translator is not perfect, but it’s the best one we have on board the starship Enterprise.

Are you a CMI user, a.k.a. a CMI-an? (pronounced the same way as the word “simian”)

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.

August 28, 2009

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.

Blog at WordPress.com.

%d bloggers like this: