Quantum Bayesian Networks

November 30, 2010

Quantum Optical X-Box

Filed under: Uncategorized — rrtucci @ 11:09 am

In my previous post, I described a paper by Aaronson and Arkhipov entitled “The Computational Complexity of Linear Optics”. In this post, I would like to suggest an implementation of their experiment with optical fibers. Call it a thought experiment (Gedanken experiment) because I’m not an experimentalist so I can’t fill in all the minute experimental details. I’m not an Einstein either, so don’t expect too much from me, although I do believe the device I propose is physically reasonable.


The device uses the following building blocks

  • photon source and photon detector (see Fig.1) These are just what their names suggests.
  • optical delay and mirror (see Fig.1) These are just what their names suggests.
  • quantum rail-switch (see Fig.2) For the purposes of this thought experiment, I will postulate an ideal element called a quantum rail-switch with the following properties. 

    A rail-switch has 3 ports. Two ports are interchangeable, while the third one, the odd-man-out, is different from the other two. 

    One of the interchangeable ports is blocked at all times. There is a switch on the device whereby one can control which of the two interchangeable ports is blocked. In our drawings, we will indicate that an interchangeable port is blocked by putting an “x” next it.


    Fig.2 shows 4 different ways of using rail-switches.

    If a mode enters the odd-man-out port, then (1) the same mode exits, unchanged, the non-blocked interchangeable port (2) nothing exits the blocked interchangeable port. 

    If a mode enters the non-blocked interchangeable port and blackness enters the blocked interchangeable port, then the noise from the blackness is blocked by the rail-switch and the mode that enters the rail-switch exits it, unchanged, through the odd-man-out port.

Our full device is shown in Fig.3. It contains a box (shown in orange in Fig.3), which we will call henceforth a quantum X-Box. The x-box contains at its center a single beam splitter (shown in purple in Fig.3). The two modes that enter the beam splitter and the two modes that exit it form an X pattern, hence the name x-box.


For definiteness, Fig.3 shows an x-box with 4 left and 4 right ports. 4 here is the value of the variable m (= total number of modes) in the AA paper. Once I explain Fig.3, you will see that this device can be generalized easily to m equal to any power of 2.

Inside the x-box
As shown in Fig.3, each of the 4 left ports of the x-box leads to an A_j switch. 

Each A_j switch has two fibers exiting it: one (indicated in green) goes directly to one of the right ports of the x-box and the other goes into one of the B_j switches. 

Each of the B_j switches has two fibers exiting it: one goes to a C_j switch located ABOVE the beam splitter, and the other goes to a C_j switch located BELOW the beam splitter.

The two C_j switches above (below, resp.) the beam splitter each sends one fiber to switch D0 (D1, resp.)

D0 (D1, resp.) sends one fiber to the top side (bottom side, resp.) of the beam splitter.  

The x-box is has left-right mirror symmetry.

Outside the x-box
As shown in Fig.3, each left-side(right-side, resp.) port of the x-box leads via a fiber to a rail-switch that in turn leads to(1) a photon source (photon detector, resp.) and (2) a delay/mirror.

How to operate it
Initially, the photon sources emit photons nearly simultaneously. The photons pass through the x-box and exit it. Each time, except the last time, that the photons exit the x-box, they meet delays/mirrors that make them to go through the x-box one more time. The last time that the photons exit the x-box, they meet the detectors.


Each time the photons are outside the x-box, busy traversing the delays, one changes the x-box as follows:

  1. two of the 4 input ports are chosen at random. These two chosen input ports are made “active”, and rest of the input ports are made “inactive”
  2. the reflection and transmission coefficients of the beam splitter are changed at random. 

Fig.4 shows an example in which the top two input ports were chosen to be the ones that are active. The red lines indicate the path of the photons that enter the active ports. Note that choosing active and inactive ports means blocking a slew of rail-switch ports, in such a way as to guarantee that: 

  1. the two modes that enter the active ports reach the beam splitter and mix there, and then re-emerge out of the x-box at the ports which are the mirror images of the ports they entered. 
  2. all modes that enter the inactive ports are immediately directed, unchanged, out of the x-box. 

It’s possible to build a quantum xbox that is balanced:

Assume that the transit time through all rail-switches is the same. Assume that in Fig.3, one makes

  1. the length of all green colored fibers the same
  2. the length of all non-green colored fibers from an A_j to a B_j switch the same
  3. the length of all fibers from a B_j to a C_j switch the same
  4. the length of all fibers from a C_j to a D_j switch the same
  5. the length of all fibers from a D_j switch to the beam splitter the same
  6. the length of any green colored fiber = the sum of the fiber lengths traversed by an active photon (plus a tiny delay equal to the transit time through 6 switches (2 B_j, 2 C_j, 2 D_j) and the beam splitter)

If these constraints are satisfied, the transit time for a photon to make one xbox pass will become path-independent (the same for all possible active and passive paths). Thus, balanced xboxes have a common transit time.

November 24, 2010

What Are the Limits of What We Can Calculate? Quantum Computers Can Sample Functions That Are Inaccessible to Classical Computers

