Efficient quantum linear solver algorithm with detailed running costs
- URL: http://arxiv.org/abs/2305.11352v1
- Date: Fri, 19 May 2023 00:07:32 GMT
- Title: Efficient quantum linear solver algorithm with detailed running costs
- Authors: David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger,
Yi\u{g}it Suba\c{s}{\i}
- Abstract summary: We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As we progress towards physical implementation of quantum algorithms it is
vital to determine the explicit resource costs needed to run them. Solving
linear systems of equations is a fundamental problem with a wide variety of
applications across many fields of science, and there is increasing effort to
develop quantum linear solver algorithms. Here we introduce a quantum linear
solver algorithm combining ideas from adiabatic quantum computing with
filtering techniques based on quantum signal processing. We give a closed
formula for the non-asymptotic query complexity $Q$ -- the exact number of
calls to a block-encoding of the linear system matrix -- as a function of
condition number $\kappa$, error tolerance $\epsilon$ and block-encoding
scaling factor $\alpha$. Our protocol reduces the cost of quantum linear
solvers over state-of-the-art close to an order of magnitude for early
implementations. The asymptotic scaling is $O(\kappa \log(\kappa/\epsilon))$,
slightly looser than the $O(\kappa \log(1/\epsilon))$ scaling of the
asymptotically optimal algorithm of Costa et al. However, our algorithm
outperforms the latter for all condition numbers up to $\kappa \approx
10^{32}$, at which point $Q$ is comparably large, and both algorithms are
anyway practically unfeasible. The present optimized analysis is both
problem-agnostic and architecture-agnostic, and hence can be deployed in any
quantum algorithm that uses linear solvers as a subroutine.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - 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) - Fast quantum algorithm for differential equations [0.5895819801677125]
We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs.
Our algorithm generates a quantum state that enables extracting features of the solution.
arXiv Detail & Related papers (2023-06-20T18:01:07Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability.
The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model.
An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
arXiv Detail & Related papers (2023-04-06T02:18:52Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.
Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
arXiv Detail & Related papers (2023-02-16T13:57:19Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15: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) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
The complexity of our algorithm is $O(rm polylog(n/epsilon))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$.
Our algorithm exponentially accelerates the solution of QNSE and has wide applications in all kinds of nonlinear problems.
arXiv Detail & Related papers (2021-12-03T00:27:16Z) - Optimal scaling quantum linear systems solver via discrete adiabatic
theorem [0.9846257338039974]
We develop a quantum algorithm for solving linear systems that is discreteally optimal.
Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.
arXiv Detail & Related papers (2021-11-16T00:21:37Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.
The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.
It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
arXiv Detail & Related papers (2020-02-20T17:52:18Z) - High-precision quantum algorithms for partial differential equations [1.4050836886292872]
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm.
We develop quantum algorithms based on adaptive-order finite difference methods and spectral methods.
Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound.
arXiv Detail & Related papers (2020-02-18T20:32:45Z)
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.