Metamorphoses

Back in high school I maintained a blog titled “Adventure is just bad planning.” A little ways into my time at USC I decided to start this current one, which went under various names, to demarcate a different chapter for myself. Well, 4 years later, I’m embarking on yet another chapter – graduate school – and I think it’s appropriate to have my blog presence begin anew.

For the adventures that come, I hope to share them with you at “A Smoother Pebble.” Thanks for all those who read and commented on this blog!

Cheap, quality Lattés

I thought I would like to share a cool trick I think every regular coffee drinker should know. Coffee isn’t cheap. Gone are the days where the standard was a $1 Dunkin’ Donuts cup of joe. Now, people routinely will shell out $3 or $4 for a Latté at starbucks, multiple times a day. I’m a grad student; I’m under extraordinary evolutionary pressure to adapt my coffee habit so that my meager earnings aren’t decimated. The result: the Grad Student Iced Latté:

1. Order a double expresso (which is usually < $2).
2. Ask for a cup of ice.
3. Add your favorite quantities of sugar/spice in the expresso.
4. Add liberal amounts of cream/milk to the expresso.
5. Pour the expresso into your cup of ice.
6. Iced Latté!

You’ve now saved yourself $1 or $2 per drink. Enjoy!

A Solution to a Generalized Pepys’s Problem

Samuel Pepys, the famed English diarist, proposed the following problem to Isaac Newton, in order to gauge his chances in a wager:

Which experiment is more probable?
A. You roll 6 fair die and get at least 1 dice that shows up as “6”;
B. You roll 12 fair die and get at least 2 die that show up as “6”;
C. You roll 18 fair die and get at least 3 die that show up as “6”.

The correct answer turns out to be experiment A. Based upon the correspondence between Newton (who provided the correct solution) and Pepys, the wagerer was not immediately convinced of the answer. When challenged, Newton attempted to give an intuitive explanation of the answer, though it is technically incorrect/incomplete (Newton probably knew this). Here it is, paraphrased from the Ye Olde Englishe version:

Imagine that B and C toss their dice in groups of six. A is most favorable because it requires a 6 in only one group toss, while B and C require a 6 in each of their group tosses.

Astute readers will recognize that this intuitive explanation neglects situations where C might get two 6’s in the first or third set, for example.

This problem has been discussed often enough that it has been titled the “Newton-Pepys Problem“, and one is likely to find it given as an elementary probability exercise. I myself came across a more general version of Pepys problem: I win if, in 6n independent rolls of dice I acquire at least n 6’s. You win if, in 6(n + 1) independent rolls of dice you acquire at least n + 1 6’s. Who is more likely to win?

When n = 1 or 2, we know from Newton that I am more likely to win (yay!), but what about for all n? The answer is of course that I still am more likely to win, but how goes the proof? It is unclear whether Newton had a general solution, as his letters to Pepys indicate a purely numerical approach (he calculated the probabilities by hand for A, B and C). My guess is that he had an elegant solution that unfortunately could not fit in the margin of his letter.

A New Kind of Sci- I mean, Solution.

In an act of egomania and narcissism that can only be matched by several Stephen Wolfram tomes on cellular automata, I present the object of my obsession over the past two weeks: A New Kind of Solution, and an Application to Recurrence Relations. In this essay (6 pages), I argue that the notion of “closed form solution” has evolved into something inherently computational in nature, and provide an illustration via the computational complexity of solving recurrence relations. This is from the first part of the essay:

The Evolution of Solution

Throughout the history of mathematics, a central goal of its practioners has been to find simple expressions for solutions to equations. Although there is no rigorous definition of “simple expression”, mathematicians have nonetheless spent enormous amounts of effort seeking solutions to their analytical problems that satisfy their aesthetic of simplicity. This aesthetic has evolved over time. In antiquity, “simple” meant rational: the ancient Greeks conducted a (misguided) search for two integers a and b such (a/b)² = 2. Later, “simple” meant having an algebraic expression, which involve only addition, multiplication, and nth-roots. For centuries, mathematicians sought the elusive quintic formula, an algebraic expression for the roots of a degree 5 polynomial. One of the greatest triumphs of mathematics was Galois’s discovery that there is no such expression, that in general polynomials are too complex to be subject to easy solution. 

Quantum Assembly Language

I kid you not, there actually is a quantum circuit assembly language.

Unfortunately, it’s only been used so far to draw quantum circuits, but one could hope that one day there will be an Google Quantum Android SDK that will take in the following…

#
# File: test17.qasm
# Date: 24-Mar-04
# Author: I. Chuang
#
# Sample qasm input file - example from Nielsen
# paper on cluster states

def MeasH,0,'\dmeter{H}'

qubit q0,\psi
qubit q1,+
qubit q2,+
qubit q3,\phi

nop q0
nop q2
ZZ q0,q1
ZZ q2,q3
ZZ q1,q2
MeasH q1
MeasH q2

 

and generate the following…

 

The most powerful supercomputer? The Web.

Recently there was news about a supercomputer in Japan taking the crown of the best in the world, for now. However, I believe that this beast of a machine has NOTHING on what is potentially the most powerful computing device, but yet lies dormant.

