Greg Kuperberg’s calculus problem

Posted on August 3, 2016 by spiros

“How good are you at calculus?”

This was the opening sentence of Greg Kuperberg’s Facebook status on July 4th, 2016.

“I have a joint paper (on isoperimetric inequalities in differential geometry) in which we need to know that

$(\sin\theta)^3 xy + ((\cos\theta)^3 -3\cos\theta +2) (x+y) - (\sin\theta)^3-6\sin\theta -6\theta + 6\pi \\ \\- 6\arctan(x) +2x/(1+x^2) -6\arctan(y) +2y/(1+y^2)$

is non-negative for x and y non-negative and $\theta$ between $0$ and $\pi$ . Also, the minimum only occurs for $x=y=1/(\tan(\theta/2)$ .”

Let’s take a moment to appreciate the complexity of the mathematical statement above. It is a non-linear inequality in three variables, mixing trigonometry with algebra and throwing in some arc-tangents for good measure. Greg, continued:

“We proved it, but only with the aid of symbolic algebra to factor an algebraic variety into irreducible components. The human part of our proof is also not really a cake walk.

A simpler proof would be way cool.”

I was hooked. The cubic terms looked a little intimidating, but if I converted x and y into $\tan(\theta_x)$ and $\tan(\theta_y)$ , respectively, as one of the comments on Facebook promptly suggested, I could at least get rid of the annoying arc-tangents and then calculus and trigonometry would take me the rest of the way. Greg replied to my initial comment outlining a quick route to the proof: “Let me just caution that we found the problem unyielding.” Hmm… Then, Greg revealed that the paper containing the original proof was over three years old (had he been thinking about this since then? that’s what true love must be like.) Titled “The Cartan-Hadamard Conjecture and The Little Prince“, the above inequality makes its appearance as Lemma 7.1 on page 45 (of 63). To quote the paper: “Although the lemma is evident from contour plots, the authors found it surprisingly tricky to prove rigorously.”

As I filled pages of calculations and memorized every trigonometric identity known to man, I realized that Greg was right: the problem was highly intractable. The quick solution that was supposed to take me two to three days turned into two weeks of hell, until I decided to drop the original approach and stick to doing calculus with the known unknowns, x and y. The next week led me to a set of three non-linear equations mixing trigonometric functions with fourth powers of x and y, at which point I thought of giving up. I knew what I needed to do to finish the proof, but it looked freaking insane. Still, like the masochist that I am, I continued calculating away until my brain was mush. And then, yesterday, during a moment of clarity, I decided to go back to one of the three equations and rewrite it in a different way. That is when I noticed the error. I had solved for $\cos\theta$ in terms of x and y, but I had made a mistake that had cost me 10 days of intense work with no end in sight. Once I found the mistake, the whole proof came together within about an hour. At that moment, I felt a mix of happiness (duh), but also sadness, as if someone I had grown fond of no longer had a reason to spend time with me and, at the same time, I had ran out of made-up reasons to hang out with them. But, yeah, I mostly felt happiness.

Greg Kuperberg pondering about the universe of mathematics.

Before I present the proof below, I want to take a moment to say a few words about Greg, whom I consider to be the John Preskill of mathematics: a lodestar of sanity in a sea of hyperbole (to paraphrase Scott Aaronson). When I started grad school at UC Davis back in 2003, quantum information theory and quantum computing were becoming “a thing” among some of the top universities around the US. So, I went to several of the mathematics faculty in the department asking if there was a course on quantum information theory I could take. The answer was to “read Nielsen and Chuang and then go talk to Professor Kuperberg”. Being a foolish young man, I skipped the first part and went straight to Greg to ask him to teach me (and four other brave souls) quantum “stuff”. Greg obliged with a course on… quantum probability and quantum groups. Not what I had in mind. This guy was hardcore. Needless to say, the five brave souls taking the class (mostly fourth year graduate students and me, the noob) quickly became three, then two gluttons for punishment (the other masochist became one of my best friends in grad school). I could not drop the class, not because I had asked Greg to do this as a favor to me, but because I knew that I was in the presence of greatness (or maybe it was Stockholm syndrome). My goal then, as an aspiring mathematician, became to one day have a conversation with Greg where, for some brief moment, I would not sound stupid. A man of incredible intelligence, Greg is that rare individual whose character matches his intellect. Much like the anti-heroes portrayed by Humphrey Bogart in Casablanca and the Maltese Falcon, Greg keeps a low-profile, seems almost cynical at times, but in the end, he works harder than everyone else to help those in need. For example, on MathOverflow, a question and answer website for professional mathematicians around the world, Greg is listed as one of the top contributors of all time.

But, back to the problem. The past four weeks thinking about it have oscillated between phases of “this is the most fun I’ve had in years!” to “this is Greg’s way of telling me I should drop math and become a go-go dancer”. Now that the ordeal is over, I can confidently say that the problem is anything but “dull” (which is how Greg felt others on MathOverflow would perceive it, so he never posted it there). In fact, if I ever have to teach Calculus, I will subject my students to the step-by-step proof of this problem. OK, here is the proof. This one is for you Greg. Thanks for being such a great role model. Sorry I didn’t get to tell you until now. And you are right not to offer a “bounty” for the solution. The journey (more like, a trip to Mordor and back) was all the money.

The proof: The first thing to note (and if I had read Greg’s paper earlier than today, I would have known as much weeks ago) is that the following equality holds (which can be verified quickly by differentiating both sides):

$4 x - 6\arctan(x) +2x/(1+x^2) = 4 \int_0^x \frac{s^4}{(1+s^2)^2} ds$ .

Using the above equality (and the equivalent one for y), we get:

$F(\theta,x,y) = (\sin\theta)^3 xy + ((\cos\theta)^3 -3\cos\theta -2) (x+y) - (\sin\theta)^3-6\sin\theta -6\theta + 6\pi \\ \\4 \int_0^x \frac{s^4}{(1+s^2)^2} ds+4 \int_0^y \frac{s^4}{(1+s^2)^2} ds.$

Now comes the fun part. We differentiate with respect to $\theta$ , x and y, and set to zero to find all the maxima and minima of $F(\theta,x,y)$ (though we are only interested in the global minimum, which is supposed to be at $x=y=\tan^{-1}(\theta/2))$ . Some high-school level calculus yields:

$\partial_\theta F(\theta,x,y) = 0 \implies \sin^2(\theta) (\cos(\theta) xy + \sin(\theta)(x+y)) = \\ \\ 2 (1+\cos(\theta))+\sin^2(\theta)\cos(\theta).$

At this point, the most well-known trigonometric identity of all time, $\sin^2(\theta)+\cos^2(\theta)=1$ , can be used to show that the right-hand-side can be re-written as:

$2(1+\cos(\theta))+\sin^2(\theta)\cos(\theta) = \sin^2(\theta) (\cos\theta \tan^{-2}(\theta/2) + 2\sin\theta \tan^{-1}(\theta/2)),$

where I used (my now favorite) trigonometric identity: $\tan^{-1}(\theta/2) = (1+\cos\theta)/\sin(\theta)$ (note to the reader: $\tan^{-1}(\theta) = \cot(\theta)$ ). Putting it all together, we now have the very suggestive condition:

$\sin^2(\theta) (\cos(\theta) (xy-\tan^{-2}(\theta/2)) + \sin(\theta)(x+y-2\tan^{-1}(\theta/2))) = 0,$

noting that, despite appearances, $\theta = 0$ is not a solution (as can be checked from the original form of this equality, unless $x$ and $y$ are infinite, in which case the expression is clearly non-negative, as we show towards the end of this post). This leaves us with $\theta = \pi$ and

$\cos(\theta) (\tan^{-2}(\theta/2)-xy) = \sin(\theta)(x+y-2\tan^{-1}(\theta/2)),$

as candidates for where the minimum may be. A quick check shows that:

$F(\pi,x,y) = 4 \int_0^x \frac{s^4}{(1+s^2)^2} ds+4 \int_0^y \frac{s^4}{(1+s^2)^2} ds \ge 0,$

since x and y are non-negative. The following obvious substitution becomes our greatest ally for the rest of the proof:

$x= \alpha \tan^{-1}(\theta/2), \, y = \beta \tan^{-1}(\theta/2).$

Substituting the above in the remaining condition for $\partial_\theta F(\theta,x,y) = 0$ , and using again that $\tan^{-1}(\theta/2) = (1+\cos\theta)/\sin\theta$ , we get:

$\cos\theta (1-\alpha\beta) = (1-\cos\theta) ((\alpha-1) + (\beta-1)),$

which can be further simplified to (if you are paying attention to minus signs and don’t waste a week on a wild-goose chase like I did):

$\cos\theta = \frac{1}{1-\beta}+\frac{1}{1-\alpha}$ .

As Greg loves to say, we are finally cooking with gas. Note that the expression is symmetric in $\alpha$ and $\beta$ , which should be obvious from the symmetry of $F(\theta,x,y)$ in x and y. That observation will come in handy when we take derivatives with respect to x and y now. Factoring $(\cos\theta)^3 -3\cos\theta -2 = - (1+\cos\theta)^2(2-\cos\theta)$ , we get:

$\partial_x F(\theta,x,y) = 0 \implies \sin^3(\theta) y + 4\frac{x^4}{(1+x^2)^2} = (1+\cos\theta)^2 + \sin^2\theta (1+\cos\theta).$

Substituting x and y with $\alpha \tan^{-1}(\theta/2), \beta \tan^{-1}(\theta/2)$ , respectively and using the identities $\tan^{-1}(\theta/2) = (1+\cos\theta)/\sin\theta$ and $\tan^{-2}(\theta/2) = (1+\cos\theta)/(1-\cos\theta),$ the above expression simplifies significantly to the following expression:

$4\alpha^4 =\left((\alpha^2-1)\cos\theta+\alpha^2+1\right)^2 \left(1 + (1-\beta)(1-\cos\theta)\right).$

Using $\cos\theta = \frac{1}{1-\beta}+\frac{1}{1-\alpha}$ , which we derived earlier by looking at the extrema of $F(\theta,x,y)$ with respect to $\theta$ , and noting that the global minimum would have to be an extremum with respect to all three variables, we get:

$4\alpha^4 (1-\beta) = \alpha (\alpha-1) (1+\alpha + \alpha(1-\beta))^2,$

where we used $1 + (1-\beta)(1-\cos\theta) = \alpha (1-\beta) (\alpha-1)^{-1}$ and

$(\alpha^2-1)\cos\theta+\alpha^2+1 = (\alpha+1)((\alpha-1)\cos\theta+1)+\alpha(\alpha-1) = \\ (\alpha-1)(1-\beta)^{-1} (2\alpha + 1-\alpha\beta).$

We may assume, without loss of generality, that $x \ge y$ . If $\alpha = 0$ , then $\alpha = \beta = 0$ , which leads to the contradiction $\cos\theta = 2$ , unless the other condition, $\theta = \pi$ , holds, which leads to $F(\pi,0,0) = 0$ . Dividing through by $\alpha$ and re-writing $4\alpha^3(1-\beta) = 4\alpha(1+\alpha)(\alpha-1)(1-\beta) + 4\alpha(1-\beta)$ , yields:

$4\alpha (1-\beta) = (\alpha-1) (1+\alpha - \alpha(1-\beta))^2 = (\alpha-1)(1+\alpha\beta)^2,$

which can be further modified to:

$4\alpha +(1-\alpha\beta)^2 = \alpha (1+\alpha\beta)^2,$

and, similarly for $\beta$ (due to symmetry):

$4\beta +(1-\alpha\beta)^2 = \beta (1+\alpha\beta)^2.$

Subtracting the two equations from each other, we get:

$4(\alpha-\beta) = (\alpha-\beta)(1+\alpha\beta)^2$ ,

which implies that $\alpha = \beta$ and/or $\alpha\beta =1$ . The first leads to $4\alpha (1-\alpha) = (\alpha-1)(1+\alpha^2)^2,$ which immediately implies $\alpha = 1 = \beta$ (since the left and right side of the equality have opposite signs otherwise). The second one implies that either $\alpha+\beta =2$ , or $\cos\theta =1$ , which follows from the earlier equation $\cos\theta (1-\alpha\beta) = (1-\cos\theta) ((\alpha-1) + (\beta-1))$ . If $\alpha+\beta =2$ and $1 = \alpha\beta$ , it is easy to see that $\alpha=\beta=1$ is the only solution by expanding $(\sqrt{\alpha}-\sqrt{\beta})^2=0$ . If, on the other hand, $\cos\theta = 1$ , then looking at the original form of $F(\theta,x,y)$ , we see that $F(0,x,y) = 6\pi - 6\arctan(x) +2x/(1+x^2) -6\arctan(y) +2y/(1+y^2) \ge 0$ , since $x,y \ge 0 \implies \arctan(x)+\arctan(y) \le \pi$ .

And that concludes the proof, since the only cases for which all three conditions are met lead to $\alpha = \beta = 1$ and, hence, $x=y=\tan^{-1}(\theta/2)$ . The minimum of $F(\theta, x,y)$ at these values is always zero. That’s right, all this work to end up with “nothing”. But, at least, the last four weeks have been anything but dull.

Update: Greg offered Lemma 7.4 from the same paper as another challenge (the sines, cosines and tangents are now transformed into hyperbolic trigonometric functions, with a few other changes, mostly in signs, thrown in there). This is a more hardcore-looking inequality, but the proof turns out to follow the steps of Lemma 7.1 almost identically. In particular, all the conditions for extrema are exactly the same, with the only difference being that cosine becomes hyperbolic cosine. It is an awesome exercise in calculus to check this for yourself. Do it. Unless you have something better to do.

Bringing the heat to Cal State LA

Posted on July 24, 2016 by Nicole Yunger Halpern

John Baez is a tough act to follow.

The mathematical physicist presented a colloquium at Cal State LA this May.¹ The talk’s title: “My Favorite Number.” The advertisement image: A purple “24” superimposed atop two egg cartons.

The colloquium concerned string theory. String theorists attempt to reconcile Einstein’s general relativity with quantum mechanics. Relativity concerns the large and the fast, like the sun and light. Quantum mechanics concerns the small, like atoms. Relativity and with quantum mechanics individually suggest that space-time consists of four dimensions: up-down, left-right, forward-backward, and time. String theory suggests that space-time has more than four dimensions. Counting dimensions leads theorists to John Baez’s favorite number.

His topic struck me as bold, simple, and deep. As an otherworldly window onto the pedestrian. John Baez became, when I saw the colloquium ad, a hero of mine.

And a tough act to follow.

I presented Cal State LA’s physics colloquium the week after John Baez. My title: “Quantum steampunk: Quantum information applied to thermodynamics.” Steampunk is a literary, artistic, and film genre. Stories take place during the 1800s—the Victorian era; the Industrial era; an age of soot, grime, innovation, and adventure. Into the 1800s, steampunkers transplant modern and beyond-modern technologies: automata, airships, time machines, etc. Example steampunk works include Will Smith’s 1999 film Wild Wild West. Steampunk weds the new with the old.

So does quantum information applied to thermodynamics. Thermodynamics budded off from the Industrial Revolution: The steam engine crowned industrial technology. Thinkers wondered how efficiently engines could run. Thinkers continue to wonder. But the steam engine no longer crowns technology; quantum physics (with other discoveries) does. Quantum information scientists study the roles of information, measurement, and correlations in heat, energy, entropy, and time. We wed the new with the old.

What image could encapsulate my talk? I couldn’t lean on egg cartons. I proposed a steampunk warrior—cravatted, begoggled, and spouting electricity. The proposal met with a polite cough of an email. Not all department members, Milan Mijic pointed out, had heard of steampunk.

Milan is a Cal State LA professor and my erstwhile host. We toured the palm-speckled campus around colloquium time. What, he asked, can quantum information contribute to thermodynamics?

Heat offers an example. Imagine a classical (nonquantum) system of particles. The particles carry kinetic energy, or energy of motion: They jiggle. Particles that bump into each other can exchange energy. We call that energy heat. Heat vexes engineers, breaking transistors and lowering engines’ efficiencies.

Like heat, work consists of energy. Work has more “orderliness” than the heat transferred by random jiggles. Examples of work exertion include the compression of a gas: A piston forces the particles to move in one direction, in concert. Consider, as another example, driving electrons around a circuit with an electric field. The field forces the electrons to move in the same direction. Work and heat account for all the changes in a system’s energy. So states the First Law of Thermodynamics.

Suppose that the system is quantum. It doesn’t necessarily have a well-defined energy. But we can stick the system in an electric field, and the system can exchange motional-type energy with other systems. How should we define “work” and “heat”?

Quantum information offers insights, such as via entropies. Entropies quantify how “mixed” or “disordered” states are. Disorder grows as heat suffuses a system. Entropies help us extend the First Law to quantum theory.

So I explained during the colloquium. Rarely have I relished engaging with an audience as much as I relished engaging with Cal State LA’s. Attendees made eye contact, posed questions, commented after the talk, and wrote notes. A student in a corner appeared to be writing homework solutions. But a presenter couldn’t have asked for more from the rest. One exclamation arrested me like a coin in the cogs of a grandfather clock.

I’d peppered my slides with steampunk art: paintings, drawings, stills from movies. The peppering had staved off boredom as I’d created the talk. I hoped that the peppering would stave off my audience’s boredom. I apologized about the trimmings.

“No!” cried a woman near the front. “It’s lovely!”

I was about to discuss experiments by Jukka Pekola’s group. Pekola’s group probes quantum thermodynamics using electronic circuits. The group measures heat by counting the electrons that hop from one part of the circuit to another. Single-electron transistors track tunneling (quantum movements) of single particles.

Heat complicates engineering, calculations, and California living. Heat scrambles signals, breaks devices, and lowers efficiencies. Quantum heat can evade definition. Thermodynamicists grind their teeth over heat.

“No!” the woman near the front had cried. “It’s lovely!”

She was referring to steampunk art. But her exclamation applied to my subject. Heat has not only practical importance, but also fundamental: Heat influences every law of thermodynamics. Thermodynamic law underpins much of physics as 24 underpins much of string theory. Lovely, I thought, indeed.

Cal State LA offered a new view of my subfield, an otherworldly window onto the pedestrian. The more pedestrian an idea—the more often the idea surfaces, the more of our world the idea accounts for—the deeper the physics. Heat seems as pedestrian as a Pokémon Go player. But maybe, someday, I’ll present an idea as simple, bold, and deep as the number 24.

A window onto Cal State LA.

With gratitude to Milan Mijic, and to Cal State LA’s Department of Physics and Astronomy, for their hospitality.

¹For nonacademics: A typical physics department hosts several presentations per week. A seminar relates research that the speaker has undertaken. The audience consists of department members who specialize in the speaker’s subfield. A department’s astrophysicists might host a Monday seminar; its quantum theorists, a Wednesday seminar; etc. One colloquium happens per week. Listeners gather from across the department. The speaker introduces a subfield, like the correction of errors made by quantum computers. Course lectures target students. Endowed lectures, often named after donors, target researchers.

What matters to me, and why?

Posted on June 26, 2016 by Nicole Yunger Halpern

Students at my college asked every Tuesday. They gathered in a white, windowed room near the center of campus. “We serve,” read advertisements, “soup, bread, and food for thought.” One professor or visitor would discuss human rights, family, religion, or another pepper in the chili of life.

I joined occasionally. I listened by the window, in the circle of chairs that ringed the speaker. Then I ventured from college into physics.

The questions “What matters to you, and why?” have chased me through physics. I ask experimentalists and theorists, professors and students: Why do you do science? Which papers catch your eye? Why have you devoted to quantum information more years than many spouses devote to marriages?

One physicist answered with another question. Chris Jarzynski works as a professor at the University of Maryland. He studies statistical mechanics—how particles typically act and how often particles act atypically; how materials shine, how gases push back when we compress them, and more.

“How,” Chris asked, “should we quantify precision?”

Chris had in mind nonequilibrium fluctuation theorems. Out-of-equilibrium systems have large-scale properties, like temperature, that change significantly.¹ Examples include white-bean soup cooling at a “What matters” lunch. The soup’s temperature drops to room temperature as the system approaches equilibrium.

Nonequilibrium. Tasty, tasty nonequilibrium.

Some out-of-equilibrium systems obey fluctuation theorems. Fluctuation theorems are equations derived in statistical mechanics. Imagine a DNA molecule floating in a watery solution. Water molecules buffet the strand, which twitches. But the strand’s shape doesn’t change much. The DNA is in equilibrium.

You can grab the strand’s ends and stretch them apart. The strand will leave equilibrium as its length changes. Imagine pulling the strand to some predetermined length. You’ll have exerted energy.

How much? The amount will vary if you repeat the experiment. Why? This trial began with the DNA curled this way; that trial began with the DNA curled that way. During this trial, the water batters the molecule more; during that trial, less. These discrepancies block us from predicting how much energy you’ll exert. But suppose you pick a number W. We can form predictions about the probability that you’ll have to exert an amount W of energy.

How do we predict? Using nonequilibrium fluctuation theorems.

Fluctuation theorems matter to me, as Quantum Frontiers regulars know. Why? Because I’ve written enough fluctuation-theorem articles to test even a statistical mechanic’s patience. More seriously, why do fluctuation theorems matter to me?

Fluctuation theorems fill a gap in the theory of statistical mechanics. Fluctuation theorems relate nonequilibrium processes (like the cooling of soup) to equilibrium systems (like room-temperature soup). Physicists can model equilibrium. But we know little about nonequilibrium. Fluctuation theorems bridge from the known (equilibrium) to the unknown (nonequilibrium).

Experiments take place out of equilibrium. (Stretching a DNA molecule changes the molecule’s length.) So we can measure properties of nonequilibrium processes. We can’t directly measure properties of equilibrium processes, which we can’t perform experimentally. But we can measure an equilibrium property indirectly: We perform nonequilibrium experiments, then plug our data into fluctuation theorems.

Which equilibrium property can we infer about? A free-energy difference, denoted by ΔF. Every equilibrated system (every room-temperature soup) has a free energy F. F represents the energy that the system can exert, such as the energy available to stretch a DNA molecule. Imagine subtracting one system’s free energy, F₁, from another system’s free energy, F₂. The subtraction yields a free-energy difference, ΔF = F₂ – F₁. We can infer the value of a ΔF from experiments.

How should we evaluate those experiments? Which experiments can we trust, and which need repeating?

Those questions mattered little to me, before I met Chris Jarzynski. Bridging equilibrium with nonequilibrium mattered to me, and bridging theory with experiment. Not experimental nitty-gritty.

I deserved a dunking in white-bean soup.

Suppose you performed infinitely many trials—stretched a DNA molecule infinitely many times. In each trial, you measured the energy exerted. You processed your data, then substituted into a fluctuation theorem. You could infer the exact value of ΔF.

But we can’t perform infinitely many trials. Imprecision mars our inference about ΔF. How does the imprecision relate to the number of trials performed?²

Chris and I adopted an information-theoretic approach. We quantified precision with a parameter $\delta$ . Suppose you want to estimate ΔF with some precision. How many trials should you expect to need to perform? We bounded the number $N_\delta$ of trials, using an entropy. The bound tightens an earlier estimate of Chris’s. If you perform $N_\delta$ trials, you can estimate ΔF with a percent error that we estimated. We illustrated our results by modeling a gas.

I’d never appreciated the texture and richness of precision. But richness precision has: A few decimal places distinguish Albert Einstein’s general theory of relativity from Isaac Newton’s 17th-century mechanics. Particle physicists calculate constants of nature to many decimal places. Such a calculation earned a nod on physicist Julian Schwinger’s headstone. Precision serves as the bread and soup of much physics. I’d sniffed the importance of precision, but not tasted it, until questioned by Chris Jarzynski.

The questioning continues. My college has discontinued its “What matters” series. But I ask scientist after scientist—thoughtful human being after thoughtful human being—“What matters to you, and why?” Asking, listening, reading, calculating, and self-regulating sharpen my answers those questions. My answers often squish beneath the bread knife in my cutlery drawer of criticism. Thank goodness that repeating trials can reduce our errors.

¹Or large-scale properties that will change. Imagine connecting the ends of a charged battery with a wire. Charge will flow from terminal to terminal, producing a current. You can measure, every minute, how quickly charge is flowing: You can measure how much current is flowing. The current won’t change much, for a while. But the current will die off as the battery nears depletion. A large-scale property (the current) appears constant but will change. Such a capacity to change characterizes nonequilibrium steady states (NESSes). NESSes form our second example of nonequilibrium states. Many-body localization forms a third, quantum example.

²Readers might object that scientists have tools for quantifying imprecision. Why not apply those tools? Because ΔF equals a logarithm, which is nonlinear. Other authors’ proposals appear in references 1-13 of our paper. Charlie Bennett addressed a related problem with his “acceptance ratio.” (Bennett also blogged about evil on Quantum Frontiers last month.)

Quantum braiding: It’s all in (and on) your head.

Posted on May 22, 2016 by Nicole Yunger Halpern

Morning sunlight illuminated John Preskill’s lecture notes about Caltech’s quantum-computation course, Ph 219. I’m TAing (the teaching assistant for) Ph 219. I previewed lecture material one sun-kissed Sunday.

Pasadena sunlight spilled through my window. So did the howling of a dog that’s deepened my appreciation for Billy Collins’s poem “Another reason why I don’t keep a gun in the house.” My desk space warmed up, and I unbuttoned my jacket. I underlined a phrase, braided my hair so my neck could cool, and flipped a page.

I flipped back. The phrase concerned a mathematical statement called the Yang-Baxter relation. A sunbeam had winked on in my mind: The Yang-Baxter relation described my hair.

The Yang-Baxter relation belongs to a branch of math called topology. Topology resembles geometry in its focus on shapes. Topologists study spheres, doughnuts, knots, and braids.

Topology describes some quantum physics. Scientists are harnessing this physics to build quantum computers. Alexei Kitaev largely dreamed up the harness. Alexei, a Caltech professor, is teaching Ph 219 this spring.¹ His computational scheme works like this.

We can encode information in radio signals, in letters printed on a page, in the pursing of one’s lips as one passes a howling dog’s owner, and in quantum particles. Imagine three particles on a tabletop.

Consider pushing the particles around like peas on a dinner plate. You could push peas 1 and 2 until they swapped places. The swap represents a computation, in Alexei’s scheme.²

The diagram below shows how the peas move. Imagine slicing the figure into horizontal strips. Each strip would show one instant in time. Letting time run amounts to following the diagram from bottom to top.

Arrows copied from John Preskill’s lecture notes. Peas added by the author.

Imagine swapping peas 1 and 3.

Humor me with one more swap, an interchange of 2 and 3.

Congratulations! You’ve modeled a significant quantum computation. You’ve also braided particles.

The author models a quantum computation.

Let’s recap: You began with peas 1, 2, and 3. You swapped 1 with 2, then 1 with 3, and then 2 with 3. The peas end up ordered oppositely the way they began—end up ordered as 3, 2, 1.

You could, instead, morph 1-2-3 into 3-2-1 via a different sequence of swaps. That sequence, or braid, appears below.

Congratulations! You’ve begun proving the Yang-Baxter relation. You’ve shown that each braid turns 1-2-3 into 3-2-1.

The relation states also that 1-2-3 is topologically equivalent to 3-2-1: Imagine standing atop pea 2 during the 1-2-3 braiding. You’d see peas 1 and 3 circle around you counterclockwise. You’d see the same circling if you stood atop pea 2 during the 3-2-1 braiding.

That Sunday morning, I looked at John’s swap diagrams. I looked at the hair draped over my left shoulder. I looked at John’s swap diagrams.

“Yang-Baxter relation” might sound, to nonspecialists, like a mouthful of tweed. It might sound like a sneeze in a musty library. But an eight-year-old could grasp half the relation. When I braid my hair, I pass my left hand over the back of my neck. Then, I pass my right hand over. But I could have passed the right hand first, then the left. The braid would have ended the same way. The braidings would look identical to a beetle hiding atop what had begun as the middle hunk of hair.

The Yang-Baxter relation.

I tried to keep reading John’s lecture notes, but the analogy mushroomed. Imagine spinning one pea atop the table.

A 360° rotation returns the pea to its initial orientation. You can’t distinguish the pea’s final state from its first. But a quantum particle’s state can change during a 360° rotation. Physicists illustrate such rotations with corkscrews.

A quantum corkscrew (“twisted worldribbon,” in technical jargon)

Like the corkscrews formed as I twirled my hair around a finger. I hadn’t realized that I was fidgeting till I found John’s analysis.

I gave up on his lecture notes as the analogy sprouted legs.

I’ve never mastered the fishtail braid. What computation might it represent? What about the French braid? You begin French-braiding by selecting a clump of hair. You add strands to the clump while braiding. The addition brings to mind particles created (and annihilated) during a topological quantum computation.

Ancient Greek statues wear elaborate hairstyles, replete with braids and twists. Could you decode a Greek hairdo? Might it represent the first 18 digits in pi? How long an algorithm could you run on Rapunzel’s hair?

Call me one bobby pin short of a bun. But shouldn’t a scientist find inspiration in every fiber of nature? The sunlight spilling through a window illuminates no less than the hair spilling over a shoulder. What grows on a quantum physicist’s head informs what grows in it.

¹Alexei and John trade off on teaching Ph 219. Alexei recommends the notes that John wrote while teaching in previous years.

²When your mother ordered you to quit playing with your food, you could have objected, “I’m modeling computations!”

PR-boxes in Minecraft

Posted on May 1, 2016 by tiyansi

As an undergraduate student at RWTH Aachen University, I asked Prof. Barbara Terhal to supervise my bachelor thesis. She told me about qCraft and asked whether I could implement PR-boxes in Minecraft. PR-boxes are named after their inventors Sandu Popescu and Daniel Rohrlich and have a rather simple behavior. Two parties, let’s call them Alice and Bob, find themselves at two different locations. They each have a box in which they can provide an input bit. And as soon as one of them has done this, he/she can obtain an output bit. The outcomes of the boxes are correlated and satisfy the following condition: If both input bits are 1, the output bits will be different, each 0 or 1 with probability 1/2. If at least one of the input bits is 0, the output bits will be the same, 0 or 1 with probability 1/2. Thus, input bits x and y, and output bits a and b of the PR-box satisfy x AND y = a⊕b, where ⊕ denotes addition modulo two. Neither Alice nor Bob can learn anything about the other one’s input from his/her input and output. This means that Alice and Bob cannot use the PR-boxes to signal to each other.

The motivation for PR-boxes arose from the Clauser-Horne-Shimony-Holt (CHSH) inequality. This Bell-like inequality bounds the correlation that can exist between two remote, non-signaling, classical systems described by local hidden variable theories. Experiments have now convincingly shown that quantum entanglement cannot be explained by local hidden variable theories. Furthermore, the CHSH inequality provides a method to distinguish quantum systems from super-quantum correlations. The correlation between the outputs of the PR-box goes beyond any quantum entanglement. If Alice and Bob were to share an entangled state they could only realize the correlation of the PR-box with probability at most cos²(π/8). PR-boxes are therefore, as far as we know, not physically realizable.

But PR-boxes would have impressive consequences. One of the most remarkable was shown by Wim van Dam in his Oxford PhD thesis in 1999. He proved that two parties can use these PR-boxes to compute any Boolean function f(x,y) of Alice´s input bit string x and Bob´s input bit string y, with only one bit of communication. This is fascinating due to the non-signaling condition fulfilled by PR-boxes. For instance, Alice and Bob could compare their two bit strings x and y of arbitrary length and compute whether or not they are the same. Using classical or quantum systems, one can show that there are lower bounds for the number of bits that need to be communicated between Alice and Bob, which grow with the length of the input bit strings. If Alice and Bob share PR-boxes, they only need sufficiently many PR-boxes (unfortunately, for arbitrary Boolean functions this number grows exponentially) and either Alice or Bob only has to send one bit to the other party. Another application is one-out-of-two oblivious transfer. In this scenario, Alice provides two bits and Bob can choose which of them he wants to know. Ideally, Alice does not learn which bit Bob has chosen and Bob does not learn anything about the other bit. One can use a PR-box to obtain this ideal behavior.

An exciting question for theorists is: why does nature allow for quantum correlations and entanglement but not for super-quantum correlations such as the PR-box? Is there a general physical principle at play? Research on PR-boxes could unveil such principle and explain why PR-boxes are not physically realizable but quantum entanglement is.

prboxAfter

But now in the Minecraft world PR-boxes are physically realized! I have built a modification that includes these non-local boxes as an extension of the qCraft modification. Each PR-box is divided into two blocks in order to give the two parties the possibility of spatially partitioning the inputs and outputs. The inputs and outputs are provided by using the in-built Redstone system. This works pretty much like building electrical circuits. The normal PR-boxes function similar as measurements on quantum mechanical states. An input is provided and the corresponding random output is obtained by energizing a block (like measuring the quantum state). This can only be done once. Afterwards, the output is maintained throughout the game. To avoid laborious redistribution and replacement after each usage, I have introduced a timed version of the PR-box in Minecraft. To get a better idea of what this all looks like, visit this demo video.

PR-boxes are interesting in particular in multiplayer scenarios since there are two parties needed to use them appropriately. For example, these new elements could be used to create multiplayer dungeons where the players have to communicate using only a small number of bits or provide a combined password to deactivate a trap. The timed PR-box may be used as a component of a Minecraft computer to simplify circuits using the compatibility with clocks.

I hope that you will try this modification and show how they can enhance gameplay in Minecraft! This mod as well as my thesis can be downloaded here. For me it was much fun to go from the first ideas how to realize PR-boxes in Minecraft to this final implementation. Just as qCraft, this is a playful way of exploring theoretical physics.

little by little and gate by gate

Posted on April 3, 2016 by Nicole Yunger Halpern

Washington state was drizzling on me. I was dashing from a shuttle to Building 112 on Microsoft’s campus. Microsoft has headquarters near Seattle. The state’s fir trees refreshed me. The campus’s vastness awed me. The conversations planned for the day enthused me. The drizzle dampened me.

Building 112 houses QuArC, one of Microsoft’s research teams. “QuArC” stands for “Quantum Architectures and Computation.” Team members develop quantum algorithms and codes. QuArC members write, as their leader Dr. Krysta Svore says, “software for computers that don’t exist.”

Small quantum computers exist. Large ones have eluded us like gold at the end of a Washington rainbow. Large quantum computers could revolutionize cybersecurity, materials engineering, and fundamental physics. Quantum computers are growing, in labs across the world. When they mature, the computers will need software.

Software consists of instructions. Computers follow instructions as we do. Suppose you want to find and read the poem “anyone lived in a pretty how town,” by 20th-century American poet e e cummings. You follow steps—for example:

1) Wake up your computer.
2) Type your password.
3) Hit “Enter.”
4) Kick yourself for entering the wrong password.
5) Type the right password.
6) Hit “Enter.”
7) Open a web browser.
8) Navigate to Google.
9) Type “anyone lived in a pretty how town e e cummings” into the search bar.
10) Hit “Enter.”
11) Click the Academy of American Poets’ link.
12) Exclaim, “Really? April is National Poetry Month?”
13) Read about National Poetry Month for four-and-a-half minutes.
14) Remember that you intended to look up a poem.
15) Return to the Academy of American Poets’ “anyone lived” webpage.
16) Read the poem.

