Search Results for « Quantum Krylov algorithms »

Abstract We introduce a multireference selected quantum Krylov (MRSQK) algorithm suitable for quantum simulation of many-body problems. MRSQK is a low-cost alternative to the quantum phase estimation algorithm that generates a target state as a linear combination of non-orthogonal Krylov basis states. This basis is constructed from a set of reference states via real-time evolution; thus, avoiding the numerical optimization of parameters. An efficient algorithm for the evaluation of the off-diagonal matrix elements of the overlap and Hamiltonian matrices is discussed and a selection procedure is introduced to identify a basis of orthogonal references that ameliorates the linear dependency problem. Preliminary benchmarks on linear H6, H8, and BeH2 indicate that MRSQK can predict the energy of these systems accurately using very compact Krylov bases.

This work provides a nonasymptotic error analysis of quantum Krylov algorithms based on real-time evolutions, subject to generic errors in the outputs of the quantum circuits. We prove upper and lower bounds on the resulting ground state energy estimates, and the error associated to the upper bound is linear in the input error rates. This resolves a misalignment between known numerics, which exhibit approximately linear error scaling, and prior theoretical analysis, which only provably obtained scaling with the error rate to the power 23 . Our main technique is to express generic errors in terms of an effective target Hamiltonian studied in an effective Krylov space. These results provide a theoretical framework for understanding the main features of quantum Krylov errors.

We present a quantum algorithm to evaluate matrix elements of functions of unitary operators. The method is based on calculating quadrature nodes and weights using data collected from a quantum processor. Given a unitary $U$ and quantum states $|ψ_0\rangle$, $|ψ_1\rangle$, the resulting quadrature rules form a functional that can then be used to classically approximate $\langleψ_1|f(U)|ψ_0\rangle$ for any function $f$. In particular, the algorithm calculates Szegö quadrature rules, which, when $f$ is a Laurent polynomial, have the optimal relation between degree of $f$ and number of distinct quantum circuits required. The unitary operator $U$ could approximate a time evolution, opening the door to applications like estimating properties of Hamiltonian spectra and Gibbs states, but more generally could be any operator implementable via a quantum circuit. We expect this algorithm to be useful as a subroutine in other quantum algorithms, much like quantum signal processing or the quantum eigenvalue transformation of unitaries. Key advantages of our algorithm are that it does not require approximating $f$ directly, via a series expansion or in any other way, and once the output functional has been constructed using the quantum algorithm, it can be applied to any $f$ classically after the fact.

Quantum Krylov algorithms are a promising approach for ground-state energy estimation on near-term quantum computers. However, their sampling cost is inherently high because each Hamiltonian term is measured individually. Despite various mitigation techniques, this overhead remains a bottleneck for large-scale electronic structure problems. We introduce mirror subspace diagonalization (MSD), which approaches the theoretical lower bound on the sampling cost for quantum Krylov algorithms built upon real-time evolution. MSD uses a finite-difference formula to express the Hamiltonian as a linear combination of time-evolution unitaries with symmetrically shifted timesteps, enabling efficient estimation of the Hamiltonian matrix within the Krylov subspace. By optimizing the timestep and shifting the energy spectrum, finite-difference and statistical errors are minimized simultaneously, allowing MSD to attain the sampling-cost lower bound up to a logarithmic factor. We further apply classical post-processing to infer Hamiltonian moments, which mitigate the ground-state energy error via the Lanczos scheme. Our analysis shows MSD is particularly effective when the Hamiltonian’s spectral norm is much smaller than its 1-norm, as in high-accuracy molecular simulations with large basis sets and strong electronic correlations. Numerical results for various molecular models show sampling-cost reductions of roughly 10 to 10,000 times over the conventional quantum Krylov algorithm.

Computing vacuum states of lattice gauge theories (LGTs) containing fermionic degrees of freedom can present significant challenges for classical computation using Monte-Carlo methods. Quantum algorithms may offer a pathway towards more scalable computation of groundstate properties of LGTs. However, a comprehensive understanding of the quantum computational resources required for such a problem is thus far lacking. In this work, we investigate using the quantum subspace expansion (QSE) algorithm to compute the groundstate of the Schwinger model, an archetypal LGT describing quantum electrodynamics in one spatial dimension. We perform numerical simulations, including the effect of measurement noise, to extrapolate the resources required for the QSE algorithm to achieve a desired accuracy for a range of system sizes. Using this, we present a full analysis of the resources required to compute LGT vacuum states using a quantum algorithm using qubitization within a fault tolerant framework. We develop of a novel method for performing qubitization of a LGT Hamiltonian based on a 'linear combination of unitaries' (LCU) approach. The cost of the corresponding block encoding operation scales as O ~ ( N ) with system size N . Including the corresponding prefactors, our method reduces the gate cost by multiple orders of magnitude when compared to previous LCU methods for the QSE algorithm, which scales as O ~ ( N 2 ) when applied to the Schwinger model. While the qubit and single circuit T-gate cost resulting from our resource analysis is appealing to early fault-tolerant implementation, we find that the number of shots required to avoid numerical instability within the QSE procedure must be significantly reduced in order to improve the feasibility of the methodology we consider and discuss how this might be achieved.

Quantum Krylov subspace diagonalization (QKSD) algorithms provide a low-cost alternative to the conventional quantum phase estimation algorithm for estimating the ground- and excited-state energies of a quantum many-body system. While QKSD algorithms typically rely on using the Hadamard test for estimating Krylov subspace matrix elements of the form $\ensuremath{\langle}{\ensuremath{\phi}}_{i}|{e}^{\ensuremath{-}i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{H}\ensuremath{\tau}}|{\ensuremath{\phi}}_{j}\ensuremath{\rangle}$, the associated quantum circuits require an ancilla qubit with controlled multiqubit gates that can be quite costly for near-term quantum hardware. In this paper, we show that a wide class of Hamiltonians relevant to condensed-matter physics and quantum chemistry contain symmetries that can be exploited to avoid the use of the Hadamard test. We propose a multifidelity estimation protocol that can be used to compute such quantities, showing that our approach, when combined with efficient single-fidelity estimation protocols, provides a substantial reduction in circuit depth. In addition, we develop a unified theory of quantum Krylov subspace algorithms and present three quantum-classical algorithms for the ground- and excited-state energy estimation problems, where each algorithm provides various advantages and disadvantages in terms of total number of calls to the quantum computer, gate depth, classical complexity, and stability of the generalized eigenvalue problem within the Krylov subspace.

Quantum computers provide new avenues to access ground and excited state properties of systems otherwise difficult to simulate on classical hardware. New approaches using subspaces generated by real-time evolution have shown efficiency in extracting eigenstate information, but the full capabilities of such approaches are still not understood. In recent work, we developed the variational quantum phase estimation (VQPE) method, a compact and efficient real-time algorithm to extract eigenvalues on quantum hardware. Here we build on that work by theoretically and numerically exploring a generalized Krylov scheme where the Krylov subspace is constructed through a parametrized real-time evolution, which applies to the VQPE algorithm as well as others. We establish an error bound that justifies the fast convergence of our spectral approximation. We also derive how the overlap with high energy eigenstates becomes suppressed from real-time subspace diagonalization and we visualize the process that shows the signature phase cancellations at specific eigenenergies. We investigate various algorithm implementations and consider performance when stochasticity is added to the target Hamiltonian in the form of spectral statistics. To demonstrate the practicality of such real-time evolution, we discuss its application to fundamental problems in quantum computation such as electronic structure predictions for strongly correlated systems.

Approximating the ground state of many-body systems is a key computational bottleneck underlying important applications in physics and chemistry. The most widely known quantum algorithm for ground state approximation, quantum phase estimation, is out of reach of current quantum processors due to its high circuit-depths. Subspace-based quantum diagonalization methods offer a viable alternative for pre- and early-fault-tolerant quantum computers. Here, we introduce a quantum diagonalization algorithm which combines two key ideas on quantum subspaces: a classical diagonalization based on quantum samples, and subspaces constructed with quantum Krylov states. We prove that our algorithm converges in polynomial time under the working assumptions of Krylov quantum diagonalization and sparseness of the ground state. We then demonstrate the scalability of our approach by performing the largest ground-state quantum simulation of impurity models using a Heron quantum processors and the Frontier supercomputer. We consider both the single-impurity Anderson model with 41 bath sites, and a system with 4 impurities and 7 bath sites per impurity. Our results are in excellent agreement with Density Matrix Renormalization Group calculations.

Quantum subspace diagonalization (QSD) algorithms have emerged as a competitive family of algorithms that avoid many of the optimization pitfalls associated with parameterized quantum circuit algorithms. While the vast majority of QSD algorithms have focused on solving the eigenpair problem for ground-state, excited-state, and thermal observable estimations, there has been a lot less work in considering QSD algorithms for the problem of quantum dynamical simulation. In this work, we propose several quantum Krylov fast-forwarding algorithms capable of predicting long-time dynamics well beyond the coherence time of current quantum hardware. Our algorithms use real-time evolved Krylov basis states prepared on a quantum computer and a multireference subspace method to ensure convergence towards high-fidelity, long-time dynamics. In particular, we show that the proposed multireference methodology provides a systematic way of trading off circuit depth with classical postprocessing complexity. We also demonstrate the efficacy of our approach through numerical implementations for several quantum chemistry problems, including the calculation of the autocorrelation and dipole moment correlation functions.

We propose an algorithm to obtain Green's functions as a continued fraction on quantum computers, which is based on the construction of the Krylov basis using variational quantum algorithms, and included in a Lanczos iterative scheme. This allows the integration of quantum algorithms with first principles material science simulations, as we demonstrate within the dynamical mean-field theory (DMFT) framework. DMFT enables quantitative predictions for strongly correlated materials, and relies on the calculation of Green's functions. On conventional computers the exponential growth of the Hilbert space with the number of orbitals limits DMFT to small systems. Quantum computers open new avenues and can lead to a significant speedup in the computation of expectation values required to obtain the Green's function. We apply our Krylov variational quantum algorithm combined with DMFT to the charge transfer insulator La$_{2}$CuO$_4$ using a quantum computing emulator, and show that with 8 qubits it predicts the correct insulating material properties for the paramagnetic phase. We therefore expect that the method is ideally suited to perform simulations for real materials on near term quantum hardware.