Lattice-Based Quantum Advantage from Rotated Measurements

Abstract

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-$X$ or $Z$ measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the $XY$-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.

36 pages. v2: added a future directions section and changed the formatting of the paper. v3: Quantum journal version

References in corpus (19)

• Quantum cryptography: Public key distribution and coin tossing
• Demonstration of a small programmable quantum computer with atomic qubits
• Coding Theorem and Strong Converse for Quantum Channels
• Universal blind quantum computation
• Quantum computing on encrypted data
• Basic circuit compilation techniques for an ion-trap quantum machine
• Universal Blind Quantum Computing with Weak Coherent Pulses
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• QFactory: classically-instructed remote secret qubits preparation
• Semi-Quantum Money
• Self-testing of a single quantum device under computational assumptions
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• On the possibility of classical client blind quantum computing
• Depth-efficient proofs of quantumness
• Security Limitations of Classical-Client Delegated Quantum Computing
• Efficient Certifiable Randomness from a Single Quantum Device
• Computational self-testing for entangled magic states
• Test of Quantumness with Small-Depth Quantum Circuits
• Parallel self-testing of EPR pairs under computational assumptions

Cited by in corpus (3)

• A computational test of quantum contextuality, and even simpler proofs of quantumness
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Zero-Knowledge Proofs of Quantumness