Building a Computer: Part I

During my senior year in high school, I was fortunate enough to participate in the Intel International Science and Engineering Fair. At the awards banquet I was seated with fourteen others and we each had the choice of ordering either salmon or steak for our respective entrées. I noticed that while taking our fifteen different orders, our waiter did not write anything down. How on Earth was he going to remember what each of us had requested?!

It turns out the answer is intimately related to Problems 2 and 5 in my last post. Did you realize you always save at least 999 people on the game show? Here’s how:

The person at the back of the line will look at all 999 hats in front of him. If the number of black hats is odd, he will shout “Black!” If the number of black hats is even, he will shout “White!” From this information, the second person in line can deduce from the hats in front of him what the color of his own hat is! For example, if Contestant 1 shouts “Black!” and Contestant 2 sees an even number of black hats in front of him, he can deduce that his own hat is black because the total number of black hats Contestant 1 sees is odd. From information given in Contestant 1’s and Contestant 2’s answers, Contestant 3 can determine his hat’s color via a similar parity argument, and so on. At least $999 will be donated to charity.

How about Problem 5? One solution requires knowledge of how to represent numbers in binary. Let’s say you owe your friend $3,761.50, and want to pay him using pennies and dimes, as well as $1, $10, $100, and hypothetical $1,000 bills. How would you pay him using the least number of monetary tokens? The answer to this is easy – we all learned about the hundredths’ place, the tenths’ place, ones’ place, the tens’ place, the hundreds’ place, and so on in elementary school. The digit in the ones’ place tells us how many $1 bills we need to give our friend, the digit in the tens’ place tells us how many $10 bills we need to give our friend, and so on. Written more suggestively,

3,761 = 3*103 + 7*102 + 6*101 + 1*100 + 5*10-1 + 0*10-2

Why does the number 10 appear so significant in the above equation? In the above equation, 10 is called the “base.” In base 10, we write every number as the sum of whole multiples of powers of 10. Notice that none of the bold numbers – the digits – can be greater than or equal to the base (10); they must be between 0 and 9. If one of the bold digits was greater than 9, we could just use a monetary token of higher value to reduce the total number of bills and coins we need to repay our friend. This leads to:

Rule #1: The value of each digit must be less than the base.

Could we use a number other than 10 as our base? Let’s try using 2! I can think of at least one way to write 3,761.50 as the sum of multiples of powers of two:

3,761.50 = 1*211 + 0*210 + 0*29 + 0*28 + 0*27 + 0*26 + 53*251*24 + 0*23 + 0*22 + 0*21 + 1*20 + 1*2-1

Continue reading

The Navajo connection

A few months ago, Prof. Keith Schwab brought visiting students and teachers from Navajo Preparatory School to tour some of the IQIM labs, listen to some quick lectures on optics, and talk to scientists. Since this opportunity was only allowed to the one carload that made the 11.5 hour drive from Farmington, NM, everyone involved agreed that we could reach far more students if the IQIM sent Caltech students there. Ana Brown and I both enjoyed speaking with the visiting students and teachers, and responded enthusiastically when Prof. Schwab offered to send us.  My enthusiasm momentarily dimmed when I realized our trip would be occurring in the dead of winter and it was projected to snow while we were there (having only lived in northern and southern California, let’s say I have a heightened sensitivity to weather), but I excitedly spent thanksgiving putting together demonstrations with supplies I found in my closet and garage. I’ve always enjoyed talking about applied math, science, and engineering to anyone, especially anyone young enough to have only heard “math is boring” or “science is too hard” few enough times I can convince them otherwise.  Navajo Prep seemed ideal for this, since the school prepares the students well and sends over 95% of the students to college, and is working to increase student interest in math, science, and engineering.

it's colder than it looks, I swear

Panorama from the center of Navajo Prep

With a suitcase half full of clothes and half full of tools and hacked-together electronics, I was picked up from the airport, and arrived at the school in the afternoon the Monday after Thanksgiving weekend. While Monday was spent arranging which classes I would attend, and what topics I would discuss, my second day involved a trip with the school’s outreach coordinator and Cody, one of the two students who visited Caltech, taking a tour of some of the local highlights, including a traditional Navajo lunch (steam corn stew, roast mutton, and I even tried ach’ii”) and toured the remnants of the cliff dwellings at Mesa Verde, about half an hour from the school. Exploring a region with such a rich history and discussing it with my hosts, who are descendants in part from that history was an incredible experience.

yup, some 70 rooms built in a recess carved into the canyon wall almost a thousand years ago.

Rooms at the Oak Tree House at Mesa Verde

