# Quantum Bayesian Networks

## January 31, 2010

### Why String Theorists Should Switch Fields to Quantum Computing

Filed under: Uncategorized — rrtucci @ 5:58 pm

String Theorists who switch to quantum computing can look forward to the following perks:

• No Loop Gravity crackpots to drive you crazy.
• No Peter Woit telling everyone that you are a B.S. artist.
• No need to reassure people that you are not at all like Lubos Motl or any other Stalin wannabes.
• Unlike string theorists, quantum computerists are funded by the Military. The Military believe in you (or your lethal potential).
• You will finally stand out: Instead of competing against Ed Witten and the likes of him, you’ll be competing against people about as intelligent as Ed Witten’s hamster.
• Takes 2 weeks instead of 1 decade to master the subject.
• Same as in String Theory: no need to do Physics if you don’t want to (just do quantum complexity theory).
• Only 3+1 dimensions.
• Only one particle, the qubit.
• More than one machine to do experiments on. Machines not as big as a city.
• Predicts something.
• We also have multiverse crackpots/mystics.
• If you can’t get a job in the Physics department, you can always get one in the Mechanical Engineering one. (If you don’t believe me, check out Seth Lloyd)

## January 28, 2010

### My Secret Life as a Captain of the Grover’s Algorithm

Filed under: Uncategorized — rrtucci @ 7:32 pm

The Knock Nevis, sister ship to the Grover's Algorithm

My wife had been imploring me all day long that I go to the supermarket to buy some vittles, whatever those are. As I drove the old Ford to market, I suddenly realized that…

Now it was up to me, and only me, to maneuver this fully loaded supertanker, the Grover’s Algorithm, to a safe fixed point, or else. The or-else was too horrible to contemplate. It was nighttime. According to radar, the Grover’s Algorithm was steaming inexorably towards some shoals, 5 miles away from a pristine Alaskan bay. Its rusty, creaky cargo holds had been filled to the brim just 2 days before with a particularly toxic grade of Prudhole crude oil. The captain and co-captain were passed out, drunk to oblivion. All other crew members were asleep in their bunk beds, blissfully unaware of the impending disaster. Even if I could wake them up in time, they would be of little use to me, as none had any knowledge of how to steer the ship. Lesser men in a similar situation would have been paralyzed by fear. Luckily, the cool analytical mind and sangfroid of the Walter-Mitty-Tucci’s prevailed in me. As the stars shone brightly above on that crisp summer night, I headed alone towards the bridge, while I tried to remember all that I had learned, from reading blogs and Wikipedia, about steering a ULCC (Ultra Large Crude Carrier)(pronounced HULK by some). Suddenly an idea clicked in my mind: what was needed was a fixed-point adaptive approach to maneuvering the Grover’s Algorithm. I applied such a scheme, conceived in utter desperation, and, praise the Lord a million times, it worked! The trajectory of the massive supertanker began to budge, ever so gradually, towards the safe fixed point I had assigned to it. No one but me would ever come to know what I had accomplished that lonely night. When the captain had regained his senses, he would assume, as was his wont, that nothing momentous had happened while he was in drunken stupor, and I would be sent back to swabbing decks…

A horn toot behind me by a rude driver awoke me from my deep reverie. I parked my car in the supermarket parking lot, with the centimeter precision one would expect from a seasoned supertanker captain. As soon as I got home, and my wife had been appeased, I began putting to paper the following account of the desperate scheme which I conceived on that lonely, frightful night when I became a temporary captain of the Grover’s Algorithm.

Check out
“An Adaptive, Fixed-Point Version of Grover’s Algorithm”, by R.R. Tucci, arxiv:1001.5200

LOTS OF PICTURES!
SOFTWARE INCLUDED!

