Exact and efficient Lanczos method on a quantum computer
- URL: http://arxiv.org/abs/2208.00567v4
- Date: Fri, 19 May 2023 14:33:48 GMT
- Title: Exact and efficient Lanczos method on a quantum computer
- Authors: William Kirby, Mario Motta, and Antonio Mezzacapo
- Abstract summary: We present an algorithm that uses block encoding on a quantum computer to exactly construct a Krylov space.
The construction is exact in the sense that the Krylov space is identical to that of the Lanczos method.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present an algorithm that uses block encoding on a quantum computer to
exactly construct a Krylov space, which can be used as the basis for the
Lanczos method to estimate extremal eigenvalues of Hamiltonians. While the
classical Lanczos method has exponential cost in the system size to represent
the Krylov states for quantum systems, our efficient quantum algorithm achieves
this in polynomial time and memory. The construction presented is exact in the
sense that the resulting Krylov space is identical to that of the Lanczos
method, so the only approximation with respect to the exact method is due to
finite sample noise. This is possible because, unlike previous quantum Krylov
methods, our algorithm does not require simulating real or imaginary time
evolution. We provide an explicit error bound for the resulting ground state
energy estimate in the presence of noise. For our method to be successful
efficiently, the only requirement on the input problem is that the overlap of
the initial state with the true ground state must be $\Omega(1/\text{poly}(n))$
for $n$ qubits.
Related papers
- A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states.
It is executable on current (hybrid) quantum hardware and does not depend on quantum memory.
We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
arXiv Detail & Related papers (2024-05-29T14:40:24Z) - Quantum Algorithm for Signal Denoising [32.77959665599749]
The proposed algorithm is able to process textitboth classical and quantum signals.
Numerical results show that it is efficient at removing noise of both classical and quantum origin.
arXiv Detail & Related papers (2023-12-24T05:16:04Z) - Single-ancilla ground state preparation via Lindbladians [4.864474385178252]
We design a quantum algorithm for ground state preparation in the early fault tolerant regime.
As a Monte Carlo-style quantum algorithm, our method features a Lindbladian where the target state is stationary.
Our algorithm can prepare the ground state even when the initial state has zero overlap with the ground state.
arXiv Detail & Related papers (2023-08-30T00:11:19Z) - Quantum Thermal State Preparation [39.91303506884272]
We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations.
We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states.
Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
arXiv Detail & Related papers (2023-03-31T17:29:56Z) - Clifford Circuit Initialisation for Variational Quantum Algorithms [0.0]
We present an initialisation method for variational quantum algorithms applicable to intermediate scale quantum computers.
We numerically demonstrate the effectiveness of the technique, and how it depends on Hamiltonian structure, number of qubits and circuit depth.
arXiv Detail & Related papers (2022-07-04T15:59:33Z) - Probing finite-temperature observables in quantum simulators of spin
systems with short-time dynamics [62.997667081978825]
We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality.
We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
arXiv Detail & Related papers (2022-06-03T18:00:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Low-rank quantum state preparation [1.5427245397603195]
We propose an algorithm to reduce state preparation circuit depth by offloading computational complexity to a classical computer.
We show that the approximation is better on today's quantum processors.
arXiv Detail & Related papers (2021-11-04T19:56:21Z) - Iterative Quantum Assisted Eigensolver [0.0]
We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian.
Our algorithm builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers.
arXiv Detail & Related papers (2020-10-12T12:25:16Z) - Algorithms for quantum simulation at finite energies [0.7734726150561088]
We introduce two kinds of quantum algorithms to explore microcanonical and canonical properties of many-body systems.
One is a hybrid quantum algorithm that computes expectation values in a finite energy interval around its mean energy.
The other is a quantum-assisted Monte Carlo sampling method to compute other quantities.
arXiv Detail & Related papers (2020-06-04T17:40:29Z) - 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.