The Free Will problem – Ron Aharoni’s view

Posted on July 12, 2024 by Gil Kalai

This post was kindly contributed by Ron Aharoni. 

Following Ron’s 2009 (Hebrew) book on philosophy  החתול שאיננו שם the two of us had in 2010 a long discussion on various philosophical questions with emphasis on the free will problem. Ron wrote this post explaining his point of view in connection with my 2021 paper on free will (see this post).  See also this birthday post for a few of Aharoni’s mathematical contributions.

The Free Will problem

Ron Aharoni

OLYMPUS DIGITAL CAMERA

 

1. The problem

The Determinism-Free Will (DFW, below) problem is born from a combination of three intuitions. None of these is explicit, and it is not at all clear why we trust them.

A. We are free to choose.

B. Events, including brain processes leading to decisions, are pre-determined.

C. A and B are incompatible.

At least one of these assumptions must be false. There are no paradoxes in real life. The world is consistent, and a paradox does not point at an absurd phenomenon in the real world, but at some flaw in our concepts, an erroneous assumption. Identifying the fallacy requires formulating the three assumptions explicitly:

A’. What is “freedom to choose”?

B’. What does it mean to be “pre-determined”?

C’. Why are the two contradictory?

These are not philosophical questions. They are factual, more specifically – psychological. They ask what happens in the brain of the person using these concepts. What are the intuitions behind the scene.

Circumventing this stage, of explicit formulation of the assumptions, results in coerced arguments. This is what happens with the solution that invokes the deus ex machina of quantum theory. It denies B, without defining A and B precisely, and without explicating C, the intuition of incompatibility. The meaning of all three assumptions is left vague.

2. Free Will as a tautology

So, let us address A’ first. I will go straight to the conclusion: the existence of Free Will is a tautology.

Let me explain.

Like all animals and plants, we are future-oriented. We were formed by Natural Selection, which is, tautologically, biased towards the future. Our eyes are placed in the front of our heads, looking in the direction of the places we shall be in, not backward, where we came from. So, an inherent temporal a-symmetry is ingrained in each living or vegetating creature.

This means that when we ponder an action, we look in the forward temporal direction. We try to predict its consequences, rather than find its causes. (“Consequences” of an event F are defined as events following it, in time, and causally linked to it; causes are defined as preceding F).

We imagine the action, and calculate its impact on future events.

In this process it is essential that we isolate the part of the action that is solely dependent on our deliberation. Namely, those parts whose causal interaction with preceding events is through the deliberation. We must distinguish them from the causal links with the past that circumvent the deliberation. Those that come from aside.

As an illustration, suppose I deliberate whether to eat a tomato or not. Suppose that a health-freak giant studies what I had for breakfast, finds out that I haven’t had my doze of vitamin C for today, by which he decides to force my hand to reach for the tomato. The action is then not given to my free will, because it had a causal link with the past that did not go through my decision process.

We are thoroughly trained to isolate the part of the action that is only dependent on the deliberation process from other past events. This is essential for survival. When I deliberate a trip to Tel Aviv I will take into account the physical possibilities, the rules of Covid isolation, and so forth. These I will not deliberate. I will only consider the part of the action that is given to the deliberation. And that part, by definition, is free.

But this means that we always feel our actions are free. Free Will just means that we know what is linked to our decision process, and what is not. And this knowledge is deeply ingrained in us, down to the physiological level.

But there are demons lurking in the dark, in the form of B and C above. We have to thwart their threats, for which purpose we have to ask for explicit formulation of the arguments.

3. What does it mean to be “pre-determined”?

Pre-determination is usually identified with prediction. The rules of nature tell us that the future event F will occur. F is predictable.

The prediction establishes a link between F and past events. For example, a wise man could predict your next choice, and write it on a piece of paper. Then your choice is pre-determined. It is equivalent to what is written in the paper.

Taking prediction more abstractly – not necessarily as words but as any event that is equivalent to F and preceding it – a prediction is just a causal link between an event and the past. That’s the essence.

For simplicity, let us combine the past events linked to F into one event, E. So E predicts F if it is causally linked to it.

For the purpose of formulation of the Determinism-Free Will paradox it is not compulsory that the prediction is perfect. A correlation between F and E suffices. For example, when I mount a bus, I can predict with good certainty that the bus driver will follow the ordinary route, and will not take us to the beach for him to have a short swim. The latter is possible, but there are good chances it will not occur.

So, pre-determination of F is any causal link connecting F with the past. Say, a giant forces your hand to take a tomato, according to some information he collected in the past. Or, a wise person predicted whether you are going to eat a tomato, and wrote his prediction on a piece of paper. These establish equivalences, or at least correlations, between your action and the past.

Of course, there is a big difference: in the first case the decision is not free, since there is a causal link circumventing the deliberation process. In the second, the wise man predicted the deliberation, so the link goes through the deliberation, not from aside. This choice was free.

The contradiction in C is there, even if we are speaking about correlation, as weak as it may be. If my future action F is in high correlation with a past event E, then I am not totally free. This suffices to form a paradox, since the feeling of being free is total – I feel I am totally free to choose F.

And even the most staunch advocators of the Quantum uncertainty solution to the problem of Free-Will will not deny the existence of such correlation. Without it no rational behavior would be possible.

4. The contradiction

Finally, we get to C’. Looking for an explicit formulation of the contradiction between A and B.

It is very simple. It is the essence of the DFW problem.

(DFW)

We can change (decide on, determine the fate of) future events,

We cannot change the fate of past events.

So, an equivalence, or even correlation, as weak as it may be, between past events and events given to our decision, is impossible.

In other words: if my action F is equivalent to a past event E then since E cannot be decided upon, so does my choice. One cannot change, or decide on, past events, and if there is some equivalence (logical or causal) with the future, I cannot change the future. I am not master of my decisions. There is no free will.

This is at the core of the feeling that determinism is incompatible with free choice.

Summarizing: F is a future action, E a past event, if they are equivalent, then since I cannot decide on E I cannot choose F. I am not free.

(*) A side remark: in a famous conundrum, called “Newcomb’s paradox”, the Determinism-Free Will paradox is stated in the contrapositive direction. It poses a situation in which (seemingly, at least) a past event E is causally linked with a choice of an act F, making it possible to determine E by choosing to do F. Contrary to our profound belief that the past cannot be affected.

The Determinism-Free Will paradox is: I cannot decide on E, so, I cannot affect F.

Newcomb’s paradox is: I can decide on F, so I can decide the fate of E. The same argument.

5. A first step in search for the flaw – looking from aside

Since arguments A and B are flawless, the error leading to the paradox must be in C. The intuition that A and B are incompatible is based on some flawed argument.

Rabi Akiva (~50 – 136), the great Jewish sage, put it:

“Everything is foreseen yet freedom of choice is granted” (Pirkey Avot 3:15)

Of course, this is an evasion, not a solution. It evades the explicit paradox, given in (DFW)
above.

Still, the persistence of the claim indicates that it is based on some deep intuition. There is something to it.

Here is this something, which is the fact most relevant to DFW:

Everything is foreseen from the outside, freedom of choice is granted from the inside.

Which means: for an onlooker, things are determined; The decider feels they are not. He cannot see the determinism. Not as long as he or she are deliberating.

This is the most crucial observation about DFW: the problem does not exist when viewed from the outside.

Why is this? Simply, because the punch line in (DFW), “so I cannot decide on F” can only be said by a decider. Looking from aside, you cannot say “so I cannot decide” – you are not deciding anyway.

