Quantum Hustles

Over at masteroftheuniverse, the master has posted a great list of prop bets. Among his bets is one that probably won't work on many computer scientists (or it shouldn't if they've had even a decent theory course) based upon the birthday problem. Sometimes the birthday problem is called the birthday paradox, but the problem is no more a paradox than the twin paradox is about twins. The birthday problem has to do with the probability that a set of randomly drawn people share a birthday. In other words, assuming that everyone in a group of N people has an equal probability of being born on a given day, what is the probability that at least two of these people share a birthday. Quite surprisingly, or at least surprising the first time you hear it, is that if N is 23, this probability is already greater than 50 percent. In computer science this type of process comes up all the time and is responsible for lots of square roots that one sees in running times of algorithms. The master's blog post reminded me of a version of the birthday paradox that Wim van Dam once told me (if anyone knows its past history, please post a comment)...a quantum birthday paradox.

Here is the setup. Suppose that we are sampling from the set i-8684404a5841c65f9c7cda75cc1cf3c3-201004151247.jpg. In particular consider the situation, classically, where we are sampling from two distributions over this set, i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg. Both i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg are distributions which are i-6995db534a5df5e3c4157017630ded21-201004150950.jpg on exactly N of the elements of i-f262aac7fd2ea37564749d7d88e2897c-201004150951.jpg and 0 on the rest of i-f262aac7fd2ea37564749d7d88e2897c-201004150951.jpg. I will guarantee you that either the distributions are equal, i-c41b45e82fc74c8e8b64af244af7b629-201004150952.jpg , or that when i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg has  i-6995db534a5df5e3c4157017630ded21-201004150950.jpg weight on an element, then i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg has weight 0. In other words, the probability vectors for these distributions are orthogonal, so I will denote this i-0dfb484fc350274fa1746cf6fb123b17-201004150954.jpg. So the problem is, given the ability to classically sample from these distributions, how many samples must one take to succeed in identifying which of these two cases, i-c41b45e82fc74c8e8b64af244af7b629-201004150952.jpg or i-0dfb484fc350274fa1746cf6fb123b17-201004150954.jpg, hold. One can easily see that this probability is like the birthday problem: by sampling from i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg one has to basically wait for a collision in order to determine that i-c41b45e82fc74c8e8b64af244af7b629-201004150952.jpg. Thus you can see that it would require about i-b7534c108d036c1dc822b1846a5c23b1-201004150956.jpg samples to distinguish these two cases. More specifically, to distinguish between these two cases with some constant probability, say a probability of 3/4, we need to sample i-e04efa333d3db5cd01e36ea0bcfc3da5-201004151235.jpg times.

Okay so what does this have to do with a quantum birthday paradox. Well now consider the situation where instead being given two probability distributions i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg, one is given two quantum states, i-528bfed7ffd7a41b7d640ec355492405-201004151255.jpg and i-36751dcccc5866e8850bfee59bc891ab-201004150957.jpg, with the property that if you simply measure them in the computational basis you will obtain the classical distribution that behave like i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg. That is let i-528bfed7ffd7a41b7d640ec355492405-201004151255.jpg and i-36751dcccc5866e8850bfee59bc891ab-201004150957.jpg be superpositions over 2N computational basis states with the property that in this basis, they have exactly N amplitudes which are i-bf935241da8056d7abba4d93d3219e45-201004150959.jpg and N amplitudes which are zero. We are guaranteed that either i-dd6d2d64299d4439d9d74692f4036e09-201004151257.jpg or i-9409b247a544d9f0d356004b9d3cbb70-201004151258.jpg and the goal is, by using many copies of i-528bfed7ffd7a41b7d640ec355492405-201004151255.jpg and i-36751dcccc5866e8850bfee59bc891ab-201004150957.jpg to distinguish between these two cases. Now if one simply measures these states in the computational basis then one obtains probability distributions that are exactly like i-f25be93ef0ebc09e4c88630496d4aeeb-201004150949.jpg and i-b8e03fb3aed12b8059bb3a8f5aace23d-201004150945.jpg. But this is the quantum world, so we don't have to measure in this basis. So is there a basis that we can measure in which can lead to using less that i-b7534c108d036c1dc822b1846a5c23b1-201004150956.jpg copies of i-528bfed7ffd7a41b7d640ec355492405-201004151255.jpg and i-36751dcccc5866e8850bfee59bc891ab-201004150957.jpg to distinguish the two cases of i-dd6d2d64299d4439d9d74692f4036e09-201004151257.jpg versus i-9409b247a544d9f0d356004b9d3cbb70-201004151258.jpg?

The answer is yes, indeed. Of course that's the answer: why else would I be writing this blog post. In particular consider the fully symmetric or anti-symmetric subspaces of the two systems. In particular, define the states

i-e6bd361f00a4ab84d70090f3609d5c08-201004151224.jpg   if i-c87ad9edc18aa961ed555899757a1b3a-201004151131.jpg

i-a280da72ff3ab184f89a45891d4d34a6-201004151132.jpg  if i-46546d5875f1cfafa044219e17329a7d-201004151244.jpg


i-c8c337a4be8b67f70c6163202ede2f00-201004151231.jpg  if i-c87ad9edc18aa961ed555899757a1b3a-201004151131.jpg

These states form a complete basis for the two systems we are considering, with the i-4c654fb4628244657df4842d78b1b941-201004151222.jpg states representing symmetric states and the i-0c89a1730b7303f043d898a6c5fdc8f7-201004151223.jpg states representing the anti-symmetric states. Suppose that on i-528bfed7ffd7a41b7d640ec355492405-201004151255.jpg and  i-36751dcccc5866e8850bfee59bc891ab-201004150957.jpg we measure the above states. Now if i-dd6d2d64299d4439d9d74692f4036e09-201004151257.jpg, then we note that i-25767e42dc15a909863fe37145d71c09-201004151259.jpg is symmetric under exchange of the two states subsystem. That is if we measure the above basis states we will only obtain i-4c654fb4628244657df4842d78b1b941-201004151222.jpg basis states. If, on the other hand i-9409b247a544d9f0d356004b9d3cbb70-201004151258.jpg then it is straightforward to see that i-25767e42dc15a909863fe37145d71c09-201004151259.jpg has support equally on symmetric and anti-symmetric states. In particular if

i-1f259b8c89bd1f4d9b3e91848b3b0cca-201004151301.jpg and i-fb62914ccf06a903b999b944f950629d-201004151305.jpg

where i-963057478c8acca07463b64c833c4fdb-201004151229.jpg, then we can expand i-25767e42dc15a909863fe37145d71c09-201004151259.jpg as

From which we can see that we will obtain the symmetric and anti-symmetric states with equal probability.
Thus we have seen that by making a measurement which distinguishes between the symmetric and antisymmetric subspaces of our two systems, if i-dd6d2d64299d4439d9d74692f4036e09-201004151257.jpg  we will only observe symmetric states and if i-9409b247a544d9f0d356004b9d3cbb70-201004151258.jpg we will observe symmetric states half the time and anti-symmetric states the other half the time. Thus we can reliably distinguish these two cases with a failure probability of i-f5e2b141841e9725b656845a09fc0c23-201004151234.jpg for k repetitions of this setup. This is significantly better from the classical case! Indeed we have succeeded in distinguishing the states with probability 3/4 using only 2 repetitions of the setup. Thus we have gone from i-b27d9650cb195c733e7e004c45310b9a-201004151236.jpg in the classical world to i-f93564b5f96343b5bcb828a7c165d085-201004151237.jpg in the quantum world. Amazing! (Of course many will argue the setup is not fair: and yes I agree it is not fair when one side gets to use this powerful thing called quantum theory and the other side hides behind the computer science of the 20th century :) ) Many of you will recognize that the above method for distinguishing states is nothing more than the quantum swap test.
So what is the moral of all this? Well, besides showing a cool case where quantum exponentially outperforms classical, it also tells you that you should be wary of quantum computers offering you bets. Indeed, I make it my own personal policy never to bet with quantum computers, and think that you should make it your policy as well.

More like this

"Well, besides showing a cool case where quantum exponentially outperforms classical,..."


By Michael Albert (not verified) on 15 Apr 2010 #permalink

Dave, it was interesting that immediately to the right of your post was a ScienceBlogs.Com link to Practically useful: what the Rosetta protein modeling suite can do for you ... which is like your post in being also about the efficient extraction of useful information from the smallest feasible number of measurements, and with the least feasible computational effort.

These two topics are IMHO equally interesting, and possibly convey a shared set of lessons-learned about fundamental physics. One key difference is that your problem's quantum states (by assumption) are not thermally equilibriated, while Rosetta's conformations (by assumption) are.

It's clear that this thermal equilibriation makes all the difference in the world, regarding the feasibility of efficient measurement, simulation, and estimation.

Since we know that our universe was born out of a thermal equilibriation process (the Big Bang), perhaps it's not surprising that (in the physical universe) we never encounter quantum dynamical systems than can't be simulated efficiently.

Indeed, we begin to wonder whether it might be infeasible even in principle to physically realize impossible-to-simulate quantum systems ... in part because the quantum state-space that was born in the Big Bang is not a linear Hilbert space, any more than the spatial geometry of the universe---that was born in the same Big Bang---is Euclidean.

I'm not clear whether constructing the classical and the quantum tests with sufficient accuracy to make the respective tests work well enough for practical purposes require comparable time and resources.

If it takes a unit A of time and resources to construct an apparatus that classically compares one element from P0 with one element from P1, and a unit B of time and resources to perform each query instance, it is not clear that it takes time and resources of order A to construct an apparatus that projects reliably to the symmetric and anti-symmetric basis sets and that it takes time and resources of order B to perform each query instance.

In the absence of a realistic estimate of the relative costs of implementation, I can't see what significance the sqrt{n} comparison has.

By Peter Morgan (not verified) on 18 Apr 2010 #permalink

> Exponentially?

Right, not exponential but like Grover it's an N1/2 improvement.

By Not Exponential (not verified) on 18 Apr 2010 #permalink

Peter: the resources needed for the swap test are certainly tractable (swap test is certainly doable...google "swap test quantum" for an explanation of the circuit.) The objection you could raise is that this an oracle result, and the oracles I'm comparing are certainly not equivalent. Fine. But if you are given a quantum oracle the fact that you can solve this problem in constant time versus N^{1/2} if you use the oracle classically should give you a double take.

Um, Not Exponential, no. Classically it's N^{1/2}. Quantum it's constant. Normally we would measure the problem size in bits to express N, i.e. this an exponential to constant improvement, i.e. MUCH MUCH better than a polynomial Grover speedup.