We break tasks into chunks executed sequentially. So do software writers. Microsoft researchers break up tasks intended for quantum computers to perform.

Your computer completes tasks by sending electrons through circuits. Quantum computers will have circuits. A circuit contains wires, which carry information. The wires run through circuit components called gates. Gates manipulate the information in the wires. A gate can, for instance, add the number carried by this wire to the number carried by that wire.

Running a circuit amounts to completing a task, like hunting a poem. Computer engineers break each circuit into wires and gates, as we broke poem-hunting into steps 1-16.¹

Circuits hearten me, because decomposing tasks heartens me. Suppose I demanded that you read a textbook in a week, or create a seminar in a day, or crack a cybersecurity system. You’d gape like a visitor to Washington who’s realized that she’s forgotten her umbrella.

Suppose I demanded instead that you read five pages, or create one Powerpoint slide, or design one element of a quantum circuit. You might gape. But you’d have more hope.² Life looks more manageable when broken into circuit elements.

Circuit decomposition—and life decomposition—brings to mind “anyone lived in a pretty how town.” The poem concerns two characters who revel in everyday events. Laughter, rain, and stars mark their time. The more the characters attune to nature’s rhythm, the more vibrantly they live:³

little by little and was by was

all by all and deep by deep
and more by more they dream their sleep

