Quantum Bayesian Networks

April 29, 2014

A Tourist in the Country of Quantum Error Correction

Filed under: Uncategorized — rrtucci @ 6:45 pm

Up to this point in my life, I’ve only learned the most basic aspects about quantum error correction (QEC) and quantum error correction codes (QECC). The quantum circuits produced by my “circuit generator” programs like Lisbeth do not include QEC. To round out my education, I’ve been learning more about QEC for the past few weeks. Consider me only a passing tourist in the country of QEC.

In my opinion, your first tourist destination in the country of QEC, the very best place to start learning about QEC, should be Chapter 7 of Preskill’s Course 219. However, Preskill has decided to pull a joke on us by omitting all the figures from his Chapter 7 and, it appears, he has also forbidden all his students from posting them on the internet. Really funny John!

After Chapter 7, the best path for a curious tourist to take when visiting QEC country for the first time, becomes much more debatable. There are hundreds of papers on QEC to choose from, depending on your taste. The field has continued to grow steadily since it began in 1995 with twin papers by Shor and Steane.

I was raised as a Catholic (couldn’t help it. Italian surname). Somehow, the experience of being a tourist in the country of QEC reminds me of the experience of being a tourist in Vatican City. There is some beauty there (like in the Vatican art, for example), maybe even some saintly people, but there is much to criticize too.

Basic Idea Quite Trivial

QEC is a straightforward generalization of classical error correction (CEC). The basic idea behind both CEC and QEC seems pretty trivial to the casual observer and tourist.

In CCE, given a message consisting of k bits, you code it (i.e., expand it) to n bits, where n>k. The idea is to build a signal that has the original message somehow embedded in it, plus some extra redundancy. When this signal goes through a channel that adds noise to it, the noise does not degrade the original message excessively. Because of the redundancy, you are able to successfully retrieve (decode) the vast majority of the original message.

QEC is very similar to CEC except that you deal with vector spaces instead of strings of bits. A simplified picture that I like to use to explain QEC is as follows. Suppose your original message lives in a vector space, say a 2D plane, called the message plane. Suppose you code things by embedding the message plane into a bigger vector space, say a 3D space. Then suppose the 3D space goes through a noisy channel that rotates the message plane but does not change what is written in that plane. Let me refer to the rotation induced by the noisy channel as “the error”. Suppose you have a way of measuring the error, but only if it’s small enough. Suppose that once you know the error, you have a way of rotating the message plane back to where it was before it was rotated by the noisy channel. That’s the basic idea behind QEC.

Often Ugly, More Math Smoke Than Physics Fire

Although the basic idea behind CEC and QEC is pretty simple, each of them has produced a mountain of very murky mathematical papers that add almost nothing new to the underlying fundamental physics picture. The cause for this proliferation of non-fundamental papers appears to be this: your choice of code is heavily dependent on the noisy channel you are considering, and there is no known way of producing an optimal code for any given noisy channel. Furthermore, the number of possible noisy channels is infinite. Furthermore, sources of noise are often mysterious and not well understood so one often ends up assuming a noise model that may or may not be a close fit to reality.

Not Much Use For The QC Programmer

Future QCs will probably do QEC automatically for the QC programmer . He/she will barely be aware that it is going on behind the scenes…if it is going on at all. Indeed, if anyonic QCs are ever built, QEC will be totally unnecessary. Hence, learning about QEC might be fun but is largely unnecessary for QC programmers.

(It’s possible that anyonic QCs will never be built, but some very smart people —Kitaev, Preskill, Freedman and his Station Q acolytes working at Microsoft/UCSB—seem to believe that they will be.)

Pity the poor QC hardware designer who is betting that his QEC won’t bomb or be superseded

One of the places, although not the only one, in which QEC is used is in QC hardware design. The problem is that QEC is highly hardware dependent. For example, Martinis is currently trying to do QEC for his QC using something called surface codes, because he thinks that surface codes are well suited to his particular QC design and fabrication methods. However, surface codes might bomb (underperform) or be superseded by something better. For an anyonic QC design, no QEC will be required at all. However, an anyonic QC might prove impossible to build or bomb too. In fact, there are NUMEROUS ways of doing QEC besides surface codes and anyons. Some ways of doing QEC are better than others for a particular QC hardware design.

So, grumpy, reluctant tourist, is there anything flattering you have to say about QEC? Well, maybe… The ceiling art and sculptures ain’t too bad. It’s also

Broadly Applicable

QEC is broadly applicable. In fact, QEC is applicable anytime you want to encode a message prior to passing it through a noisy channel, and then decode the signal that arrives on the other side with minimum loss of the original message. Taking this picture to an extreme, Preskill and Hayden have written a paper in which they view a blackhole as such a noisy channel and they apply QEC to that situation, hoping to shed some light on the blackhole information paradox.

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.

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.

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

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

Blog at WordPress.com.

%d bloggers like this: