Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
- URL: http://arxiv.org/abs/2006.04880v3
- Date: Thu, 6 May 2021 20:57:50 GMT
- Title: Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
- Authors: Uma Girish, Ran Raz, Wei Zhan
- Abstract summary: 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.
- Score: 7.510385608531827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a quantum logspace algorithm for powering contraction matrices, that
is, matrices with spectral norm at most~1. The algorithm gets as an input an
arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq
\mathrm{poly}(n)$ and outputs the entries of $A^T$, up to (arbitrary)
polynomially small additive error. The algorithm applies only unitary
operators, without intermediate measurements. We show various implications and
applications of this result:
First, we use this algorithm to show that the class of quantum logspace
algorithms with only quantum memory and with intermediate measurements is
equivalent to the class of quantum logspace algorithms with only quantum memory
without intermediate measurements. This shows that the deferred-measurement
principle, a fundamental principle of quantum computing, applies also for
quantum logspace algorithms (without classical memory). More generally, we give
a quantum algorithm with space $O(S + \log T)$ that takes as an input the
description of a quantum algorithm with quantum space $S$ and time $T$, with
intermediate measurements (without classical memory), and simulates it
unitarily with polynomially small error, without intermediate measurements.
Since unitary transformations are reversible (while measurements are
irreversible) an interesting aspect of this result is that it shows that any
quantum logspace algorithm (without classical memory) can be simulated by a
reversible quantum logspace algorithm. This proves a quantum analogue of the
result of Lange, McKenzie and Tapp that deterministic logspace is equal to
reversible logspace [LMT00].
Finally, we use our results to show non-trivial classical simulations of
quantum logspace learning algorithms.
Related papers
- A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
We introduce a novel quantum XZ24 algorithm, designed for efficiently computing the eigen-energy spectra of any quantum systems.
Compared to existing quantum methods, the new algorithm stands out for its remarkably low measurement cost.
We anticipate that the new algorithm will drive significant progress in quantum system simulation and offer promising applications in quantum computing and quantum information processing.
arXiv Detail & Related papers (2024-06-01T04:31:43Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix.
This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup.
We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
arXiv Detail & Related papers (2023-11-07T22:52:56Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [7.962205145083434]
We propose the first online quantum algorithm for zero-sum games with $tilde O(1)$ regret under the game setting.
Our quantum algorithm computes an $varepsilon$-approximate Nash equilibrium of an $m times n$ matrix zero-sum game in quantum time.
arXiv Detail & Related papers (2023-04-27T14:02:54Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z) - Quantum advantage for computations with limited space [6.327095331866255]
We consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on.
We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$- by quantum circuits, leveraging custom two-qubit gates.
arXiv Detail & Related papers (2020-08-14T17:31:12Z) - 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)
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.