Those lines play in my mind when a seminar looms, or a trip to Washington coincident with a paper deadline, or a quantum circuit I’ve no idea how to parse. Break down the task, I tell myself. Inch by inch, we advance. Little by little and drop by drop, step by step and gate by gate.

Not what e e cummings imagined when composing “anyone lived in a pretty how town”

Unless you’re dashing through raindrops to gate designers at Microsoft. I don’t recommend inching through Washington’s rain. But I would have dashed in a drought. What sees us through everyday struggles—the inching of science—if not enthusiasm? We tackle circuits and struggles because, beyond the drizzle, lie ideas and conversations that energize us to run.

e e cummings

With thanks to QuArC members for their time and hospitality.

¹One might object that Steps 4 and 14 don’t belong in the instructions. But software involves error correction.

²Of course you can design a quantum-circuit element. Anyone can quantum.

³Even after the characters die.

March madness and quantum memory

Posted on March 13, 2016 by Nicole Yunger Halpern

Madness seized me this March. It pounced before newspaper and Facebook feeds began buzzing about basketball.¹ I haven’t bought tickets or bet on teams. I don’t obsess over jump-shot statistics. But madness infected me two weeks ago. I began talking with condensed-matter physicists.

Condensed-matter physicists study collections of many particles. Example collections include magnets and crystals. And the semiconductors in the iPhones that report NCAA updates.

