Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Congress of Mathematicians (ICM)

DELEGATING COMPUTATION VIA NO-SIGNALING STRATEGIES

Yael Tauman Kalai

Published May 1, 2019• 0 citations
Publisher

Abstract

Efficient verification of computation, also known as delegation of computation , is one of the most fundamental notions in computer science, and in particular it lies at the heart of the P vs. NP question. This article contains a high level overview of the evolution of proofs in computer science, and shows how this evolution is instrumental to solving the problem of delegating computation. We highlight a curious connection between the problem of delegating computation and the notion of no-signaling strategies from quantum physics.

DOI
10.1142/9789813272880_0184

Related papers

Verification of Quantum Computation: An Overview of Existing Approaches

Alexandru Gheorghiu, Theodoros Kapourniotis, Elham Kashefi

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification , has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.

arXiv:1709.06984•Theory of Computing Systems•Jul 6, 2018•209 citations

QUANTUM COMPUTATION: AN INTRODUCTION

Adriano Barenco

When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.

WORLD SCIENTIFIC eBooks•Oct 1, 1998•13 citations

How to Delegate Computations: The Power of No-Signaling Proofs

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

Journal of the ACM•Nov 29, 2021•18 citations

P Vs NP as a Physical Problem: From Topological Invariants to Hardware Implementation

Овчинников С. В.

The relevance of the research is determined by the fundamental nature of the P vs NP problem, which has been considered a central unsolved problem in theoretical computer science for more than half a century. In this article, for the first time, it is proved that the problem of solving the P vs NP problem is not a mathematical problem, but a physical problem, the solution of which depends on the physical implementation of the computing system. The aim of this paper is to prove that the solution of the P vs NP problem depends on the type of physical system used for calculations. The leading approach to research is to synthesize three independent paradigms: 1. Algebraic topology that provides invariants for complexity classification. 2. Quantum physics, which provides parallel information processing. 3. Apparat implementation on the GPU that demonstrates the physical limitations of classical computing. Author's results include: A formal proof that P ≠ NP holds in classical physics (Newtonian mechanics, deterministic computations) and a simultaneous proof that P = NP holds in quantum physics (superposition, entanglement). Experimental confirmation of the physical implementation through a series of computational experiments. Development of hybrid system that allows you to switch between modes depending on the available resources. The theoretical significance lies in rethinking the fundamental problem of complexity theory as a physical law. Practical significance is the creation of an adaptive computing system, the efficiency of which is determined by the available physical platform.

•Jan 22, 2026•0 citations

WHY QUANTUM COMPUTATION

H. F. Chau

In this talk, I briefly review the reasons why quantum computation is an interesting subject and why sometimes quantum computation required in order to perform certain tasks efficiently. This talk is addressed to physicists who are new to this area.

International Workshop on Non-Perturbative Methods and Lattice QCD•Apr 1, 2001•0 citations

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.

Leibniz international proceedings in informatics•Jan 1, 2019•3 citations
Efficient verification of computation, also known as delegation of computation , is one of the most fundamental notions in computer science, and in particular it lies at the heart of the P vs. NP question. This article contains a high level overview of the evolution of proofs in computer science, and shows how this evolution is instrumental to solving the problem of delegating computation. We highlight a curious connection between the problem of delegating computation and the notion of no-signaling strategies from quantum physics.
Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification , has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.
When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.
We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.
The relevance of the research is determined by the fundamental nature of the P vs NP problem, which has been considered a central unsolved problem in theoretical computer science for more than half a century. In this article, for the first time, it is proved that the problem of solving the P vs NP problem is not a mathematical problem, but a physical problem, the solution of which depends on the physical implementation of the computing system. The aim of this paper is to prove that the solution of the P vs NP problem depends on the type of physical system used for calculations. The leading approach to research is to synthesize three independent paradigms: 1. Algebraic topology that provides invariants for complexity classification. 2. Quantum physics, which provides parallel information processing. 3. Apparat implementation on the GPU that demonstrates the physical limitations of classical computing. Author's results include: A formal proof that P ≠ NP holds in classical physics (Newtonian mechanics, deterministic computations) and a simultaneous proof that P = NP holds in quantum physics (superposition, entanglement). Experimental confirmation of the physical implementation through a series of computational experiments. Development of hybrid system that allows you to switch between modes depending on the available resources. The theoretical significance lies in rethinking the fundamental problem of complexity theory as a physical law. Practical significance is the creation of an adaptive computing system, the efficiency of which is determined by the available physical platform.
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.