Quantum computers are computers that exploit =
the weird=20
properties of matter at extremely small scales. Many experts believe =
that a=20
full-blown quantum computer could perform calculations that would be =
hopelessly=20
time consuming on classical computers, but so far, quantum computers =
have proven=20
devilishly hard to build. The few simple prototypes developed in the lab =
perform=20
such rudimentary calculations that it=E2=80=99s sometimes difficult to =
tell whether=20
they=E2=80=99re really harnessing quantum effects at all.
At the =
Association for=20
Computing Machinery=E2=80=99s 43rd Symposium on Theory of Computing in =
June, associate=20
professor of computer science Scott Aaronson and his graduate student =
Alex=20
Arkhipov will present a paper describing an experiment that, if it =
worked, would=20
offer strong evidence that quantum computers can do things that =
classical=20
computers can=E2=80=99t. Although building the experimental apparatus =
would be=20
difficult, it shouldn=E2=80=99t be as difficult as building a fully =
functional quantum=20
computer.
If the experiment works, =E2=80=9Cit has the potential =
to take us past=20
what I would like to call the 'quantum singularity,' where we do the =
first thing=20
quantumly that we can=E2=80=99t do on a classical computer,=E2=80=9D =
says Terry Rudolph, an=20
advanced research fellow with Imperial College London=E2=80=99s Quantum =
Optics and Laser=20
Science, who was not involved in the research.
Aaronson and =
Arkhipov's=20
proposal is a variation on an experiment conducted by physicists at the=20
University of Rochester in 1987, which relied on a device called a beam=20
splitter, which takes an incoming beam of light and splits it into two =
beams=20
traveling in different directions. The Rochester researchers =
demonstrated that=20
if two identical light particles =E2=80=94 photons =E2=80=94 reach the =
beam splitter at exactly=20
the same time, they will both go either right or left; they =
won=E2=80=99t take different=20
paths. It=E2=80=99s another of the weird quantum behaviors of =
fundamental particles that=20
defy our physical intuitions.
More =
light!
The MIT=20
researchers' experiment would use a larger number of photons, which =
would pass=20
through a network of beam splitters and eventually strike photon =
detectors. The=20
number of detectors would be somewhere in the vicinity of the square of =
the=20
number of photons =E2=80=94 about 36 detectors for six photons, 100 =
detectors for 10=20
photons.
For any run of the MIT experiment, it would be =
impossible to=20
predict how many photons would strike any given detector. But over =
successive=20
runs, statistical patterns would begin to build up. In the six-photon =
version of=20
the experiment, for instance, it could turn out that there=E2=80=99s an =
8 percent chance=20
that photons will strike detectors 1, 3, 5, 7, 9 and 11, a 4 percent =
chance that=20
they=E2=80=99ll strike detectors 2, 4, 6, 8, 10 and 12, and so on, for =
any conceivable=20
combination of detectors.
Calculating that distribution =E2=80=94 =
the likelihood=20
of photons striking a given combination of detectors =E2=80=94 is an =
incredibly hard=20
problem. The researchers=E2=80=99 experiment doesn=E2=80=99t solve it =
outright, but every=20
successful execution of the experiment does take a sample from the =
solution set.=20
One of the key findings in Aaronson and Arkhipov=E2=80=99s paper is =
that, not only is=20
calculating the distribution an intractably hard problem, but so is =
simulating=20
the sampling of it. For an experiment with more than, say, 100 photons, =
it would=20
probably be beyond the computational capacity of all the computers in =
the=20
world.
Brass tacks
The question, then, is =
whether=20
the experiment can be successfully executed. The Rochester researchers =
performed=20
it with two photons, but getting multiple photons to arrive at a whole =
sequence=20
of beam splitters at exactly the right time is more complicated. =
=E2=80=9CIt=E2=80=99s=20
challenging, technologically, but not forbiddingly so,=E2=80=9D says =
Barry Sanders,=20
director of the University of Calgary=E2=80=99s Institute for Quantum =
Information=20
Science. Sanders points out that in 1987, when the Rochester researchers =
performed their initial experiment, they were using lasers mounted on =
lab tables=20
and getting photons to arrive at the beam splitter simultaneously by =
sending=20
them down fiber-optic cables of different lengths. But recent years have =
seen=20
the advent of optical chips, in which all the optical components are =
etched into=20
a silicon substrate, which makes it much easier to control the =
photons=E2=80=99=20
trajectories.
The biggest problem, Sanders believes, is =
generating=20
individual photons at predictable enough intervals to synchronize their =
arrival=20
at the beam splitters. =E2=80=9CPeople have been working on it for a =
decade, making=20
great things,=E2=80=9D Sanders says. =E2=80=9CBut getting a train of =
single photons is still a=20
challenge.=E2=80=9D Rudolph agrees. =E2=80=9CAt the moment, the hard =
thing is getting enough=20
single photons into the chip,=E2=80=9D he says. But, he adds, =
=E2=80=9Cmy hope is that within a=20
few years, we=E2=80=99ll manage to build the experiment that crosses the =
boundary of=20
what we can practically do with classical =
computers.=E2=80=9D
Sanders points out=20
that even if the problem of getting single photons onto the chip is =
solved,=20
photon detectors still have inefficiencies that could make their =
measurements=20
inexact: in engineering parlance, there would be noise in the system. =
But=20
Aaronson says that he and Arkhipov explicitly consider the question of =
whether=20
simulating even a noisy version of their optical experiment would be an=20
intractably hard problem for a conventional computer. Although they were =
unable=20
to prove that it was, Aaronson says that =E2=80=9Cmost of our paper is =
devoted to giving=20
evidence that the answer to that is yes.=E2=80=9D He=E2=80=99s hopeful =
that a proof is=20
forthcoming, whether from his research group or =
others=E2=80=99.
The quantum singularity
A new experiment would use quantum effects to perform =
otherwise=20
intractable calculations, but conducting it should be easier than =
building a=20
quantum computer.
today's news
When the = butterfly=20 effect took flight
![3D""=20](3D"http://img.mit.edu/newsoffice/images/article_images/tn/20110301162=)
Graphic: Christine=20
Daniloff
Half a century ago, Edward Lorenz SM '43, ScD '48, overthrew the idea = of the=20 clockwork universe with his ground-breaking research on chaos. Now MIT=20 professors are working to establish a climate research center in his = name.=20
Part= s=20 of brain can switch functions
March 1, 2011
In= =20 The World: Turning old oil into new mileage
February 24, 2011
![3D""=20](3D"http://web.mit.edu/newsoffice//images/article_images/2011030116391=)
=20
A beam splitter is a device, like the one depicted =
here, that=20
bifurcates a beam of light. An experiment proposed by MIT researchers, =
which=20
relies on beam splitters, would exploit the strange behavior of quantum=20
particles to perform calculations that are hopelessly time consuming on=20
conventional computers.
Graphic: Christine=20 Daniloff
Graphic: Christine=20 Daniloff
","
"];c.fn.extend({text:function(a){if(c.isFunction(a))=
return this.each(function(b){var d=3D=0A=
c(this);d.text(a.call(this,b,d.text()))});if(typeof =
a!=3D=3D"object"&&a!=3D=3Dw)return =
this.empty().append((this[0]&&this[0].ownerDocument||s).createTextNode(a)=
);return c.text(this)},wrapAll:function(a){if(c.isFunction(a))return =
this.each(function(d){c(this).wrapAll(a.call(this,d))});if(this[0]){var =
b=3Dc(a,this[0].ownerDocument).eq(0).clone(true);this[0].parentNode&&b.in=
sertBefore(this[0]);b.map(function(){for(var =
d=3Dthis;d.firstChild&&d.firstChild.nodeType=3D=3D=3D1;)d=3Dd.firstChild;=
return d}).append(this)}return this},=0A=
wrapInner:function(a){if(c.isFunction(a))return =
this.each(function(b){c(this).wrapInner(a.call(this,b))});return =
this.each(function(){var =
b=3Dc(this),d=3Db.contents();d.length?d.wrapAll(a):b.append(a)})},wrap:fu=
nction(a){return =
this.each(function(){c(this).wrapAll(a)})},unwrap:function(){return =
this.parent().each(function(){c.nodeName(this,"body")||c(this).replaceWit=
h(this.childNodes)}).end()},append:function(){return =
this.domManip(arguments,true,function(a){this.nodeType=3D=3D=3D1&&this.ap=
pendChild(a)})},=0A=
prepend:function(){return =
this.domManip(arguments,true,function(a){this.nodeType=3D=3D=3D1&&this.in=
sertBefore(a,this.firstChild)})},before:function(){if(this[0]&&this[0].pa=
rentNode)return =
this.domManip(arguments,false,function(b){this.parentNode.insertBefore(b,=
this)});else if(arguments.length){var =
a=3Dc(arguments[0]);a.push.apply(a,this.toArray());return =
this.pushStack(a,"before",arguments)}},after:function(){if(this[0]&&this[=
0].parentNode)return =
this.domManip(arguments,false,function(b){this.parentNode.insertBefore(b,=0A=
this.nextSibling)});else if(arguments.length){var =
a=3Dthis.pushStack(this,"after",arguments);a.push.apply(a,c(arguments[0])=
.toArray());return a}},remove:function(a,b){for(var =
d=3D0,f;(f=3Dthis[d])!=3Dnull;d++)if(!a||c.filter(a,[f]).length){if(!b&&f=
.nodeType=3D=3D=3D1){c.cleanData(f.getElementsByTagName("*"));c.cleanData=
([f])}f.parentNode&&f.parentNode.removeChild(f)}return =
this},empty:function(){for(var =
a=3D0,b;(b=3Dthis[a])!=3Dnull;a++)for(b.nodeType=3D=3D=3D1&&c.cleanData(b=
.getElementsByTagName("*"));b.firstChild;)b.removeChild(b.firstChild);=0A=
return this},clone:function(a){var =
b=3Dthis.map(function(){if(!c.support.noCloneEvent&&!c.isXMLDoc(this)){va=
r =
d=3Dthis.outerHTML,f=3Dthis.ownerDocument;if(!d){d=3Df.createElement("div=
");d.appendChild(this.cloneNode(true));d=3Dd.innerHTML}return =
c.clean([d.replace(Ja,"").replace(/=3D([^=3D"'>\s]+\/)>/g,'=3D"$1">').rep=
lace(V,"")],f)[0]}else return =
this.cloneNode(true)});if(a=3D=3D=3Dtrue){ra(this,b);ra(this.find("*"),b.=
find("*"))}return b},html:function(a){if(a=3D=3D=3Dw)return =
this[0]&&this[0].nodeType=3D=3D=3D1?this[0].innerHTML.replace(Ja,=0A=
""):null;else if(typeof =
a=3D=3D=3D"string"&&!ta.test(a)&&(c.support.leadingWhitespace||!V.test(a)=
)&&!F[(La.exec(a)||["",""])[1].toLowerCase()]){a=3Da.replace(Ka,Ma);try{f=
or(var =
b=3D0,d=3Dthis.length;b