More Brainteasers

Posted on by

As promised, I’m back to tell you more about myself and tickle your brain! I’m terribly sorry for giving such a short description of my background in my last post. If I had to describe myself in another \leq 5 words, I’d write: “Breakdancing, bodybuilding physicist… Ladies: single.”

Problem 1: A thousand balloons numbered 1, 2, … , 1000 are arranged in a circle. Starting with balloon 1, every alternating balloon is popped. So balloon 1 is popped, balloon 3 is popped, balloon 5 is popped, and so on until balloon 999 is popped. But the process does not stop here! We keep going around the circle with the remaining balloons and pop every other one. So next balloon 2 is popped, balloon 4 is skipped, balloon 6 is popped, and so on. This process continues until only one balloon is left remaining; which is the last balloon standing?

A thousand red balloons numbered from 1 to 1000. Starting at the gold star, we pop every other balloon while traveling clockwise. Which is the last balloon remaining?

A thousand red balloons numbered from 1 to 1000. Starting at the gold star, we pop every other balloon while traveling clockwise. Which is the last balloon remaining?

It is of course easy to solve Problem 1 via brute force, but can you think of a more elegant solution? Do you really need to go around the circle log(n) times? If you get stuck, try working on Problem 2 for a while:

Problem 2: A thousand people stand in single file on a game show. Each person is wearing a hat which is either black or white. Each person can see the hats of all the people in front of them in line but they cannot see their own hat. Starting with the person at the back of the line and progressing forward, the game show host will ask, “What color is your hat?” Each contestant is only permitted to answer “black” or “white.” For each correct answer, the host will donate $1 to charity. If the contestants are allowed to discuss a strategy before they are lined up and given their hats, how much can they guarantee will be donated to charity?

If you managed to solve Problem 2, Problem 3 should be easy.

Problem 3: Now each person is given a hat which is one of n colors, and is allowed to answer the host’s question by giving any of the n colors. How much can the contestants guarantee will be donated to charity?

Problem 4: You are given ten coin-making machines which produce coins weighing 2 grams each. Each coin-maker can produce infinitely many coins. One of the ten machines, however, is defective and produces coins weighing 1 gram each. You are also given a scientific balance (with a numerical output). How many times must you use the balance to determine which machine is defective? What if the weight of the coins produced by the rogue machine is unknown?

I happen to be very good personal friends with Count von Count. One day as we were walking through Splash Castle, the Count told me he had passed his arithmetic class and was throwing a graduation party! Alas, before he could host the get-together, he needed to solve a problem on injective mappings from powersets to subsets of the natural numbers…

Problem 5: The Count has a thousand bottles of apple juice for his party, but one of the bottles contains spoiled juice! This spoiled juice induces tummy aches roughly a day after being consumed, and the Count wants to avoid lawsuits brought on by the innocent patrons of Sesame Place. Luckily, there is just enough time before the party for ten of the Count’s friends to perform exactly one round of taste-testing, during which they can drink from as many bottles as they please. How can the ten friends determine which bottle is both tummy ache- and lawsuit-inducing? You can assume Count’s friends have promised not to sue him if they get sick.

Please let me know what you think of these problems in the comments! Too easy? Too hard? Want more? Tell me so!

Jostling the unreal in Oxford

Posted on by
5

Oxford, where the real and the unreal jostle in the streets, where windows open into other worlds…

So wrote Philip Pullman, author of The Golden Compass and its sequels. In the series, a girl wanders from the Oxford in another world to the Oxford in ours.

I’ve been honored to wander Oxford this fall. Visiting Oscar Dahlsten and Jon Barrett, I’ve been moonlighting in Vlatko Vedral’s QI group. We’re interweaving 21st-century knowledge about electrons and information with a Victorian fixation on energy and engines. This research program, quantum thermodynamics, should open a window onto our world.

Radcliffe camera

A new world. At least, a world new to the author.

To study our world from another angle, Oxford researchers are jostling the unreal. Oscar, Jon, Andrew Garner, and others are studying generalized probabilistic theories, or GPTs.

What’s a specific probabilistic theory, let alone a generalized one? In everyday, classical contexts, probabilities combine according to rules you know. Suppose you have a 90% chance of arriving in London-Heathrow Airport at 7:30 AM next Sunday. Suppose that, if you arrive in Heathrow at 7:30 AM, you’ll have a 70% chance of catching the 8:05 AM bus to Oxford. You have a probability 0.9 * 0.7 = 0.63 of arriving in Heathrow at 7:30 and catching the 8:05 bus. Why 0.9 * 0.7? Why not 0.90.7, or 0.9/(2 * 0.7)? How might probabilities combine, GPT researchers ask, and why do they combine as they do?

Not that, in GPTs, probabilities combine as in 0.9/(2 * 0.7). Consider the 0.9/(2 * 0.7) plucked from a daydream inspired by this City of Dreaming Spires. But probabilities do combine in ways we wouldn’t expect. By entangling two particles, separating them, and measuring one, you immediately change the probability that a measurement of Particle 2 yields some outcome. John Bell explored, and experimentalists have checked, statistics generated by entanglement. These statistics disobey rules that govern Heathrow-and-bus statistics. As do entanglement statistics, so do effects of quantum phenomena like discord, negative Wigner functions, and weak measurements. Quantum theory and its contrast with classicality force us to reconsider probability.
Continue reading →

Fundamental Physics Prize Prediction: Green and Schwarz

Posted on by
9
Michael Green

Michael Green

John Schwarz

John Schwarz

The big news today is the announcement of the nominees for the 2014 Fundamental Physics Prize: (1) Michael Green and John Schwarz, for pioneering contributions to string theory, (2) Joseph Polchinski, for discovering the central role of D-branes in string theory, and (3) Andrew Strominger and Cumrun Vafa, for discovering (using D-branes) the microscopic origin of black hole entropy in string theory. As in past years, all the nominees are marvelously deserving. The winner of the $3 million prize will be announced in San Francisco on December 12; the others will receive the $300,000 Physics Frontiers Prize.

I wrote about my admiration for Joe Polchinski when he was nominated last year, and I have also greatly admired the work of Strominger and Vafa for many years. But the story of Green and Schwarz is especially compelling. String theory, which was originally proposed as a theory of the strong interaction, had been an active research area from 1968 through the early 70s. But when asymptotic freedom was discovered in 1973, and quantum chromodynamics became clearly established as the right theory of the strong interaction, interest in string theory collapsed. Even the 1974 proposal by Scherk and Schwarz that string theory is really a compelling candidate for a quantum theory of gravity failed to generate much excitement.

A faithful few continued to develop string theory through the late 70s and early 80’s, particularly Green and Schwarz, who began collaborating in 1979. Together they clarified the different variants of the theory, which they named Types I, IIA, and IIB, and which were later recognized as different solutions to a single underlying theory (sometimes called M-theory). In retrospect, Green and Schwarz were making remarkable progress, but were still largely ignored.

In 1983, Luis Alvarez-Gaume and Edward Witten analyzed the gravitational anomalies that afflict higher dimensional “chiral” theories (in which left-handed and right-handed particles behave differently), and discovered a beautiful cancellation of these anomalies in the Type IIB string theory. But anomalies, which render a theory inconsistent, seemed to be a nail in the coffin of Type I theory, at that time the best hope for uniting gravitation with the other fundamental (gauge) interactions.

Then, working together at the Aspen Center for Physics during the summer of 1984, Green and Schwarz discovered an even more miraculous cancellation of anomalies in Type I string theory, which worked for only one possible gauge group: SO(32). (Within days they and others found that anomalies cancel for E8 X E8 as well, which provided the impetus for the invention of the heterotic string theory.) The anomaly cancellation drove a surge of enthusiasm for string theory as a unified theory of fundamental physics. The transformation of string theory from a backwater to the hottest topic in physics occurred virtually overnight. It was an exciting time.

When John turned 60 in 2001, I contributed a poem to a book assembled in his honor, hoping to capture in the poem the transformation that Green and Schwarz fomented (and also to express irritation about the widespread misspelling of “Schwarz”). I have appended the poem below, along with the photo of myself I included at the time to express my appreciation for strings.

I’ll be delighted if Polchinski, or Strominger and Vafa win the prize — they deserve it. But it will be especially satisfying if Green and Schwarz win. They started it all, and refused to give up.

To John Schwarz

Thirty years ago or more
John saw what physics had in store.
He had a vision of a string
And focused on that one big thing.

But then in nineteen-seven-three
Most physicists had to agree
That hadrons blasted to debris
Were well described by QCD.

The string, it seemed, by then was dead.
But John said: “It’s space-time instead!
The string can be revived again.
Give masses twenty powers of ten!”

Then Dr. Green and Dr. Black,
Writing papers by the stack,
Made One, Two-A, and Two-B glisten.
Why is it none of us would listen?

We said, “Who cares if super tricks
Bring D to ten from twenty-six?
Your theory must have fatal flaws.
Anomalies will doom your cause.”

If you weren’t there you couldn’t know
The impact of that mightly blow:
“The Green-Schwarz theory could be true —
It works for S-O-thirty-two!”

Then strings of course became the rage
And young folks of a certain age
Could not resist their siren call:
One theory that explains it all.

Because he never would give in,
Pursued his dream with discipline,
John Schwarz has been a hero to me.
So please, don’t spell it with a “t”!

Expressing my admiration for strings in 2001

Expressing my admiration for strings in 2001.

Polarizer: Rise of the Efficiency

Posted on by
6

How should a visitor to Zürich spend her weekend?

Launch this question at a Swiss lunchtable, and you split diners into two camps. To take advantage of Zürich, some say, visit Geneva, Lucerne, or another spot outside Zürich. Other locals suggest museums, the lake, and the 19th-century ETH building.

P1040429

The 19th-century ETH building

ETH, short for a German name I’ve never pronounced, is the polytechnic from which Einstein graduated. The polytechnic houses a quantum-information (QI) theory group that’s pioneering ideas I’ve blogged about: single-shot information, epsilonification, and small-scale thermodynamics. While visiting the group this August, I triggered an avalanche of tourism advice. Caught between two camps, I chose Option Three: Contemplate polar codes.

Polar codes compress information into the smallest space possible. Imagine you write a message (say, a Zürich travel guide) and want to encode it in the fewest possible symbols (so it fits in my camera bag). The longer the message, the fewer encoding symbols you need per encoded symbol: The more punch each code letter can pack. As the message grows, the encoding-to-encoded ratio decreases. The lowest possible ratio is a number, represented by H, called the Shannon entropy.

So established Claude E. Shannon in 1948. But Shannon didn’t know how to code at efficiency H. Not for 51 years did we know.

I learned how, just before that weekend. ETH student David Sutter walked me through polar codes as though down Zürich’s Banhofstrasse.

P1040385

The Banhofstrasse, one of Zürich’s trendiest streets, early on a Sunday.

Say you’re encoding n copies of a random variable. When I say, “random variable,” think, “character in the travel guide.” Just as each character is one of 26 letters, each variable has one of many possible values.

Suppose the variables are independent and identically distributed. Even if you know some variables’ values, you can’t guess others’. Cryptoquote players might object that we can infer unknown from known letters. For example, a three-letter word that begins with “th” likely ends with “e.” But our message lacks patterns.

Think of the variables as diners at my lunchtable. Asking how to fill a weekend in Zürich—splitting the diners—I resembled the polarizer.

The polarizer is a mathematical object that sounds like an Arnold Schwarzenegger film and acts on the variables. Just as some diners pointed me outside Zürich, the polarizer gives some variables one property. Just some diners pointed me to within Zürich, the polarizer gives some variables another property. Just as I pointed myself at polar codes, the polarizer gives some variables a third property.

These properties involve entropy. Entropy quantifies uncertainty about a variable’s value—about which of the 26 letters a character represents. Even if you know the early variables’ values, you can’t guess the later variables’. But we can guess some polarized variables’ values. Call the first polarized variable u1, the second u2, etc. If we can guess the value of some ui, that ui has low entropy. If we can’t guess the value, ui has high entropy. The Nicole-esque variables have entropies like the earnings of Terminator Salvation: noteworthy but not chart-topping.

To recap: We want to squeeze a message into the tiniest space possible. Even if we know early variables’ values, we can’t infer later variables’. Applying the polarizer, we split the variables into low-, high-, and middling-entropy flocks. We can guess the value of each low-entropy ui, if we know the foregoing uh’s.

Almost finished!

In your camera-size travel guide, transcribe the high-entropy ui’s. These ui’s suggest the values of the low-entropy ui’s. When you want to decode the guide, guess the low-entropy ui’s. Then reverse the polarizer to reconstruct much of the original text.

The longer the original travel guide, the fewer errors you make while decoding, and the smaller the ratio of the encoded guide’s length to the original guide’s length. That ratio shrinks–as the guide’s length grows–to H. You’ve compressed a message maximally efficiently. As the Swiss say: Glückwünsche.

How does compression relate to QI? Quantum states form messages. Polar codes, ETH scientists have shown, compress quantum messages maximally efficiently. Researchers are exploring decoding strategies and relationships among (quantum) polar codes. With their help, Shannon-coded travel guides might fit not only in my camera bag, but also on the tip of my water bottle.

Should you need a Zürich travel guide, I recommend Grossmünster Church. Not only does the name fulfill your daily dose of umlauts. Not only did Ulrich Zwingli channel the Protestant Reformation into Switzerland there. Climbing a church tower affords a panorama of Zürich. After oohing over the hills and ahhing over the lake, you can shift your gaze toward ETH. The worldview being built there bewitches as much as the vista from any tower.

P1040476

A tower with a view.

With gratitude to ETH’s QI-theory group (particularly to Renato Renner) for its hospitality. And for its travel advice. With gratitude to David Sutter for his explanations and patience.

P1040411

The author and her neue Freunde.

The 10 biggest breakthroughs in physics over the past 25 years, according to us.

Posted on by
37

Making your way to the cutting edge of any field is a daunting challenge. But especially when the edge of the field is expanding; and even harder still when the rate of expansion is accelerating. John recently helped Physics World create a special 25th anniversary issue where they identified the five biggest breakthroughs in physics over the past 25 years, and also the five biggest open questions. In pure John fashion, at his group meeting on Wednesday night, he made us work before revealing the answers. The photo below shows our guesses, where the asterisks denote Physics World‘s selections. This is the blog post I wish I had when I was a fifteen year-old aspiring physicist–this is an attempt to survey and provide a tiny toehold on the edge (from my biased, incredibly naive, and still developing perspective.)

The IQI's

The IQI’s quantum information-biased guesses of Physics World’s 5 biggest breakthroughs over the past 25 years, and 5 biggest open problems. X’s denote Physics World’s selections. Somehow we ended up with 10 selections in each category…

The biggest breakthroughs of the past 25 years:

*Neutrino Mass: surprisingly, neutrinos have a nonzero mass, which provides a window into particle physics beyond the standard model. THE STANDARD MODEL has been getting a lot of attention recently. This is well deserved in my opinion, considering that the vast majority of its predictions have come true, most of which were made by the end of the 1960s. Last year’s discovery of the Higgs Boson is the feather in its cap. However, it’s boring when things work too perfectly, because then we don’t know what path to continue on. That’s where the neutrino mass comes in. First, what are neutrinos? Neutrinos are a fundamental particle that have the special property that they barely interact with other particles. There are four fundamental forces in nature: electromagnetism, gravity, strong (holds quarks together to create neutrons and protons), and weak (responsible for radioactivity and nuclear fusion.) We can design experiments which allow us to observe neutrinos. We have learned that they are electrically neutral, so they aren’t affected by electromagnetism. They are barely affected by the strong force, if at all. They have an extremely small mass, so gravity acts on them only subtly. The main way in which they interact with their environment is through the weak force. Here’s the amazing thing: only really clunky versions of the standard model can allow for a nonzero neutrino mass! Hence, when a small but nonzero mass was experimentally established in 1998, we gained one of our first toeholds into particle physics beyond the standard model. This is particularly important today, because to the best of my knowledge, the LHC hasn’t yet discovered any other new physics beyond the standard model. The mechanism behind the neutrino mass is not yet understood. Moreover, neutrinos have a bunch of other bizarre properties which we understand empirically, but not their theoretical origins. The strangest of which goes by the name neutrino oscillations. In one sentence: there are three different kinds of neutrinos, and they can spontaneously transmute themselves from one type to another. This happens because physics is formulated in the language of mathematics, and the math says that the eigenstates corresponding to ‘flavors’ are not the same as the eigenstates corresponding to ‘mass.’ Words, words, words. Maybe the Caltech particle theory people should have a blog?

Shor’s Algorithm: a quantum computer can factor N=1433301577 into 37811*37907 exponentially faster than a classical computer. This result from Peter Shor in 1994 is near and dear to our quantum hearts. It opened the floodgates showing that there are tasks a quantum computer could perform exponentially faster than a classical computer, and therefore that we should get BIG$$$ from the world over in order to advance our field!! The task here is factoring large numbers into their prime factors; the difficulty of which has been the basis for many cryptographic protocols. In one sentence, Shor’s algorithm achieves this exponential speed-up because there is a step in the factoring algorithm (period finding) which can be performed in parallel via the quantum Fourier transform.
Continue reading →

Can a game teach kids quantum mechanics?

Posted on by
34

Five months ago, I received an email and then a phone call from Google’s Creative Lab Executive Producer, Lorraine Yurshansky. Lo, as she prefers to be called, is not your average thirty year-old. She has produced award-winning short films like Peter at the End (starring Napoleon Dynamite, aka Jon Heder), launched the wildly popular Maker Camp on Google+ and had time to run a couple of New York marathons as a warm-up to all of that. So why was she interested in talking to a quantum physicist?

You may remember reading about Google’s recent collaboration with NASA and D-Wave, on using NASA’s supercomputing facilities along with a D-Wave Two machine to solve optimization problems relevant to both Google (Glass, for example) and NASA (analysis of massive data sets). It was natural for Google, then, to want to promote this new collaboration through a short video about quantum computers. The video appeared last week on Google’s YouTube channel:

This is a very exciting collaboration in my view. Google has opened its doors to quantum computation and this has some powerful consequences. And it is all because of D-Wave. But, let me put my perspective in context, before Scott Aaronson unleashes the hounds of BQP on me.

Two years ago, together with Science magazine’s 2010 Breakthrough of the Year winner, Aaron O’ Connell, we decided to ask Google Ventures for $10,000,000 dollars to start a quantum computing company based on technology Aaron had developed as a graduate student at John Martini’s group at UCSB. The idea we pitched was that a hand-picked team of top experimentalists and theorists from around the world, would prototype new designs to achieve longer coherence times and greater connectivity between superconducting qubits, faster than in any academic environment. Google didn’t bite. At the time, I thought the reason behind the rejection was this: Google wants a real quantum computer now, not just a 10 year plan of how to make one based on superconducting X-mon qubits that may or may not work.

I was partially wrong. The reason for the rejection was not a lack of proof that our efforts would pay off eventually – it was a lack of any prototype on which Google could run algorithms relevant to their work. In other words, Aaron and I didn’t have something that Google could use right-away. But D-Wave did and Google was already dating D-Wave One for at least three years, before marrying D-Wave Two this May. Quantum computation has much to offer Google, so I am excited to see this relationship blossom (whether it be D-Wave or Pivit Inc that builds the first quantum computer). Which brings me back to that phone call five months ago…

Lorraine: Hi Spiro. Have you heard of Google’s collaboration with NASA on the new Quantum Artificial Intelligence Lab?

Me: Yes. It is all over the news!

Lo: Indeed. Can you help us design a mod for Minecraft to get kids excited about quantum mechanics and quantum computers?

Me: Minecraft? What is Minecraft? Is it like Warcraft or Starcraft?

Lo: (Omg, he doesn’t know Minecraft!?! How old is this guy?) Ahh, yeah, it is a game where you build cool structures by mining different kinds of blocks in this sandbox world. It is popular with kids.

Me: Oh, okay. Let me check out the game and see what I can come up with.

After looking at the game I realized three things:
1. The game has a fan base in the tens of millions.
2. There is an annual convention (Minecon) devoted to this game alone.
3. I had no idea how to incorporate quantum mechanics within Minecraft.

Lo and I decided that it would be better to bring some outside help, if we were to design a new mod for Minecraft. Enter E-Line Media and TeacherGaming, two companies dedicated to making games which focus on balancing the educational aspect with gameplay (which influences how addictive the game is). Over the next three months, producers, writers, game designers and coder-extraordinaire Dan200, came together to create a mod for Minecraft. But, we quickly came to a crossroads: Make a quantum simulator based on Dan200’s popular ComputerCraft mod, or focus on gameplay and a high-level representation of quantum mechanics within Minecraft?

The answer was not so easy at first, especially because I kept pushing for more authenticity (I asked Dan200 to create Hadamard and CNOT gates, but thankfully he and Scot Bayless – a legend in the gaming world – ignored me.) In the end, I would like to think that we went with the best of both worlds, given the time constraints we were operating under (a group of us are attending Minecon 2013 to showcase the new mod in two weeks) and the young audience we are trying to engage. For example, we decided that to prepare a pair of entangled qubits within Minecraft, you would use the Essence of Entanglement, an object crafted using the Essence of Superposition (Hadamard gate, yay!) and Quantum Dust placed in a CNOT configuration on a crafting table (don’t ask for more details). And when it came to Quantum Teleportation within the game, two entangled quantum computers would need to be placed at different parts of the world, each one with four surrounding pylons representing an encoding/decoding mechanism. Of course, on top of each pylon made of obsidian (and its far-away partner), you would need to place a crystal, as the required classical side-channel. As an authorized quantum mechanic, I allowed myself to bend quantum mechanics, but I could not bring myself to mess with Special Relativity.

As the mod launched two days ago, I am not sure how successful it will be. All I know is that the team behind its development is full of superstars, dedicated to making sure that John Preskill wins this bet (50 years from now):

The plan for the future is to upload a variety of posts and educational resources on qcraft.org discussing the science behind the high-level concepts presented within the game, at a level that middle-schoolers can appreciate. So, if you play Minecraft (or you have kids over the age of 10), download qCraft now and start building. It’s a free addition to Minecraft.

The cost and yield of moving from (quantum) state to (quantum) state

Posted on by
8

The countdown had begun.

In ten days, I’d move from Florida, where I’d spent the summer with family, to Caltech. Unfolded boxes leaned against my dresser, and suitcases yawned on the floor. I was working on a paper. Even if I’d turned around from my desk, I wouldn’t have seen the stacked books and folded sheets. I’d have seen Lorenz curves, because I’d drawn Lorenz curves all week, and the curves seemed imprinted on my eyeballs.

