Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!

Posted on March 10, 2021 by Gil Kalai

Feng Pan and Pan Zhang uploaded a new paper on the arXive  “Simulating the Sycamore supremacy circuits.” with an amazing announcement.

Abstract: We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in computing a large number of correlated bitstring amplitudes and probabilities than existing methods. As an application, we study the sampling problem of Google’s Sycamore circuits, which are believed to be beyond the reach of classical supercomputers and have been used to demonstrate quantum supremacy. Using our method, employing a small computational cluster containing 60 graphical processing units (GPUs), we have generated one million correlated bitstrings with some entries fixed, from the Sycamore circuit with 53 qubits and 20 cycles, with linear cross-entropy benchmark (XEB) fidelity equals 0.739, which is much higher than those in Google’s quantum supremacy experiments.

Congratulations to Feng Pan and Pan Zhang for this remarkable breakthrough!

Of course, we can expect that in the weeks and months to come, the community will learn, carefully check, and digest this surprising result and will ponder about its meaning and interpretation. Stay tuned!

Here is a technical matter I am puzzled about: the paper claims the ability to compute precisely the amplitudes for a large number of bitstrings. (Apparently computing the amplitudes is even more difficult computational task than sampling.) But then, it is not clear to me where the upper bound of 0.739 comes from? If you have the precise amplitudes it seems that you can sample with close to perfect fidelity. (And, if you wish, you can get a F_XEB score larger than 1.)

Update: This is explained just before the discussion part of the paper. The crucial thing is that the probabilities for the 2^21 strings are distributed close to Porter-Thomas (exponentials). If you take samples for them indeed you can get samples with F_XEB between -1 and 15. Picking the highest 10^6  strings from 2^21 get you 0.739 (so this value has no special meaning.) Probably by using Metropolis sampling you can get (smaller, unless you enlarge 2^21 to 2^25, say) samples with F_XEB close to 1 and size-biased distribution (the distribution of probabilities of sampled strings) that fits the theoretical size biased distribution.  And you can also use metropolis sampling to get a sample of size 10^6 with the correct distribution of probabilities for somewhat smaller fidelity. 

The paper mentions several earlier papers in this direction, including an earlier result by Johnnie Gray and Stefanos Kourtis in the paper Hyper-optimized tensor network contraction and another earlier result in the paper Classical Simulation of Quantum Supremacy Circuits by a group of researchers Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen, from Alibaba co.  Congratulations to them as well.

I am thankful to colleagues who told me about this paper.

Some links:

Scientists Say They Used Classical Approach to outperform Google’s Sycamore QC (“The Quantum” Written by Matt Swayne with interesting quotes from the paper. )

Another axe swung at the Sycamore (Shtetl-Optimized; with interesting preliminary thoughts by Scott;  )

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , | Leave a comment

To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky’s conjectures

Posted on February 25, 2021 by Gil Kalai

There is a very famous conjecture of Irving Kaplansky that asserts that the group ring of a torsion free group does not have zero-divisors. Given a group G and a ring R, the group ring R[G] consists of formal (finite) linear combinations of group elements with coefficients in the ring. You can easily define additions in R[G], and can extend the group multiplication to R[G], which makes the group ring a ring. (And if R is a field, R[G] is an algebra, called group-algebra.)

Kaplansky’s zero divisor conjecture asserts that if G is torsion-free and K is a field then K[G] has no zero-divisors.

Irving Kaplansky

This conjecture was made in the 1950s or even 1940s. It is known to hold for many classes of groups. If G has torsion, namely an element g of order n, then (1-g)(1+g+g^2+\cdots +g^{n-1})=0.

Kaplansky made also in the 50s two other conjectures.

Kaplansky’s unit conjecture asserts that if G is torsion-free and K is a field the only units in the face ring of K[G] are of the form kg where k in a non-zero element in the field and g is an element of the group,

