Monday, February 24, 2014

Who's on First!?

“On the Uncertainty of the Ordering of Nonlocal Wavefunction Collapse when Relativity is Considered,”

by Chris D. Richardson and Jonathan P. Dowling

This preprint on the ArXiv by my former PhD student, Chris Richardson, and me, is not getting enough of the well-deserved publicity that it warrants so here I am to shamelessly promote it. (That and Chris will shortly be looking for a job.) This is really 90% Chris’s work with 10% motivational pep talks from me to him. In a previous blog post, “On the Curious Consistency of Non-Relativistic Quantum Theory with Non-Quantum Relativity Theory,” I blathered on about how odd it was that non-relativistic quantum theory always seemed to be consistent with ordinary relativity theory; even though we have no right to expect that these two theories should be consistent and every right to believe they should flat out contradict each other. This curiousness Nicolas Gisin calls the “tension” between the two theories and Gisin has even done an experiment of the EPR type with a well separated Alice and Bob, but with Bob placed in a moving reference frame (compared to Alice) to try to measure the ‘speed of collapse’ of the two-particle wave function. Gisin and his group conclude that the speed of collapse is some 10,000 times faster than the speed of light (which is consistent with infinitely fast).

This experiment motivated Chris and I to think about a closely related problem; a problem that in fact motivated Gisin’s experiment in the first place. In non-relativistic quantum theory, in an EPR experiment, if Alice makes a measurement on her particle then the state of Bob’s particle is supposed to collapse ‘instantaneously and simultaneously’ to the result anti-correlated to Alice’s measurement (if they share, say, a spin-singlet state). But words like ‘instantaneous’ and — Heaven forbid! — ‘simultaneous’ are heresy in non-quantum relativity theory.

This thought experiment gives rise to a purported paradox. If in one reference frame Alice measures first and collapses Bob’s state there can always be an observer in a different inertial frame who thinks Bob measured first and collapsed Alice’s state. The paradox then may be stated, “Who really collapsed whom first?” This curious swapping of temporal order is the paradox.

Now if I was David Deutsch I would tell you to avoid all this collapse nonsense and to instead embrace the Many Worlds Interpretation of Quantum Mechanics but instead Chris and I decided to push this paradox into a small logical corner where we could beat the heck out of it with a purely Copenhagen Gedanken experimental analysis.

The conclusion of our short paper, now in referee limbo in some journal I’d rather not mention (so as to avoid the once and future lawsuits) is that Naturenot the journal! — deploys a type of quantum-mechanical cloaking device upon the experiment to keep the paradox from arising in the first place.

The paroxysm of paradoxism is swept squarely under a round rug.

The crux of our argument is that Alice and Bob’s measurements cannot be made with infinite precision but are constrained by the Heisenberg uncertainty principle — particularly the notorious energy-time uncertainty principle. Since energy and time are not relativistically invariant quantities, different observers in different reference frames must transform their uncertainty principles accordingly.

Therein lies the rug.

To quote the conclusion of our paper; “The uncertainty in time always outruns the time difference induced by the change in reference frames. Neither Alice nor Bob will ever, with certainty, observe the two measurements swap temporal order.”

Paradox, schmäradox!

The curious consistency of quantum theory and relativity theory hides again….

Monday, February 17, 2014

Boson sampling with photon-added coherent states

Kaushik P. Seshadreesan, Jonathan P. Olson, Keith R. Motes, Peter P. Rohde, Jonathan P. Dowling
Boson sampling is a simple and experimentally viable model for non-universal linear optics quantum computing. Boson sampling has been shown to implement a classically hard algorithm when fed with single photons. This raises the question as to whether there are other quantum states of light that implement similarly computationally complex problems. We consider a class of continuous variable states---photon added coherent states---and demonstrate their computational complexity when evolved using linear optical networks and measured using photodetection. We find that, provided the coherent state amplitudes are upper bounded by an inverse polynomial in the size of the system, the sampling problem remains computationally hard.

See: arXiv:1402.0531

Thursday, October 31, 2013

The Generation of Super-Resolving Single-Photon Path-Entangled States



Wei Feng, Kebei Jiang, Michelle L.-J. Lollie, M. Suhail Zubairy, Jonathan P. Dowling