Using Lorenz curves, we illustrate how much we know about a quantum state. Say you have an electron, you’ll measure it using a magnet, and you can’t predict any measurement’s outcome. Whether you orient the magnet up-and-down, left-to-right, etc., you haven’t a clue what number you’ll read out. We represent this electron’s state by a straight line from (0, 0) to (1, 1).

Uniform_state

Say you know the electron’s state. Say you know that, if you orient the magnet up-and-down, you’ll read out +1. This state, we call “pure.” We represent it by a tented curve.

Pure_state

The more you know about a state, the more the state’s Lorenz curve deviates from the straight line.

Arbitrary_state

If Curve A fails to dip below Curve B, we know at least as much about State A as about State B. We can transform State A into State B by manipulating and/or discarding information.

Conversion_yield_part_1_arrow

By the time I’d drawn those figures, I’d listed the items that needed packing. A coauthor had moved from North America to Europe during the same time. If he could hop continents without impeding the paper, I could hop states. I unzipped the suitcases, packed a box, and returned to my desk.

Say Curve A dips below Curve B. We know too little about State A to transform it into State B. But we might combine State A with a state we know lots about. The latter state, C, might be pure. We have so much information about A + C, the amalgam can turn into B.

Yet more conversion costs Yet-more-conversion-costs-part-2

What’s the least amount of information we need about C to ensure that A + C can turn into B? That number, we call the “cost of transforming State A into State B.”

We call it that usually. But late in the evening, after I’d miscalculated two transformation costs and deleted four curves, days before my flight, I didn’t type the cost’s name into emails to coauthors. I typed “the cost of turning A into B” or “the cost of moving from state to state.”
Continue reading →

The million dollar conjecture you’ve never heard of…

Posted on by
4

Curating a blog like this one and writing about imaginary stuff like Fermat’s Lost Theorem means that you get the occasional comment of the form: I have a really short proof of a famous open problem in math. Can you check it for me? Usually, the answer is no. But, about a week ago, a reader of the blog that had caught an omission in a proof contained within one of my previous posts, asked me to do just that: Check out a short proof of Beal’s Conjecture. Many of you probably haven’t heard of billionaire Mr. Beal and his $1,000,000 conjecture, so here it is:

Let a,b,c and x,y,z > 2 be positive integers satisfying a^x+b^y=c^z. Then, gcd(a,b,c) > 1; that is, the numbers a,b,c have a common factor.

After reading the “short proof” of the conjecture, I realized that this was a pretty cool conjecture! Also, the short proof was wrong, though the ideas within were non-trivial. But, partial progress had been made by others, so I thought I would take a crack at it on the 10 hour flight from Athens to Philadelphia. In particular, I convinced myself that if I could prove the conjecture for all even exponents x,y,z, then I could claim half the prize. Well, I didn’t quite get there, but I made some progress using knowledge found in these two blog posts: Redemption: Part I and Fermat’s Lost Theorem. In particular, one can show that the conjecture holds true for x=y=2n and z = 2k, for n \ge 3, k \ge 1. Moreover, the general case of even exponents can be reduced to the case of x=y=p \ge 3 and y=z=q \ge 3, for p,q primes. Which makes one wonder if the general case has a similar reduction, where two of the three exponents can be assumed equal.

The proof is pretty trivial, since most of the heavy lifting is done by Fermat’s Last Theorem (which itself has a rather elegant, short proof I wanted to post in the margins – alas, WordPress has a no-writing-on-margins policy). Moreover, it turns out that the general case of even exponents follows from a combination of results obtained by others over the past two decades (see the Partial Results section of the Wikipedia article on the conjecture linked above – in particular, the (n,n,2) case). So why am I even bothering to write about my efforts? Because it’s math! And math equals magic. Also, in case this proof is not known and in the off chance that some of the ideas can be used in the general case. Okay, here we go…

Proof. The idea is to assume that the numbers a,b,c have no common factor and then reach a contradiction. We begin by noting that a^{2m}+b^{2n}=c^{2k} is equivalent to (a^m)^2+(b^n)^2=(c^k)^2. In other words, the triplet (a^m,b^n,c^k) is a Pythagorean triple (sides of a right triangle), so we must have a^m=2rs, b^n=r^2-s^2, c^k =r^2+s^2, for some positive integers r,s with no common factors (otherwise, our assumption that a,b,c have no common factor would be violated). There are two cases to consider now:

