Memory Compression with Quantum Random-Access Gates
- URL: http://arxiv.org/abs/2203.05599v1
- Date: Thu, 10 Mar 2022 19:27:53 GMT
- Title: Memory Compression with Quantum Random-Access Gates
- Authors: Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
- Abstract summary: We show an analogous result for quantum algorithms equipped with quantum random-access gates.
It is often possible to construct a space-inefficient, yet sparse, quantum data structure.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 $\tilde 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.
Related papers
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
Cumulative memory is a measure of time-space complexity.
We prove the first lower bounds on cumulative memory complexity for both sequential classical computation and quantum circuits.
arXiv Detail & Related papers (2023-01-13T17:57:02Z) - Quantum Subroutine Composition [1.1802674324027231]
In quantum algorithms, a subroutine may be called on a superposition of different inputs, which complicates things.
We prove this by using the technique of multidimensional quantum walks, recently introduced in arXiv:2208.13492.
The same technique that allows us to compose quantum subroutines in quantum walks can also be used to compose in any quantum algorithm.
arXiv Detail & Related papers (2022-09-28T14:52:13Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
We study the power of quantum memory for learning properties of quantum systems and dynamics.
Many state-of-the-art learning algorithms require access to an additional external quantum memory.
We show that this trade-off is inherent in a wide range of learning problems.
arXiv Detail & Related papers (2021-11-10T19:03:49Z) - Low-depth Quantum State Preparation [3.540171881768714]
A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=lceil logNrceil$-qubit state.
Here we investigate this space-time tradeoff in quantum state preparation with classical data.
We propose quantum algorithms with $mathcal O(n2)$ circuit depth to encode any $N$ complex numbers.
arXiv Detail & Related papers (2021-02-15T13:11:43Z) - Quantum Logspace Algorithm for Powering Matrices with Bounded Norm [7.510385608531827]
We give a quantum logspace algorithm for powering contraction matrices, that is, with spectral norm at most1.
The algorithm applies only unitary operators, without intermediate measurements.
This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms.
arXiv Detail & Related papers (2020-06-08T19:01:04Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.