Fetching the paper…

Reading the bibliography…

2022

Memory Compression with Quantum Random-Access Gates

Buhrman, Harry, Loff, Bruno, Patro, Subhasree et al.

Original
PDF
Post on X

Understand

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.

Memory Compression with Quantum Random-Access Gates · Around

Built on

Quantum walk algorithm for element distinctness
A. Ambainis · 2004
Earlier work this paper cites.
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem
Greg Kuperberg · 2005
Earlier work this paper cites.
Quantum algorithms for the subset-sum problem
Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer · 2013
Earlier work this paper cites.

Similar

Frameworks for Quantum Algorithms
Stacey Jeffery · 2014
Cited alongside, same era.
On the quantum complexity of closest pair and related problems
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang · 2020
Cited alongside, same era.

Then

Optimal merging in quantum k-xor and k-sum algorithms
María Naya-Plasencia and André Schrottenloher · 2020
Later among the works it cites.
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks, 2021
Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman · 2021
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…