Skip to content

Boaz’s inferior classical inferiority FAQ

October 24, 2019

(For better info, see Scott’s Supreme Quantum Superiority FAQ and also his latest post on the Google paper; also this is not really an FAQ but was inspired by a question about the Google paper from a former CS 121 student)

“Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

Paul Erdős (as quoted by Graham and Spencer, 1990, hat tip: Lamaze Tishallishmi)

In a Nature paper published this week, a group of researchers from John Martinis’s lab at Google announced arguably the first demonstration of “quantum supremacy” – a computational task carried out by a 53 qubit quantum computer that would require a prohibitive amount of time to simulate classically.

Google’s calculations of the “classical computation time” might have been overly pessimistic (from the classical point of view), and there has been work from IBM as well as some work of Johnnie Gray suggesting that there are significant savings to be made. Indeed, given the lessons that we learned from private key cryptography, where techniques such as linear and differential cryptanalysis were used to “shave factors from exponents”, we know that even if a problem requires exponential time in general, this does not mean that by being very clever we can’t make significant savings over the naive brute force algorithm. This holds doubly so in this case, where, unlike the designers of block ciphers, the Google researchers were severely constrained by factors of geometry and the kind of gates they can reliably implement.

I would not be terribly surprised if we will see more savings and even an actual classical simulation of the same sampling task that Google achieved. In fact, I very much hope this happens, since it will allow us to independently verify the reliability of Google’s chip and whether it actually did in fact sample from the distribution it is supposed to have sampled from (or at least rule out some “null hypothesis”). But this would not change the main point that the resources for classical simulation, as far as we know, scale exponentially with the number of qubits and their quality. While we could perhaps with great effort simulate a 53 qubit depth 20 circuit classically, once we reach something like 100 qubits and depth then all current approaches will be hopelessly behind.

In the language of my essay on quantum skepticism, I think this latest result, and the rest of the significant experimental progress that has been going on, all but rules out the possibility of “Skepticland” where there would be some fundamental physical reason why it is not possible to build quantum computers that offer exponential advantage in the amount of resources to achieve certain tasks over classical computers.

While the worlds of “Popscitopia” (quantum computers can do everything) and “Classicatopia” (there is an efficient classical algorithm to simulate BQP) remain mathematical possiblities (just as P=NP is), most likely we live in “Superiorita” where quantum computers do offer exponential advantage for some computational problems.

Some people question whether these kind of “special purpose” devices that might be very expensive to build are worth the investment. First of all (and most importantly for me), as I argued in my essay, exploring the limits of physically realizable computation is a grand scientific goal in its own right worthy of investment regardless of applications. Second, technology is now a 3.8 trillion dollar per year industry, and quantum computers are in a very real sense the first qualitatively different computing devices since the days of Babbage and Turing. Spending a fraction of a percent of the industry’s worth to the economy on exploring the potential for quantum computing seems like a good investment, even if there will be no practical application in the next decade or two. (By the same token, spending a fraction of a percent on exploring algorithm design and the limitations of classical algorithms is a very good investment as well.)

Is quantum supremacy here?

September 23, 2019

See Scott Aaronson’s blog. It seems like researchers in John Martinis’s group at Google might have managed to demonstrate that a quantum computer can produce samples passing a certain statistical test for which we know no efficient classical algorithm to do so.

Of course I can’t help but posting again the fake nytimes headline I produced for my 2016 crypto course when I wanted to motivate the study of so called “quantum-resistant cryptography”:

Information-Theoretic Cryptography (ITC) conference (guest post by Benny Applebaum)

September 23, 2019

[The following is a guest post by Benny Applebaum announcing a new conference on information theoretic cryptography – an area with both beautiful math and important applications. –Boaz]

Deal friends,
We are happy to announce the birth of a new conference on Information-Theoretic Cryptography (ITC). Information-theoretic cryptography studies security in the presence of computationally unbounded adversaries and covers a wide array of topics at the intersection of cryptography, coding theory, information-theory and theory of computation. Notable examples include randomness extraction and privacy amplification, secret sharing, secure multiparty computation and proof systems, private-information retrieval and locally decodable codes, authentication codes and non-malleable codes, differential privacy, quantum information processing, and information-theoretic foundations of physical-layer security. See for more information. 

