Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has a desired property, such as being 3-colorable or free of a predefined subgraph. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by one round of communication among neighbors. Later works consider extensions, called distributed interactive proofs, where the prover and the units can have multiple rounds of communication before the communication among the units. Recently, Bick, Kol, and Oshman (SODA '22) defined a zero-knowledge version of distributed interactive proofs, where the prover convinces the units that the network satisfies the property without revealing any additional information about the network's state or structure.

We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of QMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of an accepting witness can be computed in polynomial time, independently of the witness. Within this framework, we show advances in quantum zero-knowledge. We show the first commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a "sigma" protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let$\mathfrak{C}$be a class of polynomial-size concepts, and suppose that$\mathfrak{C}$can be PAC-learned with membership queries under the uniform distribution with error$1/2 -\gamma$by a time$T$quantum algorithm. We prove that if$\gamma^{2}\cdot T \ll 2^{n} /n$, then$\mathsf{BQE}\not\subset \mathfrak{C}$, where$\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$is an exponential-time analogue of$\mathsf{BQP}$. This result is optimal in both$\gamma$and$T$, since it is not hard to learn any class$\mathfrak{C}$of functions in (classical) time$T=2^{n}$(with no error), or in quantum time$T= \mathsf{poly}(n)$with error at most$1/2-\Omega(2^{-n/2})$via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

Despite the interest in the complexity class MA, the randomized analog of NP, just a few natural MA-complete problems are known. The first problem was found by (Bravyi and Terhal, SIAM Journal of Computing 2009); it was then followed by (Crosson, Bacon and Brown, PRE 2010) and (Bravyi, Quantum Information and Computation 2015). Surprisingly, two of these problems are defined using terminology from quantum computation, while the third is inspired by quantum computation and keeps a physical terminology. This prevents classical complexity theorists from studying these problems, delaying potential progress, e.g., on the NP vs. MA question. Here, we define two new combinatorial problems and prove their MA-completeness. The first problem, ACAC, gets as input a succinctly described graph, with some marked vertices. The problem is to decide whether there is a connected component with only unmarked vertices, or the graph is far from having this property. The second problem, SetCSP, generalizes standard constraint satisfaction problem (CSP) into constraints involving sets of strings. Technically, our proof that SetCSP is MA-complete is based on an observation by (Aharonov and Grilo, FOCS 2019), in which it was noted that a restricted case of Bravyi and Terhal's problem (namely, the uniform case) is already MA-complete; a simple trick allows to state this restricted case using combinatorial language. The fact that the first, more natural, problem of ACAC is MA-hard follows quite naturally from this proof, while the containment of ACAC in MA is based on the theory of random walks. We notice that the main result of Aharonov and Grilo carries over to the SetCSP problem in a straightforward way, implying that finding a gap-amplification procedure for SetCSP (as in Dinur's PCP proof) is equivalent to MA=NP. This provides an alternative new path towards the major problem of derandomizing MA.

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (${RLWE}$) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$; and if there exists no $2^{O(d^{1/\eta})}$-time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$), then there exists no $O(n^{ \log^{\nu} n} )$-time quantum learning algorithm for $poly(n)$-sized ${AC}^0$ circuits (for a constant $\nu>0$), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$, i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the MA-completeness of the problem of deciding whether the groundenergy of a uniform stoquastic local Hamiltonian is zero or inverse polynomial. We show that the gapped version of this problem, i.e. deciding if a given uniform stoquastic local Hamiltonian is frustration-free or has energy at least some constant ε, is in NP. Thus, if there exists a gap-amplification procedure for uniform stoquastic Local Hamiltonians (in analogy to the gap amplification procedure for constraint satisfaction problems in the original PCP theorem), then MA = NP (and vice versa). Furthermore, if this gap amplification procedure exhibits some additional (natural) properties, then P = RP. We feel this work opens up a rich set of new directions to explore, which might lead to progress on both quantum PCP and derandomization. We also provide two small side results of potential interest. First, we are able to generalize our result by showing that deciding if a uniform stoquastic Local Hamiltonian has negligible or constant frustration can be also solved in NP. Additionally, our work reveals a new MA-complete problem which we call SetCSP, stated in terms of classical constraints on strings of bits, which we define in the appendix. As far as we know this is the first (arguably) natural MA-complete problem stated in non-quantum CSP language.

In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP*, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP*, which is the set of languages decidable by MIP* protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP* = PZK-MIP*. This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP* protocol can be efficiently transformed into an equivalent zero knowledge MIP* protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results, we obtain the corollaries that i) all languages that can be solved in non-deterministic double exponential time have zero knowledge MIP* protocols and ii) all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP* protocols with vanishing promise gap.

The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers in multiple rounds of communication. In this work, we propose the first protocol where the client delegates her quantum computation to two servers in one-round of communication. Another advantage of our protocol is that it is conceptually simpler than previous protocols. The parameters of our protocol also make it possible to prove security even if the servers are allowed to communicate but respecting the plausible assumption that information cannot be propagated faster than speed of light, making it the first relativistic protocol for quantum computation.

International audience