Tag Archives: Greg Kuperberg

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

Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

Wolfgang Haken found an algorithm to tell if a knot is trivial, and, more generally with Hemion, if two knots are equivalent.

Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is in NP. This is a major result!

An outstanding problem for many years was to determine if telling that a knot is unknotted is in coNP or equivalently if telling that a knot is nontrivial is in NP as well. A few month ago Greg Kuperberg proved it under GRH (the generalized Riemann hypothesis)! Amazing! Kuperberg ingenious short proof is based on a recent important knot-theoretic result by Kronheimer and Mrowka combined with computational complexity result by Koiran (discussed in the section “from Primes to Complexity”over this GLL’s post).

There were several results in knot theory in recent years that gradually showed that several invariants (related, generally speaking, to Jones polynomials but more detailed, e.g., Khovanov homology,) are enough to tell if a knot is trivial. I am not so sure about how this fascinating story goes.

An earlier, different,  approach (via the Thurston norm) from 2002 to showing that verifying that a knot is trivial is in coNP was by Ian Agol.   

It is very interesting if the dependence on GRH can be removed. Of course, a major problem is if telling if a knot is trivial is in P. Showing that the problem is in BQP will also be great.

Eralier,  in a SODA 2005 article, Hara, Tani, and Yamamoto proved  that unknotting is in AM \cap coAM. As mentioned in the comments the argument was incomplete. (One thing I learned from Greg’s preprint is that there is a preprint by Chad Musick who is describing a polynomial-time algorithm for testing if a knot is trivial. His work is based on a knot-invariant called “the crumble,” and its status is unclear at present.)

I am not sure what is the complexity for telling if two knots are equivalent. Haken and Hemion proved that it is decidable. Telling if a knot is trivial feels a little like PRIMALITY while telling two knots apart feels a little like FACTORING. Here is a survey article by Joel Hass on the computability and complexity of knots and 3-manifolds equivalence. It looks that the algorithmic theory of knots is related to both coltures of 3-dim topology, the one related to structural results, combinatorial group theory, geometrization etc, and the other related to invariants and physics, and this is nice. See also the post over GLL entitled “What makes a knot knotty.”

And here is Greg’s description of his ingenious proof. (It is not as easy as the description suggests.) Reading Greg’s short page paper is  recommended.

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.


The Sylvester-Gallai Theorem:  Let X be a finite set of n points in an eulidean space such that for every two distinct points x,y \in X the line through x and y contains a third point z \in X. Then all points in X are contained in a line. 

I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a  The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)

My MO question

Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this:

Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection  is “complicated”. Then n cannot be too large.

I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:

If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13

The result by Barak, Dvir, Wigderson and Yehudayoff

Theorem:  Let X be a finite set of n points in an Euclidean space such that for every point x \in X the number of y, y\in X,y \ne x such that the line through x and y contains another point of X is at least \delta (n-1). Then

\dim (Aff(X))\le 13/\delta^2

Some remarks:

1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1’s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix.

2)  The context – locally correctable codes:  A q-query locally correctable (q,\delta)-code over a field F is a subspace of F^n so that, given any element \tilde y that disagrees with some y \in C in at most \delta n positions and an index i, 1 \le i \le n we can recover y_i with probability 3/4 by reading at most q coordinates of \tilde y.  The theorem stated above imply that, for two queries,  over the real numbers (and also over the complex numbers), such codes do not exist when n is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences.

3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to \dim (Aff(X))=O(1/\delta )? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.

Combinatorics, Mathematics, Academics, Polemics, …

1. About:

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.  








 Gosset polytope– a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope. Continue reading