QIP – Post 3

Let me begin by saying that I’m developing a growing dislike of theoretical computer scientists (cue the flaming in three, two, one…).  These people don’t really seem to be connected to reality.  They discuss, with impunity, results for such outrageous things as T = 0K (any pre-med majors I have taught over the years can explain what’s wrong with this – and, no, it was not a typo) and various parameters (frequently something nebulous like n) at infinity.  While there may be admittedly valid mathematical results in these cases, they have little or no connection to reality.  Personally I don’t think people should be working on physics problems if they can’t recognize the physical from non-physical (note that I consider CTCs physical, though they are not necessarily real – there is an important distinction).  At any rate, I will have another blog post about something related to this in a moment.

So the first talk was by Ben Reichardt from Waterloo on quantum query complexity using span programs.  Monotone span programs are equivalent to linear secret sharing schemes in cryptography.  In fact he was able to derive Grover’s search algorithm using these span programs.  I’m afraid I don’t have much more to say on the issue, though.  Ben has a very soothing voice and the room was sweltering, thus I had a hard time keeping my eyes open.

David Gross (not the one with the Nobel Prize – the other one from Hannover) gave a very well-organized talk (there are so few of these) on non-commutative compressed sensing related to quantum tomography.  Suppose you have some unknown density matrix \rho on \mathbb{C}^{d} with rank r << rd. In any case, that was the purpose of this work – to answer questions like that. David gave a great analogue to a pipe organ in that the pipes were d and the number of fingers the organist had were r. One of the questions that arises from the pipe organ analogy is whether we can perform an exact Fourier transform given only partial information. Again, the answer is yes – even in the classical (i.e. pipe organ) case using classical compressed sensing. So the idea in the quantum case is to recover the density matrix if the rank r is unknown. In the quantum case this is possible of we know rd(log d) randomly chosen Pauli expectation values. Technically the scheme is probabilistic, but it is so with a very high degree of success. David highlighted the difference between physicists and mathematicians by noting that the mathematical proof of the classical case was 50 pages long while the proof of the quantum case was 4.

I missed most of Norbert Schuch’s talk while finishing up my poster. Then I did manage to catch Dominic Berry’s (Caltech) on the query complexity of Hamiltonian simulation. Basically, if you want to implement N \times N unitary matrices, you need \Omega(N^2) gates just to approximate it. In essence this work, done with Andrew Childs, is an extension of Childs’ quantum random walk stuff.

Maarten Van den Nest of MPQ Garching gave a talk about simulating quantum computers using probabilistic methods. It was more algorithmic stuff and I can’t say it was overly exciting to me.

I ate lunch with the D-Wave and Google guys – yes, Google is here. Google recently used D-Wave’s chip to do some interesting things and their presentation at QIP centers around using it to, essentially, make Streetview even scarier. Basically they used D-Wave’s chip to train a piece of recognition software to tell the difference between a car and a truck. I’m not kidding. They gave me a demo at lunch using matchbox cars. I might actually get involved in some of this since it uses adiabatic quantum computing, of which I am swiftly becoming a HUGE fan (his Pontiffness welcomed me to the Dark Side).

Phillippe Corboz (Queensland) gave a very nicely organized talk (I’m starting to notice things like this) on simulating fermionic lattice models in 2-D using tensor network algorithms. As someone else in the audience pointed out, there’s an eerie similarity between some of these methods and categorical quantum mechanics. Anyway, quantum Monte Carlo methods tend to fail for many-body problems and this turns out to be a nice alternative since it allows you to approximate sums over exponentially-many terms with something polynomial. The ground state is the most interesting, of course, though I’ll note that it was Phillipe who equated this to T = 0K (tsk, tsk). The problem with the fermionic case is that you end up with negative probabilities in some cases. Tensor networks, however, get around this problem. They also tackled the 2-D Hubbard model of high-T_C superconductors. Tree tensor networks are very good for describing states obeying an area law. The CS people in the audience had no clue about the physics stuff (I really don’t think they should be working on physics problems). The computational cost of tensor networks is still high but it provides some symmetries that can be exploited for useful purposes.

