Block-encoding structured matrices for data input in quantum computing
- URL: http://arxiv.org/abs/2302.10949v2
- Date: Mon, 8 Jan 2024 10:49:12 GMT
- Title: Block-encoding structured matrices for data input in quantum computing
- Authors: Christoph S\"underhauf, Earl Campbell, Joan Camps
- Abstract summary: We show how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix.
The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The cost of data input can dominate the run-time of quantum algorithms. Here,
we consider data input of arithmetically structured matrices via block encoding
circuits, the input model for the quantum singular value transform and related
algorithms. We demonstrate how to construct block encoding circuits based on an
arithmetic description of the sparsity and pattern of repeated values of a
matrix. We present schemes yielding different subnormalisations of the block
encoding; a comparison shows that the best choice depends on the specific
matrix. The resulting circuits reduce flag qubit number according to sparsity,
and data loading cost according to repeated values, leading to an exponential
improvement for certain matrices. We give examples of applying our block
encoding schemes to a few families of matrices, including Toeplitz and
tridiagonal matrices.
Related papers
- Block encoding of sparse structured matrices coming from ocean acoustics in quantum computing [2.4487770108795393]
Block encoding is a data input model commonly used in a quantum computer.
New base scheme of block encoding is given which generalizes the one in citecamps2024 by removing the constraint that every data item should appear in all columns.
arXiv Detail & Related papers (2024-05-28T09:49:58Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks.
The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions.
We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
arXiv Detail & Related papers (2023-09-30T15:57:14Z) - FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
We propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner.
FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates.
We show that FABLE circuits can be compressed and sparsified.
arXiv Detail & Related papers (2022-04-29T21:06:07Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph.
Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework.
We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
arXiv Detail & Related papers (2022-03-28T02:24:08Z) - 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) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
We introduce a new inference scheme that avoids explicit construction of the covariance matrix.
Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm.
On several simulations, our method scales better than existing approaches in computation time and memory.
arXiv Detail & Related papers (2022-02-25T16:35:26Z) - 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) - Robust 1-bit Compressive Sensing with Partial Gaussian Circulant
Matrices and Generative Priors [54.936314353063494]
We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing.
We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
arXiv Detail & Related papers (2021-08-08T05:28:06Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Sparsifying Parity-Check Matrices [60.28601275219819]
We consider the problem of minimizing the number of one-entries in parity-check matrices.
In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages.
We propose a simple matrix row manipulation which alters the PCM, but not the code itself.
arXiv Detail & Related papers (2020-05-08T05:51:40Z)
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.