Kaplansky’s idempotents conjecture asserts that if G is torsion-free and K is a field then the only idempotents in K[G] are 0 and 1.

If G has torsion, namely an element g of order n, then $(1-g)(1+g+g^2+\cdots +g^{n-1})=0$. It is not very hard to see that the unit conjecture implies the zero-divisor conjecture which in turn implies the idempotent conjecture.

A few days ago, Giles Gardam gave a great, very pleasant, lecture about Kaplansky’s conjectures.

After introducing the conjectures themselves, Giles explained that these conjectures are related to several other conjectures like the Baum-Connes conjecture or Farrell-Jones and a conjecture of Atiyah. So this implies, for example that the zero divisors conjecture holds for residually torsion free solvable group. Now, as an aside let me say that it is good to know what does it mean for a property X to say that a groups G is “residually X”. I tried to explain it in this post. But I myself forgot, so together with you, devoted readers, I will go to the old post to be reminded. Let’s get reminded also of the easier concept of “virtually X”.

The assertion of Kaplansky’s unit conjecture holds for torsion-free unique-product groups. The unique product property says the following if A and B are finite subsets of the group there is an element c that can be written in a unique way as c=ab where a belongs to A and b belongs to B.

This concept was defined in 1964 by Rudin and Schneider and for two decades it was not even known that there are groups without the unique-product property. The first example of a group without this property was discovered by Rips and Segev.

Let me make a small diversion here. From time to time I talk about results by people I personally know and usually I don’t mention that in the posts. For example, in the post about Yuansi Chen’s work on Bourgain’s slicing conjecture and the KLS conjecture I personally knew about 70% of the heroes in that story (update: 19:25). In fact, both Bo’az Klartag and me are living in the very same apartment building in Tel Aviv.  (Officially, I am in number 9 and Bo’az is in number 7 but topologically it is the same building.)

But here I must mention that Yoav Segev is my class mate in undergraduate years and is now a Professor at Ben Gurion University in Beer-Shava. He is responsible to one of the final steps in the classification program, to knocking down several other conjectures in algebra, and also to works on fixed-point free actions of non solvable groups on simplicial complexes. This last topic is close to my own interests and from time to time we chat about it. And of course, Ilya Rips is extraordinary mathematician and we are emeritus colleagues at HUJI – see this post about Ripsfest.

So let me go back to Giles’s lecture. Giles discussed two classes of examples of groups without the unique product property. And at minute 49 of the (50-minute) lecture Giles said: “I am nearly at the end of the talk and its time for me to tell you what’s new, um, what’s my contribution to this story, um, so I am really happy to be able to announce today for the first time, that, in fact, the unit conjecture is false.”

Theorem (Giles Gardam, 2021): Let P be the torsion-free virtually abelian group

<a,b | (a^2)^b=a^{-2}, (b^2)^a=b^{-2}>

And lt K be the field with two elements. Then there is a nontrivial unit \alpha in K[G], so that both \alpha and \alpha^{-1} have support of size 21.

(This group does satisfy the zero-divisor conjecture.)

Here is the paper: Giles Gardam, A counterexample to the unit conjecture for group rings. Congratulations, Giles!

Posted in Algebra | Tagged , | 7 Comments

Nostalgia corner: John Riordan’s referee report of my first paper

Posted on February 19, 2021 by Gil Kalai

In 1971/1972 academic year, I was an undergraduate student at the Hebrew University of Jerusalem and toward the end of the year I wrote a paper about Abel’s sums. I sent it to John Riordan the author of the books  “Combinatorial Identities” and “Combinatorial Analysis”.

I received this letter shortly after my 17th birthday, and I was surely very happy to read the sentence “I think you have had a splendid idea”.  Here is part of Riordan’s remarks. The full report is here.

It took me some time to revise the paper and get it printed. And here is the report for the second version.

And here is part of Riordan’s second round of remarks. The full report is here.

