Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians

• URL: http://arxiv.org/abs/2309.12826v1
• Date: Fri, 22 Sep 2023 12:26:50 GMT
• Title: Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians
• Authors: Hui-Min Li, Zhi-Xi Wang, Shao-Ming Fei
• Abstract summary: We decompose $sigma_xotimes A$ into a sum of at most 7 and $(4d+1)$ Hermitian, one-sparse, and self-inverse operators. We explicitly design the quantum circuits to evaluate efficiently the loss function.
• Score: 0.9865722130817715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving a Poisson equation is generally reduced to solving a linear system with a coefficient matrix $A$ of entries $a_{ij}$, $i,j=1,2,...,n$, from the discretized Poisson equation. Although the variational quantum algorithms are promising algorithms to solve the discretized Poisson equation, they generally require that $A$ be decomposed into a sum of $O[\text{poly}(\text{log}_2n)]$ simple operators in order to evaluate efficiently the loss function. A tensor product decomposition of $A$ with $2\text{log}_2n+1$ terms has been explored in previous works. In this paper, based on the decomposition of sparse Hamiltonians we greatly reduce the number of terms. We first write the loss function in terms of the operator $\sigma_x\otimes A$ with $\sigma_x$ denoting the standard Pauli operator. Then for the one-dimensional Poisson equations with different boundary conditions and for the $d$-dimensional Poisson equations with Dirichlet boundary conditions, we decompose $\sigma_x\otimes A$ into a sum of at most 7 and $(4d+1)$ Hermitian, one-sparse, and self-inverse operators, respectively. We design explicitly the quantum circuits to evaluate efficiently the loss function. The decomposition method and the design of quantum circuits can also be easily extended to linear systems with Hermitian and sparse coefficient matrices satisfying $a_{i,i+c}=a_{c}$ for $c=0,1,\cdots,n-1$ and $i=0,\cdots,n-1-c$.

Related papers

• Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method [1.775629639045375]
  We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshevpoly approximation.<n>We derive the sufficient conditions for the diagonalization of the Carleman embedding matrix.<n>The success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution.
  arXiv  Detail & Related papers  (2025-10-21T19:14:23Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Arbitrary Boundary Conditions and Constraints in Quantum Algorithms for Differential Equations via Penalty Projections [5.720812431258812]
  Complicated boundary conditions are essential to accurately describe phenomena arising in nature and engineering.<n>We design an efficient quantum algorithms for solving differential equations with arbitrary boundary conditions.
  arXiv  Detail & Related papers  (2025-06-26T20:14:32Z)
• Variational quantum algorithm for the Poisson equation based on the banded Toeplitz systems [4.7487511537612335]
  We give a variational quantum algorithm for solving the discreted Poisson equation. We decompose the matrix $A$ and $A2$ into a linear combination of the corresponding banded Toeplitz matrix. Based on the decomposition of the matrix, we design quantum circuits that evaluate efficiently the cost function.
  arXiv  Detail & Related papers  (2025-04-21T03:07:49Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  The inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N2$ elements of the input operator--can be accomplished in $O(ksigma)$ time. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines.
  arXiv  Detail & Related papers  (2025-01-16T09:39:31Z)
• 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)
• A quantum central path algorithm for linear optimization [5.450016817940232]
  We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality. In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
  arXiv  Detail & Related papers  (2023-11-07T13:26:20Z)
• Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
  We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
  arXiv  Detail & Related papers  (2023-11-05T03:33:44Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems.
  arXiv  Detail & Related papers  (2023-07-13T08:46:19Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Variational Quantum algorithm for Poisson equation [4.045204834863644]
  We propose a Variational Quantum Algorithm (VQA) to solve the Poisson equation. VQA can be executed on Noise Intermediate-Scale Quantum (NISQ) devices. Numerical experiments demonstrate that our algorithm can effectively solve the Poisson equation.
  arXiv  Detail & Related papers  (2020-12-13T09:28:04Z)
• 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)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)

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.