1. SupercheQ: Quantum Advantage for Distributed Databases
- Author
-
Gokhale, P., Anschuetz, E. R., Campbell, C., Chong, F. T., Dahl, E. D., Frederick, P., Jones, E. B., Hall, B., Issa, S., Goiporia, P., Lee, S., Noell, P., Omole, V., Owusu-Antwi, D., Perlin, M. A., Rines, R., Saffman, M., Smith, K. N., and Tomesh, T.
- Subjects
Quantum Physics - 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 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.
- Published
- 2022