Caltech professor Gil Refael studies condensed matter. He specializes in many-body localization. By “many-body,” I mean “involving lots of quantum particles.” By “localization,” I mean “each particle anchors itself to one spot.” We’d expect these particles to spread out, like the eau de hotdog that wafts across a basketball court. But Gil’s particles stay put.

How many-body-localized particles don’t behave.

Experts call many-body localization “MBL.” I’ve accidentally been calling many-body localization “MLB.” Hence the madness. You try injecting baseball into quantum discussions without sounding one out short of an inning.²

I wouldn’t have minded if the madness had erupted in October. The World Series began in October. The World Series involves Major League Baseball, what normal people call “the MLB.” The MLB dominates October; the NCAA dominates March. Preoccupation with the MLB during basketball season embarrasses me. I feel like I’ve bet on the last team that I could remember winning the championship, then realized that that team had last won in 2002.

March madness has been infecting my thoughts about many-body localization. I keep envisioning a localized particle as dribbling a basketball in place, opponents circling, fans screaming, “Go for it!” Then I recall that I’m pondering MBL…I mean, MLB…or the other way around. The dribbler gives way to a baseball player who refuses to abandon first base for second. Then I recall that I should be pondering particles, not playbooks.

Localized particles.

Recollection holds the key to MBL’s importance. Colleagues of Gil’s want to build quantum computers. Computers store information in memories. Memories must retain their contents; information mustn’t dribble away.

