# SupercheQ: Quantum Advantage for Distributed Databases

Preprint · E. R. Anschuetz, P. Gokhale, B. Tonekaboni, C. Campbell, F. T. Chong, E. D. Dahl, P. Frederick, E. B. Jones, B. Hall, S. Issa, P. Goiporia, J. Liu, S. Lee, P. Noell, V. Omole, D. Owusu-Antwi, M. A. Perlin, R. Rines, M. Saffman, K. N. Smith, T. Tomesh

- Archive id: arxiv:2212.03850
- Published: 2022-12-07
- arXiv: https://arxiv.org/abs/2212.03850
- Citations: 5
- Source URL: https://arxiv.org/abs/2212.03850
- PDF: https://arxiv.org/pdf/2212.03850
- Provenance: arxiv

## Abstract

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 $2^{O(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 $\\mathrm{poly}(n^\\ell)$ depth to enable verification for files with $O(n^\\ell)$ bits for arbitrary constant $\\ell$. 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^{\\ell})$ bits), while supporting incremental updates to the fingerprint using only a constant number of $(\\ell-1)$-qubit gates. Moreover, Supercheq-IE at $\\ell=2$ ($\\geq 3$) only requires Clifford gates (gates in the $\\ell-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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.