Simple tests of quantumness also certify qubits

DOI10.1007/978-3-031-38554-4_6MaRDI QIDQ6190136zbMATH OpenFDO

Authors Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, Thomas Vidick

Publication date 6 February 2024

Published in Advances in Cryptology – CRYPTO 2023 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.01293

Mathematics Subject Classification ID

Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx) Cryptography (94A60)

Abstract: 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. Certifying qubits was previously only known to be possible based on the hardness of the Learning with Errors problem and the use of adaptive hardcore (Brakerski et al., 2018). Our framework allows certification of qubits based only on the existence of post-quantum trapdoor claw-free functions, or on quantum fully homomorphic encryption. These can be instantiated, for example, from Ring Learning with Errors. On the technical side, we show that the quantum soundness of any such protocol can be reduced to proving a bound on a simple algorithmic task: informally, answering ``two challenges simultaneously in the protocol. Our reduction formalizes the intuition that these protocols demonstrate quantumness by leveraging the impossibility of rewinding a general quantum prover. This allows us to prove tight bounds on the quantum soundness of (Kahanamoku-Meyer et al., 2021) and (Kalai et al., 2022), showing that no quantum polynomial-time prover can succeed with probability larger than $co{s}^{2}fracpi8approx0.853$. Previously, only an upper bound on the success probability of classical provers, and a lower bound on the success probability of quantum provers, were known. We then extend this proof of quantum soundness to show that provers that approach the quantum soundness bound must perform almost anti-commuting measurements. This certifies that the prover holds a qubit.

Recommendations

• A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
• scientific article; zbMATH DE number 7651035
• Classical verification of quantum computations
• Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources
• How to Verify a Quantum Computation

Cites work

• A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
• Candidate trapdoor claw-free functions from group actions with applications to quantum protocols
• Classical homomorphic encryption for quantum circuits
• scientific article; zbMATH DE number 2086396 (Why is no real title available?)
• scientific article; zbMATH DE number 7651035 (Why is no real title available?)
• On lattices, learning with errors, random linear codes, and cryptography
• Proposed experiment to test local hidden-variable theories
• The computational complexity of linear optics
• The need for structure in quantum speedups

Cited in

(5)

• Candidate trapdoor claw-free functions from group actions with applications to quantum protocols
• Compiled nonlocal games from any trapdoor claw-free function
• On the power of oblivious state preparation
• Adaptive hardcore bit and quantum key leasing over classical channel from LWE with polynomial modulus
• How to verify that a small device is quantum, unconditionally

This page was built for publication: Simple tests of quantumness also certify qubits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6190136)