(batteries not included, but none are needed. Okay, I confess, the software is pretty trivial, just some Octave m-files:

but that’s more software than you’ll ever get with any paper by a “quantum complexity theorist”. (By the way, if you didn’t know, Octave is a free, open source attempt to clone, at least partially, Matlab. It’s a lifesaver for people like me who are very poor and can’t afford to buy Matlab. Octave m-files supposedly work in the Matlab environment with zero or few modifications.)

## January 14, 2010

### Wringing Out H2 Info From Two Qubits

Filed under: Uncategorized — rrtucci @ 5:19 pm

Check out
“Two-qubit quantum system used to model the hydrogen molecule”
By Casey Johnston (Ars Technica, January 13, 2010)

Casey at the bat, doesn’t disappoint. Keep up the good work, Miss Johnston. An excellent (balanced, accurate, informative) bit of scientific journalism on an interesting but grossly over-hyped-by-some research result.

For comic relief, read Harvard University’s/Aspuru-Guzik’s/Andrew White’s press release entitled “Quantum computer calculates exact energy of molecular hydrogen”. Oh boy, a “quantum computer calculates exact”. (Very brief mention at the end that the “quantum computer” consists of just 2 photons. No need to describe the experiment. No need to mention the extreme difficulty of scaling this experimental setup to simulate any other molecules besides H2.) “exact energy” obtained by an “exact simulation”. WowWee!

For more info on the use of QCs to simulate other quantum systems, see my previous post: Set a Thief to Catch a Thief

## January 9, 2010

### Bored Teenagers Eavesdrop On Quantum Crypto, Undetected, Using Chewing Gum Technology

Filed under: Uncategorized — rrtucci @ 10:13 pm

Eavesdropping device and students who built it. (photo from website of NTNU Quantum Hacking Group)

“26C3: Researchers demonstrate brilliant quantum hack”

An excerpt:

Two researchers have shown how they can eavesdrop unnoticed on a provably secure quantum key distribution. To do so, Qin Liu and Sebastien Sauge did not of course change the laws of quantum physics. Instead, in archetypal hacker fashion, they successfully attacked the weakest point of a real world, and thus imperfect, implementation of a quantum key distribution system.

Liu and Sauge gave a live demonstration at 26C3 (26th Chaos Communication Congress), a conference organized by the Chaos Computer Club, held on Dec. 27-30, 2009 in Berlin. Here is the excellent C3 web page for their talk. The eavesdropping device was built by Prof. Johannes Skaar’s superb “Quantum Hacking Group” at the NTNU university in Norway.

My previous posts on quantum cryptography

## January 6, 2010

### Grover’s Algorithm for Dummies

Filed under: Uncategorized — rrtucci @ 9:20 pm

When first trying to learn about Grover’s algorithm (GA), many people can follow the math (which is fairly simple if you understand the basics of quantum mechanics and Dirac notation), but they can’t understand the purpose of GA. Can GA be used to search an unstructured database, as is frequently claimed? For instance, can it be used to search a disordered telephone directory for the telephone number of Mary Smith? Not really. So then, what are quantum computerists raving about? Are they all lying or seriously deluded? Not really. It turns out that they are right to rave; GA is indeed a very useful result. In my opinion, the problem is that most GA expositions do an atrocious job explaining its use. So let me try to do a better job here.

I will assume that you’ve read the GA math, which you can find, for example, in this Wikipedia article.

Let $N_S=2^{N_B}$ be the number of states for $N_B$ bits. GA is most useful when $N_B$ is very large. However, for simplicity, let’s assume that $N_B=4$. Suppose you have a register with $N_B$ bits. Let $Tar$ be a target configuration for that register. For example, for $N_B=4$, $Tar$ might be $1010$. Let the beginning configuration be the zero configuration, the one in which all bits are zero. Suppose the job of the computer, whether classical or quantum mechanical, is to transform the register from the zero configuration to configuration $Tar$.

A classical computer might do this

$0000\rightarrow 0001\rightarrow0010\rightarrow0011\ldots\rightarrow Tar$

Here each arrow represents one step. I’ll call this sequence of steps CW (Classical Walk). On average, a CW will take $N_S/2$ steps to go from $0000$ to $Tar$.

A quantum computer, on the other hand, can do GA, which looks like this

$|0000\rangle\rightarrow |Super_1\rangle\rightarrow |Super_2\rangle \rightarrow \dots\rightarrow |Tar\rangle$.

Here we define $|Super_1\rangle=\frac{1}{\sqrt{N_S}}\sum_{x=0}^{N_S-1}|x\rangle$. Furthermore, $|Super_2\rangle$, $|Super_3\rangle$, etc. denote linear combinations (i.e., Superpositions) of the vectors $|x\rangle$ for $x=0,1,\ldots, N_S-1$.
The number of steps GA takes to reach $Tar$ is about $\sqrt{N_S}$, much smaller than the number of steps taken by CW. That’s because one GA step is much more powerful than one CW step. In each step, GA performs, in one fell swoop, a matrix multiplication by a HUGE $N_S\times N_S$ matrix (albeit a sparse one).

So why can’t the classical computer (or the quantum one) just go from $0000$ to $Tar$ (respectively, from $|0000\rangle$ to $|Tar\rangle$ ) in just one step? Or else, suppose $Tar=0101$. Why can’t the classical computer (or the quantum one) do this: $0000\rightarrow 0100\rightarrow 0101$ (respectively, $|0000\rangle\rightarrow |0100\rangle\rightarrow |0101\rangle$ )? Because the rules of the game entail that it is not possible for any step to know $Tar$ so well that it can change one or more of the bits to their final value in one fell swoop. That would require much more precise information about $Tar$ than the oracle is capable of giving.

Note that each CW step is “almost Tar-blind”; meaning that it does not depend on what $Tar$ is, except in deciding whether to stop or go on. It’s as if we were moving from $0000$ to $Tar$ in a dark room, taking small blind steps, until we hit the target. Once we hit the target, we recognize it as such and stop.

Now note that each GA step is NOT almost Tar-blind; in fact, each GA step is a rotation by a small angle $\alpha$ in the plane that contains the vectors $|Super_1\rangle$ and $|Tar\rangle$, and $\alpha$ depends on the angle between $|Super_1\rangle$ and $|Tar\rangle$. So the GA steps are not almost Tar-blind. Far from it.

You might ask, if the CW steps are constrained to be almost Tar-blind and the GA steps aren’t, isn’t the analogy between CW and GA unfair? The analogy between CW and GA is ultimately just that, an analogy. Analogies are not unique or perfect. The only perfect analogy of X is X itself. Many people, including Grover himself, find the CW/GA analogy useful. In fact, it appears that this analogy is what led Grover to discover his algorithm in the first place. So the analogy can indeed be useful. But don’t push it, buddy. An unfortunate and very common example of pushing it too far: it’s clear that one can use CW to search a disordered telephone directory for Mary Smith. However, one cannot use GA, all alone, to do such a search. So it’s incorrect, and quite confusing to beginners, to assert that GA can be used to search an unstructured database.

If GA can’t be used to search an unstructured data base, then what good is it? Well, it is extremely useful for doing “amplitude amplification”, meaning that it magnifies the amplitude of $|Tar\rangle$. It tells you how to go from $|Super_1\rangle$ to $|Tar\rangle$ in $\sqrt{N_S}$ “easy” steps! By easy steps, I mean that each step can be decomposed into a SEO (Sequence of Elementary Operations like CNOTs and qubit rotations), in such a way that the SEO has a length that is merely polynomial in $N_B$.

And that’s the lesson. For overachievers, here are a few additional observations:

Fig.1

Geometric Picture of GA
If $n\in \{0,1\}$, then clearly $(-1)^n = 1 -2n$. To prove it, just substitute 0 and 1 for $n$ on both sides. If $|\psi\rangle$ is a normalized quantum state, then it is likewise true that $(-1)^{|\psi\rangle\langle\psi|}= 1 - 2|\psi\rangle\langle\psi|$. As you can see from Fig.1, the operation $1 - 2|\psi\rangle\langle\psi|$ is a reflection: it takes any vector and replaces it by its reflection about the plane perpendicular to $|\psi\rangle$. Let $\Gamma$ be the plane that contains vectors $|Tar\rangle$ and $|Super_1\rangle$, and let $\Gamma^\perp$ be the axis perpendicular to $\Gamma$. Reflections are a special type of orthogonal matrix. Since $R_{Tar}=(-1)^{|Tar\rangle\langle Tar|}$ and $R_1=(-1)^{|Super_1\rangle\langle Super_1|}$ are both orthogonal matrices, $G=-R_1R_{Tar}$ must be an orthogonal matrix too. In fact, one can show that $G$ is a rotation (about the axis $\Gamma^\perp$) by an angle $\alpha=2\arcsin(\langle Tar|Super_1\rangle)\sim 1/\sqrt{N_S}$. To do GA, one applies $G$ about $\sqrt{N_S}$ times to $|Super_1\rangle$, and this yields (approximately) $|Tar\rangle$.

Use of GA in Quantum Gibbs Sampling
Being such a rabid fan of quantum Gibbs sampling, I cannot resist mentioning the fact that quantum Gibbs sampling is an application of GA. If $\pi(x)$ is a probability distribution where $x=0,1,2,\dots,N_S-1$, then define the state $|\sqrt{\pi(x)}\rangle = \sum_x \sqrt{\pi(x)}|x\rangle$. The goal of Gibbs sampling is to steer an arbitrary, known quantum state into $|\sqrt{\pi(x)}\rangle$. Then $N_{sam}$ measurements of $|\sqrt{\pi(x)}\rangle$ will yield $N_{sam}$ samples $x^{(s)}$ for $s=1,2,\dots N_{sam}$. These samples will be distributed according to $\pi(x)$. The steering is done using GA. (Besides GA, it takes a few more ingredients to cook a tasty quantum Gibbs sampler; for example, it also takes quantum multiplexors, Szegedy operators and quantum Phase Estimation.)

## January 4, 2010

### I Don’t Have to Show You Any Stinking Mixed States

Filed under: Uncategorized — rrtucci @ 2:41 pm

From the 1948 film “The Treasure of the Sierra Madre” with Humphrey Bogart

QB nets don’t need any stinking mixed states. Given a mixed state, you can always replace it by a pure state (called a “purification”) that lives in a bigger space. Technically, if a mixed state is described by a density matrix $\rho_1$ acting on a Hilbert space ${\cal H}_1$, you can always find a Hilbert space ${\cal H}_2$ and a pure state $|\Psi_{12}\rangle\in {\cal H}_1\otimes{\cal H}_2$ such that $\rho_1= tr_2(|\Psi_{12}\rangle\langle\Psi_{12}|)$. For example, if $\rho_1$ has eigenvalues $w_r$ and eigenvectors $|\psi_r\rangle$ so that $\rho_1 = \sum_r w_r |\psi_r\rangle\langle\psi_r|$, then a possible purification of $\rho_1$ is $|\Psi_{12}\rangle = \sum_r \sqrt{w_r} |\psi_r\rangle\otimes |\psi_r\rangle$.