Document type
Conference papers
Document subtype
Full paper
Title
Memory Compression with Quantum Random-Access Gates
Participants in the publication
Buhrman, Harry (Author)
Loff, Bruno (Author)
Dep. Matemática
Patro, Subhasree (Author)
Speelman, Florian (Author)
Summary
In the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may "compress" it into another algorithm which uses only m logM memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m logM) memory, and runs in time O~(T). We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.
Date of Submisson/Request
2022-07-04
Date of Acceptance
2022-07-04
Date of Publication
2022-07-04
Event
Theory of Quantum Computation (TQC 2022)
Publication Identifiers
Document Identifiers
DOI -
https://doi.org/10.4230/LIPIcs.TQC.2022.10