ITC replaces the International Conference on Information Theoretic Security (ICITS), which was dedicated to the same topic and ran 2005-2017. ITC can be seen as a reboot of ICITS with a new name, a new steering committee and a renewed excitement.  (beware: there is  a fake website for ICITS 2019 created by a known fraudulent organization)  

The conference will have two tracks: a conference track and  a “greatest hits” track. The conference track will operate like a traditional conference with the usual review process and published proceedings. The “greatest hits” track consists of invited talks (not included in the proceedings) that highlight the most exciting recent advances in the area. We solicit nominations for “greatest hits” talks from the community.

The first ITC conference will take place in Boston, MA on June 17-19, 2020 (just before STOC).  The submission deadline for ITC 2020 is Dec 16, 2019 and the call for papers (including a nomination procedure for the greatest hits track) is available here:

Please submit your best work to ITC 2020! We hope to see many of you there!

best regards,The Steering Committee:  Benny Applebaum (Chair), Ivan Damgård , Yevgeniy Dodis,  Yuval Ishai, Ueli Maurer,  Kobbi Nissim, Krzysztof Pietrzak, Manoj Prabhakaran, Adam Smith, Yael Tauman Kalai, Stefano Tessaro, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs, Mary Wootters,  Chaoping Xing, Moti Yung

Swiss TCS winter school (guest post by David Steurer)

September 18, 2019

[Guest post by David Steurer – seems like a great opportunity! –Boaz]

The Swiss Winter School on Lower Bounds and Communication Complexity (10-14 February 2020, ) is the first in a series of annual winter schools in Theoretical Computer Science jointly organized by EPFL and ETH Zurich. The goal of the school is to educate top international theory PhD students about exciting recent developments in the field. The winter school will be held in Zinal, a mountain village in the Swiss Alps that has a long tradition of hosting academic workshops and that allows for nice excursions and stimulating discussions in a relaxed atmosphere.

This year’s installment features an exciting trinity of speakers: Kasper Green Larsen (Data Structure Lower Bounds), Raghu Meka (Communication Complexity) and Amir Shpilka (Algebraic complexity).

The application deadline is November 15th 2019, and acceptance notifications will be sent by December 1st 2019. The application form is available at Attendance of the winter school is free of charge and includes room and board (shared rooms).

Organizers: Michael Kapralov (EPFL), David Steurer (ETH) , Ola Svennson (EPFL)

Make equations blue in powerpoint

September 4, 2019

Microsoft Powerpoint has a surprisingly powerful equation editor, which also allows to use latex macros such as \alpha to get \alpha.

I’ve blogged about the equation editor before but one pet peeve of mine was that I like to have my math in a different color, but never found a way to do this automatically. I finally decided to invest the time and find out how to do it. After a mere several years of investigation, I am happy to report that it is in fact possible to do so using Visual Basic for Applications (VBA).

You can view the developer tab by following these instructions, and then click on “macros”, type a name such as All_eqs and click on “create” at which point you can add the following code:

Sub All_eqs()

Dim oSld As Slide
Dim oShp As Shape
Dim oShapes As Shapes
For Each oSld In ActivePresentation.Slides
  Set oShapes = oSld.Shapes
  For Each oShp In oShapes
   If oShp.HasTextFrame Then
      If oShp.TextFrame.HasText Then
                With oShp.TextFrame.TextRange
                    For x = 1 To .Characters.Count
                        If .Characters(x).Font.Name = "Cambria Math" Then
                            .Characters(x).Font.Color.RGB = RGB(0, 112, 192)
                        End If
                    Next x
                End With

    End If
    End If
    Next oShp
 Next oSld
End Sub

Update on the Safe ToC initiative (guest post by Sandy Irani)

August 30, 2019

[Guest post by Sandy Irani; see also the new website for more information on this initiative. –Boaz ]

Update and follow-up on the Safe ToC initiative: 

Last year, a group of us served on an ad hoc committee to combat harassment and discrimination in the Theory of Computing community.  In our report, we suggested a number of measures that the various theory conferences could adopt to help in this effort. At a minimum, we wanted conferences to adopt a code of conduct and to appoint volunteers to serve as ToC Advocates whose role will be to provide support to any individual who has experienced harassment at a conference.  Our full final report is now available here:

A small subset of the original committee along with Yuval Rabani in his capacity as IEEE TCMF chair are working on implementing some of the recommendations in the recent report. We have now launched a web site for the SafeToC Initiative:

So far, the support from the broader community has been strong. Quite a few conferences have passed resolutions to adopt the recommended practices in our report. The new web site lists all the participating conferences as well as the names of volunteers who have signed on to be ToC Advocates. The web site also provides information for ToC Advocates, conference organizers, and members of the ToC community. 

Participating conferences all have codes of conduct and are ensuring that participants agree to abide by the code as part of their registration process. In addition, some of these conferences are adopting new mechanisms for author-declared conflicts of interests. This is especially important if an author feels that he or she may receive an unfair review due to a previous harassment-related incident. 

Of course, the work is not done, and this important effort needs to continue. What can everyone do from here?

  • First, we are in need of trained ToC Advocates, to spread this important service around!  An advocate would be a designated conference attendee who would be available to provide support and information to anyone who has observed or experienced harassment at the conference The work is not difficult. Right now the training consists of an hour-long webinar sponsored by the ACM. We are envisioning one or two group Skype meetings per year to share experiences and best practices. If you are interested in serving as a ToC Advocate for a conference, you can contact someone on the steering committee for that conference.
  • Second, even if you are not serving as an Advocate, please familiarize yourself with the various codes of conduct, and perhaps even listen to a training video!  A larger community of invested bystanders who are aware of these issues and prepared to support and/or intervene as needed is critical. This does not have to mean formal reporting – even helping to diffuse a problematic situation or checking in on a colleague to be sure they are ok after a difficult conversation can make a big difference to someone involved in an incident.

We will continue to update the web page as participation in this effort grows. Thank you to everyone for helping to make our community a safe and welcoming place for everyone.

Erin Chambers
Martin Farach-Colton
Sandy Irani
Yuval Rabani

List of Resources:

Sensitivity conjecture proved!

July 2, 2019

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.)

The proof is beautiful and simple. I will write a few words here, but it is probably easier for you to just read the paper. The sensitivity conjecture was known to follow from the following statement: let G_n be the Boolean Cube which is the degree n graph on N=2^n vertices identified with \{0,1\}^n such that for every x,y\in \{0,1\}^n, x \sim y if their Hamming distance is one. Then, the maximum degree of every subgraph H of G_n of size >N/2 is at least \sqrt{n}.

Hao proves the above statement by showing that there is a signing of the N\times N adjacency matrix of G_n that turns it into a matrix with N/2 eigenvalues equaling +\sqrt{n} and N/2 eigenvalues equaling -\sqrt{n}. That is, he shows (using a simple but clever inductive argument, see the 5 line proof of his Lemma 2.2) that there is an N\times N matrix A with entries in \{ 0, \pm 1 \} whose nonzero entries correspond to the edges of the Boolean cube, and such that all the N eigenvalues of A are \pm \sqrt{n} and they sum up to zero. (Note that this makes sense since A should have the same Frobenius norm as the adjacency matrix of G_n. The Frobenius norm squared is both the sum of squares of entries, which is N\cdot n for G_n which is a degree n graph, and also equal to the sum of squares of the eigenvalues, which is N\cdot n if all eigenvalues are \pm \sqrt{n}.)

Once you have such a signing, the result follows from Cauchy’s Interlace Theorem that says that for every N\times N matrix A and any M\times M matrix B that is a principle sub-matrix of A,

\lambda_{1+N-M}(A) \leq \lambda_1(B) \leq \lambda_1(A)

where \lambda_1(A) \geq \lambda_2(A) \cdots \geq \lambda_N(A) are the eigenvalues of A and \lambda_1(B) is the maximum eigenvalue of B. A corollary of this (which is the only fact we need) is that if A has its top eigenvalue \lambda_1(A) with multiplicity K (i.e., \lambda_1(A)=\lambda_K(A)), then every principle sub-matrix B of order larger than N-K will satisfy \lambda_1(B) = \lambda_1(A). (In fact, we only need \lambda_1(B) \geq \lambda_1(A).)

Indeed, suppose that H is a subgraph of the Boolean cube of size M>N/2. Then the principle submatrix B of A corresponding to the vertices of H satisfies \lambda_1(B) \geq \lambda_{1+N-M}(A) = \sqrt{n} (since M>N/2 and the first N/2 eigenvalues of A are +\sqrt{n}). But it’s easy to show that for every matrix B the maximum eigenvalue of B is upper bounded by the maximum \ell_1 norm of its rows, which in our case is the maximum degree of the graph H.