For example, observing a colony of ants without intervention in their decisions, you can know the regularity governing their actions, and still view their actions as given to their will (yes, ants certainly have wills, just look at an ant fighting a grain of wheat). The two facts are totally compatible.

So, the secret of Hobbes, Hume and Mill is that they look from aside. From the point of view of a detached observer. The secret of their opponents is that they look from the inside. From the point of view of the decider. They want to play the role of the decider and the describer at the same time.

Who is right? The onlookers or the deciders?

Or is the truth in the middle? Or each side has its right for its point of view?

In this case there is a side that is right: the detached observers – Hobbes, Hume, and Mill.

The detached observers are always right. The right way to study human thinking is from aside. Separating object from subject.

A rule of thumb: if a problem disappears upon detachment between observer and observed, it is a sign that it is the result of a special type of sin, namely of an error. It means sinning in circularity. Some circular (self-defined) argument is at work.

But before I explain why, here is a small digression, on a big subject, “What is philosophy”.

6. An aside: what is philosophy?

In my book “The cat that is not there” I tried to answer the question “what is philosophy” in a non-philosophical way. Indeed, it is not at all a philosophical question, it is empirical. It is answered by observing what kind of conceptual structure people identify as “philosophical”.

My answer is that every philosophical discussion commits the same sin, of non-separation between observer and observed.

A philosophical investigation studies some conceptual structure, from the point of view of its user. This is problematic – the right way to study one’s thinking is to partition oneself into two totally separate entities, observer and observed. If this is not done, philosophy emerges.

Non-separation can lead to two possible outcomes:

A. Absurdities. Circularly constructed concepts easily lead to paradoxes.

B. Philosophical flavor of the problem. The problem is a factual one, about human thought, but a feeling arises that the problem cannot be answered by observing reality. This is the famous feeling of loss of stable ground, absence of Archimedian leverage point, characteristic of philosophy.

Both are unfounded, which can be realized when separation is applied.

Upon separation, every philosophical problem has one of two fates:

A. It can disappear, testimony to its entire existence being the result of an error. There are problems that just disappear, like the problem of Idealism – is there an external world. Watching Joe speaking about the chair in front of him, and informing us about the chair, we can just check whether indeed there is a chair there, and validate his observation. Yes, there is a chair in the external world. There is no self-reliance in this. When I ask about my own consciousness, my testimony “yes, there is a chair there” relies on the same perception that was put to doubt. It looks circular. Of course, the sin is viewing myself as both observer and observed. Separation should apply, after which the problem disappears.

The problems that disappear are the paradoxical ones – like the Mind-Body
problem. It does not exist in detached observation of other people. The DFW problem is another problem of this type. It, too, does not exist when the point of view of a detached onlooker is adopted.

B. The problem can lose its philosophical flavor. It becomes factual, an ordinary empirical problem about the world. For example, “What is truth” becomes “How does Joe handle the concept of truth”, or “How does Western society use the concept”. “What is “good”?”, the classical Socratean problem, becomes “how do we use the word “good”?”, in other words what are our ethical values, where “our” can be my own personally, or the set of values of our society. A famous definition of “philosophy” is that it clarifies concepts. But clarifying the concepts of Joe does not generate a sense of philosophicality. No more than understanding in depth the workings of a computer program.

7. The fallacy

Let us return to the person deciding whether to eat a tomato or not.

We noted that there are two types of causal links connecting the decision with the past.

If the motion of the hand is forced by a giant, then it is by definition “not free”, so there is no problem. A pre-determined action which is not free – this is to be expected.

This is true for any causal link between F (the decision on the tomato) and E (any past event) that circumvents the process of deliberation. Such a link means the action is not free.

So, the only problem is if the causal link goes through the process of deliberation. For example, when a wise man predicted the deliberation. In this case the paradox arises: the deliberator feels his decision is free (no giant forcing his hand), and yet there is a past event equivalent to it (say, the prediction the sage wrote in his piece of paper).

Here comes the deception, the fallacious argument. The argument leading to the contradiction is: “If I can change (determine, decide upon) F then I can change the past event E”. But in the second case in effect what this means is: “I will change F, so that the deliberation process will be such and such, so that E is so and so”.

In other words, in the second case, we deliberate F with the aim in mind of affecting the deliberation process.

We want to decide on our decision process. We want the decision process to be such and such.

An obviously impossible task.

Thus the argument “If I can change F then I can change E”, or contra-positively – “Since I cannot determine the fate of E I am not free to choose F”, is flawed. It is trying to lift yourself by pulling at your hair. You cannot decide on your decision process, or choose your very present motives.

Not very surprising: a problem that exists in self-perception and not from the point of view of a detached observer is bound to be born from the sin of circular argumentation.

8. Summary: Thou shalt not look back

The above can be summarized in one rule:

The decider feels free, because he does not look back.

He just can’t look back. He is wearing blinders, like horses. The kind of blinders Lot may have regretted his wife didn’t wear (as you may remember, when she disobeyed God’s order and looked back she turned into a pillar of salt).

You do not deliberate by looking back, at your motives and your history. You enact the motives, not observe them. You think about the future outcomes of your pondered action, not about the causality behind the action.

This has two reasons, both having to do with circularity. One is shallow and the other deep.

The simple reason is the familiar phenomenon of measurement affecting the measured – a popular interpretation of the uncertainty principle of quantum theory. If you take your motives into account in the deliberation (“I will do so and so because my motives are such and such”) the knowledge becomes part of the motive and may change it. The likely effect of knowing your motives will be – “Yes, but I and not obliged to choose this way. I can always choose otherwise!”

This is a circularity phenomenon – knowledge interfering with its object.

The deeper circularity phenomenon is the one discussed above. It hinders not only the use of knowing (in real time, not in hindsight) of one’s deliberation process. It hinders the use of its very existence. Deliberation means finding, and using, causal links between your action and future events. If you want to use a link with the past, there are two possibilities: if the link circumvents the decision process, the action is not free; if the link goes through the deliberation, then using it is tantamount to choosing your deliberation process, in other words, choosing your motives. An obviously circular task.

The deliberation is a partition, that separates us from the past. It makes us look only forward in time. We cannot know the rules governing our actions, and we cannot even use their existence for the purpose of deliberation. When deciding, our face is only to the future.

Posted in Philosophy | Tagged , , , | 1 Comment

Prague 2024: The First Jiří Matoušek’s Lecture

Posted on July 9, 2024 by Gil Kalai

Jiří Matoušek was a great mathematician and computer scientist and a wonderful person who enlightened our communities and our lives in many ways. A few weeks ago I visited beautiful Prague (and the historic building of the computer science and applied mathematics departments) for a few days to give the first Jiří Matoušek memorial lecture.  The Matoušek Lectures in Computer Science will take place yearly in the Jiří Matoušek Auditorium. My lecture was about Tverberg’s theorem and here are the slides.

gil-jirka.jpg

liri-pavel99prague24

eingev-crete2000

gil-jirka-ascona

Captions for the pictures, row by row: Jirka and I, Ascona 1999 (credit: Emo Welzl). We discussed topological approaches for Tverberg’s theorem based on iterative \mathbb Z_2 actions.; Jirka and Pavel Valtr (Ein-Gev conference 1999) (credit: Helena Nyklová); Shaking hands with Jiří Sgall and my lecture (credit: Tomáš Rubín); touring the historical computer science building with its 1000 years old archeology. Our guide is the former dean Jan (Honza) Kratochvíl (credit: Helena Nyklová); Pictures from 2000 conference in Crete (credit: Helena Nyklová); A slide from the lecture with more pictures from Ascona 1999 conference (click here for the full picture collection; photographer: Emo Welzl). 

 

 

