Tipo
Artigos em Conferência
Tipo de Documento
Artigo Completo
Título
Memory Compression with Quantum Random-Access Gates
Participantes na publicação
Buhrman, Harry (Author)
Loff, Bruno (Author)
Dep. Matemática
Patro, Subhasree (Author)
Speelman, Florian (Author)
Resumo
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.
Data de Submissão/Pedido
2022-07-04
Data de Aceitação
2022-07-04
Data de Publicação
2022-07-04
Evento
Theory of Quantum Computation (TQC 2022)
Identificadores da Publicação
Identificadores do Documento
DOI -
https://doi.org/10.4230/LIPIcs.TQC.2022.10