SupercheQ: Quantum Advantage for Distributed Databases
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 poly(n^l)
depth to enable verification for files with O(n^l) bits for arbitrary constant
l. The quantum advantage is achieved by random circuit sampling, thereby
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. The second variant, SupercheQ-IE (Incremental
Encoding), uses n qubits to verify files with O(n^2) bits while supporting
constant-time incremental updates to the fingerprint. Moreover, SupercheQ-IE
only requires Clifford gates, ensuring relatively modest overheads for
error-corrected implementation. We experimentally demonstrate proof-of-concepts
through Qiskit Runtime on IBM quantum hardware. We envision SupercheQ could be
deployed in distributed data settings, accompanying replicas of important
databases.
P. Gokhale E. R. Anschuetz C. Campbell F. T. Chong E. D. Dahl P. Frederick E. B. Jones B. Hall S. Issa P. Goiporia S. Lee P. Noell V. Omole D. Owusu-Antwi M. A. Perlin R. Rines M. Saffman K. N. Smith T. Tomesh