Consider recording halftime scores. You could encode the scores in the locations of the particles that form eau de hotdog. (Imagine you have advanced technology that manipulates scent particles.) If Duke had scored one point, you’d put this particle here; if Florida had scored two, you’d put that particle there. The particles—as smells too often do—would drift. You’d lose the information you’d encoded. Better to paint the scores onto scorecards. Dry paint stays put, preserving information.

The quantum particles studied by Gil stay put. They inspire scientists who develop memories for quantum computers. Quantum computation is gunning for a Most Valuable Player plaque in the technology hall of fame. Many-body localized systems could contain Most Valuable Particles.

Remembering the past, some say, one can help one read the future. I don’t memorize teams’ records. I can’t advise you about whom root for. But prospects for quantum memories are brightening. Bet on quantum information science.

¹Non-American readers: University basketball teams compete in a tournament each March. The National Collegiate Athletic Association (NCAA) hosts the tournament. Fans glue themselves to TVs, tweet exaltations and frustrations, and excommunicate friends who support opposing teams.

²Without being John Preskill.

Some like it cold.

Posted on February 7, 2016 by Nicole Yunger Halpern

When I reached IBM’s Watson research center, I’d barely seen Aaron in three weeks. Aaron is an experimentalist pursuing a physics PhD at Caltech. I eat dinner with him and other friends, most Fridays. The group would gather on a sidewalk in the November dusk, those three weeks. Light would spill from a lamppost, and we’d tuck our hands into our pockets against the chill. Aaron’s wife would shake her head.