On Wednesday, I began talking to the freshman physics classes about optics, intending to discuss the properties of light, like frequency, speed, wavelength, velocity, energy, and momentum, but to give some context I began with a historical summary of discoveries in optics. I know I was surprised when I was preparing, so you might enjoy answering the same questions that I asked the class. Take a second, and guess when you think the first lenses were made and when wearable glasses were first used. (After you think you have a guess, scroll to the bottom to see how you did.)  When I realized that the class was more interested in seeing rather than hearing about optics, I skimmed over what I’d prepared in order to spend more time on the demonstrations where I showed refraction in glass and explained how that can be derived from assuming a different speed of light in the material. We found lenses for the students to manipulate/play with, and even though historically there were about 300 years between invention of glasses (and the proliferation of lens-making) and the invention of the telescope, some of the students unintentionally built telescopes after taking a second lens from their friends and were shocked to hear that what they had just made was better than the one Galileo used to first discover the four largest moons of Jupiter.

I promise this shot is not advertising for Under Armour.

Measuring focal lengths and observing lensing with a drop of water on a glass slide

We also demonstrated double slit diffraction and calculated light’s wavelength for three different laser pointers to within 5% accuracy using only a tape measure, a post-it, and a knife. I decided not to bring a demonstration to measure the speed of light with a laser, a few mirrors, a computer fan, and a reverse-biased photodiode hooked up to an old speaker, because I couldn’t get the fan to spin fast enough to get a reasonably short delay length. (From that can you guess what my set-up was?) On Thursday, Ana and I gave a similar lecture to a different pair of 90 minute freshman physics classes, and spent the other periods talking with math classes. In calculus, I described the different kinds of math classes offered in college, their applications, and their connections to each other in an attempt to give more meaning to the course titles they would no doubt be reading next fall. In geometry and trigonometry I answered the perennial high school math question: “when will we ever use this?” by talking about some applications in geometric optics.

Since I figure you readers like thinking about this sort of thing, I’ll elaborate: I started with the fact that a light beam’s incident angle (measured from the perpendicular of a surface) is equal to its reflected angle. This means that light propagation, like much of (but not all of) physics, is reversible in all but a few specific cases. As a result, light generated at or passing through the center of a circle is reflected off the circle back to the center. An ellipse has a similar property where light through one focus is all reflected to the other. Try deriving that from the fact that an ellipse is defined to be the set of all points where the sum of the distances to the two foci equals some fixed constant. In the lecture, I then used the fact that a parabola is the set of all points equidistant from a point (the focus) and a line (the directrix) to show that light from the focus is reflected off the parabola and collimated (focused at infinity).

Ana brought some IQIM hats and shirts, which the freshman physics classes seemed to definitely enjoy when we met with each class for 40 minutes on Friday.

We probably tripled the number of high school varsity football players who've worn IQIM gear in that one picture

One of the four freshman physics classes we got to spend time with

I tried to give them an impression of what we do in the IQIM, but I had a hard time giving a satisfactory explanation of the significance of quantum information, and Ana easily convinced me that it would be more engaging to use the 90 minute introduction I had already given them on optics to explain and describe solar energy, since many buildings deep in the Navajo reservation are off the power grid.  There are also plans to construct a large solar power plant on the reservation that will be much cleaner than the three local coal power plants in the region.

I think I made a joke and Ana might have been the only one to laugh.  Still, it's proof I can be funny.

Action shot during the lecture on solar

Ana and I also spoke to the senior seminar, which contained the entire graduating class, where she talked about the difficulties transitioning to college experienced by some of her friends in college who were from the Navajo reservation. She gave such great advice on applying to schools, applying for fellowships, and developing a healthy work/life balance, that the only thing I felt like I could contribute was some advice on picking a major (since I’ve picked about 4 different majors), where I described the difference between science and engineering, and talked about different fields within each. I loved how truly helpful I felt when so many of the students told us that they either found certain pieces of advice to be useful, thanked us for introducing them to an idea they hadn’t heard of, or asked us to come back soon.

Occasionally a student asked what I personally do, and their curiosity was rewarded with an explanation that lasted as long as they were interested.  The shortest lasted two sentences and the longest explanation (given to a calculus class of 5 people) involved 30 minutes with my laptop out showing all the steps I take to fabricate nanoscale devices to trap light in almost a cubic-wavelength volume in proximity to an “optically interesting” rare earth ion which my advisor and I hope will provide a viable quantum optical memory.  (Here‘s a little more about our work.)

In the evenings we cheered for the school’s basketball team, had dinner with some of the students and teachers, and discussed the school’s science curriculum and science fair projects. Ana and I consulted on a solar water heating project some of the students were working on, and, after the students all went home for the weekend, I even spent 2 hours in 17ºF weather the last night calibrating an 8″ diameter Schmidt-Cassegrain telescope that had been donated to the school. Compared to Pasadena the viewing was spectacular, and I could easily spot galaxies, nebulae, and discern stripes on Jupiter and the four Galilean moons. I can only expect that some of the students I met will be as excited as I was.

From wikipedia: “The earliest known lenses were made from polished crystal, often quartz, and have been dated as early as 700 BC for Assyrian lenses” and “Around 1284 in Italy, Salvino D’Armate is credited with inventing the first wearable eye glasses.” For anyone who’s interested in the history of science, I’d suggest you check it out.

More Brainteasers

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

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