2026-07-22T19:33:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16517 2024-03-06T10:57:43Z ddc:004 open_access

Memory Compression with Quantum Random-Access Gates Buhrman, Harry Loff, Bruno Patro, Subhasree Speelman, Florian complexity theory data structures algorithms quantum walk 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 log M 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 log M) memory, and runs in time Õ(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harry Buhrman and Bruno Loff and Subhasree Patro and Florian Speelman 2022 Is Part Of LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2022.10 urn:nbn:de:0030-drops-165177 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.10 eng https://creativecommons.org/licenses/by/4.0/legalcode