“The fridge is running,” she’d explain.

Aaron cools down mechanical devices to near absolute zero. Absolute zero is the lowest temperature possible,¹ lower than outer space’s temperature. Cold magnifies certain quantum behaviors. Researchers observe those behaviors in small systems, such as nanoscale devices (devices about 10^-9meters long). Aaron studies few-centimeter-long devices. Offsetting the devices’ size with cold might coax them into exhibiting quantum behaviors.

The cooling sounds as effortless as teaching a cat to play fetch. Aaron lowers his fridge’s temperature in steps. Each step involves checking for leaks: A mix of two fluids—two types of helium—cools the fridge. One type of helium costs about $800 per liter. Lose too much helium, and you’ve lost your shot at graduating. Each leak requires Aaron to warm the fridge, then re-cool it. He hauled helium and pampered the fridge for ten days, before the temperature reached 10 milliKelvins (0.01 units above absolute zero). He then worked like…well, like a grad student to check for quantum behaviors.

Aaron came to mind at IBM.

“How long does cooling your fridge take?” I asked Nick Bronn.

Nick works at Watson, IBM’s research center in Yorktown Heights, New York. Watson has sweeping architecture frosted with glass and stone. The building reminded me of Fred Astaire: decades-old, yet classy. I found Nick outside the cafeteria, nursing a coffee. He had sandy hair, more piercings than I, and a mandate to build a quantum computer.

IBM Watson

“Might I look around your lab?” I asked.

“Definitely!” Nick fished out an ID badge; grabbed his coffee cup; and whisked me down a wide, window-paneled hall.