Hari Krovi (UConn) gave a talk on adiabatic quantum optimization failing for random instances of NP-complete problems, though I heard through the grapevine he wasn’t sure he believed his own results (I suppose one could take that to mean he thought the real world might behave a bit differently than the math). He talked a lot about Anderson localization and had to apologize at one point for not being “rigorous” enough (ah, those CS people…).

Correction: I want to apologize to Hari Krovi for the aforementioned statement.  The last line was actually meant to imply that, personally, I thought he was rigorous enough. At the time I was in a particularly virulent mood about the rigor of the CS people since physicists generally recognize that the real world is a messy place (not to offend CS people – I think the differing views are products of the differing disciplines themselves).  Of course, it was apparently a physicist who made the comment that produced Hari’s reply, but I didn’t realize it at the time.  In addition, spreading an unsubstantiated rumor is, of course, wrong.  As a scientist I’m sure he believes his results.  Why else would he present them?

Kristan Temme (Vienna) gave another very well-done talk on quantum metropolis sampling. Basically they were looking at simulating quantum systems on a universal quantum computer. Adiabatic quantum computation is one way to give access to the states. Anyway, the classical Metropolis problem (named after the lead author of the paper) appeared in 1953 and didn’t find practical use until the first useful computers arrived. So these guys tried to find a quantum version. In both cases they were trying to essentially simulate a system plus a bath. The classical version used stochastic maps that converged (over many iterations) to the Gibb’s state. This improved things by 6-10 orders of magnitude. The quantum case used CP maps instead, though it did introduce a few problems along the way, notably the introduction of quantum phase transitions that brought led to imperfections.

Finally, Sergei Bravyi gave a talk based on the question: is there a fundamental upper bound on the amount of quantum information that can be stored reliably in a volume of d-dimensional space? The main result was that the upper bound found using the quantum situation was k \le \frac{cn}{d^2} while classical codes obey the weaker bound k \le \frac{cn}{\sqrt{d}}. What’s interesting about this is that, usually, the classical cases for things like this are a squareroot of the quantum case. Here it’s the fourth root for some reason (they don’t know the reason yet). Oddly, somewhere in the middle they seemed to come close to invoking the Cerf-Adami inequalities that I will be giving a poster on on Thursday.

More tomorrow…


QIP – Post 2

The afternoon’s talks began with one by Rahul Jain.  Frankly, it was another talk on computational complexity and, while interesting, is a topic for which I have a threshold that Jain’s talk exceeded.

Stefano Pironio followed Jain with a really cool discussion on using violations of Bell inequalities to generate random numbers (it included a great Dilbert cartoon in which Dilbert is introduced to a random number generator that is a horned monster that only spits out the number 9, the comment being that one can never really know if it is truly a random occurrence or not).  Anyway, Pironio’s main idea is that violations of Bell inequalities are inherently random events.  The first suggestion that this could be used for cryptography appeared in Roger Colbeck’s PhD thesis and embodies many aspects of no-signalling theorems.  For his Bell estimator, Pironio did not use probabilities.  The result is an expansion of randomness that, in conjunction with Chris Monroe’s group, was used to generate 42 new random bits.

The last talk of the afternoon was on the great paper by the collaboration I’m now calling Flame-broiled Bacon.  Yes, I’m referring to the paper on adiabatic gate teleportation, some of which is discussed here by his co-authorness, The Pontiff (AKA The Bacon).  Mr. Flame-broiled (i.e. Steve Flammia) used some nifty Metallica font to begin the talk, introducing the newly arrived Baby Bacon, named Max (someone in the audience suggested renaming him Min).  Basically, the work Steve spoke about involved creating a spin triplet but in which two of the particles are entangled using a specific Hamiltonian.  This entangled state is then transferred to the third + the middle one (I’m explaining this really badly).  Essentially, the adiabatic evolution teleports the state of one to another.  [Note that somewhere in here Steve made a possibly unintentional reference to the Jackson 5 (ABC, easy as 123) and missed a great opportunity to make a reference to ZZ Top courtesy of ZZ coupling.  Hey, if you want a serious synopsis, go somewhere else.  This blog highlights the hidden gems.]  Their scheme has the advantage of being more robust to errors.  Steve also highlighted an interesting implementation involving turning on and off B-fields in a way that can be used to teleport information., pointing out that this is a bit like a quantum transistor.  The applied field introduces a quantum phase transition that yields a quantum logic gate.  Instead of transferring current as in a transistor, this scheme transfers information!

QIP 2010 – Post 1 – Update

Supposedly there’s something out there called “live blogging” but I haven’t the slightest idea what it’s all about so a collection of posts will have to do.  First, let me point out that all the talks are being recorded so I won’t give über-detailed posts since you should be able to get the details from the videos once they are available.

The first talk was by Umesh Vazirani.  It was somewhat of an overview and covered a lot of ground.  The thing that seemed to get the most response was his discussion of an interesting algorithm for, what amounts to, making optimal choices based on “expert” advice.  So, suppose you have n financial advisors who are giving public advice on stock picks.  You want to make your buy stock based on the advice of one of these dudes each day.  As you move through the year, you keep track of how well each advisor is doing so you get some idea of who’s good and who’s not, giving you a better sense of “who to follow.”  The idea is to optimize your choices.

The interesting thing about this algorithm is that it closely resembles an intuitive one that my wife used to kick my ass in a football pool this year.  She did a very similar thing using the “experts” from ESPN, CNNSI, etc.

The next couple of talks were interesting.  I’ll have a photo of Dan Gottesman soon since he looked an awful lot like Steve Jobs at MacWorld when he gave his talk.  Scott Aaronson finished up the session with “freeze-dried” computation – how much computational work can be stored in a quantum state for later retrieval?  If quantum states are exponentially large, then possibly a huge amount can be stored, though one still must contend with the Holevo bound.  In any case, in investigating this idea, Scott found a new complexity class that he called YQP – Yoda Quantum Polynomial-Time (he decided there needed to be a complexity class beginning with Y – I think we need one beginning with a letter that has an umlaut).  In any case, $BQP \subseteq YQP \subseteq QMA \cap BQP/Poly$. Scott also made the point that this stuff is a little bit like cooking – combining a lot of ingredients and sometimes finding new ones to make something interesting. His main tool was something known as the Majority-Certificates Lemma which relates to boosting in computational learning theory.

More to come this afternoon…

QIP 2010 – The Arrival

Well, I have arrived in Zürich relatively intact and surprisingly awake (I guess one benefit of not sleeping well in general is that one never really gets jet lag).  I somehow managed to forget my ATM code, though, so I’m reduced to using my credit card for the time being.  QIP hasn’t started yet, so I’ll make some random travel observations as I sit in the airport hoping my ATM code pops back into my head.

  • I’ve flown on a lot of airlines including a number of European ones.  But Swiss Air’s economy seats are absolutely the most cramped I have ever been in.  Much more cramped than either Aer Lingus or Iceland Air.  A sardine can would be roomy compared to Swiss Air economy.
  • As long as people keep their mouths shut, it’s now virtually impossible to tell where someone is from just by looking at them.  Unfortunately we Americans might as well have a giant warning tatooed to our foreheads that says: Warning: dumb American; only speaks English.
  • I’m not sure what this says about the state of the world, but the ethnicity of airport employees is the same everywhere.
  • I must have observed hundreds if not thousands of people in the past twelve or thirteen hours and I can’t remember seeing a single dress and maybe only one or two skirts (not counting the stewardesses).  I wonder if humanity is witnessing the long, slow decline of the dress.
  • White trash is not a uniquely American phenomenon.  Nor is it necessarily white.
  • Things that have become ubiquitous: baseball hats (including the varying ways in which they are worn – backwards, sideways, etc.), jeans, large stomachs (mine’s only medium at the moment), sneakers, McDonald’s (I really wish they’d just go away), body piercings, and iPhones.  Amazingly I haven’t seen a Starbuck’s yet but then I’m still in the airport.
  • ATM code, ATM code, what art thou ATM code.
  • I remember the days of free airport WiFi.  Those days are no more.
  • You can spot the physicists a mile away, especially if there is a conference in whatever town you’re heading to.  Just look for the people carrying tubes (for the uninitiated, these house poster presentations).  If they’re not carrying tubes, just look for the particularly geeky looking people.