I ran across this link: http://www.statlect.com/ideas_computational_engine.htm, which puts forth the rather BRILLIANT idea of harnessing Wikipedia or other heavily-trafficked websites as a supercomputer. Simply install a small amount of JavaScript on each page, and take advantage of the user’s likely supply of idle CPU cycles to do something useful for the world, such as finding cures for cancer, or searching for extraterrestrial life, or folding proteins, or solving some difficult mathematical problem. The possibilities are endless!

What I would really like to see – and here I raise a developer’s call-to-arms – is for someone or a group of people to get together and create a distributed crowd sourced computing platform that runs solely on JavaScript. Then a website owner could just drop a small amount of JavaScript (much like they would to install google analytics) into their page, and voila! Every time a visitor navigates to their website, their computers will be periodically send back computational work done in the browser, until they leave the website.

I could see a company like Google or Amazon getting behind such an effort. I can see universities, governments, organized crime wanting to get involved too. Here are some of the possibilities:

– pedestrian science like curing cancer and folding proteins (NIH, universities)
– search for Ramsey numbers
– run simulations or nuclear explosions (governments)
– run molecular dynamics simulations
– factorize large numbers to break encrypted messages (governments, criminals)
– off load your company’s computing costs to unwitting users across the world by disguising it as a protein folding problem (corporations)

I can for see browsers in the future allowing you to throttle how much “free work” you are willing to do for organizations you don’t even know (it’s not really free because of energy costs). Or, perhaps users can charge for the work being done on their computers! This could open up a whole new market, a new type of economics of computing! For example,

In exchange for lending your CPU cycles, the New York Times might give you free access to their content, and the New York Times could be using your computer to run computations for China, who needs to simulate new materials design for their aircraft fleet.

This is great stuff for a technothriller novel. This reminds me of the many sci-fi stories I’ve read that involve aliens/machines using humans/brains as a computational substrate. We’re not quite there, but it’s happening to our personal computing devices. Our laptops, phones, tablets could be enslaved by shadowy organizations in order to come up with the next super mega-virus, or crack RSA, or run massive DDoS attacks (oh wait….).

Here I go again, letting my imagination run amok…

Triangle Inequality for Inner Products in Euclidean Space

Due to great public pressure, I’ll appease my widespread readership with an extremely engaging blog post entitled “Triangle Inequality for Inner Products in Euclidean Space.” Hold onto your seats!

Sarcasm aside, I’ll try my best to make this somewhat un-soporific! Let me start by briefly describing the motivation for this little article: I wanted to analyze the effect of a repeated sequence of quantum circuits on a noisy input. Let’s say you have a quantum circuit Q that you want to run multiple times in order to perform success probability amplification (much as one might want to amplify a BPP algorithm’s success probability from 2/3 to something exponentially close to 1). One way to do that is have k copies of the circuit Q and run them in parallel, and take the majority vote of the answers.

However, I’m not satisfied with this approach. It’s not environmentally friendly – after all, as a theorist living in California, I have a duty to make my theorems as green as possible. Having k parallel copies of Q requires k-times the number of qubits, and that’s quite wasteful. Getting one or two more coherent qubits in a quantum computer is a nightmare for experimentalists all around the world, so wantonly repeating Q a polynomial number of times would be just insult to injury for them. Let’s be environmentally friendly AND nice!

Lens Conference Videos

If you weren’t able to attend the Lens Conference last weekend, you will be able to experience at least half of its amazingness via the videos posted here: http://www.eecs.berkeley.edu/IPRO/lensconference2011/. (The other half is the experience of meeting and engaging with the other participants of the conference!).

Lens Conference 2011

This past weekend I attended the Theory of Computation as a Lens on the Sciences 2011 at UC Berkeley. As one might guess from the title, the theme is the importance of theoretical computer science not only as a means of studying computation itself, but rather as a means of bringing a new perspective on the major mysteries of the natural sciences – a lens, if you will.

Of course, computers have been undeniably crucial to the progress of science in the last half century, but for the most part, computation has been used as a tool for carrying out science, much as one might have a particle accelerator or gel electrophoresis as a tool. Here, the focus is on viewing quantum physics, molecular biology, evolution, as computational phenomena. If one does this, then one can bring out the big guns of theoretical computer science out – theorems and concepts of complexity, computability, algorithms – and potentially make groundbreaking discoveries in the initial science.

Sunset, a poem

This is a poem I wrote on a plane from Frankfurt to Amsterdam, in 2008. It references the Omega Point theory. It describes the final moments of the universe, as it is dissolving into an maximally entropic state.

Sunset

I watch despondently
As the lights wink out
One by one
Great tired suns heaving
Their last sighs
Dousing this universe in a deep
Enveloping gloom.

I am the Omega Point
I am Life itself
I am the triumph
of the uncountably infinite multitudes
who have ever roamed space and time
With my coming came they into me
Their voices joined as one, asking deliverance
From the dark recesses whence they came.

I brace myself –
The final bitter cold sets in,
Holding myself tightly to save the last
Vestiges of warmth; but
slowly,
Quietly,
Like an innocent gas leak
Life seeps out
Into the hungry void.

The candles burn low;
I can almost imagine
A terrible snow storm raging outside.
But there is no snow
There is no storm
There is no outside
Of this quickly emptying cell.

God has sent me to witness
The terminal days of this place
Alone.
There is none left
To share my burden, and to
Weep with me.
For all that ever was,
And could have been
Will never be.