Different researchers, across the world, are building quantum computers from different materials. IBMers use superconductors. Superconductors are tiny circuits. They function at low temperatures, so IBM has seven closet-sized fridges. Different teams use different fridges to tackle different challenges to computing.

Nick found a fridge that wasn’t running. He climbed half-inside, pointed at metallic wires and canisters, and explained how they work. I wondered how his cooling process compared to Aaron’s.

“You push a button.” Nick shrugged. “The fridge cools in two days.”

IBM, I learned, has dry fridges. Aaron uses a wet fridge. Dry and wet fridges operate differently, though both require helium. Aaron’s wet fridge vibrates less, jiggling his experiment less. Jiggling relates to transferring heat. Heat suppresses the quantum behaviors Aaron hopes to observe.

Heat and warmth manifest in many ways, in physics. Count Rumford, an 18th-century American-Brit, conjectured the relationship between heat and jiggling. He noticed that drilling holes into canons immersed in water boils the water. The drill bits rotated–moved in circles–transferring energy of movement to the canons, which heated up. Heat enraptures me because it relates to entropy, a measure of disorderliness and ignorance. The flow of heat helps explain why time flows in just one direction.

A physicist friend of mine writes papers, he says, when catalyzed by “blinding rage.” He reads a paper by someone else, whose misunderstandings anger him. His wrath boils over into a research project.

Warmth manifests as the welcoming of a visitor into one’s lab. Nick didn’t know me from Fred Astaire, but he gave me the benefit of the doubt. He let me pepper him with questions and invited more questions.

Warmth manifests as a 500-word disquisition on fridges. I asked Aaron, via email, about how his cooling compares to IBM’s. I expected two sentences and a link to Wikipedia, since Aaron works 12-hour shifts. But he took pity on his theorist friend. He also warmed to his subject. Can’t you sense the zeal in “Helium is the only substance in the world that will naturally isotopically separate (neat!)”? No knowledge of isotopic separation required.

Many quantum scientists like it cold. But understanding, curiosity, and teamwork fire us up. Anyone under the sway of those elements of science likes it hot.

With thanks to Aaron and Nick. Thanks also to John Smolin and IBM Watson’s quantum-computing-theory team for their hospitality.

¹In many situations. Some systems, like small magnets, can access negative temperatures.

Life, cellular automata, and mentoring

Posted on January 10, 2016 by Nicole Yunger Halpern

One night last July, IQIM postdoc Ning Bao emailed me a photo. He’d found a soda can that read, “Share a Coke with Patrick.”

Ning and I were co-mentoring two Summer Undergraduate Research Fellows, or SURFers. One mentee received Ning’s photo: Caltech physics major Patrick Rall.

“Haha,” Patrick emailed back. “I’ll share a Coke.”

Patrick, Ning, and I shared the intellectual equivalent of a six-pack last summer. We shared papers, meals, frustrations, hopes, late-night emails (from Patrick and Ning), 7-AM emails (from me), and webcomic strips. Now a senior, Patrick is co-authoring a paper about his SURF project.

The project grew from the question “What would happen if we quantized Conway’s Game of Life?” (For readers unfamiliar with the game, I’ll explain below.) Lessons we learned about the Game of Life overlapped with lessons I learned about life, as a first-time mentor. The soda fountain of topics contained the following flavors.

Update rules: Till last spring, I’d been burrowing into two models for out-of-equilibrium physics. PhD students burrow as no prairie dogs can. But, given five years in Caltech’s grassland, I wanted to explore. I wanted an update.

Ning and I had trespassed upon quantum game theory months earlier. Consider a nonquantum game, such as the Prisoner’s Dilemma or an election. Suppose that players have physical systems, such as photons (particles of light), that occupy superposed or entangled states. These quantum resources can change the landscape of the game’s possible outcomes. These changes clarify how we can harness quantum mechanics to process, transmit, and secure information.

How might quantum resources change Conway’s Game of Life, or GoL? British mathematician John Conway invented the game in 1970. Imagine a square board divided into smaller squares, or cells. On each cell sits a white or a black tile. Black represents a living organism; white represents a lack thereof.

Conway modeled population dynamics with an update rule. If prairie dogs overpopulate a field, some die from overcrowding. If a black cell borders more than three black neighbors, a white tile replaces the black. If separated from its pack, a prairie dog dies from isolation. If a black tile borders too few black neighbors, we exchange the black for a white. Mathematics columnist Martin Gardner detailed the rest of Conway’s update rule in this 1970 article.

Updating the board repeatedly evolves the population. Black and white shapes might flicker and undulate. Space-ship-like shapes can glide across the board. A simple update rule can generate complex outcomes—including, I found, frustrations, hopes, responsibility for another human’s contentment, and more meetings than I’d realized could fit in one summer.

Modeled by Conway’s Game of Life. And by PhD students.

Initial conditions: The evolution depends on the initial state, on how you distribute white and black tiles when preparing the board. Imagine choosing the initial state randomly from all the possibilities. White likely mingles with about as much black. The random initial condition might not generate eye-catchers such as gliders. The board might fade to, and remain, one color.*

Enthusiasm can fade as research drags onward. Project Quantum GoL has continued gliding due to its initial condition: The spring afternoon on which Ning, Patrick, and I observed the firmness of each other’s handshakes; Patrick walked Ning and me through a CV that could have intimidated a postdoc; and everyone tried to soothe everyone else’s nerves but occasionally avoided eye contact.

I don’t mean that awkwardness sustained the project. The awkwardness faded, as exclamation points and smiley faces crept into our emails. I mean that Ning and I had the fortune to entice Patrick. We signed up a bundle of enthusiasm, creativity, programming skills, and determination. That determination perpetuated the project through the summer and beyond. Initial conditions can determine a system’s evolution.

Long-distance correlations: “Sure, I’d love to have dinner with you both! Thank you for the invitation!”

Lincoln Carr, a Colorado School of Mines professor, visited in June. Lincoln’s group, I’d heard, was exploring quantum GoLs.** He studies entanglement (quantum correlations) in many-particle systems. When I reached out, Lincoln welcomed our SURF group to collaborate.

I relished coordinating his visit with the mentees. How many SURFers could say that a professor had visited for his or her sake? When I invited Patrick to dinner with Lincoln, Patrick lit up like a sunrise over grasslands.

Our SURF group began skyping with Mines every Wednesday. We brainstorm, analyze, trade code, and kvetch with Mines student Logan Hillberry and colleagues. They offer insights about condensed matter; Patrick, about data processing and efficiency; I, about entanglement theory; and Ning, about entropy and time evolution.

We’ve learned together about long-range entanglement, about correlations between far-apart quantum systems. Thank goodness for skype and email that correlate far-apart research groups. Everyone would have learned less alone.

Long-distance correlations between quantum states and between research groups

Time evolution: Logan and Patrick simulated quantum systems inspired by Conway’s GoL. Each researcher coded a simulation, or mathematical model, of a quantum system. They agreed on a nonquantum update rule; Logan quantized it in one way (constructed one quantum analog of the rule); and Patrick quantized the rule another way. They chose initial conditions, let their systems evolve, and waited.

In July, I noticed that Patrick brought a hand-sized green spiral notepad to meetings. He would synopsize his progress, and brainstorm questions, on the notepad before arriving. He jotted suggestions as we talked.