Filed under: Uncategorized — rrtucci @ 9:06 pm

If 20th century humans had entrusted complexity theorists with the task of building digital computers, I dare say we would all still be using abacuses. And complexity theorists would still be writing papers about the amazing complexity issues raised by the abacus. Complexity theorists are not known for their skill at building practical things.

Maybe you don’t have the time and energy necessary to grok the definitions and inter-relationships among the hundreds of complexity classes in the Complexity Class Zoo. Maybe you are waiting for an executive summary, issued after complexity theorists figure out a classification theorem for all those classes. Until that executive summary is available, the field of complexity theory will continue to seem hopelessly half-baked to many of us.

Nevertheless, there is no doubt that some very smart people are complexity theorists, and that their work has enriched quantum computing significantly. So it pays off, even if you are a person with a more practical bend of mind, to pay attention to what they are up to. Complexity theorists also help to sell quantum computers to the public, by proving that quantum computers can calculate certain quantities that are totally inaccessible to classical computers. For example, Peter Shor proved that quantum computers can find the factors of very large integers in polynomial time, whereas all known classical algorithms require exponential time to do so. Another example is the recent paper:

“The Computational Complexity of Linear Optics”, by AA (Scott Aaronson and Alex Arkhipov). ArXiv abstract here. Scott’s blog post about it here.

This paper is about a topic that is near and dear to my heart, a topic that is key to what my program Quibbs does. The topic is: using a QC to sample probability distributions. So the rest of this blog post will be devoted to giving a brief summary of the AA paper. Perhaps I’ll say enough to pique your interest in the dark arts of complexity theory.

AA propose an optics experiment that would calculate (to a certain precision) a special probability distribution. For photon numbers 10<n<50, the AA optics experiment would take polynomial(n) steps to calculate this probability distribution, if quantum mechanics is to be believed. AA prove (assuming some very plausible conjectures about complexity classes) that a classical computer would require exponential(n) steps to calculate the same probability distribution (to the same precision). For n slightly larger than 50, classical computers would take longer than the age of the universe to get an answer.


  • m= number of modes (m is mnemonic for mode) 
  • n= total number of photons 
  • \Phi^m_n = set of m-tuples (s_1, s_2, \ldots, s_m), where the components s_j are non-negative integers, and where s_1 + s_2 + \ldots +s_m = n. Each s_j represents the number of photons in the j’th mode and thus n is the total number of photons. For example, \Phi^2_3 = \{(3,0), (2,1), (1,2), (0,3)\}
  • 1_n = (1,1,\ldots,1,0,0,\ldots,0), where there are n ones and m-n zeros. This assumes m\geq n.

AA consider a conditional probability distribution P(s|\theta)=|\langle s |U(\theta)| t\rangle|^2 where

  • s, t \in \Phi^m_n and t=1_n is preferable. 
  • U(\theta) is a unitary transformation produced by an ideal (free of environmental noise) optical device consisting of passive elements (beam splitters and phase shifters). The optical device has m input ports and the same number of output ports. A “mode” (i.e., a monochromatic beam of light) enters and exits each input and output port. By assumption, all input modes have the same frequency. Because phase shifters and beam splitters do not affect the frequency of a mode, all modes inside the device are at the same frequency too. 
  • \theta takes poly(n) bits to specify. It includes all parameters that U depends on

Let \hat{P}_N(s|\theta) be an estimate of P(s|\theta) calculated from a number N=poly(m,n) of samples of s. These samples are obtained from a non-ideal experiment with environmental noise. AA assume (they expect experimentalists to corroborate this) that it is possible to perform an optical experiment with poly(n) elementary gates (beam splitters or phase shifters) for which \sum_s |P(s|\theta)-\hat{P}_N(s|\theta)| < \epsilon where \epsilon = \frac{1}{p(n)} for some polynomial p() of n.

November 9, 2010

IBM is Still Alive – Honest Truth

Filed under: Uncategorized — rrtucci @ 8:55 am

Check out

Quantum Computing Reaches for True Power
by John Markoff, NY Times, Nov. 8, 2010

A reasonable article, almost free of hype. Mr. Markoff mentions the efforts of IBM, Yale, UCSB, Toshiba, and D-Wave to construct a large scale QC. There are other important research efforts that he fails to mention, but it’s an omission that is understandable, because there are quite a few of them.


Significantly, I.B.M. has reconstituted what had recently been a relatively low-level research effort in quantum computing. I.B.M. is responding to advances made in the past year at Yale University and the University of California, Santa Barbara,

The company has assembled a large research group at its Thomas J. Watson Research Center in Yorktown Heights, N.Y., that includes alumni from the Santa Barbara and Yale laboratories and has now begun a five-year research project.

The Santa Barbara researchers said they believe they will essentially double the computational power of their quantum computers next year.

John Martinis, a physicist who is a member of the team, said, “We are currently designing a device with four qubits, and five resonators,” the standard microelectronic components that are used to force quantum entanglement. “If all goes well, we hope to increase this to eight qubits and nine resonators in a year or so.”