I was certainly happy to read the following sentence: “I would remark that the result for  p = -1  is new and perhaps the simplest derivation of Abel’s result.”

In 1978 I actually visited John Riordan in his office at Rockefeller University, NYC. I remember him as very cheerful and he told me that when his first book appeared he was working at Bell Labs and his managers wanted to talk to him. He was a bit worried that they would not approve of him spending time and effort to write a book in pure mathematics. But actually, they gave him a salary raise!

(If you have a picture of John Riordan, please send me.)

In 1979 the paper appeared.

Posted in Combinatorics, personal | Tagged , , , | 7 Comments

At the Movies III: Picture a Scientist

Posted on February 18, 2021 by Gil Kalai

A few days ago I saw the great, emotionally steering, movie Picture a Scientist. I strongly recommend it. Here is the link to the  hompage trailer, and IMBd page.

SYNOPSIS

PICTURE A SCIENTIST chronicles the groundswell of researchers who are writing a new chapter for women scientists. Biologist Nancy Hopkins, chemist Raychelle Burks, and geologist Jane Willenbring lead viewers on a journey deep into their own experiences in the sciences, ranging from brutal harassment to years of subtle slights. Along the way, from cramped laboratories to spectacular field stations, we encounter scientific luminaries – including social scientists, neuroscientists, and psychologists – who provide new perspectives on how to make science itself more diverse, equitable, and open to all.

Raychelle Burks, Nancy Hopkins, and Jane Willenbring 

Posted in Movies, Women in science | Tagged , , , , | 2 Comments

At the Movies II: Kobi Mizrahi’s short movie White Eye makes it to the Oscar’s short list.

Posted on February 17, 2021 by Gil Kalai

My nephew Kobi Mizrahi is a well known movie producer and it was just announced that his short film “White eye” (עין לבנה) made it to the short list of ten Oscar candidates in the live-action short category. The director is Tomer Shushan.

Congratulations, Kobi!

I saw the movie and I highly recommend it! Let me use use the opportunity to recommend a full-length action movie the Dive  that Kobi produced two years ago.

Kobi Mizrahi

Our previous post: And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev.

Posted in Movies, People, personal | Tagged , | Leave a comment

And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev

Posted on February 16, 2021 by Gil Kalai

My mother Carmela Kalai often said that if there was something she is thankful for it was that she was born in the era of movies. Indeed, she loved movies from a very early age throughout her life.  So, I was especially excited to hear that my long-time friend Meir Feder and his colleagues at the Amimon company won the 2021 Academy Award for scientific contributions to the movie industry. It is very nice to see deep ideas from information theory, computer science and engineering come to play in the movies. Congratulations!

From right to left: Ron Yogev, Meir Feder, Zvi Reznic and Guy Dorman

Here is Meir’s thank-you speech.

Posted in Computer Science and Optimization, Information theory, Movies | Tagged , , , | 1 Comment

Thomas Vidick: What it is that we do

Posted on February 15, 2021 by Gil Kalai

A wonderful post by Thomas Vidick to cheer you up in difficult times with a lot of food for thought and for discussion. What is it that we (mathematicians) do?

It goes back to ancient Greece and also mention the legendary historian, poet, and philosopher Reviel Nets (whose two wonderful talks in Jerusalem we mentioned here and here).

MyCQstate

This post is a follow-up on some somewhat off-hand comments that I made earlier regarding the notion of truth in a “proof-based” discipline such as pure mathematics or theoretical computer science. Since the former is easier to circumscribe and also has a larger literature available on it, for the purposes of the post I will discuss my emerging take on truth in mathematics; what I say applies to TCS as well. (I wasn’t able to find satisfactory writings on the practice of computer science, even more broadly interpreted than just “theory”; any pointers on this are very welcome.) I obviously don’t claim any originality here; I suspect that to some the points I make might be interesting while to others they could feel passé–in the latter case, please help me make progress in the comments!

A circle is a plane figure contained by one line such that all the straight…

View original post 2,277 more words

Posted in What is Mathematics | Tagged | 1 Comment

To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k)

Posted on February 8, 2021 by Gil Kalai

What will be the next polymath project? click here for our post about it. 

New lower bounds for van der Waerden numbers by Ben Green

Abstract: We show that there is a red-blue colouring of [N] with no blue 3-term arithmetic progression and no red arithmetic progression of length e^{C(\log N)^{3/4}(\log \log N)^{1/4}}. Consequently, the two-colour van der Waerden number w(3,k) is bounded below by k^{b(k)}, where b(k)=c(\frac{\log k}{\log \log k})^{1/3}. Previously it had been speculated, supported by data, that w(3,k)=O(k^2).

The left side of the picture shows the world record holders for W(3,k). On the left Ben Green (LB) and in the centre Tomasz Schoen (UB). The pictures on the right shows protective mittens for people who make bold mathematical conjectures (see Igor Pak’s post) 

The two-colour van der Waerden number w(m,k) is the smallest  N such that however [N] = {1, . . . , N} is coloured blue and red, there is either a blue m-term arithmetic progression or a red k-term arithmetic progression. The celebrated theorem of van der Waerden implies that w(m, k) is finite.

The van der Waerden number w(m,k) is analogous to the Ramsey number R(m,k). Finding the behaviors of R(m,k) is an important problem in Ramsey theory and much attention is given to R(k,k) and of R(3,k). Similarly, understanding the values of W(m,k), and especially of W(k,k) and W(3,k)  are also  central problems in Ramsey theory. A big difference between van der Waerden number and Ramsey numbers is that there are density theorems for the existence of k-terms arithmetic progressions. (Roth’s theorem for k=3 and Szemeredi’s theorem for general k.) There are several important methods to derive those density theorems (including Fourier methods, ergodic methods, and Szemeredi-type regularity) and these methods, as far as I know, do not apply for ordinary Ramsey numbers. (But correct me if I am wrong here, and if I am right and you have some insights as to why ergodic methods or Fourier methods do not apply to “ordinary” Ramsey, please share.)

Green’s paper  studies the values of w(3,k). The best known upper bound is of Tomasz Schoen, w(3, k)<e^{k^{1-c}} for some constant c > 0. The best known lower bound until the new paper, was by Li and Shu: w(3, k) \gg (k/ log k)^2. (This result, as the earlier bound by Robertson, used a probabilistic argument and relied on Lovasz’s local lemma.)

Several people conjectured, also based on empirical data, that w(3,k) = O(k^2) but now Green proved a super-polynomial lower bound! This is amazing! Congratulations, Ben!

It is largely conjectured that the Behrend-type bounds give the correct quantitative behaviour for Roth’s theorem (and Szemeredi theorem). In rough terms what we see from Green’s example is that this might be true also for van der Waerden numbers.

The proof is rather involved and long, so, naturally, there is  little I can say about it, which only slightly exceeds the little I actually know about it. The overview and other fragments of the paper I looked at are very illuminating. Here are a few things that caught my eyes.

1) A word about Tomasz Schoen’s upper bound and important paper: A subexponential upper bound for van der Waerden numbers W(3,k).  Among other things Schoen’s proof relies on a lemma developed by Schoen for improved Roth bound. This relies on a structure theory of Bateman and Katz.  The paper gives a nice description of the state of the art regarding the diagonal values w(k,k). (Schoen’s upper bound on w(3,k) follows also from the more recent bound for Roth’s theorem by Bloom and Sisask.)

2) Among the people that speculated that w(3,k) behaves like k^2 is Ben Green himself. This is recorded in reference [9] of the paper. However, Green’s first reaction to this possibility was that it must be false. But he realized that some ideas for showing that it is false are themselves false.

3) Reference [9] in the paper is: B. J. Green, 100 open problems, manuscript, available on request. If you are curious about the list, request it!

4) New lower bounds in Ramsey theory are nor frequent. Thirteen years ago I described Elkin’s improvement to Behrend’s bound and a few days ago I mentioned Linial and Shraibman’s new lower bounds for the corner problem.  Green’s study started by looking at complements of 3-AP free sets. An example by Green and Julia Wolf (that followed Elkin’s result) turned out to be important for reaching some parts of Green’s strategy.

5) In some sense, something about the k^2 prediction is not entirely lost. The construction gives a sort of a multi-scale behaviour where in the rth scale the example’s cardinality is k^r.  (So all the empirical data comes from the r=2 regime.) Ben Green boldly suggests that the true values of w(3,k) might exhibit such multi-scale behaviour. He conjectures that the true value of w(3, k) is quasi-polynomial, namely it lies somewhere in between the bound given by his construction and  something like k^{c\log k} (which is Behrend-bound behaviour on the nose) .

6) Until Ben’s list of 100 problems becomes available to you, you may find interest in Francis Su’s 100 questions about mathematics for discussion and reflection.

7) In connection with Linial and Shraibman’s new lower bounds for the corner problem, let me mention that the best upper bound is by I.D. Shkredov. The paper is:  On a two-dimensional analog of Szemeredi’s Theorem in Abelian groups, Izvestiya of Russian Academy of Sciences, 73 (2009), 455–505.

Posted in Combinatorics, Number theory | Tagged , | 2 Comments

To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols

Posted on February 3, 2021 by Gil Kalai

What will be the next polymath project? click here for our previous post. 

Number on the forehead, communication complexity, and additive combinatorics

Larger Corner-Free Sets from Better NOF Exactly-N Protocols, by Nati Linial and Adi Shraibman

Abstract: A subset of the integer planar grid [N]×[N] is called corner-free if it contains no triple of the form (x,y),(x+δ,y),(x,y+δ). It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrend’s large subset of [N] with no 3-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity.

In the 3-players exactly-N problem the players need to decide whether x+y+z=N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.

This is remarkable for various reasons. On the additive combinatorics side, improved constructions are rare. For example, we reported here in 2008 Elkin’s (small) improvements of Behrend’s bound. For the corner-free problem the paper of Nati and Adi goes beyond the Behrend’s (and Elkin’s) constructions. On the communication complexity side this is significant progress on a classical 1983 problem of Chandra, Furst and Lipton. The connection that goes from improved result on communication complexity to additive combinatorics is exciting — certainly a new frontier for Nati and Adi. On the blogging side, I cannot compete with the beautifully written introduction. Click here to read the paper.

Remark 1: The number of the forehead problem is  related to Levine’s hat problem that we discussed in this post.

Remark 2: Ryan Alweiss just told me about Ben Green’s new paper New lower bounds for van der Waerden numbers. It gives a construction of a red blue colouring of {1,2,…,N} with no 3 term blue or a k-term red arithmetic progression, where N is super-polynomial! Stay tune for a fuller report.

Posted in Combinatorics, Computer Science and Optimization | Tagged , | 3 Comments

Possible future Polymath projects (2009, 2021)

Posted on January 29, 2021 by Gil Kalai

What will be our next polymath project?

A polymath project (Wikipedia) is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution. The project began in January 2009 on Timothy Gowers’s blog when he posted a problem and asked his readers to post partial ideas and partial progress toward a solution. This experiment resulted in a new answer to a difficult problem, and since then the Polymath Project has grown to describe a particular process of using an online collaboration to solve any math problem.

After the success of Polymath1 and the launching of Polymath3 and Polymath4, Tim Gowers wrote a blog post “Possible future Polymath projects” for planning the next polymath project on his blog. The post mentioned 9 possible projects. (Three of them later turned  to polymath projects, and one turned into a project of a different nature.) Following the post and separate posts describing some of the proposed projects, a few polls were taken and a problem – the Erdős discrepancy problem, was selected for the next project polymath5. 

One of our next posts will have the same title and similar purpose as Tim’s 2009 post.  I will describe several possibilities for my next polymath project. (A quick rather vague and tentative preview can be found at the end of this post.) Today we go back to Tim’s 2009 post and the problems posed there.

Comments on the 2009 proposed projects, the new proposed projects, other proposed projects, and on the polymath endeavor, are most welcome. (At the end of the post I also mention a few “meta” questions.)

Let me also mention The PolyTCS Project aimed for proposing projects in theoretical computer science. There are so far three very interesting proposals there, and the first proposal is the Friedgut-Kalai Entropy/Influence conjecture. For various proposals, see also the polymath blog administered by Tim Gowers, Michael Nielsen, Terry Tao, and me, and this MO question.

The proposed projects in Gowers’s 2009 post and updates regarding these projects.

1. Littlewood’s conjecture and related problems.

The conjecture states that if \alpha and \beta are any two real numbers, and \epsilon>0, then there exists a positive integer n such that ||\alpha n||\,||\beta n||\leq\epsilon/n. Famously, Einsiedler, Katok and Lindenstrauss proved that the Hausdorff dimension of the set of counterexamples to the conjecture is zero. Gowers had ideas for an elementary approach, and his ideas  are described in this later post. This project was not launched and I am also not aware of progress related to the problem (but I am not an expert). 

2. A DHJ-related project.

DHJ stands for “density Hales Jewett” which was the topic of polymath1. The second proposed project was to build on the success of polymath1 and at a later post the following problem was proposed.

Conjecture:  For every \delta>0 and every positive integer k there exists n such that if A is any subset of [k]^{[n]^2} of density at least \delta, then A contains a combinatorial line such that the wildcard set is of the form X\times X for some subset X\subset[n].

As far as I know, this conjecture is still open.

Both questions “what kind of forbidden patters in [k]^n force exponentially small density” and “what kind of forbidden patters in [k]^n force vanishing density” are fascinating. Let me recommend again the Frankl-Rodl theorem and its proof as a role model.

3. Four Erdős-style combinatorial problems.

3a. Erdős’s discrepancy problem

This was the problem that was eventually chosen for polymath5. This was a very nice story. The problem was presented in this blog post and selected as polymath5 after some polls among readers. The polymath project was the longest in polymath history. There were six preliminary discussion posts with more than 600 comments followed by 21 official posts EDP1-EDP21. There was some short revival of the project (EDP22-EDP27) in 2012 where I contributed three posts. Famously, in 2015 Terry Tao solved the problem. The paper appeared in the journal Discrete Analysis. Tao’s solution relies on some insights from the polymath project including a crucial reduction that Terry himself contributed. It also crucially relied on a (then) new theory by Kaisa Matomaki and Maksym Radziwill. The solution was triggered  by a blog comment by Uwe Stroinski who pointed to a possible connection to EDP, and a subsequent one by Kodlu who seconded Uwe’s suggestion. This is reported in EDP28, and here on my blog we celebrated the solution in this post.  

3b. The Erdős-Hajnal conjecture.

Let k be a positive integer and let H be a graph. Erdös and Hajnal conjectured that there is a constant C=C(H) such that if G is any graph with at least k^C vertices that does not contain any induced copy of H, then either G or G^c contain a clique of size k.

Tim asserted that the simplest open case is where H is a pentagon. This special case was recently settled by Maria Chudnovsky, Alex Scott, Paul Seymour and Sophie Spirkl. They rely on recent results by Janos Pach and Istvan Tomon. See this videotaped lecture by Paul Seymour at IBS Discrete Mathematics Group, South Korea.

3c. Frankl’s union-closed conjecture.

Continue reading →

Posted in Combinatorics, Mathematics over the Internet, Open discussion | Tagged , , | 22 Comments