Case I: r is even. This implies that 2r=a_0^m and s=a_1^m, where a=a_0\cdot a_1 and a_0,a_1 have no factors in common. Moreover, since b^n=r^2-s^2=(r+s)(r-s) and r,s have no common factors, then r+s,r-s have no common factors either (why?) Hence, r+s = b_0^n, r-s=b_1^n, where b=b_0\cdot b_1 and b_0,b_1 have no factors in common. But, a_0^m = 2r = (r+s)+(r-s)=b_0^n+b_1^n, implying that a_0^m=b_0^n+b_1^n, where b_0,b_1,a_0 have no common factors.

Case II: s is even. This implies that 2s=a_1^m and r=a_0^m, where a=a_0\cdot a_1 and a_0,a_1 have no factors in common. As in Case I, r+s = b_0^n, r-s=b_1^n, where b=b_0\cdot b_1 and b_0,b_1 have no factors in common. But, a_1^m = 2s = (r+s)-(r-s)=b_0^n-b_1^n, implying that a_1^m+b_1^n=b_0^n, where b_0,b_1,a_1 have no common factors.

We have shown, then, that if Beal’s conjecture holds for the exponents (x,y,z)=(n,n,m) and (x,y,z)=(m,n,n), then it holds for (x,y,z)=(2m,2n,2k), for arbitrary k \ge 1. As it turns out, when m=n, Beal’s conjecture becomes Fermat’s Last Theorem, implying that the conjecture holds for all exponents (x,y,z)=(2n,2n,2k), with n\ge 3 and k\ge 1.

Open Problem: Are there any solutions to a^p+b^p= c\cdot (a+b)^q, for a,b,c positive integers and primes p,q\ge 3?

PS: If you find a mistake in the proof above, please let everyone know in the comments. I would really appreciate it!

Frontiers of Quantum Information Science

Posted on by
6

Just a few years ago, if you wanted to look for recent research articles about quantum entanglement, you would check out the quantum physics [quant-ph] archive at arXiv.org. Since 1994, quant-ph has been the central repository for papers about quantum computing and the broader field of quantum information science. But over the past few years there has been a notable change. Increasingly, exciting papers about quantum entanglement are found at the condensed matter [cond-mat] and high energy physics – theory [hep-th] archives.

I don’t know for sure, but that trend may have had something to do with an invitation I received a few months ago from David Gross, to organize the next Jerusalem Winter School in Theoretical Physics. David has been the General Director of the School for, well, I’m not sure how long, but it must be a long time. In the past, the topic of the school has rotated between particle physics, condensed matter physics, and astrophysics. Every year, a group of world-class scientists gives lectures on cutting-edge research for an enthusiastic audience of postdoctoral scholars and advanced graduate students.

David suggested that a good topic for the next school would be “quantum information, broadly envisaged — from quantum computing to strongly correlated electrons.” After some hesitation for family reasons, I embraced this opportunity to amplify David’s message: quantum information has arrived as a major subfield of physics, and its relevance to other areas of physics is becoming broadly appreciated.

I’m not good at organizing things myself, so I recruited two friends who are very good at it to help me: Michael Ben-Or and Patrick Hayden. As the local organizer at The Hebrew University, Michael has to do a lot of the hard work that I’m glad to avoid. We decided to call the school “Frontiers of Quantum Information Science,” and put together a slate of 10 lecturers, which I’m very excited about. The lectures will cover the core areas of quantum information, as well as some of the important ways in which quantum information relates to quantum matter, quantum field theory, and quantum gravity. Each lecturer will give three or four ninety-minute lectures, on these topics:

Scott Aaronson (MIT), Quantum complexity and quantum optics
David DiVincenzo (Aachen), Quantum computing with superconducting circuits
Daniel Harlow (Princeton), Black holes and quantum information
Michal Horodecki (Gdansk), Quantum information and thermodynamics
Stephen Jordan (NIST), Quantum algorithms
Rob Myers (Perimeter), Entanglement in quantum field theory
Renato Renner (ETH), Quantum foundations
Ady Stern (Weizmann), Topological quantum computing
Barbara Terhal (Aachen), Quantum error correction
Frank Verstraete (Vienna), Quantum information and quantum matter

The school will run from 30 December 2013 to 9 January 2014 at the Israel Institute for Advanced Studies at The Hebrew University in Jerusalem. If you are interested in attending, please visit the website for more information and fill out the registration form by November 1. I hope you can come — it’s going to be a lot of fun.

Rereading the first paragraph of this post, I got slightly nervous about whether the trend I described can be documented, so I have done a little bit of research. Going back to 2005, I plotted the number of papers with the word “entanglement” in the title on quant-ph, cond-mat, hep-th, and also the general relativity and quantum cosmology [gr-qc] archive. For 2013, I rescaled the data for the year up to now, taking into account that Sep. 22 is the 265th day of the year. I didn’t make any adjustment for papers being cross-listed on multiple archives.

