Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other related classes) and quantum computers. In his celebrated 1994 paper Papadimitriou introduced and systematically studied several important complexity classes like PLS, PPAD and others. (Papadimitriou's paper relied on some earlier papers and, in particular, as Aviad noted, PLS was introduced by Johnson-Papadimitriou-Yannakakis in 1988.)

My main question is:

Do quantum computers give some advantage for problems in $PPAD$? or in $PLS$? or in $PLS \cap PPAD$? etc...

Another question is if there is some quantum analogs of PLS and PPAD and Christos' other classes.

I note that a recent remarkable connections of PPAD to cryptography was found in these papers: On the cryptographic hardness of finding a Nash equilibrium‏ by N Bitansky, O Paneth, A Rosen and Can PPAD hardness be based on standard cryptographic assumptions? by A Rosen, G Segev, I Shahaf, and Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir by Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum. I also note that in my opinion Christos' classes are especially close to mathematics and mathematical proofs.

Update: Ron Rothblum commented (over FB) that the Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, and G. Rothblum's results implies that PPAD is plausibly beyond the power of quantum computers. (I will be happy to see an elaborated answer explaining it.)

One more comment: A related nice question is if finding the sink in a unique singe orientation of the $n$-cube has an efficient quantum algorithm. (I think this task is easier than $PLS$ but I am not sure how it is related to $PPAD$.) This is related to the quest to find quantum advantage for $LP$ see https://cstheory.stackexchange.com/a/767/712 .

enter image description here Happy birthday, Christos!

  • 1
    $\begingroup$ I have helped you to ask Prof. Umesh V. Vazirani about this question in Papafest. He feels this is an interesting question, but he has no answer now. $\endgroup$ – Rupei Xu Sep 10 '19 at 1:04
  • 1
    $\begingroup$ Regarding Unique-Sink-Orientation (USO), it was recently shown to reduce to a problem called Unique-End-Of-Potential-Line, which is (polynomially-equivalent) to End-of-Metered-Line (EOML). Both these problems lie in a class $CLS\subseteq PLS\cap PPAD$ which is, loosely-speaking, a "smooth" counterpart of PLS. The CHKPRR results also show how to build hard instances of EOML, and therefore CLS. However since it is not known if EOML reduces to USO, it could still be the case that USO is easy for quantum computers. $\endgroup$ – Occams_Trimmer Feb 14 at 13:51
  • $\begingroup$ Dear @Occams_Trimmer, is there reason to think that USO is hard for classical computers? E.g. is it complete for some of the classes you mentioned? $\endgroup$ – Gil Kalai Feb 14 at 13:59
  • 1
    $\begingroup$ No, it is not known to be complete for any class (as far as I know). Since USO is quite low in the hierarchy, it is plausible that it is easy in the classical case too. $\endgroup$ – Occams_Trimmer Feb 14 at 14:04

Two answers that I learnt while writing a blog post about this question

  1. No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. As Ron points out, this extends to computational complexity under plausible assumptions.

  2. Maybe: Nash equilibrium is arguably the flagship problem of "Christos classes". Here, giving players access to quantum entanglement suggests a new solution concept of "quantum correlated equilibrium" which generalizes Nash equilibrium. Its complexity is still open. See this cool paper by Alan Deckelbaum.

And one historical note: PLS was actually introduced by Johnson-Papadimitriou-Yannakakis in 1988.

| cite | improve this answer | |
  • 1
    $\begingroup$ Many thanks, Aviad! And welcome to the site! $\endgroup$ – Gil Kalai Sep 9 '19 at 7:07
  • $\begingroup$ Welcome Aviad! Your answer is excellent! I just moved my thing to the comment part(to avoid sharing voting scores from you :) ). $\endgroup$ – Rupei Xu Sep 10 '19 at 1:08
  • $\begingroup$ I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes "breaking Fiat-Shamir" hard for QC unlike, say "breaking RSA". $\endgroup$ – Gil Kalai Sep 11 '19 at 8:55

I will attempt to elaborate a bit on why CHKPRR shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers.

At a high level, CHKPRR builds a distribution over end-of-line instances where finding a solution requires to either:

  • break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or
  • solving a $\sharp \mathsf{P}$-complete problem

