Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- URL: http://arxiv.org/abs/2302.01873v3
- Date: Mon, 20 May 2024 23:01:18 GMT
- Title: Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Authors: Samson Wang, Sam McArdle, Mario Berta,
- Abstract summary: We propose a class of randomized quantum algorithms for the task of sampling from matrix functions.
Our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures.
- Score: 3.4137115855910767
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For $N\times N$ Hermitian matrices, the space cost is $\log(N)+1$ qubits and depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size $O(N^2)$, when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these sub-routines to present a scheme for calculating Green's functions of quantum many-body systems.
Related papers
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
We propose a quantum algorithm inspired by the classical multi-row iteration method.
Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
arXiv Detail & Related papers (2024-09-06T03:32:02Z) - Quantum sampling algorithms for quantum state preparation and matrix block-encoding [0.0]
We first present an algorithm based on QRS that prepares a quantum state $|psi_frangle propto sumN_x=1 f(x)|xrangle$.
We then adapt QRS techniques to the matrix block-encoding problem and introduce a QRS-based algorithm for block-encoding a given matrix $A = sum_ij A_ij |irangle langle j|$.
arXiv Detail & Related papers (2024-05-19T03:46:11Z) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - 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) - 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) - Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices [4.2389474761558406]
We show how efficient quantum circuits can be explicitly constructed for some well-structured matrices.
We also provide implementations of these quantum circuits in sparse strategies.
arXiv Detail & Related papers (2022-03-19T03:50:16Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model.
These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z) - 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.