The task of estimating the ground state of Hamiltonians is an important problem in physics with numerous applications ranging from solid-state physics to combinatorial optimization. We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian that builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers. Our algorithm systematically constructs the ansatz by using any given choice of the initial state and the unitaries describing the Hamiltonian. The only task of the quantum computer is to measure overlaps and no feedback loops are required. The measurements can be performed efficiently on current quantum hardware without requiring any complicated measurements such as the Hadamard test. Finally, a classical computer solves a well-characterized quadratically constrained optimization program. Our algorithm can reuse previous measurements to calculate the ground state of a wide range of Hamiltonians without requiring additional quantum resources. Further, we demonstrate our algorithm for solving a class of problems with thousands of qubits. The algorithm works for almost every random choice of the initial state and circumvents the barren plateau problem.
The task of estimating the ground state of Hamiltonians is an important problem in physics with numerous applications ranging from solid-state physics to combinatorial optimization. We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian that builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers. Our algorithm systematically constructs the ansatz by using any given choice of the initial state and the unitaries describing the Hamiltonian. The only task of the quantum computer is to measure overlaps and no feedback loops are required. The measurements can be performed efficiently on current quantum hardware without requiring any complicated measurements such as the Hadamard test. Finally, a classical computer solves a well-characterized quadratically constrained optimization program. Our algorithm can reuse previous measurements to calculate the ground state of a wide range of Hamiltonians without requiring additional quantum resources. Further, we demonstrate our algorithm for solving a class of problems with thousands of qubits. The algorithm works for almost every random choice of the initial state and circumvents the barren plateau problem.
We propose a hybrid quantum-classical algorithm for approximating the ground state and ground state energy of a Hamiltonian. Once the Ansatz has been decided, the quantum part of the algorithm involves the calculation of two overlap matrices. The output from the quantum part of the algorithm is utilized as input for the classical computer. The classical part of the algorithm is a quadratically constrained quadratic program with a single quadratic equality constraint. Unlike the variational quantum eigensolver algorithm, our algorithm does not have any classical-quantum feedback loop. Using convex relaxation techniques, we provide an efficiently computable lower bound to the classical optimization program. Furthermore, using results from Bar-On et al. (Journal of Optimization Theory and Applications, 82(2):379--386, 1994), we provide a sufficient condition for a local minimum to be a global minimum. A solver can use such a condition as a stopping criterion.
Quantum simulation can help us study poorly understood topics such as high-temperature superconductivity and drug design. However, existing quantum simulation algorithms for current quantum computers often have drawbacks that impede their application. Here, we provide a hybrid quantum-classical algorithm for simulating the dynamics of quantum systems. Our approach takes the ansatz wave function as a linear combination of quantum states. The quantum states are fixed, and the combination parameters are variationally adjusted. Unlike existing variational quantum simulation algorithms, our algorithm does not require any classical-quantum feedback loop and by construction bypasses the barren plateau problem. Moreover, our algorithm does not require any complicated measurements such as the Hadamard test. The entire framework is compatible with existing experimental capabilities and thus can be implemented immediately.
Estimating the ground-state energy of Hamiltonians is a fundamental task for which it is believed that quantum computers can be helpful. Several approaches have been proposed toward this goal, including algorithms based on quantum phase estimation and hybrid quantum-classical optimizers involving parameterized quantum circuits, the latter falling under the umbrella of the variational quantum eigensolver. Here, we analyze the performance of quantum Boltzmann machines for this task, which is a less explored ansatz based on parameterized thermal states and which is not known to suffer from the barren-plateau problem. We delineate a hybrid quantum-classical algorithm for this task and rigorously prove that it converges to an ε-approximate stationary point of the energy function optimized over parameter space, while using a number of parameterized-thermal-state samples that is polynomial in ε−1, the number of parameters, and the norm of the Hamiltonian being optimized. Our algorithm estimates the gradient of the energy function efficiently by means of a quantum circuit construction that combines classical random sampling, Hamiltonian simulation, and the Hadamard test. Additionally, supporting our main claims are calculations of the gradient and Hessian of the energy function, as well as an upper bound on the matrix elements of the latter that is used in the convergence analysis.
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 Ω ( 1 / poly ( n ) ) for n qubits.
Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.
We propose a quantum-classical hybrid algorithm of the power method, here dubbed as the quantum power method, to evaluate Ĥn |ψ with quantum computers, where n is a non-negative integer, Ĥ is a time-independent Hamiltonian of interest, and |ψ is a quantum state.We show that the number of gates required for approximating Ĥn scales linearly in the power and the number of qubits, making it a promising application for near-term quantum computers.Using numerical simulation, we show that the power method can control systematic errors in approximating the Hamiltonian power Ĥn for n as large as 100.As an application, we combine our method with a multireference Krylov-subspace-diagonalization scheme to show how one can improve the estimation of ground-state energies and the ground-state fidelities found using a variational-quantum-eigensolver scheme.Finally, we outline other applications of the quantum power method, including several moment-based methods.We numerically demonstrate the connectedmoment expansion for the imaginary-time evolution and compare the results with the multireference Krylov-subspace diagonalization.