Intuitively, the reduction starts from a $\sharp \mathsf{SAT}$ instance. Counting requires an exponential number of polynomial steps; the authors make this counting incrementally verifiable by letting the counting procedure maintain a state, updated after every step, which proves the correctness of the computation so far. This incrementally verifiable counting procedure is then used to build an instance of the relaxed sink-of-verifiable-line problem, a promise problem which can be reduced to total search problems in $\mathsf{PPAD}$.

To instantiate this idea, the main technical challenge is to come up with a way to make the counting incrementally verifiable: we need a short, non-interactive proof at each step of the computation, which demonstrates correctness of the computation so far. Here, non-interactivity is the core issue; indeed we already know of a short interactive proof for demonstrating statements of the form $\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$, where $f$ is some low-degree $n$-variate polynomial over a field $\mathbb{F}$, which would work perfectly fine in this setting: the sumcheck protocol. Converting an interactive proof into a non-interactive one (maintaining public verifiability and compactness) is exactly what the Fiat-Shamir heuristic does.

Instantiating Fiat-Shamir

The Fiat-Shamir heuristic is very simple: fix some hash function, start with a public-coin interactive proof, and replace each random message of the verifier by a hash of the entire transcript so far. The question is then under which property of the hash function we can prove that the resulting protocol is still sound (note that it cannot be statistically sound anymore; the hope is that it remains computationally sound).

Before I elaborate on this, let me address your comment:

I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes "breaking Fiat-Shamir" hard for QC unlike, say "breaking RSA".

The high level description I gave should make it clear, I hope, that "breaking Fiat-Shamir" and "breaking RSA" are not really comparable problems. RSA is a concrete, specific hardness assumption, and if you can factor large integers, then you can break it.

On the other hand, the conjectured hardness of breaking Fiat-Shamir is a much more generic assumption. When you instantiate the Fiat-Shamir heuristic, you pick a concrete choice of hash function; but it suffices for the $\mathsf{PPAD}$-hardness result of CHKPRR that there exists some hash function for which Fiat-Shamir is sound. Breaking Fiat-Shamir with a quantum computer would require showing an attack against its soundness for any possible choice of the underlying hash function. At an intuitive level, this is not what quantum computers are good at, because this is a problem that does not seem to necessarily have a strong structure which it could exploit (unlike, e.g., discrete logarithm and RSA): hash functions can be typically very "unstructured".

In more concrete terms, there are two natural alternatives when picking a hash function to instantiate Fiat-Shamir:

The heuristic, concretely efficient approach:

pick your favorite hash function, say, SHA-3. We have of course no proof that instantiating Fiat-Shamir with SHA-3 gives us a hard problem; but neither do we know of any non-trivial attack on the soundness of proof systems obtained by applying Fiat-Shamir with SHA-3 to a non-degenerate interactive proof system. This extends to the quantum setting as well: we do not know of any quantum attack that does better than the usual quadratic speedup given by Grover's algorithm. After decades of cryptanalysis attempts, the consensus in the cryptographic community is that quantum algorithm do not seem, as far as we can see, to provide superpolynomial speedups for "Minicrypt-style" primitives (hash functions, PRGs, block ciphers, etc) without some strong underlying algebraic structure - such as SHA-2, SHA-3, AES, etc.

The provable security approach:

here the goal is to isolate a clean property of the hash function that makes the Fiat-Shamir heuristic sound, and to build a hash function which satisfies this properties under plausible cryptographic assumptions.

This provable security approach has a long and dense history in crypto. Among the most promising candidates is the notion of correlation-intractable hash functions: a (keyed) hash function is said to be correlation-intractable with respect to some relation $R$ if it is computationally infeasible, given a random hash key $K$, to find an input $x$ such that $(x, H_K(x)) \in R$. Intuitively, this captures what we want from Fiat-Shamir in a natural way: in an interactive proof system, where soundness is statistical, there exists some "bad verifier messages" which are very unlikely, but which would allow the prover to cheat. What we want is that the prover cannot compute a transcript such that, when computing the verifier's next message by hashing it, he manages to find one of those "bad messages". Any interactive proof system is therefore associated to some sparse relation $R$ that contains the pairs (transcript, bad message for this transcript), and Fiat-Shamir is sound when instantiated with a hash function which is correlation-intractable for this sparse relation $R$.