Here is the data for quant-ph:quantph-plot-pdfIt’s remarkably flat. Here is the aggregated data for the other three archives:arxiv-plot-pdfIt’s pretty clear that something started to happen around 2010. I realize one could do a much more serious study of this issue, but since I was only willing to spend an hour on it, I feel vindicated.

Free Feynman!

Posted on by
9

Last Friday the 13th was a lucky day for those who love physics — The online html version of Volume 1 of the Feynman Lectures on Physics (FLP) was released! Now anyone with Internet access and a web browser can enjoy these unique lectures for free. They look beautiful.

Mike Gottlieb at Caltech on 20 September 2013. He's the one on the right.

Mike Gottlieb at Caltech on 20 September 2013. He’s the one on the right.

On the day of release, over 86,000 visitors viewed the website, and the Amazon sales rank of the paperback version of FLP leapt over the weekend from 67,000 to 12,000. My tweet about the release was retweeted over 150 times (my most retweets ever).

Free html versions of Volumes 2 and 3 are in preparation. Soon pdf versions of all three volumes will be offered for sale, each available in both desktop and tablet versions at a price comparable to the cost of the paperback editions. All these happy developments resulted from a lot of effort by many people. You can learn about some of the history and the people involved from Kip Thorne’s 2010 preface to the print edition.

A hero of the story is Mike Gottlieb, who spends most of his time in Costa Rica, but passed through Caltech yesterday for a brief visit. Mike entered the University of Maryland to study mathematics at age 15 and at age 16 began a career as a self-employed computer software consultant. In 1999, when Mike was 39,  a chance meeting with Feynman’s friend and co-author Ralph Leighton changed Mike’s life.

At Ralph’s suggestion, Mike read Feynman’s Lectures on Computation. Impressed by Feynman’s insights and engaging presentation style, Mike became eager to learn more about physics; again following Ralph’s suggestion, he decided to master the Feynman Lectures on Physics. Holed up at a rented farm in Costa Rica without a computer, he pored over the lectures for six months, painstakingly compiling a handwritten list of about 200 errata.

Kip’s preface picks up the story at that stage. I won’t repeat all that, except to note two pivotal developments. Rudi Pfeiffer was a postdoc at the University of Vienna in 2006 when, frustrated by the publisher’s resistance to correcting errata that he and others had found, he (later joined by Gottlieb) began converting FLP to LaTeX, the modern computer system for typesetting mathematics. Eventually, all the figures were redrawn in electronic form as scalable vector graphics, paving the way for a “New Millenium Edition” of FLP (published in 2011), as well as other electronically enhanced editions planned for the future. Except that, before all that could happen, Caltech’s Intellectual Property Counsel Adam Cochran had to untangle a thicket of conflicting publishing rights, which I have never been able to understand in detail and therefore will not attempt to explain.

Rudi Pfeiffer and Mike Gottlieb at Caltech in 2008.

Rudi Pfeiffer and Mike Gottlieb at Caltech in 2008.

The proposal to offer an html version for free has been enthusiastically pursued by Caltech and has received essential financial support from Carver Mead. The task of converting Volume 1 from LaTeX to html was carried out for a fee by Caltech alum Michael Hartl; Gottlieb is doing the conversion himself for the other volumes, which are already far along.

Aside from the pending html editions of Volumes 2 and 3, and the pdf editions of all three volumes, there is another very exciting longer-term project in the works — the html will provide the basis for a Multimedia Edition of FLP. Audio for every one of Feynman’s lectures was recorded, and has been digitally enhanced by Ralph Leighton. In addition, the blackboards were photographed for almost all of the lectures. The audio and photos will be embedded in the Multimedia Edition, possibly accompanied by some additional animations and “Ken Burns style” movies. The audio in particular is great fun, bringing to life Feynman the consummate performer. For the impatient, a multimedia version of six of the lectures is already available as an iBook. To see a quick preview, watch Adam’s TEDxCaltech talk.

Mike Gottlieb has now devoted 13 years of his life to enhancing FLP and bringing the lectures to a broader audience, receiving little monetary compensation. I asked him yesterday about his motivation, and his answer surprised me somewhat. Mike wants to be able to look back at his life feeling that he has made a bigger contribution to the world than merely writing code and making money. He would love to have a role in solving the great open problems in physics, in particular the problem of reconciling general relativity with quantum mechanics, but feels it is beyond his ability to solve those problems himself. Instead, Mike feels he can best facilitate progress in physics by inspiring other very talented young people to become physicists and work on the most important problems. In Mike’s view, there is no better way of inspiring students to pursue physics than broadening access to the Feynman Lectures on Physics!