S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for unstructured sparse matrices

• URL: http://arxiv.org/abs/2401.04234v1
• Date: Mon, 8 Jan 2024 20:57:16 GMT
• Title: S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for unstructured sparse matrices
• Authors: Parker Kuklinski, Benjamin Rempfer
• Abstract summary: The Fast Approximate BLock-Lazy algorithm (FABLE) is a technique to block-encode arbitrary $Ntimes N$ dense matrices into quantum circuits. We describe two modifications of FABLE to efficiently encode sparse matrices.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Fast Approximate BLock-Encoding algorithm (FABLE) is a technique to block-encode arbitrary $N\times N$ dense matrices into quantum circuits using at most $O(N^2)$ one and two-qubit gates and $\mathcal{O}(N^2\log{N})$ classical operations. The method nontrivially transforms a matrix $A$ into a collection of angles to be implemented in a sequence of $y$-rotation gates within the block-encoding circuit. If an angle falls below a threshold value, its corresponding rotation gate may be eliminated without significantly impacting the accuracy of the encoding. Ideally many of these rotation gates may be eliminated at little cost to the accuracy of the block-encoding such that quantum resources are minimized. In this paper we describe two modifications of FABLE to efficiently encode sparse matrices; in the first method termed Sparse-FABLE (S-FABLE), for a generic unstructured sparse matrix $A$ we use FABLE to block encode the Hadamard-conjugated matrix $H^{\otimes n}AH^{\otimes n}$ (computed with $\mathcal{O}(N^2\log N)$ classical operations) and conjugate the resulting circuit with $n$ extra Hadamard gates on each side to reclaim a block-approximation to $A$. We demonstrate that the FABLE circuits corresponding to block-encoding $H^{\otimes n}AH^{\otimes n}$ significantly compress and that overall scaling is empirically favorable (i.e. using S-FABLE to block-encode a sparse matrix with $\mathcal{O}(N)$ nonzero entries requires approximately $\mathcal{O}(N)$ rotation gates and $\mathcal{O}(N\log N)$ CNOT gates). In the second method called `Lazy' Sparse-FABLE (LS-FABLE), we eliminate the quadratic classical overhead altogether by directly implementing scaled entries of the sparse matrix $A$ in the rotation gates of the S-FABLE oracle. This leads to a slightly less accurate block-encoding than S-FABLE, while still demonstrating favorable scaling to FABLE similar to that found in S-FABLE.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
  The problem of encoded quantum gate generation is studied in this paper. The emphReference Input Generation Algorithm (RIGA) is generalized in this work.
  arXiv  Detail & Related papers  (2024-09-02T10:41:15Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  We show that our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. In particular, our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. Our main algorithm can be viewed as a randomized block coordinate descent method.
  arXiv  Detail & Related papers  (2023-12-14T12:53:34Z)
• Block encoding of matrix product operators [0.0]
  We present a procedure to block-encode a Hamiltonian based on its matrix product operator (MPO) representation. More specifically, we encode every MPO tensor in a larger unitary of dimension $D+2$, where $D = lceillog(chi)rceil$ is the number of subsequently contracted qubits that scales logarithmically with the virtual bond dimension.
  arXiv  Detail & Related papers  (2023-12-14T12:34:24Z)
• Improved Synthesis of Toffoli-Hadamard Circuits [1.7205106391379026]
  We show that a technique introduced by Kliuchnikov in 2013 for Clifford+$T$ circuits can be straightforwardly adapted to Toffoli-Hadamard circuits. We also present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits.
  arXiv  Detail & Related papers  (2023-05-18T21:02:20Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
  We develop sparse co-occuring directions, which reduces the time complexity to $widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$ in expectation. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD.
  arXiv  Detail & Related papers  (2020-09-08T05:39:19Z)

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.