The question is now how to build correlation-intractable hash functions for relations we care about - and in this specific context, for the relation associated to the sumcheck protocol. Here, a recent line of work (essentially 1,2,3,4,5,6) has shown that, for many relations of interest, one can actually build correlation intractable hash functions under lattice-based assumptions.

Lattice-based cryptography is cryptographers' current best bet for building quantum-safe cryptographic primitives. For most problems over lattices considered by the crypto community, no better quantum algorithm is known than the usual "classical algorithm + Grover quadratic speedup". So, if we could base a correlation-intractable hash function for the sumcheck relation on a well-established lattice assumption, this would be seen in the crypto community as a very strong indication that quantum computers cannot always break Fiat-Shamir (hence, cannot solve $\mathsf{PPAD}$).

We are not exactly there, in fact. The recent breakthrough result of Peikert and Shiehian (the last paper in the list I gave previously) showed that for important relations, we can build correlation-intractable hash function under well-established lattice problems, such as learning with error, or the SIS problem; however, the sumcheck relation is not captured by this work.

Still, CHKPRR, building on this work showed that one can build a correlation-intractable hash function under the assumption that any of many concrete constructions of fully-homomorphic encryption schemes has quasi-optimal circular security against superpolynomial time attacks.

Let's break down this assumption:

  • Fully homomorphic encryption (FHE) is a primitive which we know how to build under a variety of lattice assumptions. If the scheme must only evaluate bounded size circuits, we know in fact how to build it under the standard learning with error assumption.
  • Circular security states that the FHE should be hard to break even when it is used to encrypt its own secret key. This is stronger than the usual security notion, which does not allow key dependent messages. It is a major and long standing open problem to build a circularly-secure FHE under a standard lattice assumption, such as LWE. Still, a decade after Gentry's first FHE construction and a lot of cryptanalysis attempts, the circular security of established FHE candidates has itself become a relatively safe-looking assumption (even against quantum computers), and we do not know of any attack that exploits key-dependent encryptions in a nontrivial way.
  • quasi-optimal hardness means that all polynomial algorithms have exponentially low probability of breaking the scheme (i.e., probability $2^{\omega(\log \lambda) - \lambda}$, where $\lambda$ is the security parameter). Note that while we might know non-trivial exponential time algorithms, that would break the scheme with non-negligible probability in time $2^{c\lambda}$ for some $c < 1$, we do not know of any polynomial time algorithm that breaks the scheme with a probability $2^{-c \lambda}$ for some $c < 1$.
  • Finally, we want all the above to still hold if we allow superpolynomial running time to the attacker. This is still in line with what known algorithms can achieve.

All in all, this is clearly not a great, highly plausible and well-established assumption. However, it creates a very interesting connection: it connects the hardness of solving $\mathsf{PPAD}$ with a quantum computer to the question of obtaining strong nontrivial improvements over the best known quantum algorithms to attack important lattice-based cryptographic primitives (fully homomorphic encryption), which is a well-investigated question.

Of course, one of the main open questions left by CHKPRR is to build a correlation-intractable hash function for the sumcheck relation under a better lattice-based assumption - ideally, the LWE assumption. This seems non-trivial, but not implausible, given that this is a very recent line of work, where many surprising results have already been achieved for other interesting relations.


Apparently, the above result has just been improved in this paper to rely solely on the subexponential hardness of LWE (together with the average case hardness of $\#$SAT). This is a major and impressive improvement (not yet peer reviewed, but from very strong researchers, hence very believable) which provides very strong support (essentially as strong as we could hope for using well-studied cryptographic assumptions) for the hypothesis that PPAD is beyond the power of quantum computers.

| cite | improve this answer | |
  • 1
    $\begingroup$ Dear Geoffroy, very many thanks for your great answer! $\endgroup$ – Gil Kalai Sep 12 '19 at 14:56
  • 1
    $\begingroup$ You are welcome. I just edited by answer to mention a very recent result that shows PPAD hardness under a much, much better assumption, the subexponential hardness of LWE, which is widely believed to hold against quantum computers. This essentially resolves the main open problem from the paper I discussed in my answer, of basing PPAD hardness on some of the most well-studied plausibly quantum-secure cryptographic assumption (the previous paper was more of a win-win result, showing that quantum attacks on PPAD hardness would provide non-trivial speedups for attacking important crypto schemes). $\endgroup$ – Geoffroy Couteau Jul 16 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.