Variational Quantum Linear Solver

• URL: http://arxiv.org/abs/1909.05820v4
• Date: Tue, 21 Nov 2023 16:31:34 GMT
• Title: Variational Quantum Linear Solver
• Authors: Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, Patrick J. Coles
• Abstract summary: We propose a hybrid quantum-classical algorithm for solving linear systems on near-term quantum computers. We numerically solve non-trivial problems of size up to $250times250$ using Rigetti's quantum computer.
• Score: 0.3774866290142281
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare $|x\rangle$ such that $A|x\rangle\propto|b\rangle$. We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision $\epsilon$ is achieved. Specifically, we prove that $C \geq \epsilon^2 / \kappa^2$, where $C$ is the VQLS cost function and $\kappa$ is the condition number of $A$. We present efficient quantum circuits to estimate $C$, while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of $1024\times1024$. Finally, we numerically solve non-trivial problems of size up to $2^{50}\times2^{50}$. For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in $\epsilon$, $\kappa$, and the system size $N$.

Related papers

• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ frackn = frac13 $. We demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs.
  arXiv  Detail & Related papers  (2024-10-05T11:56:15Z)
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations [7.319050391449301]
  We show that any quantum algorithm for solving systems of linear equations with time complexity has a lower bound on $Omega(kappa)$ on the depth of queries. The state-of-the-art quantum algorithm for this problem is due to Costa, An, Sanders, Su, Babbush, and Berry (2022), with optimal query complexity $Theta(kappa)$.
  arXiv  Detail & Related papers  (2024-07-08T15:05:46Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• High-Entanglement Capabilities for Variational Quantum Algorithms: The Poisson Equation Case [0.07366405857677226]
  This research attempts to resolve problems by utilizing the IonQ Aria quantum computer capabilities. We propose a decomposition of the discretized equation matrix (DPEM) based on 2- or 3-qubit entanglement gates and is shown to have $O(1)$ terms with respect to system size. We also introduce the Globally-Entangling Ansatz which reduces the parameter space of the quantum ansatz while maintaining enough expressibility to find the solution.
  arXiv  Detail & Related papers  (2024-06-14T16:16:50Z)
• Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
  We develop a quantum eigensolver based on a D-Wave Quantum Annealer (D-Wave QA) This approach performs iterative QA measurements to optimize the eigenstates $vert psi rangle$ without the derivation of a classical computer. We confirm that the proposed QE algorithm provides exact solutions within the errors of $5 times 10-3$.
  arXiv  Detail & Related papers  (2024-06-05T15:19:53Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Multi-Resolution Measurement with application to Quantum Linear Solver [0.0]
  We propose a quantum multi-resolution measurement (QMRM) that gives a solution with an accuracy $epsilon$ in $O(nlog(1/epsilon))$ measurements. The QMRM computational cost with an accuracy $epsilon$ is smaller than $O(n/epsilon2)$. We also propose an algorithm entitled QMRM-QLS (quantum linear solver) for solving a linear system of equations.
  arXiv  Detail & Related papers  (2023-04-12T16:31:44Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• 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)
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number [0.0]
  We show that solving a Quantum Linear System entails a runtime linear in $kappa$ when $A$ is positive definite. We present two new quantum algorithms featuring a quadratic speed-up in $kappa$.
  arXiv  Detail & Related papers  (2021-01-28T08:41:21Z)
• 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.