One of the big drawbacks for using N00N states in quantum lithography is the need for a N-photon absorbing resist, which has a very low cross section for large N. In this paper, we propose two protocols for generating super-resolving single-photon path-entangled states from general maximally path-entangled N00N states. We also show that both protocols generate the desired state with different probabilities depending on the type of detectors being used. Such super-resolving single-photon path-entangled states preserve high resolving power but lack the requirement of a multi-photon absorbing resist, which makes this state, in principle, a perfect candidate for quantum lithography.

Friday, September 13, 2013

On the Curious Consistency of Non-Relativistic Quantum Theory with Non-Quantum Relativity Theory

For years I have puzzled over what some have called the ‘tension’ between non-relativistic quantum theory and non-quantum relativity theory. Standard quantum information theory is of the non-relativistic variety based on ordinary quantum mechanics without any appeal to, say, relativistic quantum field theory. In run of the mill quantum information theory there is nary a c, the speed of light, in sight. The term ‘relativity’ shows up only four times in the Nielsen and Chuang book, QuantumComputation and Quantum Information (a book we all call ‘Mike and Ike’ after the first names of the authors). In all four of these places it appears only so much as a foil against which quantum information theory is proffered. The authors point out that, for example, you cannot use quantum informatic teleportation to send signals faster than the speed of light — but why not?

I would naively expect non-relativistic quantum theory to make predictions that outright conflicted with the predictions of non-quantum relativity theory. For example non-relativistic Newtonian physics makes just such conflicting (and wrong) predictions. Newtonian mechanics, for example, states that an object’s mass is conserved and that said object may always be accelerated up to arbitrarily high velocities and that information-bearing signals may travel faster than light. This directly contradicts the confirmed predictions of special relativity but nobody cares because nobody expects non-relativistic Newtonian mechanics to be consistent with relativity.

And yet, over time, we have come to expect — in many venues — non-relativistic quantum information theory (and the non-relativistic quantum theory upon which it is based) to be consistent with non-quantum relativity. One example is the caveat in Mike and Ike that quantum teleportation cannot be used to send signals faster than light. The correct statement is more close to quantum teleportation cannot be used to send signals instantaneously. According to the non-relativistic version of quantum teleportation, in some sense the state to be teleported is transferred instantaneously, but it can only be extracted with help from a luminal-speed communication from Alice to Bob through some classical channel.

Another example of this ‘tension’ comes to us from Nick Herbert’s publication years ago on a superluminal-signaling scheme he called FLASH. This scheme is discussed in my book, Schrödinger’s Killer App, in David Kaiser’s book, How the HippiesSaved Physics, and in an arXiv posting by Asher Peres, “How the No-Cloning Theorem Got It’s Name.” The FLASH scheme, like teleportation, required two parties, Alice and Bob, to have set up shared entangled states, but unlike teleportation, also a noiseless state-amplification machine. The communication scheme was not only superluminal; it was instantaneous. Many physicists, including Peres and Glauber, knew the scheme had to be wrong, and the downfall of FLASH came with the invention of the no-cloning theorem and its closely related cousin, the no non-noiseless amplification theorem. Cloning and noiseless amplification devices violate the unitary and linear nature of quantum theory and so cannot exist. Everybody heaved a sigh of relief, but I was puzzled. Why were Glauber and Peres so sure that non-relativistic quantum theory should not contradict the theory of non-quantum relativity theory? If it had, I would have said this is of no more concern than noting that Newtonian mechanics contradicts relativity. One would not expect any non-relativistic theory to be consistent with a relativistic one and would in fact expect them to make inconsistent predictions.

Another example along these lines is the Bohr’s resolution to Einstein’s photon-in-a-box paradox from the Sixth Solvay Congress in 1930. Einstein cooked up a thought experiment about weighing a box before and after a photon was allowed to escape from it. He showed that this scheme apparently violated the Heisenberg energy-time uncertainty relationship. Bohr resolved the paradox and saved the uncertainty principle by invoking the gravitational red shift, a general relativistic effect. Why on earth should general relativity have anything to do with the non-relativistic Heisenberg uncertainty principle? And yet the consistency of the latter requires the former.

