Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoherent state exchange in multi-prover quantum interactive proof systems
137
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches 1. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.
rate research
Read More
We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, this proves that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP*, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the possibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed classical two-prover constant-bit interactive proof systems are known not to be entanglement-resistant. This is currently the strongest expressive power of any known constant-bit answer multi-prover interactive proof system that achieves a constant gap. Our result is based on an oracularizing property of certain private information retrieval systems, which may be of independent interest.
We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state rho and a collection of measurement operators such that (i) the probability of obtaining a particular outcome when a particular measurement is performed on rho is specified by the conditional probability distribution, and (ii) the measurement operators satisfy the constraints. For example, the constraints might specify that some measurement operators must commute. We show that if an instance of the quantum moment problem is unsatisfiable, then there exists a certificate of a particular form proving this. Our proof is based on a recent result in algebraic geometry, the noncommutative Positivstellensatz of Helton and McCullough [Trans. Amer. Math. Soc., 356(9):3721, 2004]. A special case of the quantum moment problem is to compute the value of one-round multi-prover games with entangled provers. Under the conjecture that the provers need only share states in finite-dimensional Hilbert spaces, we prove that a hierarchy of semidefinite programs similar to the one given by Navascues, Pironio and Acin [Phys. Rev. Lett., 98:010401, 2007] converges to the entangled value of the game. It follows that the class of languages recognized by a multi-prover interactive proof system where the provers share entanglement is recursive.
Coherent-one-way quantum key distribution (COW-QKD), possessing the simple experimental setup and the ability against the photon-number-splitting attack, has been implemented in various experiments and commercial applications. However, recent works have proved that current COW-QKD with key rate scaling linearly with transmittance is totally insecure under the zero-error attack. This conclusion leads to a crucial consequence that all the current attempts for practicalization are in vain. To solve this pending issue, here we conduct a minor revision on original COW-QKD while maintaining the original experimental setup as well as the simplicity of implementation. By more precisely estimating the amount of leaked information, we provide an explicit unconditional secure key rate which scales with $0.7%$ of the bound that quadratically scales with transmittance. Our work provides a revised COW-QKD which guarantees the availability of the current implementations of COW-QKD within 100 km and establishes the theoretical foundations for further application.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
