Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification

• URL: http://arxiv.org/abs/2303.01545v2
• Date: Thu, 18 May 2023 01:09:30 GMT
• Title: Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
• Authors: Anand Natarajan and Tina Zhang
• Abstract summary: Kalai et al. defined a black-box cryptographic compilation procedure that applies to any nonlocal game. We make progress towards a full understanding of the quantum value of the single-prover protocols. We give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis.
• Score: 2.298932494750101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a step towards the goal of producing a general cryptographic 'compilation' procedure which can translate any entangled nonlocal game into a single-prover interactive protocol while preserving quantum completeness and soundness, using cryptography to simulate the separation between the provers. A candidate for such a procedure was introduced by Kalai et al. (STOC '23), who defined a black-box cryptographic compilation procedure that applies to any nonlocal game and showed that it preserves classical value. In this work, we make progress towards a full understanding of the quantum value of the single-prover protocols that result from applying the Kalai et al. compilation procedure to entangled games. For the special case of CHSH, we prove that the Tsirelson bound holds under the compilation procedure introduced by Kalai et al., and we also recover a strong version of the 'rigidity' property that makes CHSH so useful. As an application, we give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis. Our protocol replicates the functionality of Mahadev's protocol (FOCS '18) but with two advantages: (1) the protocol is conceptually intuitive and requires fewer bespoke ingredients, and the soundness analysis is simpler and directly follows the analysis of the nonlocal case, and (2) the soundness analysis does not explicitly use the assumption of a TCF or an adaptive hardcore bit, and only requires QFHE as a black box (though currently the only known constructions of QFHE use TCFs).

Related papers

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States [0.0]
  We turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol. We provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information.
  arXiv  Detail & Related papers  (2023-03-02T18:38:15Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  We study the performance of a practical continuous-variable (CV) quantum key distribution protocol. We focus on the Gaussian-modulated coherent-state protocol with heterodyne detection in a high signal-to-noise ratio regime. This allows us to study the performance for practical implementations of the protocol and optimize the parameters connected to the steps above.
  arXiv  Detail & Related papers  (2022-05-20T12:37:09Z)
• Quantum Advantage from Any Non-Local Game [14.903809621145893]
  We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game. Our compiler uses any quantum homomorphic encryption scheme.
  arXiv  Detail & Related papers  (2022-03-29T19:45:44Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• On Information-Theoretic Classical Verification of Quantum Computers [0.38073142980733]
  We show that any protocol from this family is bound to require an extremely powerful prover. We hint at possible ways one might try to realize a protocol where the prover can be weaker, namely a quantum computer.
  arXiv  Detail & Related papers  (2021-05-12T20:10:35Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  Continuous-variable quantum key distribution (QKD) employs the quadratures of a bosonic mode to establish a secret key between two remote parties. We consider a protocol with homodyne detection in the general setting of composable finite-size security. In particular, we analyze the high signal-to-noise regime which requires the use of high-rate (non-binary) low-density parity check codes.
  arXiv  Detail & Related papers  (2021-03-30T18:02:55Z)
• Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
  A client remotely prepares a quantum state using a classical channel. Privacy loss incurred by employing $RSP_CC$ as a sub-module is unclear. We show that a specific $RSP_CC$ protocol can replace the quantum channel at least in some contexts.
  arXiv  Detail & Related papers  (2020-07-03T13:15:13Z)
• Quantum Key-Distribution Protocols Based on a Quantum Version of the Monty Hall Game [0.0]
  The study proposed two quantum key-distribution protocols based on the quantum version of the Monty Hall game devised by Flitney and Abbott. The motivation behind the second proposal is to simplify a possible physical implementation by adapting the formalism of the qutrit protocol to use qubits and simple logical quantum gates.
  arXiv  Detail & Related papers  (2020-05-11T22:06:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.