Well, my battery is running a bit low and I need to conserve it until my wife wakes up and I can pester her about my ATM code.  Hopefully I’ll have something interesting to blog about during tomorrow’s talks.

Update: How silly of me.  There is a Starbuck’s in the airport.  I simply didn’t look hard enough.

“There was a lot of smoke.”

That is how my son, who is in 3rd grade, described a class science experiment gone awry.  The experiment involved electrical tape, a battery, lightbulb, and a piece of insulated wire with the insulation stripped off on the ends.  Yes, amazingly simple, but it’s 3rd grade.  Apparently, in the middle of setting up the experiment, the teacher’s classroom phone rang.  Apparently the phone conversation, at one point, included the words “Scotch tape.”  Several students who were listening in to the conversation proceeded to substitute Scotch tape for electrical tape (presumably to tape the wires to the bulb).  Let’s just say that, what followed included the lightbulb briefly lighting up, a kid (not mine) crying from a minor burn on his fingers, and “a lot of smoke.”

Kind of reminds me a bit of the old pickle experiment.  I did this once or twice when I taught at Simmons College.  Basically, if you run electricity through a pickle it fluoresces.  The way we used to do it was to nail a pickle to a block of wood with two nails.  Then we used what my lab manager at the time called his “suicide plug” – a standard electrical plug (probably pulled off of a lamp or toaster or something) connected to two bare wires which were hooked up to the nails.

This also reminds me of when I broke the van de Graaff generator at my current place of employment.  This happened during a classroom demonstration about five years ago.  I don’t remember a lot of smoke but there was a lot of noise as the belt broke.  Amazingly they still gave me tenure.  I haven’t broken the new one, but I have managed to make it arc a good four or five inches to my eyebrow (have I mentioned I’ve nearly been struck my lightning three times?).

100,000 digits of Pi

I’m a total number theoretic geek.  I stumbled on this and thought it was pretty cool.  I’m sure there are similar things out there on the web, but this is the first I came across so it gets a post.

It’s a binary day … two days in a row!

In the US, today is 01/11/10 which, when taken as the binary number 011110 and converted to base-10 decimal is 30.  However, in much of the rest of the world today is written 11/01/10 or 110110 which is 54.  Conversely, yesterday was 01/10/10 or 011010 in the US which is 26 or 10/01/10 or 100110 in much of the rest of the world which is 38.  Of course, New Year’s Day was the same everywhere – 01/01/10 or 010110 which is 22.

There are a whole ton of binary days coming up this year.  Check out someone’s (alcohol-inspired?) list

Holy craptacular, Batman

I just spent two days in an intense strategic planning committee meeting.  No, I am not kidding.  Then I stayed up until 3 AM to finish a rebuttal for the QIP people before getting up at 6:40 to get the kids on the bus.  Then I walked four miles (my regular exercise routine).  Then I went back to sleep.  Then I went fishing in a snowstorm.  I will have more coherent things to say once I get some real sleep and thaw myself out.

Blog at WordPress.com.

Up ↑