Some Real and Some Virtual News

Gossip and more.

Composite of , src1, src3

Jessica Deters, Izabel Aguiar, and Jacqueline Feuerborn are the authors of the paper, “The Mathematics of Gossip.” They use infection models—specifically the Susceptible-Infected-Recovered (SIR) model—to discuss gossip. Their work was done before the present pandemic, in 2017–2019. It is also described in a nice profile of Aguiar. Their analogy is expressed by a drawing in their paper:

Not just for today, but for the summer at least, Ken and I want to share some gossip, share some problems, and ask our readers a question.

The question first. Ken and I wonder if GLL should start a virtual theory “lunch” meeting, that would meet periodically via Zoom. It would be like meeting for a theory lunch in the old days—just not all in the same room. Some topic might be agreed on, perhaps a short presentation, and always a chance to swap some gossip. Plus maybe ask the group for advice on a problem.

I do miss the old meetings:

AcademicKeys #78 source

What do you think? Should we have such meetings?

Some Gossip

The study of gossip feeds into other issues of the spread of information and misinformation during an election year. Ken’s Buffalo colleague Kenny Joseph has research on the spread of fake news and Twitter sentiment using mathematical tools adjacent to those of the trio above. Ken and I still intend to say more about epidemiology models ourselves when we get time. But no, here by “gossip” we just mean actual pieces of gossip—just as at a conference or other kind of in-person meeting.

Here are two examples of the kind of gossip we might exchange.

Anna Gilbert is moving from Michigan math to Yale math and statistics. She will be the John C. Malone Professor of Mathematics, Professor of Statistics & Data Science. Pretty impressive. She was at Michigan math for years. She told me that she could not wait for the next power of , and thus had to try a new place, with new challenges.

Rich DeMillo is a long time friend who is at Georgia Institute of Technology and is not moving. He continues working on making voting fair, secure, and efficient. He is referenced in a recent article on voting issues in Georgia. See here for details.

Note: we have in mind pleasant and factual gossip. The most useful kind is about probable directions and emphases to make projects attractive to pursue. This leads into our other component.

Possible Problems To Present

Here are a problem from each of us as examples of what could be discussed in these meetings and why that might give advantage over just hunting the literature. Both are about factoring—always factoring…

Factoring: Ken

I, Ken, would like to know about field tests of approximative methods in quantum computing, specifically of shortcuts to Shor’s Algorithm. The approximations I have in mind are rougher than those I find in the literature and need not be physically natural.

To explain, the way Shor’s algorithm is proven correct in Shor’s paper and all textbooks we know—including ours—uses an exact analysis involving the quantum Fourier transform, in which exponentially fine phase angles appear in terms. Approximation can be argued in several ways. Circuits of Hadamard, CNOT, and -gates, in which no phase angle finer than appears, can approximate arbitrary quantum circuits to exponential precision with polynomial overhead. With just Hadamard and Toffoli gates, hence and as the only phases, one can approximate the data returned by measurements in the algorithm, though without approximating the algorithm’s result vectors in complex Hilbert space. There are other ways to approximate those vectors while eliding the finer phase components. We would like to see more attention to the concrete overheads of all these methods.

What I would really like to discuss, however, is efforts toward more-brusque approximations that could yield new classical attempts on factoring. For a broad example, note that not only does reduce to but also individual steps in Shor’s algorithm can be broken down as reductions to counting. Now suppose we apply approximate counting heuristics to those steps. The stock answer for why this doesn’t work to approximate quantum measurement properties globally is that those probabilities have the form

where and are functions and is something like . Note the knowledge beforehand that is between and . The point is that is exponential yet smaller than the additive approximations possible in polynomial time for and individually, so the approximation gives no help to the difference.

However, this does not prevent using approximations of magnitudes that are not differences at intermediate steps. For a vein of more particular examples, I raise the translation from quantum gates to Boolean formulas in my 2018 paper with Amlan Chakrabarti and my recent PhD graduate Chaowen Guan. This translation can encode the state at any intermediate stage of an execution of Shor’s algorithm by a Boolean formula . The size of stays linear in the size of the quantum circuit being simulated—the exponential explosion happens only when we try to count solutions to . The formula encodes all the information in , including the implicit presence of fine phase angles. Now suppose we alter to a whose corresponding is a simplified approximation of . The kicker is that might not need to be a legal quantum state. The transformations in our paper for later stages of the circuit will still apply building on .

Is there any chance of this working? Heuristic approaches applying SAT to factoring have been tried and found to be tough. The nice site BeyondNP includes links to #SAT counters such as sharpSAT and Cachet. Thus we are not asking anything outlandish. Leveraging Shor’s algorithm might be a new approach. Has anyone tried it? That’s the kind of question I would visit a conference to ask, where wider arity might work better than asking people individually. Thus also for raising it in a meeting.

Factoring: Dick

I have recently been thinking about the power of weak sub-theories of Peano Arithmetic. There are many proofs known that there are an infinite number of prime numbers. The usual proofs use this:

For all there is some prime that divides .

Given this it is not hard to prove, in many ways, that there are an infinite number of primes. Euclid’s original proof uses it in the step: Let divide . The idea is suppose some weak theory can prove the above. This means that it can prove:

I believe that this shows that if the theory is weak enough that this implies that factoring is in polynomial time. Is this known? Is it true?

Once again, we can hunt for literature on this. We can ask individual people, such as Avi Wigderson and various co-authors of his. But our hunch is that this topic was explored in the 1990s without a definitive resolution. It could be more effective to get up to speed on it and share ideas in a meeting.

Open Problems

Should we start a virtual theory lunch? Would you attend?

Added 6/21: Getting back to gossip, we wonder if the all-to-all nature of a Zoom meeting, versus few-to-few in a conference hallway, would filter out the badder kinds of gossip.