The notepad began guiding meetings in July. Patrick now steers discussions, ticking items off his agenda. The agenda I’ve typed remains minimized on my laptop till he finishes. My agenda contains few points absent from his, and his contains points not in mine.

Patrick and Logan are comparing their results. Behaviors of their simulations, they’ve found, depend on how they quantized their update rule. One might expect the update rule to determine a system’s evolution. One might expect the SURF program’s template to determine how research and mentoring skills evolve. But how we implement update rules matters.

Caltech’s 2015 quantum-information-theory Summer Undergraduate Research Fellows and mentors

Life: I’ve learned, during the past six months, about Conway’s Game of Life, simulations, and many-body entanglement. I’ve learned how to suggest references and experts when I can’t answer a question. I’ve learned that editing SURF reports by hand costs me less time than editing electronically. I’ve learned where Patrick and his family vacation, that he’s studying Chinese, and how undergrads regard on-campus dining. Conway’s Game of Life has expanded this prairie dog’s view of the grassland more than expected.

I’ll drink a Coke to that.

Glossary: Conway’s GoL is a cellular automaton. A cellular automaton consists of a board whose tiles change according to some update rule. Different cellular automata correspond to different board shapes, to boards of different dimensions, to different types of tiles, and to different update rules.

*Reversible cellular automata have greater probabilities (than the GoL has) of updating random initial states through dull-looking evolutions.

**Others have pondered quantum variations on Conway’s GoL.

Quantum Information: Episode II: The Tools’ Applications

Posted on December 27, 2015 by Nicole Yunger Halpern

Monday dawns. Headlines report that “Star Wars: Episode VII” has earned more money, during its opening weekend, than I hope to earn in my lifetime. Trading the newspaper for my laptop, I learn that a friend has discovered ThinkGeek’s BB-8 plushie. “I want one!” she exclaims in a Facebook post. “Because BB-8 definitely needs to be hugged.”

BB-8 plays sidekick to Star Wars hero Poe Dameron. The droid has a spherical body covered with metallic panels and lights.Mr. Gadget and Frosty the Snowman could have spawned such offspring. BB-8 has captured viewers’ hearts, and its chirps have captured cell-phone ringtones.

ThinkGeek’s BB-8 plushie

Still, I scratch my head over my friend’s Facebook post. Hugged? Why would she hug…

Oh. Oops.

I’ve mentally verbalized “BB-8” as “BB84.” BB84 denotes an application of quantum theory to cryptography. Cryptographers safeguard information from eavesdroppers and tampering. I’ve been thinking that my friend wants to hug a safety protocol.

Charles Bennett and Gilles Brassard invented BB84 in 1984. Imagine wanting to tell someone a secret. Suppose I wish to coordinate, with a classmate, the purchase of a BB-8 plushie for our friend the droid-hugger. Suppose that the classmate and I can communicate only via a public channel on which the droid-hugger eavesdrops.

Cryptographers advise me to send my classmate a key. A key is a random string of letters, such as CCCAAACCABACA. I’ll encode my message with the string, with which my classmate will decode the message.

I have to transmit the key via the public channel. But the droid-hugger eavesdrops on the public channel. Haven’t we taken one step forward and one step back? Why would the key secure our information?

Because quantum-information science enables me to to transmit the key without the droid-hugger’s obtaining it. I won’t transmit random letters; I’ll transmit quantum states. That is, I’ll transmit physical systems, such as photons (particles of light), whose properties encode quantum information.

A nonquantum letter has a value, such as A or B or C. Each letter has one and only one value, regardless of whether anyone knows what value the letter has. You can learn the value by measuring (looking at) the letter. We can’t necessarily associate such a value with a quantum state. Imagine my classmate measuring a state I send. Which value the measurement device outputs depends on chance and on how my classmate looks at the state.

If the droid-hugger intercepts and measures the state, she’ll change it. My classmate and I will notice such changes. We’ll scrap our key and repeat the BB84 protocol until the droid-hugger quits eavesdropping.

BB84 launched quantum cryptography, the safeguarding of information with quantum physics. Today’s quantum cryptographers rely on BB84 as you rely, when planning a holiday feast, on a carrot-cake recipe that passed your brother’s taste test on his birthday. Quantum cryptographers construct protocols dependent on lines like “The message sender and receiver are assumed to share a key distributed, e.g., via the BB84 protocol.”

BB84 has become a primitive task, a solved problem whose results we invoke in more-complicated problems. Other quantum-information primitives include (warning: jargon ahead) entanglement distillation, entanglement dilution, quantum data compression, and quantum-state merging. Quantum-information scientists solved many primitive problems during the 1990s and early 2000s. You can apply those primitives, even if you’ve forgotten how to prove them.

A primitive task, like quantum-entanglement distillation

Those primitives appear to darken quantum information’s horizons. The spring before I started my PhD, an older physicist asked me why I was specializing in quantum information theory. Haven’t all the problems been solved? he asked. Isn’t quantum information theory “dead”?

Imagine discovering how to power plasma blades with kyber crystals. Would you declare, “Problem solved” and relegate your blades to the attic? Or would you apply your tool to defending freedom?

Primitive quantum-information tools are unknotting problems throughout physics—in computer science; chemistry; optics (the study of light); thermodynamics (the study of work, heat, and efficiency); and string theory. My advisor has tracked how uses of “entanglement,” a quantum-information term, have swelled in high-energy-physics papers.

A colleague of that older physicist views quantum information theory as a toolkit, a perspective, a lens through which to view science. During the 1700s, the calculus invented by Isaac Newton and Gottfried Leibniz revolutionized physics. Emmy Noether (1882—1935) recast physics in terms of symmetries and conservation laws. (If the forces acting on a system don’t change in time, for example, the system doesn’t gain or lose energy. A constant force is invariant under, or symmetric with respect to, the progression of time. This symmetry implies that the system’s energy is conserved.) We can cast physics instead (jargon ahead) in terms of the minimization of a free energy or an action.

Quantum information theory, this physicist predicted, will revolutionize physics as calculus, symmetries, conservation, and free energy have. Quantum-information tools such as entropies, entanglement, and qubits will bleed into subfields of physics as Lucasfilm has bled into the fanfiction, LEGO, and Halloween-costume markets.

BB84, and the solution of other primitives, have not killed quantum information. They’ve empowered it to spread—thankfully, to this early-career quantum information scientist. Never mind BB-8; I’d rather hug BB84. Perhaps I shall. Engineers have realized technologies that debuted on Star Trek; quantum mechanics has secured key sharing; bakers have crafted cakes shaped like the Internet; and a droid’s popularity rivals R2D2’s. Maybe next Monday will bring a BB84 plushie.

The author hugging the BB84 paper and a plushie. On my wish list: a combination of the two.

Quantum Frontiers

A blog by the Institute for Quantum Information and Matter @ Caltech

Category Archives: Theoretical highlights

Greg Kuperberg’s calculus problem

Bringing the heat to Cal State LA

What matters to me, and why?

Quantum braiding: It’s all in (and on) your head.

PR-boxes in Minecraft

little by little and gate by gate

March madness and quantum memory

Some like it cold.

Life, cellular automata, and mentoring

Quantum Information: Episode II: The Tools’ Applications

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this: