Quantum computing: achievable reality or unrealistic dream

QC-michel-view QC-gilview

Michel Dyakonov’s View on QC                                     My view (based on Michel’s drawing*)



Alexander Vlasov’s view (based on Michel and Konstantin’s drawing)

It has been a while since I devoted a post to quantum computation. Meanwhile, we had a cozy, almost private, easy-going, and very interesting discussion thread on my previous, March 2014 post (that featured my Simons Institute videotaped lectures (I,II).)

What can we learn from a failure of quantum computers?

Last week we had a workshop on “Quantum computing: achievable reality or unrealistic dream.” This was a joint venture of the  American Physics Society and the Racah Institute of Physics here at HUJI, organized by Professor Miron Ya. Amusia, and it featured me and Nadav Katz as the main speakers. Here are the slides of my lecture: What can we learn from a failure of quantum computers.


Noise Sensitivity and BosonSampling

Earlier, I gave a lecture in our CS colloquium about a recent work with Guy Kindler on noise sensitivity of BosonSampling. We show that for a constant level of noise, noisy BosonSampling can be approximated by bounded-depth computation, and that the correlation between the noisy outcome and the noiseless outcome tends to zero if the noise level is ω(1/n) where n is the number of bosons.  Here is the paper Gaussian noise sensitivity and BosonSampling, the videotaped lecture  Complexity and sensitivity of noisy BosonSampling, and the slides of the lecture.

Contagious error sources would need time travel to prevent quantum computation

On the positive side, Greg Kuperberg and I wrote a paper  Contagious error sources would need time travel to prevent quantum computation  showing that for a large class of correlated noise, (teleportation-based) quantum fault-tolerance works! Greg and I have had a decade-long email discussion (over 2000 emails) regarding quantum computers, and this work grew from our 2009 discussion (about my “smoothed Lindblad evolution” model), and heavily relies on  ideas of Manny Knill.

Nadav Katz: Quantum information science – the state of the art

Some years ago, two brilliant experimentalists, Hagai Eisenberg and Nadav Katz,  joined  the already strong, mainly theoretical, quantum information group here at HUJI.  Nadav Katz gave the second lecture in the workshop, and here are the slides of Nadav’s  lecture: Quantum information science – the state of the art.


Experimental progress toward stable encoded qubits

Also very much on the positive side, Nadav mentioned a remarkable recent progress by the Martini’s group showing certain encoded states based on 9 physical qubits which are order-of-magnitude (factor 8.4, to be precise,) more stable than the “raw” qubits used for creating them !!

Here is a link to the paper:  State preservation by repetitive error detection in a superconducting quantum circuit, by J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis.

Update:  Further comments on a Shtetl-optimized post (especially a comment by Graeme Smith,) help to place the new achievement of the Martinis group within the seven smilestones toward quantum computers from a 2012 Science paper by Schoelkopf and Devoret, originated by David DiVincenzo’s 2000 paper “The physical implementation of quantum computation“. (You can watch these milestone here also .)

The new achievement of having a very robust realization of certain encoded states can be seen as achieving the 3.5 milestone.   The difference between the 3.5th milestone and the 4th milestone plays a central role in the seventh post of my 2012-debate with Aram Harrow in connection with a conjecture I made in the first post (“Conjecture 1″). Aram made the point that classical error-correction can lead to very stable encoded qubits in certain states (which is essentially the 3.5 milestone). I gave a formal description of the conjecture, which essentially asserts that the 4th milestone, namely insisting that encoded qubits allows arbitrary superpositions, cannot be reached.  As I said many times (see, for example, the discussion in my 2012 Simons Institute videotaped lecture 2), a convincing demonstration of the 4th milestone, namely  implementation of quantum error-correction with encoded qubits which are substantially more stable than the raw qubits (and allow arbitrary superposition for the encoded qubit) will disprove my conjectures. Such stable encoded qubits are  expected from implementations of distance-5 surface code. So we are 0.5 milestones away :)

I will be impressed to see even a realization of distance-3 (or distance-5) surface code that will give good quality encoded qubits, even if the encoded qubits will have a quality which is somewhat worse than that of the raw qubits used for the encoding. These experiments, including those that were already carried out, also give various other opportunities to test my conjectures.

Peter Shor’s challenge #1 and my predictions from the failure of quantum computation

My lecture on predictions from the failure of QC is based on two lengthy recent comments (first, second) regarding predictions from the failure of quantum computers. On April 2014, Peter Shor challenged me with the following: Continue reading

Why Quantum Computers Cannot Work: The Movie!

Here are links to a videotaped lecture in two parts entitled “why quantum computers cannot work” recorded at the Simons Institute for the Theory of Computing on December 2013 and two additional videos: a short talk on topological quantum computers and a twelve minute overview.  Here are the links: OverviewPart IPart IITopological QC.  (Update, Nov 14: BosonSampling.)

Why Quantum Computers Cannot Work:

Overview and Vision.

Why Quantum Computers Cannot Work I:

From the “Trivial Flow” to Smoothed Lindblad Evolutions

Why Quantum Computers Cannot Work II:

Debate, Reasons to Disbelieve, and Experimentation

Why Topological Quantum Computers Cannot Work

The Geometry of Spacetime is Enabled by the Failure of Quantum Fault-Tolerance


Left: Nick Read; Right The front page of Nick’s 1990 famous paper with Greg Moore on nonabelions, and below his email to me from March 2005 on topological quantum computation. (click for full view.)


Left: the argument regarding topological QC demonstrated via Harris’ famous cartoon. While not strictly needed I expect the argument to extend from qubits to gates as well. Right: a recent discussion with Nick over Shtetl Optimized (click for full view). Update: We are actually not in an agreement as it seems from the above discussion (see the discussion below). 

Update (Nov’ 2014): A fifth video, this time in front of a live audience

Complexity and Sensitivity of Noisy BosonSampling

Update: A subsequent post by Steve Flammia, Quantum computers can work in principle over The Quantum Pontiff. (July:) See also this post: Quantum future” just beyond our grasp.

Added later (April 18): Let me quote from what Steve wrote about the videos: The surprising part is the superior production value relative to your typical videotaped lecture (at least for the first overview video). Producing the videos was an interesting and demanding experience and I was certainly happy to read Steve’s description of the production value.  (Of course, the main purpose of Steve’s post was to express his disagreement with the content of the videos. See either the post or Co-‘s comment below.) 

Also there are two earlier versions of my lecture (in 1-hour format) that were videotaped. The first was taken by Jesus De Loera in Davis. Very interesting shooting-angle and interesting comments by Greg Kuperberg, Bruno Nachtergaele and other participants.  The second was taken in Seattle in a UW-PIMS colloquium lecture. Again interesting questions by several participants including James Lee and John Sidles.

(July:) The Simons Institite (almost identical) versions of the movies are now linked from the web-page of my November 15 lecture at SI.

(Added nov 2014): The only difference from the HUJI version is that there are no opening slides and that for the closing slides I used two pictures of my department’s administrative staff.

es1  es2

The administrative crew of the Einstein Institite of Mathematics (click to enlarge)

I thought of it as a nice opportunity to thank our great administrative staff whose part is crucial  in the academic endeavor, and this is a good opportunity to thank the staff in my second academic home – Yale University, in the Simons Institute, in many other places.


Alistair Sinclair and the Simons Institure friendly and helpful staff (click for full size) 

Following Saharon Shelah: How to watch these videos

(Added Nov 2014)

Saharon Shelah explained in an introduction to one of his books, that instructions on “how to read this book” are actually instruction on “how to not read this book”. If you want to read the book you start on page 1 and read through to the last page.  Instructions for “how to read  this book” rather tell you how to jump to a place that interests you.

So, in a similar spirit, here are direct links to the different parts of the videos.

Continue reading

Pictures from Recent Quantum Months


A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

2013-08-01 10.09.28

With Robert Alicki in Gdynia near Gdansk


With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.


With Michel Dyakonov (Jerusalem, a few days ago)


With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)


Aram Harrow and me meeting a year ago at MIT.

2013-08-01 10.12.45

2013-08-01 10.12.52

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.


A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

GTprod2This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.

My Quantum Debate with Aram III

This is the third and last post giving a timeline and some non technical highlights from my debate with Aram Harrow.  

Where were we

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate towards the end of 2011, the first post in our debate describing my point of view was launched on January, 2012 and was followed by three posts by Aram. The discussion was intensive and interesting.  Here is a link to my 2011 paper that initiated the debate and to a recent post-debate presentation at MIT.

 Happy_Passover  Happy passover, readers!

Back to the debate: Conjecture C is shot down!


In addition to his three posts, Aram and Steve Flammia wrote a paper refuting one of my Conjectures (Conjecture C).  We decided to devote a post to this conjecture.

Quantum refutations and reproofs

Post 5, May 12, 2012. One of Gil Kalai’s conjectures refuted but refurbished

Niels Henrik Abel was the patron saint this time

The first version of the post started with this heartbreaking eulogy for Conjecture C. At the end most of it was cut away. But the part about Aram’s grandchildren was left in the post.

Eulogy for Conjecture C

(Gil; old version:) When Aram wrote to me, inn June 2011, and expressed willingness to publicly discuss my paper, my first reaction was to decline and propose having just private discussions. Even without knowing Aram’s superb track record in debates, I knew that I put my beloved conjectures on the line. Some of them, perhaps even all of them, will not last. Later, last December, I changed my mind and Aram and I started planning our debate. My conjectures and I were fully aware of the risks. And it was Conjecture C that did not make it.

A few words about Conjecture C

Conjecture C, while rooted in quantum computers skepticism, was a uniter and not a divider! It expressed our united aim to find a dividing line between the pre- and post- universal quantum computer eras.

Aram’s grandchildren and the world before quantum computers

When Aram’s grandchildren will ask him: “
Grandpa, how was the world before quantum computers?” he could have replied: “I hardly remember, but thanks to Gil we have some conjectures recording the old days, and then he will state to the grandchildren Conjectures 1-4 and the clear dividing line in terms of Conjecture C, and the grandchildren will burst in laughter about the old days of difficult entanglements.” Continue reading

Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a $50 prize! 

Let me also bring to your attention an interesting discussion (starting here) between Peter Shor and me regarding smoothed Lindblad evolutions.

(Cris Moore, the debate’s very first comment!) I am also a little confused by Gil’s motivation for his conjectures.  (My response:)  To the best of my memory, my main motivation for skeptically studying quantum fault-tolerance was that I thought that this is a direction worth pursuing and that I had a shot at it.

micheldevoretposter (1)

While listening with Ravi Kannan to this 2002 lecture by Michel Devoret at Yale, I wondered if there are enough scientists working on the “mirage” side.

Flashback: Mittag-Leffler 2005

I started systematically thinking about quantum fault-tolerance in February 2005. There were several things that triggered my interest to the question in the previous fall and I decided to spend some time learning and thinking about it in our winter break.  One of those triggers was something Dorit Aharonov told me a few months earlier: she said that once, when she was telling her students about quantum computers, she suddenly had a feeling that maybe it was all just nonsense. Another trigger came from a former student who told me about a Polish scientist (whose name he could not remember) who wrote an article about impossibility of quantum error-correction. I thought that the lack of a quantum analog of the repetition code, and the unique properties of the majority function  in terms of sensitivity to noise that I studied with Itai Benjamini and Oded Schramm earlier could be a good starting point for looking skeptically at quantum computers.  

In our 2005 winter break, I spent two weeks at Yale and then additional two weeks at the Mittag-Leffler institute near Stockholm.  At Yale, I only had little time to think about quantum computers. I had to finish a survey article with Muli Safra about threshold phenomena (To a volume that Cris Moore and Allon Perkus were among the editors).  One of the last days in Yale we went to dinner with two guests, Chris Skinner who gave the colloquium talk, and Andrei Okounkov who visited me and gave a talk about partition enumeration and mirror symmetry. At the dinner Andrew Casson asked, out of the blue, if we think that quantum computers can be built and it almost seemed as if that Andrew was reading my mind on what I plan to work on the weeks to come. My answer there was the same as my answer now, that I tend to find it implausible.

Mittag-Leffler Institute February 2005 with Xavier Viennot and Alain Lascoux

In Sweden I spent most of my time on quantum fault-tolerance. I was jet-lagged and being jet-lagged in the Mittag-Leffler institute already worked for me once, when finding my subexponential randomized variant of the simplex algorithm was a substitute for sleeping some night in fall 1991 . In 2005 it was not as bad, I just came to my office very early in the morning and started working. And very early in the morning somebody was already playing the piano.

And who was playing the piano at the institute in the cold Swedish mornings of February 2005? The first reader to guess correctly, and convince me in a comment that she or he knows the answer without revealing it to everybody else will get $50. Continue reading

My Quantum Debate with Aram II

This is the second of three posts giving few of the non-technical highlights of my debate with Aram Harrow. (part I)

After Aram Harrow and I got in touch in June 2011, and decided to have a blog debate about quantum fault-tolerance towards the end of 2011, the first post in our debate was launched on January 30, 2012.  The first post mainly presented my point of view and it led to lovely intensive discussions. It was time for Aram’s reply and some people started to lose their patience.

(rrtucky) Is Aram, the other “debater”, writing a dissertation in Greek, as a reply?

Flying machines of the 21st century

Post II, February 6, 2011. First of three responses by Aram Harrow

Dave Bacon was the patron saint for Aram’s first post.

(Aram) There are many reasons why quantum computers may never be built…  The one thing I am confident of is that we are unlikely to find any obstacle in principle to building a quantum computer.

(Aram) If you want to prove that 3-SAT requires exponential time, then you need an argument that somehow doesn’t apply to 2-SAT or XOR-SAT. If you want to prove that the permanent requires super-polynomial circuits, you need an argument that doesn’t apply to the determinant. And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn’t also refute fault-tolerant classical computing.

From the discussion

Why not yet? Boaz set a deadline


(Boaz Barak could [you] explain a bit about the reasons why people haven’t been able to build quantum computers with more than a handful of qubits yet? Continue reading

My Quantum Debate with Aram Harrow: Timeline, Non-technical Highlights, and Flashbacks I

How the debate came about


(Email from Aram Harrow, June 4,  2011) Dear Gil Kalai, I am a quantum computing researcher, and was wondering about a few points in your paper

(Aram’s email was detailed and thoughtful and at the end he proposed to continue the discussion privately or as part of a public discussion.)

(Gil to Aram) Thank you for your email and interest. Let me try to answer the points you raised. …   (I gave a detailed answer.) …  Right now, I don’t plan on initiating a public discussion. How useful such public discussions are (and how to make them useful) is also an interesting issue. Still they were useful for me, as two of my conjectures were raised first in a discussion on Dave Bacon’s blog and another one is partially motivated by a little discussion with Peter Shor on my blog. Continue reading

A Few Slides and a Few Comments From My MIT Lecture on Quantum Computers

I gathered a few of the comments made by participants of my lecture “Why quantum computers cannot work and how”, and a few of my answers. Here they are along with some of the lecture’s slides. Here is the link for the full presentation.

1) Getting started


Continue reading

Meeting with Aram Harrow, and my Lecture on Why Quantum Computers Cannot Work.

Last Friday, I gave a lecture at the quantum information seminar at MIT entitled “Why quantum computers cannot work and how.” It was a nice event with lovely participation during the talk, and a continued discussion after it. Many very interesting and useful remarks were made. Here are the slides. (The abstract can be found on this page.)

After having an almost a year-long debate with Aram Harrow, I finally met Aram in person, and we had nice time together during my visit.


Aram is so nice that had it been up to me I would certainly make quantum computers possible :) (But this is not up to us and all we can do is to try to explore if QC are possible or not.)

We talked about quite a few topics starting with various exotic models of noise that treat differently classic and quantum information, the relevance of locally correctable codes and their quantum counterparts, the sum of Squares/Lasserre hierarchy, unique games and hypercontractivity, my smoothed Lindblad evolutions , NMR and spin-echo, quantum annealing and stoquasicity, and works by Mossbüer, Rekha Thomas, and Monique Laurent were mentioned. 


I just returned yesterday night from Yale after a very fruitful visit.  Here is a picture of a snowcar decorated with car mirrors from the great blizzard.

winter12 224

Symplectic Geometry, Quantization, and Quantum Noise

Over the last two meetings of our HU quantum computation seminar we heard two talks about symplectic geometry and its relations to quantum mechanics and quantum noise.

Yael Karshon: Manifolds, symplectic manifolds, Newtonian mechanics, quantization, and the non squeezing theorem.


The first informal lecture by Yael Karshon gave an introduction to the notions of manifolds and symplectic manifolds. Yael described the connection with Newtonian physics, gave the example of symplectic structure on phase spaces coming from physics, and talked about dynamics and physical laws. She also gave other examples of symplectic manifolds. The 2-dimensional sphere S^2 is an important example, and also complex projective manifolds are symplectic.


Now, if symplectic geometry describes Newtonian mechanics how should we move to describe quantum mechanics?  Yael talked a little about quantization, described an impossibility theorem by Groenweld and Van Hove for certain general types of quantization, and mentioned a few ways around it. (More details at the end of this post.)

Non squeezing, symplectic camels and uncertainty.

Yael concluded with Gromov’s non-squeezing theorem. This theorem asserts that a ball of radius R cannot be “squeezed” by a symplectic map to a cylinder whose base is a circle of radius r,  for R > r. Yael mentioned that Gromov’s non squeezing theorem can be regarded as a classical manifestation of the uncertainty principle from quantum mechanics. (The Wikipedia article gives a nice description of the theorem,  mention the metaphor of  passing a symplectic camel through the eye of a needle, and notes the connection with the uncertainty principle.)

Leonid Polterovich: Geometry of Poisson Brackets and Quantum Unsharpness


A week later Leonid Polterovich gave a lecture entitled “Geometry of Poisson brackets and quantum unsharpness.” (Here are the slides Update: here is a video of a related lecture in QStart). Leonid reviewed the notion of symplectic manifolds, and gave a vivid explanation, based on areas of parallelograms, of how to think about a symplectic form.  Then he defined a displaceable set (a notion introduced by Helmut Hofer) in a symplectic manifold. This is a set X such that you can find a Hamiltonian diffeomorphism so that the image of X is disjoint from X. On S^2 small discs are displaceable but the equator is not!

Poisson brackets and the fiber theorem

Another crucial ingredient in the lecture was the notion of Poisson brackets which measure non-commutativity of Hamiltonian flow. Leonid continued to describe the Polterovich-Entov “non displaceable fiber theorem,” which asserts that if you have a function from a compact symplectic manifold to R^n described by n real functions whose pairwise Poisson brackets vanish, then there is a point whose pre-image is not displaceable.

Partition of unity, classical registration, and cell phones.

A partition of unity is a collection of non-negative valued real functions that sum up to 1. Suppose we are given an open cover \cal U of M by n sets and ask if there exists a partition of unity 1=f_1+f_2+\dots f_n such that f_i is supported on U_i and all Poisson brackets {f_i,f_j} vanish.  Next comes a theorem of Entov Polterovich and Zapolsky which asserts that this is not possible for covers with small sets, namely, if all sets are displaceable.  In fact, the theorem gives a quantitative relation between how small the sets in the cover are and a “measure of non-commutativity” for any partition of unity that respects this open cover.  Both the proof and the interpretations of this theorem have strong relations to quantum mechanics. This was the next topic in Leonid’s lecture. Leonid gave us a choice between ideas of QM playing a role in the proof and QM interpretation of the result and connections to quantum noise. In the end he talked about both topics.

Before going quantum, note that if the sets in the cover represent areas covered by an antenna for cell phones, you can ask how to register cellphones to antennas and regard the partition of unity as a probabilistic recipe.

Quantum mechanics,  The correspondence principle

Enters quantum mechanics. Here is a dictionary


The correspondence principle in physics states that the behavior of systems described by the theory of quantum mechanics reproduces classical physics in the limit.

POVMs and projector valued POVMs (von-Neumann observables).

Leonid talked about two notions of observables. The more general one is based on positive operator valued measures (briefly – POVM’s). The more special one is von-Neumann observables which are special cases of POVM’s (called projector valued POVM’s). POVM’s on the quantum side are analogs of partition of unity on the classic side, and they lead to a sort of “quantum registration.” (This is the familiar probabilistic aspect of quantum measurement.)

Quantum noise, non-commutativity and the unsharpness principle

Following Ozawa, and Busch-Heinonen-Lahti,  Leonid described a notion of “systematic quantum noise” and described a lower bound referred to as an “unsharpness principle” (Janssens 2006, Miyadera-Imai, 2008, and Polterovich 2012)  of the systematic noise in terms of non commutativity of the components of the POVM. Quantum noise, in this context, refers only to measurements, and systematic quantum noise describes the extent to which POVM’s are not von-Neumann observables.

An unsharpness principle for Berezin-Toeplitz quantization

Leonid described next the unsharpness principle based on the Berezin-Toeplitz quantization of a symplectic manifold. In this case we can talk about a POVM which corresponds to an open cover of the manifold by small sets. The conclusion is that these POVMs cannot be too close to  projector-valued POVM’s. The proof relies on the theorem of Entov-Polterovich-Zapolsky, the (difficult) correspondence principles for the quantization, and the linear-algebraic unsharpness principle for POVM’s. (I will give some more details below.)

Links to Leonid’s papers

Here are links to Leonid’s papers on quantum noise:  Quantum unsharpness and symplectic rigidity and Symplectic geometry of quantum noise.

Grete Hermann


Leonid briefly mentioned in his lecture the name of Grete Hermann. She was a German mathematician and philosopher, who is famous for her early work on the foundations of quantum mechanics and  early criticism of  the no-hidden-variable theorem by John von Neumann. Here is an English translation of her 1935 paper: The foundations of quantum mechanics in the philosophy of nature.  At age 26 Hermann finished her Ph. D. in mathematics with Emmy Noether. In the 30s she participated in an underground movement against the Nazis and lived in exile from 1936 until 1946.

Symplecticism and skepticism: possible relations with my work

As some of you may know I am quite interested in quantum noise and quantum fault-tolerance. My work is about properties and models of quantum noise which do not enable quantum fault tolerance believed to be crucial for building quantum computers. (Here are slides from a recent talk.) Ultimately, the hope is to use the theory of quantum error-correction and quantum fault-tolerance to describe principles of quantum noise which do not enable computational superior devices based on quantum physics.

Leonid and I were surprised to discover that we are both interested in quantum noise, and some of the statements we made look linguistically similar. For example, we both talk about a certain “hard-core” noisy kernel that cannot be avoided, and relate it to measures of non-commutativity. Leonid talks about “smearing” while I talk about “smoothing,” etc.

Yet, there are also clear differences. The unsharpness principle talks about noisy measurements and not about noisy approximations to unitary evolutions or to pure states which are what my work is mainly about.

Yet again, there may be ways to reconcile these differences. Ideal quantum computer evolutions induce non-unitary operations on parts of the quantum memory, even when it comes to two qubits. (And I am quite interested in the case of two qubits.) Beside that, quantum fault-tolerance is based fundamentally on non-unitary evolutions. Another interesting question is to see if my “smoothed Linblad evolutions” which are obtained from an arbitrary noisy evolution by adding a certain “smoothing” in time satisfy the unsharpness principle. And another interesting question is to see if physics-models of noisy quantum computers like the ones proposed by Aharonov-Kitaev-Preskill, and Preskill do obey the unsharpness principle.

It will be interesting to explore connections between Leonid’s work and mine. The notion of a quantum computer abstracts away the geometry and much of the physics and this is also the case for models of noisy quantum computers – both the standard ones and mine. The same is true for classical computers – classical computers can be used to describe classical physics but the laws of physics do not emerge from Turing machines or Boolean circuits. In the quantum and classical cases alike, more structure is needed.  So in order to check my conjectures on the behavior of noisy quantum systems we either need to study very specific proposed implementations of quantum computers or other specific noisy quantum systems, or to consider some middle ground that manifests the physics. Symplectic geometry can give a useful such middle ground.

Other relations with quantum information and quantum computation

Yet again once more, it looks like the connection of symplectic geometry, quantization and noise with the theory of quantum information and computation need not be restricted to my little skeptical corner. Useful ideas and examples can flow in both directions and involve mainstream quantum computation. The symplectic angle is certainly a good thing to be aware of and explore (and for me it will probably be a slow process).

A few more details on quantization in symplectic geometry as explained by Yael Karshon.

The challenge is to associate to every symplectic manifold  M a Hilbert space  H  and to every real valued smooth function on  M a self-adjoint operator  on  H such that

  1.  Linear combinations of functions go to linear combinations of operators,
  2.  Poisson brackets of functions go to  i  times  the commutator of operators,
  3.  the function  1  goes to the identity operator,  and
  4.  a “complete” family of functions passes to a “complete” family of operators.

The axioms (1)-(4) are attributed to Dirac. In (4), a family of functions is “complete” if it separates points almost everywhere and a family of operators is “complete” if it acts irreducibly.  (There may be variations in these definitions. Some people require more, e.g., that the powers of a function be mapped to the powers of the corresponding operator.)

“No go theorems” say that there does not exist a correspondence (that is nontrivial in some sense) that satisfies the properties (1)-(4). A “no go theorem” for  M = R^{2n} was given by Groenweld and Van Hove. Later “no go theorems” were also found for some compact symplectic manifolds. The 1996 review paper “Obstruction results in quantization theory”, by Gotay, Grundling, and Tuynman, should be relevant.

The first step in Geometric Quantization, which is called Prequantization, more or less achieves (1), (2), (3) but fails at (4). One compromise is to define the correspondence not for all smooth functions, but, rather, to restrict it to a sub-Poisson-algebra of the smooth functions. With this compromise, Geometric quantization can achieve (1)-(4). (But it depends on a choice of a so-called “polarization”.  Often different choices give isomorphic answers but this is only partially understood.)

Other methods of quantization involve asymptotic in h-bar. This means that the desired correspondence is demonstrated in the limit with respect to some parameter regarded as 1 over the Planck constant.  One of these is the Berezin-Toeplitz quantization that Leonid works with. Another is Deformation Quantization.

Berezin-Toeplitz quantization, smearing,  coherent noise, and quasi-states as further explained by Leonid Polterovich

Berezin-Toeplitz quantization

Berezin-Toeplitz quantization is a procedure to move from a symplectic manifold M to a sequence of Hilbert spaces which satisfy in the limit (when m tends to infinity) the quantization requirements. Leonid did not explain the construction in the lecture but later explained to Dorit Aharonov, Guy Kindler, and me how it works for the special case where    M is a Cartesian product of n copies of S^2. Very roughly you associate to each S^2 an m-dimensional Hilbert space and let m tend to infinity. The proofs of the correspondence principle: namely, the relation between commutators and Poisson brackets when m tends to infinity involve deep and difficult mathematics, with certain shortcuts when the symplectic manifolds have the extra structure of a “Kahler manifold.” While the main interest in the literature is for the case that m tends to infinity, for us, the case m=2 is quite interesting as it relates unitary evolution on an n-qubit quantum computer with Hamiltonian evolution on a Cartesian product of 2-spheres.

Quantum registration, smearing, unsmearing and coherent noise

POVMs can be used to describe a quantum registration rule analogous to the classical probabilistic rule based on partition of unity. Leonid described a statistical smearing operation on POMVs that increases noise. He asked to what extent we can denoise using unsmearing, and proved that, in certain circumstances, a certain amount of “inherent noise” persistent under unsmearing must remain.

Quantum and symplectic quasi-states

The lecture mentioned briefly another interesting aspect of the classical-quantum correspondence through symplectic geometry. Gleason proved in 1957 that for Hilbert spaces of dimension 3 or more every “quasi-state” is a state.  (Quasi states are defined based on linearity requirement just when the observables are commuting.) Non linear symplectic “quasi-states” do exist and this is related to deep developments in symplectic geometry. Leonid’s talk shows that quasi-states provided by symplectic geometry vanish on functions with dispaceable (“small”) supports. This readily rules out existence of Poisson commuting partitions of unity with displaceable supports.)


Happy new year, everybody!

A planned “Kazhdan’s seminar” spring 2014.

In 2003/2004 David Kazhdan and I ran a seminar on polytopes, toric varieties, and related combinatorics and algebra. (A lot has happened since and this spring Sam Payne and I will give together a course at Yale on similar topics this spring. There will be a separate post about it.) David and I felt that it is time to run another such event in 2014, perhaps establishing a tradition for a decennial joint seminar. So next spring, the plan is that David with me and Leonid and hopefully also Michael and Dorit will devote one of David’s Sunday seminars to computation, quantumness, symplectic geometry, and information.

A 1965 letter by Richard Palais

In a widely circulated but unpublished letter in 1965, Richard Palais explained the symplectic formulation of Hamiltonian mechanics. See this MO question.

Small and large in mathematics

Different notions of “small” and “large” and the tension between them are quite important in many areas of mathematics. Of course, sets of measure zero, sets of Baire-category one, sets of lower dimensions, subsets of smaller (infinite) cardinality, come to mind. In the symplectic context displaceable sets are small: note that the lower-dimensional equator is symplectically “large” while caps with positive area are “small.”

Let me remind myself that I should attempt to blog some time about deep recent results on “null-sets” in Eucledian spaces connected also to combinatorics. (Meanwhile, here are links to two papers by  Alberti, Csörnyei, and Preiss, Structure of null sets in the plane and applications, and Differentiability of Lipschitz functions, structure of null sets, and other problems.)

Trivia question

In theoretical computer science, what do the terms “Yaelism” and “Adamology” refer to?

Camels and elephants through the eye of a needle

The term “symplectic camel” refers to a quote of Jesus: “It is easier for a camel to pass through the eye of a needle than for a rich man to enter heaven.” (I learned about it when it was used in Aram Harrow’s reply in one part of our quantum debate, See also this post on The Quantum Pontiff ) A nice discussion of this phrase can be found here. The Jewish analog (from the Talmud) is about passing an elephant through the eye of a needle which is used to describe making convoluted arguments which have no basis in reality, attributed to the scholars of Pompeditha. Rabbi Shesheth answered Rabbi Amram “Maybe you are from the school at Pumbeditha, where they can make an elephant pass through the eye of a needle.”

Greg Kuperberg referred in this context to:  Rowan Atkinson – Conservative Conferencecamel

“It is easier for a rich man to pass through the eye of a needle than…for a camel to!”

An additional clarification on symplectic camels by Yael

Gromov Nonsqueezing and the Symplectic Camel Theorem are two different theorems.  (The Wikipedia article is unclear about this.) The Symplectic Camel theorem says this. Take  R^{2n}, say, with coordinates  x_i,y_i. Remove the hyperplane y_n=0  minus a ball of radius r   in this hyperplane.

Thus, we get two “rooms” separated by a “wall” but with a “hole” in the wall.  If  R<r  then a ball of radius  R  that lies entirely in the “left room”   y_n < 0  can be continuously translated through the “hole” into the “right room”  y_n > 0. If  R>r  we cannot move the ball to the “right room” continuously by translations nor rigid transformations but we can move it through volume preserving transformations (by first squishing it so it becomes long and narrow).  The theorem says that we cannot do this symplectically: if  R > r  then there is no path of symplectic embeddings of the ball of radius  R   that starts with an embedding into  y_n < 0  and ends with an embedding into  y_n > 0. (An interesting open question is whether there exists a “compact camel“: a compact symplectic manifold in which the space of symplectic embeddings of a ball of some fixed radius   R  into the manifold is disconnected.)