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
- Quantum random power method for ground state computation [0.0]
We present a quantum-classical hybrid random power method that approximates a Hamiltonian ground state.
We show that our method converges to an approximation of a ground state of the Hamiltonian.
arXiv Detail & Related papers (2024-08-16T06:41:16Z) - 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) - Single-ancilla ground state preparation via Lindbladians [4.328210085579236]
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 be implemented using just one ancilla qubit and efficiently simulated on a quantum computer.
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) - Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
An ideal state preparation protocol can be characterized by being easily generated classically.
We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC)
We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
arXiv Detail & Related papers (2022-11-18T20:31:10Z) - 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) - 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.