A final example, that I lift from Scott Aaronson’s book, QuantumComputing Since Democritus, involves black holes. Here the idea is to resolve the black hole information paradox. If you throw information-bearing quantum states into a black hole and they disappear forever then this would violate unitarity. One proposed resolution is that, near the event horizon, the quantum state is somehow duplicated — in apparent violation of the no-cloning theorem — and one copy vanishes into the singularity and the other is remitted as Hawking radiation. (This is a concept close to a resolution proposed by Chris Adami and Greg Ver Steeg in their 2004 arXiv posting, “Classical Information Capacity of Quantum Black Holes.”) 

To violate the no-cloning theorem you could grab the copy that comes out and then rocket into the black hole and grab the other copy and thus have two copies of the unknown quantum state. However, if you try to do this, apparently it takes so long for the first copy to be emitted that by the time you grab on to it the second copy has always already been gobbled up by the singularity and the no-cloning theorem is saved. Why on earth should the non-relativistic version of the no-cloning theorem be consistent with the relativistic theory of black holes? To quote Aaronson, “So it’s funny that there are these little things that seem like they might cause a conflict with quantum mechanics … but when you really examine them, it no longer seems like they do.”

It’s not funny — it’s downright bizarre.

What this tension between non-relativistic quantum theory and non-quantum relativity theory suggests to me is that there is some ur-theory, likely a phenomenological one, which unifies non-relativistic quantum theory and non-quantum relativity theory. Now I know what you are all going to say, “Sure — it's a quantum theory of gravity!” Indeed, if we had that, I expect all this tension would go away. But for quantum theories of gravity — string theory and loop-quantum gravity — the tension between relativity and quantum mechanics is down at the Planck length or up at the Planck energy. In the examples I discuss above, this tension is at ordinary length and energy scales. I don’t need physics at the Planck scale to talk about superluminal signaling, photons in boxes, or black hole information paradoxes.

Hence I suggest that there is some intermediate unified theory between quantum gravity and what we have now and that this theory in certain limits produces non-relativistic quantum theory and non-quantum relativity theory. The best lame analogy I can come up with is the unification of electricity and magnetism within Maxwell’s equations, which are phenomenological equations derived from close observations of experiments. We know now that the electromagnetic field must be quantized — à la quantum electrodynamics — when wavelengths are short and energies large and photons are needed. But the unquantized Maxwell equations served us quite well for 100 years before we hit that point. In this lame analogy, electricity and magnetism are the analog of non-relativistic quantum theory and non-quantum relativity theory; Maxwell’s equations are the analog of the unifying (but yet unknown) ur-theory, and quantum electrodynamics is the analog of a full theory of quantum gravity.

So how to find this phenomenological ur-theory that unifies non-relativistic quantum theory with non-quantum relativity theory? Continue to explore these tensions between the two; both in theory and experiment. Gisin and his group have done experiments measuring the speed of the collapse of the wave function of entangled photon pairs over large distances with detectors in different moving frames. Work along these lines should be encouraged and not disparaged.

(THU 26 SEP 2013)

Just found this comment while reading the book by Haroche and Raimond:

"The consistency between the EPR correlations and relativity is by itself also
strange, in some way. Quantum laws do ultimately satisfy relativity in their field theory
version, but the measurement description we have implicitly invoked to compute the
EPR correlations is non-relativistic. If it had violated causality, we could have invoked
the necessity to use a relativistic version of measurement theory, dealing with the
proper time of detection events. We do not have to do this. Non-relativistic quantum
physics is non-local in a way subtle enough not to contradict the inherently relativistic
causality principle.
" (Italics mine.)

Haroche, Serge; Raimond, Jean-Michel (2006-08-10). Exploring the Quantum:Atoms, Cavities, and Photons (Oxford Graduate Texts) (Page 65). OUP Oxford. Kindle Edition.

Wednesday, July 31, 2013

Spontaneous parametric down-conversion photon sources are scalable in the asymptotic limit for boson-sampling

Boson-sampling has emerged as a promising avenue towards post-classical optical quantum computation, and numerous elementary demonstrations have recently been performed. Spontaneous parametric down-conversion is the mainstay for single-photon state preparation, the technique employed in most optical quantum information processing implementations to-date. Here we present a simple architecture for boson-sampling based on multiplexed parameteric down-conversion and demonstrate that the architecture is limited only by the post-selected detection efficiency. That is, given that detection efficiencies are sufficiently high to enable post-selection, photon-number errors in the down-converters are sufficiently low as to guarantee correct boson-sampling most of the time. Thus, we show that parametric down-conversion sources will not present a bottleneck for future boson-sampling implementations. Rather, photodetection efficiency is the limiting factor and thus future implementations may continue to employ down-conversion sources.

For all of my colleagues who thought from my previous blog post that I was a boson sampling skeptic.....

Sunday, July 28, 2013

Sampling — Schmämpling!

In January of 2011, I went on a six-month sabbatical — my first sabbatical ever — and, as is often the case on such ventures (in order to have such sabbatical requests approved by parsimonious deans), I declared to the dean that I would write a book.

Luna Han, my editor at Taylor & Francis, had been hounding me for some years to write a textbook.. Having moved to academia in 2004 (after 10 years of working for the federal government), I was not in a good position to write a textbook as I did not have years and years of class notes that could be 'easily' up-converted into one. I did, however, have lots and lots of notes and anecdotes spanning the 15 years I was involved in the US Government program to build a quantum computer.

Hence it was with some trepidation that I called up Ms. Han in and declared, "Well I have good news and bad news!" Ever the stoic, Luna replied, "Whenever anybody says that it is only ever bad news." I continued on, "Well the good news is I'm done with chapter one!" Luna's temper improved slightly, "Sound good so far...." Then I went in for the kill, "It's a popular book and not a textbook." This did not go over well, as popular books have much lower profit margins and so forth, but she told me to email her chapter one anyway and she would take a look. A few days latter I got her response, "I love what I'm reading ... I certainly hope you’ll consider sending me the full [book] proposal. "

The proposal was reviewed (and at times reviled) by my friends and colleagues, but the reviews were (for the most part) so positive that I went under contract with Taylor & Francis and began typing four hours a day. I shunned all refereeing, committee meetings, conference travel, proposal reviews, and did nothing much else than work on the book for two years. I fell so far off the grid that some of my colleagues were asking around to see if had met some untimely end. I submitted the book on schedule in September of 2012, then worked with the typesetters for the next few months and spent my Xmas break in 2012 proofreading the 450 page proofs, and then Schrödinger's Killer App: Race to Build the World's First Quantum Computer, was off to press.

I then emerged in the January of 2013 like Rip Van Winkle, sleeping for two years after an all-night bender with some magical dwarfs; rubbing my eyes and blinking. Then I strolled down into my village only to discover that everybody was talking about the boson-sampling problem. My reaction was to inquire, "What the heck is boson the boson-sampling problem!?" I was entreated to read a 94 page preprint posted in 2010 by Scott Aaronson and Alex Arkhipov on the ArXiv, but to a great extent I found this paper, written in the language of quantum computer complexity class theory, to be almost completely incomprehensible. However I understood enough to realize that these computer scientists were claiming that us quantum physicists had missed something very important about the nature of linear optical interferometers with Fock-state (number-state) inputs. Well, I have been working on the theory of linear optical interferometers for 25 years, and this clearly now was a turf war. What the Fock did I miss? It turns out that, what I had missed, was precisely the Fock. (If you don't want to read that 94-page paper either then try this two-page introduction to boson sampling theory and experiment, written by James Franson.)

Rather than take a crash course in quantum complexity theory and then go figure out that 94-page paper, I decided to roll up my sleeves and dig into these interferometers myself in my own way and figure out just what the heck was going on — avoiding quantum computer complexity class theory like the plague — and using only elementary tools from quantum optics theory. Until the rise of the boson sampling problem, I would attest that nearly every quantum optician on Earth, including myself, did not think there was much interesting going on in passive, linear optical interferometers, no matter what quantum state of light you put into them — Fock or not. (For a fun an flippant overview of why we all thought this way about these interferometers, see my recent lecture given at the 2013 Rochester Quantum Information and Measurement Conference; a conference where Robert Boyd came up to me and declared, "Jon! It's so good to see you! Nobody has seen you in a couple of years and people were asking if you were all right.")

It turned out that two of my undergraduates, Bryan Gard and Robert Cross, also in 2010, were working on a problem that was closely related to the boson-sampling problem (but none of us knew it at the time); they were analytically and numerically studying quantum random walks with multi-photon Fock states in a linear optical interferometer. I gave this to them as an undergraduate 'starter' problem, motivated by experiments in Jeremy O'Brien's group with two-photon Fock states. Since I did not expect anything too interesting to happen when you went from quantum random walks with one or two photons to random walks with multiple photons, I expected the undergrads to come up with a closed form solution predicting the photon output from an arbitrary photon input.

Then I went on sabbatical and when was buried in the writing of my book for two years and I did not pay too much attention to them when they complained that they could not come up with even a numerical simulation for more than a few photons in an interferometer with only a few modes. They particularly complained that, "The problem blows up exponentially fast!" "These undergrads," I thought, "they see exponential blow ups whenever the math gets a little hairy." Of course, as usual, my undergrads were right and I was wrong. The thing does blow up exponentially fast.

In January of 2013 we were trying to get this random walk paper published, and after endless rounds of refereeing, we finally did and it recently appeared in JOSA B as, "Quantum Random Walks with Multiple Photons." But in the final round of refereeing, in response to a toss-off comment we made in the paper about the apparent exponential growth of the problem's complexity, a referee suggested, "Were the authors to make this comparison [to the boson sampling problem], they would be in a position to comment on the computational hardness of such systems, which would be insightful." My thought, and that of Bryan and Robert, was, "What the heck is the boson sampling problem!?"

The referee cited an experimental paper out of Andrew White's group, and then I suddenly I remembered Andrew gave at lecture on this in a NASA conference in January of 2012. However I was then so engrossed in the writing of my book that the only take-home message I got from his talk was that Andrew was experimenting with permanents, and I joked that perhaps he was experimenting with new hairdos. Suddenly things started to click and I finally became fully aware of that daunting 94-pager by Aaronson and Arkhipov.

So Bryan and Robert and I rolled up our sleeves even farther and tackled this problem again from the point of view of counting all the resources and comparing coherent-state and squeezed-state inputs to Fock-state inputs and sure enough, although not much interesting happens with coherent and squeezed, everything blows up with the Fock. When I showed co-author Hwang Lee our proof that the Hilbert space dimension blows up as a function of the number of modes and number of photons, he retorted, "This is shocking!" But what is shocking to a quantum optical theorist is not necessarily shocking to a quantum computational theorist.

We fired off the paper to Physical Review Letters (PRL) — and the referees immediately pounced. One said that our result was not new and our proof was not nearly as good as invoking the "collapse of the polynomial hierarchy" as did Aaronson and Arkhipov. At that point I had no idea what the polynomial hierarchy even was — some computer science-y thing — and I certainly did not much care if it collapsed or not and so we retorted, "Physical Review is a physics journal and not a computer science journal." Comments from Aaronson and Peter Rhode were much more helpful. They both pointed out that, due to the Gottesman-Knill theorem, it is now well-known, in spite of Feynman's arguments to the contrary, that sometimes systems with exponentially large Hilbert spaces are still efficiently simulateable — who knew!? When Aaronson and Rohde both pointed out that fermionic linear interferometers with Fock state inputs also have an exponentially large Hilbert space — I didn't believe it! But in spite of that blow up the fermionic devices were still efficiently simulateable do to special properties of matrix determinants that matrix permanents don't have. Sometimes, boys and girls, there are polynomial shortcuts through your exponentially large Hilbert space....

Rolling up our sleeves again (this time to our eyeballs) first I had to take a crash course on fermionic interferometers (think neutrons) and prove the Hilbert space blows up there too. (It does.) Then we had to augment our paper and bring the argument back around to matrix permanents (nothing to do with Andrew White's hairdo) and matrix determinants. (We did.) And now our revised paper, "Classical Computers Very Likely Can Not Efficiently Simulate Multimode Linear Optical Interferometers with Arbitrary Fock-State Inputs-An Elementary Argument,"  sits in the limbo that awaits quantum optics papers that are not too horribly rejected from Physical Review Letters, and so you try to transfer them to Physical Review A (PRA) instead. In Catholic school I was taught that limbo was just like heaven — except you never got to see the face of God. Similarly, PRA-limbo is just like PRL-heaven — except you never get to see the face of Basbas....

But now finally to the point of this post. This post has a point? Finally! I think it was Einstein who once said that doing physics research is like staggering around drunk in a dark, unfamiliar, furniture-filled room, bumping over chairs and ottomans, while groping for the light switch.  In this vein, having me explain to you how we do research in our group is a bit like having your Würst vendor explain to you how he makes his sausages. However, if you want to pursue a career in sausage making, it might be best to know what you are getting into up front. After all you want to make sure you are always getting the best of the Würst! However when it comes to the experiments done so far on boson sampling, it is not quite yet the best....

Now, after pondering the  theory of this boson sampling business for six months and now knowing enough to be dangerous, I have finally decided to dive fully in and read the flurry of nearly simultaneously published recent papers claiming to implement boson sampling with three or four photons  [Broome2013, Spring2012, Crespi2012, Tillmann2013, Spagnolo13]. It is clear to me now, that in order to implement boson sampling, the input photons must be in Fock states that is the whole point. Coherent states and squeezed states and other so-called Gaussian states simply will not do, as it is well known (due to work of Sanders and Braunstein and others) that linear optical interferometers with Gaussian-state inputs are always efficiently simulateable.

The whole point of boson sampling is that the input needs to be in the form of pure photon Fock states in order to perform the sampling. That is, thinking of the interferometer as the information processor, the processing must take place on Fock states and not on Gaussian states. If you input only Gaussian states, as in the four-photon experiment of Crespi, et al., you are clearly not doing boson sampling at all. If you mix one-photon Fock states with a two-mode Gaussian state (as all the three-photon experiments do) it is not clear what you are doing, but you are certainly not implementing boson sampling as advertised. Yet all these experiments do this. I'll focus on the three-photon experiments, as they are the most tricky. (The single four-photon experiment can be discarded out of hand as there is not a Fock state in sight.)

To do this right one would need to have three, distinct,  heralded single-photon Fock states. Instead all the three-photon experiments herald only one single-photon Fock state and then mix it with the output of a spontaneous parametric downconverter (SPDC) —an output which is a Gaussian state! In particular it is not the product of two-distinct single-photon Fock states that is required for boson sampling.

The output of the SPDC, in the Fock basis, is a superposition of mostly twin vacuum states, some twin single-Fock states, some fewer twin double-Fock states, and so on — all summing up to a Gaussian state. The experimentalist's hope is that by post-selecting only on events where three photons (in total) are counted that this experiment is equivalent to having three distinct single-photon-Fock states to begin with.

It is not. 

What matters for boson sampling is what you put in to the interferometer and not so much what you do to what comes out. This post-selection process fools you into thinking that only three photons went in. That is not true. A single photon went in mixed with a Gaussian, two-mode squeezed vacuum (of indeterminate photon number) — a two-mode squeezed vacuum state is definitely not two photons in a pair of Fock states.

To kick in the large Hilbert space and the permanents of matrices and the things that make boson sampling interesting the processor must process only Fock states. You can't just pretend at the end of the experiment that what you sent in were Fock states. Whatever these experiments are doing it is not boson sampling as advertised. A three-photon boson sampling experiment will require that all three of the input photons are heralded — not just one (or in the case of the four-photon experiment not just none).

Now before my old friend Andrew White (in his curly new hairdo) comes flying down from Brisbane to pummel me here in Sydney, where I am visiting for a few weeks, let me say that all of these experiments were impressive tours de force carried out by some of the best quantum mechanics in the galaxy. Each and every experiment required hard work and lots of hours in the lab and most of these experiments are on the forefront of integrated quantum photonics, which will have a plethora of applications to quantum optical computing, metrology, and imaging. And someday soon one of these extraordinary experimental groups will demonstrate boson sampling with three photons — but I venture that this day has not yet come.

And yes, yes, yes, I know why all the experimentalists all do it this way — I may not know much about quantum complexity theory but I do know a thing or two about quantum optics. The point is that with the SPDC sources the probability of heralding exactly N photons scales exponentially poorly with N. That is if they tried to do this with three really heralded single photons, then the data collection would have taken months, and if they tried to do this with four really heralded single photons, then it would have taken years.

Nonetheless, while it is true in previous experiments in other areas of quantum optics that it does not really matter too much if you have real single-photon inputs, or post-select the outputs and then pretend that you had real single-photon inputs, for boson sampling this distinction is critical. The linear optical interferometer must process only Fock input states to be in the boson sampling regime. If, instead, it processes only Gaussian states or admixtures of Gaussian states with Fock states, well then it is not carrying out boson sampling it is doing something else — no matter how much you pretend to the contrary. 

To summarize this entire diatribe in three words: What? The Fock!

Tuesday, July 23, 2013

NP or NOT NP — What is the Question?

I'm reading Scott Aaronson's book, Quantum Computing Since Democritus, which according to is frequently bought together with Schrödinger's Killer App (the second, funniest book on quantum computing to appear this year).

In spite of Stephen Wolfram's scathing review, and apparent exponential growth of mind-bending computer science acronyms, I am finding it quite enjoyable and, as a simple-minded quantum physicist, I am also finding that I'm learning quite a lot and, against my own will, thinking a lot about computer complexity theory.

A particular comment by Aaronson, connecting the P vs NP business to something in physics, struck a nerve. I first heard about this business in graduate school in the 1980s when the mathematics students would jokingly scrawl "P=NP!" on the chalkboard only to find the next day somebody added a slash so it read "P≠NP!" and they all had a good laugh and the physics students all just shook their heads.

I had to wrestle with this again in 1994 after Shor's algorithm hit the fan and, as a reviewer of quantum computing proposals for the Department of Defense, I had to have at least some idea of what all these proposals were talking about. However I felt it was all really a bunch of non-physical mumbo jumbo about what the computer scientists thought were hard or not hard problems, even though they could not much prove anything.

I really did not care if it turned out that P=NP or not and most physicists I talk to don't much care either. If it indeed turns out that someday P=NP it would just mean that the computer scientists were not trying hard enough to find a proof and in any case it had little to do with physics.

However I'm ready to not quite eat but perhaps just reheat my 'umble pie. The bit in Scott's book that struck a nerve was his discussion of the feeling that if P=NP, even on a quantum computer, then we would have 'God-like' powers. Again that sounds just like hype but here's the physics.

From the 1998 paper by Daniel Abrams and Seth Lloyd we know that if quantum mechanics was nonlinear, with even a small non-linearity of the Weinberg type, then we could build super-duper quantum computers to solve not only NP-complete problems, but also the supposed even harder class of #P problems, all in polynomial time on the nonlinear quantum mechanics machine.

However the Weinberg model for nonlinear quantum mechanics would also permit superluminal communication and the violation of the second law of thermodynamics. The superluminal communication is the worst as this would lead to a violation of Einstein causality, something that never happens in ordinary linear quantum theory. It is well known that with superluminal communication, allowing you to send messages backwards in time, you can get a computational speedup by just letting your classical computer run for an exponential amount of time and then have it transmit the answer backwards in time to you so that the overall effect is a polynomial-time computation.

So if Nature gave us Weinberg nonlinear quantum mechanics, instead of ordinary linear quantum mechanics, we could use that to compute NP-complete and #P problems in polynomial time, violate causality, and for extra credit violate the second law of thermodynamics. Physicists should be very concerned if we could do the latter two things and hence, I posit along with Aaronson, that physicists should be very concerned if we could do the first two things as well.

Beware! There is no proof that the ability to solve NP-complete or #P problems implies the violation of causality or the second law. But it is suggestive that there is one resource, nonlinear quantum mechanics of the Weinberg type, that allows you do all of these — that is it gives us 'God-like' powers.

I suggest then that physicists who shudder at the thought of a theory that implies a violation of Einstein causality and the second law should also shudder at the thought that someday we will find a polynomial route to solving NP-complete problems using the laws of physics as we currently understand them.