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

• Dimension Independent and Computationally Efficient Shadow Tomography [0.0]
  We describe a new shadow tomography algorithm that uses $n=Theta(sqrtmlog m/epsilon2)$ samples, for $m$ measurements and additive error $epsilon$. This stands in contrast to all previously known algorithms that improve upon the naive approach.
  arXiv  Detail & Related papers  (2024-11-03T03:07:35Z)
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings [0.0]
  A quantum random access memory (QRAM) is a promising architecture for realizing quantum oracles. We develop a new design for QRAM and implement it with Clifford+T circuit. We achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit count same.
  arXiv  Detail & Related papers  (2024-08-28T18:39:56Z)
• 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 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)
• 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.