2022/12/07 by E. R. Anschuetz, Gokhale, P., P. Gokhale +37
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2212.03850
openalex publication_date 2022/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We introduce Supercheq, a family of quantum protocols that achieves asymptotic advantage over classical protocols for checking the equivalence of files, a task also known as fingerprinting. The first variant, Supercheq-EE (Efficient Encoding), uses n qubits to verify files with 2O(n) bits -- an exponential advantage in communication complexity (i.e.~bandwidth, often the limiting factor in networked applications) over the best possible classical protocol in the simultaneous message passing setting. Moreover, Supercheq-EE can be gracefully scaled down for implementation on circuits with poly(n^ℓ) depth to enable verification for files with O(n^ℓ) bits for arbitrary constant ℓ. The quantum advantage is achieved by random circuit sampling, thereby potentially endowing circuits from recent quantum supremacy and quantum volume experiments with a practical application. We validate Supercheq-EE's performance at scale through GPU simulation motivated by Infleqtion's Sqale neutral atom QPU gateset. The second variant, Supercheq-IE (Incremental Encoding), also achieves arbitrary-polynomial advantage in fingerprint size (n qubits to verify files with size O(nℓ) bits), while supporting incremental updates to the fingerprint using only a constant number of (ℓ-1)-qubit gates. Moreover, Supercheq-IE at ℓ=2 (≥ 3) only requires Clifford gates (gates in the ℓ-1 level of the Clifford hierarchy), ensuring relatively modest overheads for error-corrected implementation. We experimentally demonstrate proof-of-concepts on quantum hardware from Diraq (spin qubit) and IBM (superconducting). We envision Supercheq could be deployed in distributed data settings, accompanying replicas of important databases.