# Techniques: A computational test of quantum contextuality, and even simpler proofs of quantumness

## What the paper contributes (one paragraph)

The paper shows how to turn any contextuality game into an operational "test of contextuality" that runs on a single quantum device interacted with classically, replacing the usual physical loopholes (such as the device being memoryless) with the single assumption that the device is computationally bounded. The construction adapts the KLVY non-local-game compiler, but instead of cryptographically enforcing spatial separation between two subsystems it enforces temporal separation between sequential measurements, re-using the encrypted post-measurement state across two rounds. The enabling tool is a new cryptographic primitive, the oblivious (Pauli) pad, which lets a prover obliviously re-encrypt a quantum state. Using the same ideas the authors build a streamlined two-round proof of quantumness from the classical hardness of Learning With Errors that needs only one coherent NTCF evaluation and a single qubit kept coherent between rounds.

## Techniques offered

- **Contextuality game compiler (cryptographic single-device test of contextuality)** - compiles an arbitrary contextuality game into a single-prover, two-round (four-message) operational test that an efficient quantum device passes but no efficient classical device can, assuming only a computationally bounded device.
  - guarantee: interactive completeness and soundness bounds under standard cryptographic assumptions (QFHE plus the oblivious pad, ultimately LWE); a QPT prover wins with probability at least (1 + valQu)/2 - negl, while any PPT prover wins with probability at most (1 + valNC)/2 + negl.
  - quote: "We show that, using cryptographic techniques, an arbitrary contextuality game can be compiled into an ``operational test of contextuality'' involving a single quantum device, where the only assumption is that the device is computationally bounded."

- **Oblivious (Pauli) pad** - a cryptographic primitive that takes a state and a public key and outputs a Pauli-padded state together with a ciphertext string, letting a prover obliviously "re-encrypt" a post-measurement state non-interactively so the verifier can later reveal an overall decryption key safely.
  - guarantee: computational indistinguishability via a distinguishing game; no PPT prover can distinguish the true decoded pad from a fresh uniformly random pad with non-negligible advantage, whereas a QPT prover can. Realised from LWE in the quantum random oracle model.
  - quote: "The main technical tool that we introduce to formalise this idea, which may find applications elsewhere, is a primitive that we call {\emph{oblivious (Pauli) pad}}."

- **Simplified two-round proof of quantumness** - a streamlined classical test of quantum advantage with a single device that needs only one coherent NTCF evaluation, one layer of single-qubit Hadamards, and a single qubit kept coherent between rounds.
  - guarantee: soundness from the classical hardness of LWE (a single application of the encrypted CNOT operation, no adaptive hardcore bit required); can be made non-interactive via the Fiat-Shamir transformation.
  - quote: "Our second contribution streamlines the ideas introduced to prove \Thmref{infMain1} in order to obtain a 2-round proof of quantumness relying on the classical hardness of the Learning-with-Errors (LWE) problem~\cite{LWE}."

## Where it could apply

- Target primitive(s): sampling / interactive protocols (proof of quantumness and operational test of contextuality); the encrypted-CNOT and NTCF machinery is generic quantum-advantage verification rather than VQE/QAOA/QPE.
- Target application group(s): platforms_tooling (verification of quantum advantage, foundational benchmarking of single untrusted devices); cross-cutting cryptographic primitives for quantum_ml or chemistry_materials verification only indirectly.
- Code family / hardware assumptions: hardware-agnostic; assumes a computationally bounded quantum device and standard cryptographic hardness (QFHE / LWE, with the oblivious pad in the quantum random oracle model heuristically instantiated by a hash function such as SHA3). No surface-code, qLDPC, neutral-atom, or photonic assumption.

## Caveats

The contributions are cryptographic protocols and a new primitive, not a code, decoder, or mitigation method that plugs into a chemistry, optimisation, or fault-tolerance pipeline. Suppliability to an external vendor or application result is indirect: these are tools for verifying quantum advantage and demonstrating contextuality on a single computationally bounded device, and they rest on cryptographic hardness assumptions (LWE, plus the quantum random oracle model for the oblivious pad). Bounds are asymptotic in a security parameter (negligible-function gaps), not concrete fidelities, and the proof of quantumness currently requires an LWE-based NTCF to implement the encrypted CNOT.