Posted in Combinatorics, Computer Science and Optimization, Convexity, Geometry, personal | Tagged | Leave a comment

Noga Alon and Adi Shamir won the 2024 Wolf Prize

Posted on July 7, 2024 by Gil Kalai

Congratulations to Noga Alon and Adi Shamir for winning the 2024 Wolf Prize.

Noga Alon received the prize “for his fundamental contributions to Combinatorics and Theoretical Computer Science,” and Adi Shamir “for his fundamental contributions to Mathematical Cryptography.”

noga-adi

This is also wonderful news for the Israeli scientific community and for the areas of combinatorics and theoretical computer science. Here are a few blog posts about Noga’s work.

Noga Alon and Udi Hrushovski won the 2022 Shaw Prize; An interview with Noga Alon (2019); Test Your Intuition (27) about the Alon-Tarsi Conjecture (2017); The seventeen camels riddle, and Noga Alon’s camel proof and algorithms (2017); Subspace Designs, Unit and Distinct Distances, and Piercing Standard Boxes (2023); NogaFest, NogaFormulas, and Amazing Cash Prizes (2015); A lecture by Noga (2014); Cap Sets, Sunflowers, and Matrix Multiplication (2011);

Adi Shamir is perhaps the most famous researcher in cryptography in the world (with many contributions to other areas of computer science). He is famous for being the ‘S’ of “RSA”, for the Fiat-Shamir heuristic, for his theorem that IP=PSPACE, and he is among the few researchers that do research both in cryptography and in cryptoanalysis. Adi’s work on IP=PSPACE is mentioned in this post, and mathematical cryptography theory in this post.

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , | 1 Comment

Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma’s paper on the Effect of Non-unital Noise on Random Circuit Sampling

Posted on June 12, 2024 by Gil Kalai

fig1-Feffermanetal

I would like to discuss the following remarkable paper posted on the arXiv in June 2023.

Effect of Non-unital Noise on Random Circuit Sampling,

by Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma’s 

Abstract: In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates — meaning it is never too “flat” — regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

I am thankful to Soumik and Kunal, two of the authors, for bringing the paper to my attention and to Soumik for helpful clarifications and useful discussion. This work was featured on the UChicago CS departmental website.

In this post I will describe some findings of the new paper and possible relevance to my study (with Yosi Rinott and Tomer Shoham) of the Google 2019 quantum supremacy paper.  As far as we can see, the phenomenon described in the new paper is not witnessed in the experimental data of the Google 2019 experiment. 

Noisy random circuit sampling 

Random quantum circuits have an important role for the study of NISQ (noisy intermediate quantum) computers, which, in turn, represent much of current efforts for demonstrating quantum computation. There were several important theoretical papers for understanding the effect of noise on the ideal probability distribution and for connecting it with classical computational hardness and easiness of the sampling task preformed by the quantum computer.  We devoted a post to the paper by Xun Gao et al. where we also mention a more recent paper by Aharonov et al. 

Update: Here is a very interesting very recent paper on random circuit sampling Incompressibility and spectral gaps of random circuits, by Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan, and a related paper by Lucas Gretta, William He, and Angelos Pelecanos, More efficient approximate k-wise independent permutations from random reversible circuits via log-Sobolev inequalities. There are interesting (speculative) connections between random quantum circuits and black holes. 

Anticoncentration and some findings of the new paper

A central problem studied in the new paper is 

Do random quantum circuits, under the influence of physically motivated noise models, anticoncentrate?

Anticoncentration means that the distribution is not concentrated on a sufficiently small number of outcomes and it is an important property for RCS samples under basic noise models. In mathematical terms, if the probability for a bitstring x is denoted by p(x), anticoncentration refers to a situation where  \displaystyle \sum_x p(x)^2 = c /2^n, for some c \ge 1. When the probability distribution is uniform we have c=1, and for Porter-Thomas distributions we have c=2. 

In the words of the authors, what the new paper shows is that 

“In this work, we answer this question in the negative: we show how random quantum circuits, under noise models inspired by real hardware, which is a mixture of both unital and non-unital noise of certain types, exhibit a lack of anticoncentration, regardless of the depth of the circuit. This shows that the output distribution does not resemble the uniform distribution, or close variants of the same. Interestingly, we find that this behaviour is exhibited even when there are also unital noise sources, like the depolarizing noise, present in the system, whose property is to push the system towards the maximally mixed state — which, when measured in the standard basis, gives the uniform distribution. In this sense, these non-unital sources ”dominate” the other sources.

(In mathematical terms this means that the effect of non-unital noise is that \displaystyle \sum_x p(x)^2, is a function that diverges with n.) The paper studies specifically the amplitude damping noise which (according to Soumik) is closely related to  a T1 decay of a gate. (T1 decay is a feature of all realistic hardware.) The effect of non-unital gate errors like amplitude dampling errors is to have larger fractions of zeroes in the samples produced by the quantum computer.  

Rethinking computational hardness and easiness 

According to the authors a key takeaway of the results is that we need to think carefully about new techniques to prove asymptotic easiness or hardness for random circuit sampling with constant noise rates. Existing techniques for both make strong assumptions on the nature of noise present — for instance, modeling the noise as completely depolarizing — which is unsatisfactory, because these techniques are very sensitive to such assumptions and break down for more realistic noise models. The paper suggests that the moment realistic noise models come into play, the true complexity of random circuit sampling is still an unresolved open question.

Relevance to the statistical analysis and the concerns regarding the Google 2019 experiment

In the past few years, Yosi Rinott, Tomer Shoham and I were engaged in a comprehensive statistical study of the Google’s 2019 quantum computer experiment. We wrote four papers:

  1. Y. Rinott, T. Shoham, and G. Kalai, Statistical Aspects of the Quantum Supremacy Demonstration, Statistical Science  (2022)
  2. G. Kalai, Y. Rinott and T. Shoham, Google’s 2019 “Quantum Supremacy” Claims: Data, Documentation, & Discussion  (see this post).
  3. G. Kalai, Y. Rinott and T. Shoham, Questions and Concerns About Google’s Quantum Supremacy Claim (see this post).
  4. G. Kalai, Y. Rinott and T. Shoham, Random circuit sampling: Fourier expansion and statistics. (this post)

The new paper by Fefferman et al. is related to this statistical study and in particular to bias toward ‘0’ for the experimental bitstrings.  It appears that the phenomena described in the paper of bias toward ‘0’ as a consequence of non-unital gate errors is not witnessed in the Google experimental data.

This reminds me of the  the paper by Xun Gao et al, which influenced our fourth paper. The story is similar: theoretical analysis suggests that gate errors contribute additional effects of similar mathematical nature to the effect of readout errors. Our paper used Fourier methods and statistical tools to study these effects and showed that these effects of gate errors are confirmed by simulations but are not witnessed in the Google 2019 experimental data. 

Asymmetric readout errors

One basic form of errors are readout errors: the probability that a measured qubit will read as ‘0’ instead of ‘1’  and vice versa. For the Google 2019 experiment the paper reports that the the probability q_1  that 1 is read as 0 is 0.055 and the probability q_2 that 0 is read as 1 is 0.023.

There are several ways to study the values of q_1 and q_2. 

  1. We can get an estimate on q_1-q_2 based on the statistics of 0’s and 1’s in the empirical samples. Namely the expected number of 0s is 1/2+(q_1-q_2)/2. (This gives estimates for individual qubits as well.) 
  2. The Google method was simply to initialize (computational states representing) many known random bitstrings and then simply measure many times. This method provides the values for readout errors for individual qubits, in fact, it gave readout errors for a specific set of  qubits
  3. We developed a statistical method (based on knowing the amplitudes of the ideal circuit) to estimate q_1 and q_2, and implemented it for one circuit with 12 qubits. 

Note that the first and third methods accounts not only for bias toward 0 for asymmetric readout errors but also for additional bias toward 0 coming from non unital gate errors that is considered in the new Fefferman et al.’s paper. It appears that Google’s method (item 2) does not involve the effect of non unital gate errors.  The raw data for the effect of readout errors as studied in the second item was provided by the Google team in January 2021. (The file type is not supported by WordPress, but if you are interested drop me a comment/email.)  

Are non-unital gate errors manifested for the Google 2019 data?

Comparing the different methods for estimating the parameters q_1 and q_2 we observe: 

  • There is a good fit between the readout errors q_1,q_2 obtained by Google’s method of item 2 and the fractions of 0s and 1s in the Google experimental samples (item 1). 
  • For n=12 (and circuit number 0) our MLE estimates for q_1 and q_2 are also consistent (and somewhat lower) than the Google’s estimates. Our estimation gave q_1=0.0465, q_2= 0.0196.

Both these findings show no sign in the Google experimental samples for additional asymmetry between 0s and 1s caused by non-unital gate errors. This finding is quite interesting; it may simply reflect the fact that the non-unital error rates are very low, it may be  a genuine finding about NISQ devices, or specific finding about the Sycamore quantum computer, it may be a legitimate effect of the Google’s calibration method, and it may also be an artifact of some methodological problems with the 2019 experiment of the kind suggested by our previous papers (mainly the third paper).   

Of course, this may also show some misunderstanding or mistake on my part; and, I asked, a few weeks ago, the Google team’s members (and other participants of our email discussion about the 2019 experiment) on this matter.  As always, comments are welcome. 

Let me also mention that the dependency of the ratios of 0s and 1s on the location of the bit that is witnessed in the empirical samples does not appear to be manifested in Google readout raw data. 

Fourier methods for  the asymmetric case

Fourier-theoretical aspects of asymmetric readout errors are quite interesting and are related to  p-biased version of the Fourier-Walsh basis that appeared in the works of Talagrand, Friedgut, and others. We also still do not know how to apply variants of the Fast Fourier transform for quick computations for estimators of noise with asymmetry.

Soumik Ghosh’s remark: The low and high noise regimes

Soumik Ghosh made the following insightful remark:

“Here’s my perspective on why Google potentially did not see the effect of gate errors in their data, which you write about in your blog post.

There are two noise regimes: low and high. High is when the noise rate is a constant. Low is when the noise rate scales as ~1/n (ie, goes down with system size). These two noise regimes have very different properties (see here for instance: https://arxiv.org/abs/2305.04954).

Implicitly, Google’s claims are in the low noise regime. For their 53 and 67 qubit devices, their noise rates are indeed of the order ~ 1/50 or 1/67. It doesn’t mean they will always be in the low noise regime in the future too, without major technological breakthroughs in noise reduction, but so far, there’s a claim to be made that they probably are.  

What our results imply is that if they are ever not in the low noise regime — say if the noise reduction capabilities bottom out and the noise stays a constant with a increase in system size — then they will see effects of gate errors very prominently. This will be true even if they mitigate readout bias. 

What if they are always in the low noise regime? Then it’s an open question as to what happens. Theoretically, it is known is that if the noise is purely unital (which is unrealistic), then the entire noise manifests as just a global depolarizing noise in the readout (the so called white noise model: https://arxiv.org/abs/2111.14907). It is an open question as to what happens with realistic non-unital noise models in this regime.”

From my point of view,  the distinction between low and high error regimes and Soumik’s remark are very much to the point. The distinction between the low and high error regimes is indeed important from theoretical and practical purposes. In my works on noise sensitivity, I indeed argue that in the high error regime the noisy samples will have a noise stable component (representing low degree Fourier-Walsh coefficients) which represent a very primitive computation and a noise sensitive component (representing high degree Fourier-Walsh coefficients) which does not enable computation at all. In the low rate error regime interesting computation and more importantly the creation of good quality error correcting codes are possible.

My theory predicts that in the intermediate scale the low error regime that allows quantum supremacy and good quality quantum error correcting codes cannot be reached. (See e.g.,  this post and this paper.) 

Let me move now from theory to the matter of scrutinizing the Google 2019 experiment and other NISQ experimental assertions. To check the effect of non-unital gate noise on the ratio of zeroes and ones for the Google experiments we probably need to run simulations with the noise parameters of the experiment. I hope that the Google team, other teams involved in the 2019 experiment, like those from NASA, and teams involved in other recent NISQ experiments will double-check this matter by themselves.

Posted in Computer Science and Optimization, Physics, Quantum, Statistics | Tagged , , , , | 4 Comments

Andrew Granville: Accepted Proofs: Objective Truth, or Culturally Robust?

Posted on June 7, 2024 by Gil Kalai

AndreGrandville

Andrew Granville (home page; the comics book: “The Prime Suspects“)

Andrew Granville, a famous number theorist, wrote a wonderful paper about proofs in mathematics published at  the Annals of Mathematics and Philosophy. 

M×Φ

Accepted Proofs: Objective Truth, or Culturally Robust?

I will give some quotes from the paper and some remarks (that follow an email correspondence with Andrew). The paper touches on subjects of many mathematical discussions over the last 150 years (and more). Several of the issues in the paper were discussed here over the blog; let me especially mention my essay About Mathematics. You can learn from Andrew’s paper not only about mathematics and proofs but also about Andrew himself and his views on a variety of issues. There is a very nice Quanta Magazine’s article written by Jordana Cepelewicz about Andrew’s views: Why mathematical proof is a social compact.

This post has four parts: 1. On the Nature of mathematical proofs, and the relevance of Gödel’s theorem, 2. Footnote (15) – are simple number-theoretic conjectures independent from ZFC,  3. On the nature of mathematical explanation, 4. Computers and proofs. We conclude with a few selected footnotes. But first (sound of trumpets),

King Fredrick II’s opinions about mathematicians

The starting view of the paper is:

Vanity of vanities! Vanity of mathematics!– Frederick II of Prussia (1778)

See, the 0th footnote of the paper for the identity of the person King Fredrick was complaining about and to whom the complaint was addressed.

And here is Oscar Wilde’s view of mathematicians (from the  Happy Prince .)

[T]he Mathematical Master frowned and looked very severe, for he did not approve of children dreaming.

1. The Nature of mathematical proofs, and the relevance of Gödel’s theorem, 

The first sections in Granville’s paper discuss what is a mathematical proof, and Gödel’s theorems.

§ 1. — Proof– why and how.

Aristotle wrote

If … understanding is as we posited, it is necessary for demonstrative understanding … to depend on things which are true and primitive and immediate and more familiar than and prior to and explanatory of the conclusion.

and Dan Rockmore wrote

The proofs actually conjure mathematics into existence.

And here is a quote from the paper itself

Prularity The foundations of mathematics starts with a set of axioms, but which set? Hilbert’s proposals leave open the possibility of working within different axiomatic systems, and perhaps those different axiomatic systems will lead to contradictory conclusions to the same simple questions. Then how do we decide which axiomatic system is the correct one to use?

§ 2. — Living with, and ignoring, the Gödel crisis.

The general mathematical culture is to not worry about these things too much. If one works on a question close to where some problem has been found that is undecidable within the “standard” axiomatic framework then one needs to act carefully,(14) but for the most part it seems like a distant problem, and not one that we meet in our day-to-day work.(15)

Footnote (14) explains the notion of “undecidable”

(14) By “undecidable” we mean that if it is true it is not provable using the axioms
in the theory, and if it is false it is not refutable using those same axioms.

Footnote (15) expressed an interesting opinion about  suggestions that certain mathematical conjectures are undecidable. (In fact discussing this issue with Andrew was how I learned about the paper.) We will come back to it below, but let us first discuss other inherent obstacles for proving mathematical statements.

Other inherent obstacles for finding a proof

The end of Section 2 raises the following question:

Can there be a mathematical statement that is provable within our standard axiomatic framework, for which every proof is too long for humans’ timespan?

There is a brief discussion on the relation with the P ≠ NP problem, and a quote of Avi Wigderson

problems in NP are really all the problems we … mathematicians, can ever hope to solve, because [we need to] know if we have solved them.

In the  post Why is mathematics possible?  we talked about  three (potential) inherent obstacles for proving a (simple to state) mathematical assertion: 1) Independence from ZFC, 2) The proof is too long, 3) It is computationally intractable to find the proof. The post raised the question of why we can usually safely ignore these obstacles. Here is a link to a 1999 paper of Kazhdan, and to Tim Gowers’s view.

2. Are simple number-theoretic conjectures independent from ZFC?

Footnote (15) of Andrew’s paper expressed an interesting opinion about  suggestions that certain mathematical conjectures are undecidable. In fact, discussing this issue with Andrew was how I learned about the paper.

(15) One does hear people suggest that popular unsolved problems might be “undecidable” within our axiomatic framework, which I regard as hubris; just because we have not yet found a good understanding of something does not make it an eternal mystery. Knuth [37] even makes the tenuous argument “the Goldbach conjecture … [is] a problem that’s never going to be solved. I think it might not even have a proof. It might be one of the unprovable theorems that Gödel showed exist … we now know that in some sense almost all correct statements about mathematics are unprovable,” and goes on to claim that Goldbach must be “true because it can’t be false” for which he then gives a standard heuristic. The only salvageable truth from this is that Goldbach might not be provable in Peano arithmetic since there might be a different model of integers that satisfy Peano arithmetic yet for which Goldbach fails; however if so then we tinker with our axioms and add one to ensure we remain in the usual integers and then Goldbach should be provable. People have made analogous fatuous claims about the Riemann Hypothesis, the twin prime conjecture, etc. with no real substance to back their claims. There is a good discussion of all this at https://mathoverflow.net/questions/27755/

The very interesting MathOverflow question referred to in Footnote (15) deals with Knuth’s intuition that Goldbach’s conjecture is independent from ZFC. 

Here is something I learned from the comments there: referring to the existence of odd perfect numbers, the iteration of numerical functions, the existence of infinitely many Fermat primes, etc.,  Enrico Bombieri opined (1976):

Some of these questions may well be undecidable in arithmetic; the construction of arithmetical models in which questions of this type have different answers would be of great importance.

Gowers’s answer to the MO question mentions Don Zagier who talked of a general intuition “that the quality that may make some natural statements unprovable is the quality of telling you just what you would expect to happen anyway.”

As seen from footnote (15), Andrew is skeptical of intuitions that various simple number theoretical conjectures are independent from ZFC. Andrew’s interpretation of progress he himself has witnessed in his life time is strongly against such ZFC-independence speculations.

My view is that it may be important (as it was important in the past) to find mathematical frameworks for understanding inherent obstacles for proving number theoretical conjectures, whether obstacles of specific techniques or obstacles of the entire ZFC. I find the following idea quite appealing 

From ZFC’s perspective,  primes are “psedorandom” entities and the set of primes looks like a “sample” of integers based on some “approximated Cramer heuristics”.

I completely agree that there is no evidence for this idea. 

A diversion: Cramer heuristics

Talking about Cramer heuristic, Andrew himself is perhaps the world expert.

Indeed in  a 2007 Annals paper An uncertainty principle for arithmetic sequences, by Andrew Granville Kannan Soundararajan, Andrew and Sound established an uncertainty principle which more-or-less shows that there is no formulation of Cramer type heuristics that can give completely correct predictions! They use among other things results and ideas from the theory of irregularity of distributions and especially results of Jiri Matousek and Joel Spencer. 
 
My impression is that the coarse insights from Cramer’s theory (e.g. “there is always a prime between n and n+\log ^4n,”)  are not harmed by such deviations and perhaps my “large deviation heuristics”  can give some (conjectural) insights about the worse case behavior of possible deviations. Regarding systematic deviations from Cramer’s heuristics let me mention an older 1995 paper by Andrew (published in the Scandinavian Actuarial Journal) entitled Harald Cramér and the distribution of prime numbers, and a related paper by William Banks, Kevin Ford, and Terence Tao.

 

The question about the plurality of the natural numbers

The following question is very interesting:

Is there some reasons to think that for the natural numbers there is a (platonic) notion of “true” natural numbers along with a variety of pseudo-natural numbers that satisfies the same axioms, or a better intuition is that of geometries (without the parallel axiom), namely, that there are genuinely different models with different properties, with no “priority” of one of the models?

(See Joel David Hamkins answer to the MO question mentioned above, and comments to Joel’s answer.) Of course, the same question is important when we refer to group theory and (mostly) to set theory rather than to number theory. 

3. The nature of mathematical explanation

Sections 3-6 and 13 in Andrew’s paper discuss the nature of mathematical explanations, acceptance of proofs as correct, famous cases of mathematical mistakes, and objectivity in mathematics. 

§ 3. — Formal proof vs culturally appropriate, intuitive explanation.

Section 3 discusses formal proofs, “good proofs,” and beauty. Here are two very nice quotes:

There is no … mathematician so expert in his science as to
place entire confidence in his proof immediately on his
discovery of it…Every time he runs over his proofs, his
confidence increases; but still more by the approbation
of his friends; and is rais’d to its utmost perfection by the
universal assent and applauses of the learned world.
. — David Hume (1739)

Mathematics …[does not] reward passive consumption.
Understanding a mathematical paper is like visualizing
a building based on the architect’s drawings: the text and
formulas are only a blueprint that the reader must use to
reconstruct the author’s imaginary world in her mind. If
she does that, however, then the best mathematical theories
have the same breathtaking quality as the image
of Paris folded on itself. The experience can be both
exhilarating and addictive. — Izabella Laba

§ 4. — What is an accepted proof in pure mathematics?

This section discusses the refereeing process.

Famously, Littlewood would ask  — Is it new? Is it correct? Is it surprising?

An interesting side issue is the question of blind refereeing. I remember discussing this matter with Andrew over Facebook a couple years ago.

Famous mistakes in mathematics in the last 50 years

Sections § 5. and §6. are about Mistakes and Rethinking axioms and language. Section 5 deals with famous cases of mathematical mistakes. In some cases the mistakes were corrected and in some cases they were not. Section 6 deals with a couple of cases where mistakes led to rethinking various aspects of mathematics.

§ 13. — Myths of objectivity.

Andrew opens this section with the following question:

In confirming that a proof is correct we believe that we can recognize and establish an objective truth. But can we? It is easy to believe in one’s own objectivity, or that of an “unbiased machine”, but are such beliefs valid, or are they self-serving?

He then referred to Turing who remarks that in the time of Galileo, the quotations “The sun stood still … and delayed going down about a whole day” —Joshua 10:13 “He laid the foundations of the earth, that it should not move at any time” —Psalm104:556 were considered by many to be an objective refutation of the Copernican theory. 

Here is a great blog post by Thomas Vidick: What it is that we do about objectivity of proofs, with some discussion between Thomas and me.  

My opinion is that objectivity of mathematical proofs is not a myth and the objectivity of mathematical truths is an important pillar of human culture. 

4. Computers and proofs

The second half of Granville’s paper deals with computers.

§ 7. – § 12.— Computers and proofs.

Section 7 starts with three skeptical views about computer-generated proofs

I don’t believe in a proof done by a computer … I believe
in a proof if I understand it. — Pierre Deligne
I’m not interested in a proof by computer … I prefer to
think. — John H. Conway [53]
Computer-generated proofs…teach us very little(55).
— Vladimir Voevodskĭ [53]

Section 8 lucidly describes some famous cases of using computers in major theorems. For more examples see this MathOverflow question and this one. Let me also mention Doron Zeilberger’s important role and notable opinions regarding computers and mathematics. 

The following sections in Andrew’s paper discuss some aspects of computers and proofs.

Andrew raises the question

Can we design a computer verifier to learn and think like a human?

What do you think?

Section 12 is devoted to the Lean Theorem prover (see this post and this one). Here is a quote of Kevin Buzzard

In the near future I believe that maybe computers will be able to help humans like myself (an arithmetic geometer) to do mathematics research, by filling in proofs of lemmas, and offering powerful search tools for theorems … but there is still a huge amount of work to do before this happens.

§ 14. — Will machines change accepted proof?

The concluding Section 14 starts with the assertion

In this article I have asserted that proof verification does little to change the central tenets of proof as a social construction.

And there is a short reference to quantum computing

For us the question is whether quantum computing could be adapted to the task of finding proofs (for example, if one uses a ridiculously large search tree).

I agree with the spirit of Andew’s  concluding words

Indeed it is only a matter of time before we learn how to uncover tremendous possibilities for mathematics and for proofs revealed by computing power, software, and brilliant
programming ideas.

 A few noteworthy footnotes

Double-blind refereeing: Footnote (40)

Andrew opined that “…the expert can truly make the difference in helping an author who has good ideas but perhaps has not yet developed the technical skills to take their ideas all the way. In my experience as an editor many referees are encouraging and helpful in these circumstances, particularly if the author is an “unknown”, explaining how they might modify what they have done to make the argument correct, or the theorem stronger or more general.(40)

(40) This is why I am against “double blind-reviewing” in which the authors’ name is concealed from the referee, as it discourages the referee’s generosity: It seems referees tend to assume an anonymous author “should know better” than to make that mistake, and so give a terse explanation about a mistake, rather than a helpful one.

What is a leaner? 

(74) A leaner is someone who implements a proof in Lean.

Ofer Gabber

(86) A mathematician who is known to insist on the right details. (Referring to Ofer Gabber, a great mathematician whom I first met in 1971 when we were both teenagers.)

Footnote (96): Examples

(96) In pure mathematics, finding extensive examples is often a precursor to better understanding, and thus truly new Theorems.

In my view, examples are of central importance in mathematics just like “theorems” and “proofs”. For many examples see the MO question fundamental examples. (While the nature of scientific proofs is very different for different sciences, the central role of examples is common to many academic areas.) 

Posted in Logic and set theory, Number theory, Philosophy, What is Mathematics | 1 Comment

Andrii Arman, Andriy Bondarenko, Fedor Nazarov, Andriy Prymak, and Danylo Radchenko Constructed Small Volume Bodies of Constant Width

Posted on May 31, 2024 by Gil Kalai

Schramm-problem

From left to right: Andrii Arman, Andriy Bondarenko and Danylo Radchenko, Fedor Nazarov, and Andriy Primak. 

The n-dimensional unit Euclidean ball has width 2 in every direction. Namely, when you consider a pair of parallel tangent hyperplanes in any direction the distance between them is 2.

There are other sets of constant width 2. A famous one is the Reuleaux triangle in the plane. The isoperimetric inequality implies that among all sets in \mathbb R^d of constant width 2, the unit ball of radius 1 has maximum volume denoted by V_n. (It is known that in the plane, the Reuleaux triangle has minimum volume.) 

Oded Schramm asked in 1988 if for some \varepsilon >0 there exist sets K_n, n=1,2,\dots  of constant width 2 in dimension n whose volume satisfies

\displaystyle \mathrm{vol}(K_n) \le (1-\varepsilon)^n V_n. 

(See also this MO problem.) 

Oded himself proved that the volume of sets of constant width 1 in n dimensions is at least

\displaystyle (\sqrt{3 + \frac {2}{n+1}}-1)^n \cdot V_n.  

In the paper Small volume bodies of constant width, Andrii Arman, Andriy Bondarenko, Fedor Nazarov, Andriy Prymak, and Danylo Radchenko, settled Schramm’s problem and constructed for sufficiently large n  a set K_n of constant width 1 such that

\displaystyle \mathrm{vol}(K_n) \le (0.9)^n V_n.

I am very happy to see this problem being solved. This new result may be the dawn of an asymptotic era in the study of sets of constant width. Congratulations Andrii, Andriy, Fedja, Andriy, and Danylo!

20240531_183430

Posted in Convexity, Open problems, Updates | Leave a comment

Sheila Sundaram, May 19th, 18:05 (Israel time):  Stirling numbers, Koszul duality and cohomology of configuration spaces (joint work with Ayah Almousa and Vic Reiner)

Posted on May 18, 2024 by Gil Kalai
Let me share an announcement of a zoom lecture by Sheila Sundaram. The lecture (tomorrow, Sunday) is about the paper
 

Koszulity, supersolvability, and Stirling representations,

by Ayah Almousa, Victor Reiner, and Sheila Sundaram.

_____________
 

Bar-Ilan Combinatorics Seminar

The next meeting will be, IYH, on Sunday 11 Iyar (May 19th), 18:05 pm 

(18:05 refers to Israel time.)

*Note change to unusual time
 
on zoom
 

Title:  Stirling numbers, Koszul duality and cohomology of configuration spaces

Abstract: (Joint work with Ayah Almousa and Vic Reiner)

 
The unsigned Stirling numbers c(n,k) of the first kind give the Hilbert function for two algebras associated to the hyperplane arrangement in type A, the Orlik-Solomon algebra and the graded Varchenko-Gelfand algebra. Both algebras carry symmetric group actions with a rich structure, and have been well studied by topologists, algebraists and combinatorialists: the first coincides with the Whitney homology of the partition lattice, and the second with a well-known decomposition (Thrall’s decomposition, giving the higher Lie characters) of the universal enveloping algebra of the free Lie algebra. In each case the graded representations have dimension c(n,k).

Both these algebras are examples of Koszul algebras, for which the Priddy resolution defines a group-equivariant dual Koszul algebra. Now the Hilbert function is given by the Stirling numbers S(n,k) of the second kind, and hence the Koszul duality relation defines representations of the symmetric group whose dimensions are the numbers S(n,k). Investigating this observation leads to the realisation that this situation generalises to all supersolvable matroids.

 
The Koszul duality recurrence is shown to have interesting general consequences. For the resulting group representations, it implies the existence of branching rules which, in the case of the braid arrangement, specialise by dimension to the classical enumerative recurrences satisfied by the Stirling numbers of both kinds. It also implies representation stability in the sense of Church and Farb.
 
The associated Koszul dual representations appear to have other properties that are more mysterious; for example, in the case of the braid arrangement, the Stirling representations of the Koszul dual are sometimes tantalisingly close to being permutation modules.
 
We also show a connection with the homology of the subword order poset, from previous work of the speaker, where Stirling numbers arise again in the representations.

You are welcome to attend

 

Posted in Combinatorics, Updates | Tagged , , | Leave a comment

My First Paper with Dr. Z. : Bijective and Automated Approaches to Abel Sums

Posted on May 15, 2024 by Gil Kalai

My new (and first!) paper with Dr. Z.

Gil Kalai and Doron Zeilberger, Bijective and Automated Approaches to Abel Sums

Abstract: In this tribute to our guru, Dominique Foata, we return to one of our (and Foata’s) first loves, and revisit Abel sums and their identities, from two different viewpoints.

abelblog

From left to right: John Majewicz, Doron Zeilberger, and Dominique Foata

Our preface to the paper: In the very first issue of Crelle’s journal (the first mathematical periodical solely dedicated to mathematics), Niels Henrik Abel published a two-page paper [A], stating and proving his eponymous identity. This lead to an intensive study of general Abel Sums by many people, (see [R] [C] and their numerous references), and to beautiful bijective approaches pioneered by Dominique Foata and Aimé Fuchs [Fo][FoFu] that led to Francon’s elegant proof [Fr] (see [C], p. 129). This tribute consists of two independent parts. The first part is bijective, while the second part is automated, elaborating and extending John Majewicz’s 1997 PhD thesis [M1][M2], and more important, fully implementing it (and its extension) in a Maple package.

The papers’ webpage on Doron’s web page has various complementary materials. 

Some background – Abel’s identity.

Abel’s identity is:

\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^{k-1} (n-k+y)^{n-k} =\frac {1}{n+x}(n+x+y)^n

In his book John Riordan extended the left hand side to a more general expression

A_n(x,y;p,q)= \displaystyle \sum_{k=0}^n {{n}\choose{k}}(k+x)^{k+p}(n-k+y)^{n-k+q}.

Riordan referred as Cauchy’s formula to the following evaluation for p=0,q=0:

\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^k (n-k+y)^{n-k}=\sum_{k=0}^n {{n} \choose {k}}k!(x+y+k)^{n-k}

In 1972 I found a formula for A_n(x,y;p,q) which gives for the special case q=0 the following identity:

\displaystyle \sum_{k=0}^n {{n} \choose {k}} (k+x)^{k+p} (n-k+y)^{n-k} = \sum_{k=0}^n {{n} \choose {k}}(n+x+y)^{n-k} \Delta^kx^{p+k}.

Here the difference operator \Delta is defined by \Delta f(x)=f(x+1)-f(x). My general formula was

\displaystyle A_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}} (k+x)^{k+p} (n-k+y)^{n-k+q} =\\ \sum_{k=0}^n {{n} \choose {k}}(n+x+y)^{n-k} (\Delta_x-\Delta_y)^kx^{p+k}(y+n-k)^q.

It is a legitimate question in what sense does the right hand side of this general formula simplify the left hand side and I tried to justify it in the paper. The story of Riordan’s referee reports to my paper is told in this post. Since the paper appeared in 1979, it was cited once in an unpublished manuscript from 2018 by Darij Grinberg about non-commutative Abel-type identities, and now, once again by our paper. 

Meeting Doron at the Weizmann Institute 

In 1978, my mother made the decision to purchase a car. My parents had never owned a car before, and neither of them held a driving license. However, my mother resolved to buy a car and concurrently take driving lessons. At the time, I was nearing the end of my army service, and after passing successfully my (fifth) driving test, I participated in acquiring our family’s first Subaru, and for some time I was the sole driver.  

In fall 1980, I was newly married, and a year into my graduate studies. We still used the Subaru for trips outside Jerusalem and  on a particular day, my mother, sister (Tami)  and me had planned to travel together to the Rehovot area. I intended to meet Doron, who was a new faculty member in Weitzman Institute (and already a well-known combinatorialist), while my mother and sister wished to visit some family and friends. (Come to think about it I don’t remember how the connection with Doron was made and not even if he expected my visit or I just showed up.) Shortly after we entered Doron’s office, my mother began to display impatience and reminded me of our scheduled commitments.

“Madam Kalai (גברת קלעי)” said Doron. “Your son is a m-a-t-h-e-m-t-i-c-i-a-n and he came here especially to talk and work with me. I suggest that you and Tami take a leisurely stroll in the lovely gardens of the Weizmann Institute for an hour, and then return to continue your journey with Gil.”. 

I was flattered by Doron’s words, but to my surprise, my mother was also flattered. Indeed, she and my sister left us for a significant amount of time to engage in conversation about mathematics. Doron shared various interesting insights and even showed me a draft of his paper on Sister Celine’s method. I believe that this draft marked one of the initial stages of the renowned WZ theory. When my mother and sister came back Doron showed Tami how to prepare certain types of origami, and then we continued in our trip plans.

Here is a nice combinatorial identity

I mentioned to Doron a special case of (Cauchy’s) Abel-type identity.

\displaystyle \sum_{k=0}^n {{n} \choose {k}} k^k (n-k)^{n-k} = \sum_{k=0}^n {{n} \choose {k}} k! n^{n-k},

and wondered about a simple bijective proof. The two sides have a clear combinatorial interpretation: The left hand side is the number of pairs  (A, f) where f:[n] \to [n], f(A) \subset A and f(\bar A) \subset \bar A; the right hand side is the number of pairs (B, f) where f:[n] \to [n] and f(B) = B.

A few weeks later I got a postcard from Doron. He wrote me that for every function f there is a bijection between the A‘s and the B‘s, given by

B=f(f(f(\cdots f(A))))), 

and 

A=f^{-1}(f^{-1}(\cdots f^{-1} (B)))))).

This is very beautiful!

[Comment: the dots means apply until it stabilizes…]

Doron attributed the method to Dominique Foata and this bijection and an extension of it is the basis of the first part of our new paper. (After my first visit, I visited Doron a couple of other times at WI,  once, still as a student, he invited me to give a colloquium there, and since then our paths met many times.) 

The second part of our paper deals with automatic proofs for Abel-type identities following John Majewicz’s 1997 PhD thesis. Of course, automated proofs is a very large and very important topic, and Doron is one of its pioneers. A question that comes to mind is if the process of finding bijective proofs can also be automated. Timothy Chow raised this question over MathOverflow six years ago: Automated search for bijective proofs.

ab

Top from left to right: Marko Petkovsek, Herbert Wilf, Doron and Donald Knuth, and the cover of the book A=B. Bottom: Sister Celine Fasenmyer, Exercise 1.2.6.23 in Knuth’s AoCP part I, and Knuth’s forward. The forward starts with: “Science is what we understand well enough to explain to a computer. Art is everything else we do.”  

Here is a trivia question: There are two notable figures in the A=B story (both are mentioned in the book) whose names differ by a single vowel, who are they?  0-knowledge answers please!

Posted in Combinatorics | Tagged | 1 Comment

My Notices AMS Paper on Quantum Computers – Eight Years Later, a Lecture by Dorit Aharonov, and a Toast to Michael Ben-Or

Posted on April 27, 2024 by Gil Kalai

The first part of the post is devoted to eight-year anniversary of my 2016 paper. I will go on to describe a recent lecture by Dorit Aharonov and conclude with my toast to Michael Ben-Or.

The Quantum Computer Puzzle, Notices AMS, May 2016.

In the eight years since my Notices AMS paper (with the beautiful drawings by my daughter Neta) “The quantum computer puzzle” appeared, my point of view has been challenged by several experimental attempts for demonstrating quantum advantage and quantum error correction. From what I can discern, my argument still holds as a serious alternative to the prevalent optimistic view regarding quantum computing.

The main experimental challenge to my theory, the fantastic 2019 “quantum supremacy” claim by Google, was largely refuted. Moreover, my Fourier-Hermite analysis (with Guy Kindler) proved valuable in scrutinizing (and largely refuting) another specific claim of “quantum supremacy” via boson sampling. Recently, I applied related Fourier methods (with Rinott and Shoham) for statistical analysis of samples coming from quantum computer experiments.

The crux of the matter lies in understanding quantum computers at the intermediate scale, both theoretically and experimentally. There are various interesting experimental endeavors employing diverse approaches to quantum computing in this direction.

Critically analyzing experimental claims is a vital and engaging aspect of this area. Alongside my collaborators, I endeavor to foster an open and candid technical dialogue with experimentalists, patiently await necessary raw data from experiments, conduct meticulous analyses, and provide detailed technical reports of our findings.

FBmemory

Facebook reminded me of the anniversary (click on the picture for the FB post and comments)

The original summary

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.

Note that what I refer to as “small-scale” is now commonly called “intermediate-scale”. Here is the link to the original 2016 post about the paper (that also dealt with other matters).

qnoti

The prevalent optimistic view

Optimism about quantum computers is a source of excitement and hope for many scientists and non-scientists including personal friends and individuals I greatly appreciate. The optimistic view (depicted in Neta’s drawing below) is shared by many members of the quantum computing community. Some attribute the possibility of quantum computing from it being a clear consequence of quantum physics, and others base their optimism mainly on recent experimental advances. 

The question if quantum computation is possible is a clear cut important scientific question and naturally I believe that my theory for why quantum computers are inherently impossible will prevail. I find it exciting to understand others’ perspectives and intuitions on this central question, as well as to follow advances in quantum computational complexity and quantum algorithms.  

Ob

Chinese version

puzz.ch

In 2017 my paper appeared also in Chinese.

Dorit Aharonov’s recent lecture in the workshop dedicated to Michael Ben-Or

Dorit Aharonov’s brilliant lecture at the workshop dedicated to Michael Ben-Or described two central quantum tales, and briefly mentioned an additional research direction (open problem) suggested by her in the late 90s. Dorit also briefly mentioned her view on the skeptical efforts (from 16:45) and her beliefs regarding the state of matters today (19:26): She described a discussion from 2005 of Robert Alicki, Dorit, Michael, and me, and praised the skeptical efforts as important. She further asserted  that in contrast to the mid 90s when quantum computation was considered the most theoretical part of computer science, at present many groups are approaching going beyond the break-even point for quantum error-correction. (She cited Google, Quantinuum and QuEra as examples.) Referring to the skeptical position and to the picture of Michael, Dorit, Robert and me, Dorit said:

I think that at this point, some of the people in this picture are starting to rethink whether their criticism [is valid].  It seems like reality is very close to prove that they’re wrong. 

(Dorit said that maybe she will change her mind as well.)

dorit-MBO24Snapshots from Dorit’s lecture: The top-left slide is about the threshold theorem (mid-late 90s). The bottom-left slide is about later developments related to the threshold theorem (and the 2005 picture that I mentioned above); The top-right slide is about how a classical computer can test that a quantum computer did what it claimed to do. The 2008 paper of Aharonov, Ben-Or and Elad Eban started an exciting direction, and Dorit mentioned that it was motivated in part by Oded Goldreich and Madhu Sudan’s (skeptical) question about evidence for quantum physics in the high complexity regime. The bottom-right shows Dorit and Tal Rabin during the lecture. Below, Dorit’s question on the physics description of quantum fault tolerance and the transition from quantum to classical physics and her 1999 paper on the transition from the quantum world to the classic world.

QtoCtransition

A Toast to Michael Ben-Or

Michael Ben Or is a great friend, a great thinker, a great teacher, and a great scientist. Allow me to share our remarkable journey together. Michael and I met when we were 15 in a mathematics course for mathematically inclined high school students and shortly thereafter, we both embarked on our university studies. Following our service in the army, we pursued graduate studies together, and our families became closely intertwined during our time as MIT postdocs. In this picture, you can see our daughters, Abigail and Neta.

abne

In summer 1984 Michael returned to Jerusalem as a faculty member and a year later, I followed suit. Silvio hosted a farewell party for Michael, attended by Avi and Shafi, although Michael himself was delayed by traffic jams on the highway from NYC to Boston.

In 1987 Michael and Nati wrote their influential paper on influences which profoundly impacted my own career trajectory.  The year 1988 was the annus mirabilis for the theory of computing in Jerusalem. Michael authored several groundbreaking papers, including the two-prover paper mentioned by Shafi, as well as a seminal work on fault tolerance. It was also in 1988 that Tal Rabin, Michael’s brilliant student, completed her master’s thesis.

Let me move forward to 1995 and to the amazing and immensely important threshold theorem that Michael and Dorit proved. I always admired this breakthrough but only a decade later I also got interested in quantum computing, and specifically in the threshold theorem. I started attending the cozy quantum seminar at HUJI and learned a lot from Michael. Since both Michael and I are shy people the first time I asked Michael explicitly if he thinks that quantum computers are realistic was seven years later during one of the quantum workshops we organized.  Michael affirmed that, yes, he is quite confident that quantum computers could be built! (However, Michael confided in me, that his original motivation in pursuing quantum fault tolerance was to prove the opposite theorem.)

During the years both Michael and I were involved in the center of rationality at HUJI and the HUJI Quantum Science Center (perhaps, small island of rationality in our troubled area, or are they?). It was a pleasure to host many quantum information scientists including Charles, John and Umesh in our conferences and international schools.

Here you can see Michael, Dorit, me, and Robert Alicki (one of the few scientists doing quantum computing research in the skeptical direction) in 2005 and seven years later in 2012.

GMDR0512

Just a few weeks ago Michael drew my attention to the paper about logical quantum computing, for neutral atom quantum computers that demonstrate quantum error-correction and some rudimentary form of quantum fault tolerance and to a lecture here at the Simon Institute about this breakthrough.

Michael, best wishes for many years of science and friendship.

(The videotaped version was somewhat shorter; in the full version I tried to mention all the speakers of the workshop. It turned out that although Tal Rabin is a decade younger than me she first met Michael before me!)

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , | 7 Comments

Arturo Merino, Torsten Mütze, and Namrata Apply Gliders for Hamiltonicty!

Posted on April 23, 2024 by Gil Kalai

Happy Passover to all our readers

On the way from Cambridge to Tel Aviv I had a splendid three hour visit to London (from Kings Cross to UCL and back), where I met my graduate student Gabriel Gendler and Freddie Illingworth from UCL. (Like Tim Gowers and Imre Leader but a few decades later, Freddie and Gabriel first met at an IMO.)  Gabriel and Freddie told me about several striking things including the remarkable “glider” proof for showing that Kneser graphs, Schrijver graphs, and stable Kneser graphs are Hamiltonian.  (These proofs settled old standing conjectures.) To quote Merino, Mütze, and Namrata:

“Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life.”

Here are relevant links: 

  1. Arturo Merino, Torsten Mütze, and Namrata:  Kneser graphs are Hamiltonian.
  2.  Torsten Mütze and Namrata, Hamiltonicity of Schrijver graphs and stable Kneser graphs.
  3. (A forthcoming survey article in the Notices of the AMS) Torsten Mütze, On Hamilton cycles in graphs defined by intersecting set systems.
  4.  Torsten Mütze, Gliders in Kneser graphs, Internet site.
  5.  (While looking at 4. I discovered this very cool site) COS++: The combinatorial object server.

     

 

glider2

Continue reading →

Posted in Combinatorics, Updates | Tagged , , | Leave a comment