Classical Verification of a Remote Quantum Processor via Degenerate Concordant Computations: An Application to Randomness Generation
Abstract
A client renting a cloud quantum processor cannot easily tell whether its bitstrings came from a quantum device. Certification by random circuit sampling runs on present hardware, but scoring each sample costs O(2n). We give a protocol in which the client scores each round in O(n) time, based on degenerate concordant ensembles: mixed states that are classical probability distributions over a product basis, with several basis states sharing a probability. For such a state, every concordance-preserving gate factorizes into local basis changes, a relabeling of basis states, and a block factor rotating labels of equal probability. This factor commutes with the state, so it cancels from the ensemble while entangling each pure component. The client holds a secret parity whose cosets are the degenerate sectors of every layer, enabling circuit construction and ensemble prediction with one inner product per layer. The secret never leaves the client. Uniformly random inputs are sent, and the client privately records each input's eigenvalue in the hidden state. An input--output agreement test and a weighted collision test compare server samples with the computation's non-flat output distribution. We prove completeness, client efficiency, and soundness in an ideal model where the compiled circuit reveals nothing about the secret; a classical server holding it passes. For the explicit construction, we prove that the single-qubit symmetry test used in efficient concordant-computation simulations fails on non-product inputs with unbiased marginals. We also find that a published local-basis finder halts on every tested layer, the transmitted component attains maximal Schmidt rank, the circuit is non-Clifford, and matrix-product spoofers are rejected. Soundness of the explicit construction remains conjectural.
Related
- Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
- Typed Transverse Momentum Parton distribution function computations
- Randomness can be certified in energy-constrained semi-device-independent scenarios
- Lattice dynamics of disordered phases of silicon and spatially resolved computations of thermal conductivity
- Simple QKD keyrate computations from tangent-line bounds
BibTeX
@misc{das2026classical,
title = {{Classical Verification of a Remote Quantum Processor via Degenerate Concordant Computations: An Application to Randomness Generation}},
author = {Bishal Kumar Das and Lakshya Priyadarshi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08185},
eprint = {2610.08185},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08185},
}
RIS
TY - UNPB
TI - Classical Verification of a Remote Quantum Processor via Degenerate Concordant Computations: An Application to Randomness Generation
AU - Bishal Kumar Das
AU - Lakshya Priyadarshi
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.08185
UR - https://arxiv.org/abs/2610.08185
AB - A client renting a cloud quantum processor cannot easily tell whether its bitstrings came from a quantum device. Certification by random circuit sampling runs on present hardware, but scoring each sample costs O(2^n). We give a protocol in which the client scores each round in O(n) time, based on degenerate concordant ensembles: mixed states that are classical probability distributions over a product basis, with several basis states sharing a probability. For such a state, every concordance-preserving gate factorizes into local basis changes, a relabeling of basis states, and a block factor rotating labels of equal probability. This factor commutes with the state, so it cancels from the ensemble while entangling each pure component. The client holds a secret parity whose cosets are the degenerate sectors of every layer, enabling circuit construction and ensemble prediction with one inner product per layer. The secret never leaves the client. Uniformly random inputs are sent, and the client privately records each input's eigenvalue in the hidden state. An input--output agreement test and a weighted collision test compare server samples with the computation's non-flat output distribution. We prove completeness, client efficiency, and soundness in an ideal model where the compiled circuit reveals nothing about the secret; a classical server holding it passes. For the explicit construction, we prove that the single-qubit symmetry test used in efficient concordant-computation simulations fails on non-product inputs with unbiased marginals. We also find that a published local-basis finder halts on every tested layer, the transmitted component attains maximal Schmidt rank, the circuit is non-Clifford, and matrix-product spoofers are rejected. Soundness of the explicit construction remains conjectural.
ER -