Hartmut Neven, an artificial-intelligence researcher at Google, said the company had received a proposal from D-Wave and NASA’s Jet Propulsion Laboratory to develop a quantum computing facility for Google next year based on the D-Wave technology.

On the whole, pretty good news. Looks like the QC race is heating up. The reinvigoration of IBM might be a bellwether. At least, I hope so. Big, bureaucratic IBM is not known for being the first one to arrive at parties. Big Blue usually arrives when the party is almost over.

November 6, 2010

Google’s Advice: Do Not Invest in Quantum Computing

Filed under: Uncategorized — rrtucci @ 7:17 am

You are a rich individual or company with lots of money to invest. My advice: put your money into gold. Gold is an extremely safe investment. Always goes up in value. And it’s a very exciting investment too. Just think how storing gold in your safe will change the course of human history, generate interesting jobs and products, advance scientific understanding of our world, find cures for horrible diseases…

But if gold is not your cup of tea, maybe you should consider following the example of Google Ventures. Here is a list of the companies that Google Ventures currently invests in. Quantum computing has to do with computer programming, Bayesian networks, doing statistical analyses of very large data sets, etc. All these topics are Google specialties. And yet, Google Ventures has never invested in quantum computing, so why should you? Google’s advice to you is clear: do not invest in quantum computing.

And why should Google Ventures invest in something that isn’t too important, like quantum computing, when it can invest in stuff that is much more important to the future of physics, computer science, engineering, and the future of humanity itself, like SCVNGR, for example?

Seth Priebatsch, Founder of SCVNGR

The following recent article from CNN explains Google’s rationale for investing in SCVNGR, instead of investing in the less promising field of quantum computing:

The modern tech CEO: Barefoot and 21
By John D. Sutter, CNN
November 2, 2010 10:04 a.m. EDT | Filed under: Innovation

Some excerpts

Age 12: Outsourcing to India
By 12, Seth had gotten used to waking up at 3 a.m.
He started an online company called Giftopedia, a digital shopping list of sorts that automatically searched the internet for the world’s best prices and made purchases for its users.
The only problem: Seth didn’t really know how to write code for the site.
So, after searching the internet, reading up on outsourcing and talking with his parents, he hired workers in Russia and India to do the coding for him.

Age 19: Dropping out of Princeton
It’s a call most mothers would rather not get.
“My instinct honestly was to fall upon the ground and flail,” Suzanne Priebatsch, Seth’s mom, said of the Saturday afternoon when her son called to tell her he was dropping out of Princeton to start SCVNGR.
But then she listened to his pitch for the company. She was sold.
Seth is fond of saying SCVNGR is “a game layer on top of the world.

After Seth won an entrepreneur contest at Princeton, investors started calling him about SCVNGR. Peter Bell, from the firm Highland Capital Partners, which gave Seth $730,000 in December 2008, first noticed two things about the surprisingly mature 19-year-old who entered his office: He wasn’t wearing shoes and he sat on the back of the chair instead of in the seat.

“Seth — basically — he works, he jogs, he eats and sleeps,” Bell said in a phone interview. “He doesn’t do anything else.
You could argue that’s not healthy. But you get older and your kids have soccer games and you work with charities and those things make you a whole person. But there’s something to be said for just putting the blinders on and being able to focus.

He lives in his office — keeping a sleeping bag under his couch and sometimes staying at his parents’ house, down the street, as a backup.
He works seven days a week. Runs every morning. He doesn’t have any friends outside work and sees friendship in a light that he admits can seem “caustic” from the outside. But to him it’s just utilitarian.

But Priebatsch — whose business card says he is SCVNGR’s “chief ninja”

On his 21st birthday, December 14, 2009, Priebatsch got $4 million in funding from Google Ventures, one of the most notable start-up financing groups in Silicon Valley.

Okay. Let’s recap. He still plays with toy cars, but he denies it. He wears orange ski sunglasses over his head, at work. A top notch programmer: his first computer program was written for him by his coolies from India and Russia. On days when investors come to visit, he attends business meetings barefoot. He sits on the back of chairs instead of sitting on the flat part. He dropped out of college one year before getting his degree. He lives in his office or at his parents house (at 21). He works 7 days a week. Why would the CEO of a company with 60 employees, most of them programmers, need to keep those hours? Don’t know. He likes to be called “chief Ninja”, which leads me to believe that he still sleeps in his Ninja PJs.

And here is the SCVNGR web site
Their ad says:

Play SCVNGR! It’s a game all about going places, doing challenges and earning points.

Sounds like FourSquare, a game that doesn’t appeal to me.

According to the above CNN article, at 21, Seth is an ideal CEO of an ideal company. By comparison, Eric Schmidt, Chairman and CEO of Google, 55 years old according to Wikipedia, is only valuable to the owners of the Soylent Green corporation. Ditto for Steve Jobs (55) and Bill Gates (55). Eric Schmidt, Steve Jobs, and Bill Gates are so old, they are no longer capable of coming up with new ideas, not the way a 21-year-old can. Really new ideas like, for instance, copying vastly improving FourSquare.

Blog at WordPress.com.

%d bloggers like this: