Skip to content

Some Real and Some Virtual News

June 21, 2020

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 {2^{4}} years. She told me that she could not wait for the next power of {2}, 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 {T}-gates, in which no phase angle finer than {\pi/4} appears, can approximate arbitrary quantum circuits to exponential precision with polynomial overhead. With just Hadamard and Toffoli gates, hence {0} and {\pi} 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 {\mathsf{BQP}} reduce to {\mathsf{\#P}} 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

\displaystyle  p = \frac{f_1(x) - f_2(x)}{D}

where {f_1} and {f_2} are {\mathsf{\#P}} functions and {D} is something like {2^{n/2}}. Note the knowledge beforehand that {p} is between {0} and {1}. The point is that {D} is exponential yet smaller than the additive approximations possible in polynomial time for {f_1(x)} and {f_2(x)} 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 {\Phi} at any intermediate stage of an execution of Shor’s algorithm by a Boolean formula {\phi}. The size of {\phi} stays linear in the size of the quantum circuit being simulated—the exponential explosion happens only when we try to count solutions to {\phi}. The formula {\phi} encodes all the information in {\Phi}, including the implicit presence of fine phase angles. Now suppose we alter {\phi} to a {\phi'} whose corresponding {\Phi'} is a simplified approximation of {\Phi}. The kicker is that {\Phi'} 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 {\phi'}.

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 {x>1} there is some prime {p} that divides {x}.

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 {p} divide {p_{1}\cdots p_{n} + 1}. The idea is suppose some weak theory can prove the above. This means that it can prove:

\displaystyle  \forall x>1 \ \exists y \ y|x \text{ and } \mathsf{prime}(y).

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.

14 Comments leave one →
  1. June 21, 2020 10:44 am

    Discussions of viral contagion, biological and dis-informational, come up a lot on the blogs and FB pages I frequent. My usual slogan is, “Funny how all viruses work alike”, by which I mean they all seem to aim at creating mass quantities of copies of themselves to the detriment and destruction of their hosts. Funny as a broken body or mind or society, I guess. My last bit of wit on FB by way of a theoretical perspective went a bit like this —

  2. June 21, 2020 11:03 am

    Thanks for linking to us 🙂

  3. June 22, 2020 4:50 am

    If factoring is polynomial, that immediately
    means according to my paper that P=NP:

  4. Anuj Dawar permalink
    June 22, 2020 3:03 pm

    I supervised a Master’s project (by Louis-Pascal Xhonneux) that did exactly what you suggest: use model counters like Cachet and sharpSAT to simulate Shor’s algorithm in an attempt to factor. It proved pretty hopeless. They both failed to factor 15 after 36 hours on a high-performance cluster.

    • June 23, 2020 4:07 pm

      Anuj, indeed, that was our experience too when attempting to simulate the algorithm exactly. But have you tried ways of “cheating” it? That’s what my Q is about.

      • Anuj Dawar permalink
        June 24, 2020 6:02 am

        No, not the kind of cheat you suggest – of tweaking the formula to an approximate one. We did try an approximate model counter on the exact formula: ApproxMC. It proved even slower the Cachet or sharpSAT.

      • Christoph Haase permalink
        June 25, 2020 6:16 pm

        Anuj, the phenomena you observed are not too suprising: At least in 2018, there was a lot of progress on exact model counting, and said exact model counters would outperform approximate ones by a factor of up to 10.

  5. June 24, 2020 4:18 pm

    Sometimes I feel this news is virtually real, but at other times, it seems really virtual …

    • June 26, 2020 12:46 pm

      Hi, Vijay, 🙂 Don’t know why the mod algorithm snagged this.

      • Vijay Vazirani permalink
        June 26, 2020 1:19 pm

        It was being more proper then you intended it to be 🙂

    • rjlipton permalink*
      June 26, 2020 12:46 pm

      Dear Vijay:

      Thanks for your comment. Too much news is virtual. Hope you are doing well—both real and virtually.

      Best and stay safe


      • Vijay Vazirani permalink
        June 26, 2020 1:20 pm

        Thanks Dick! Hope you too.
        Fortunately Newport beach is still real — and open!


  1. Taking a Problem Down a Peg | Gödel's Lost Letter and P=NP
  2. Intellectual Fireworks? | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s