Simulating the dynamics of many-body quantum systems is believed to be one of the first fields that quantum computers can show a quantum advantage over classical computers. Noisy intermediate-scale quantum (NISQ) algorithms aim at effectively using the currently available quantum hardware. For quantum simulation, various types of NISQ algorithms have been proposed with individual advantages as well as challenges. In this work, we propose a new algorithm, truncated Taylor quantum simulator (TQS), that shares the advantages of existing algorithms and alleviates some of the shortcomings. Our algorithm does not have any classical-quantum feedback loop and bypasses the barren plateau problem by construction. The classical part in our hybrid quantum-classical algorithm corresponds to a quadratically constrained quadratic program (QCQP) with a single quadratic equality constraint, which admits a semidefinite relaxation. The QCQP based classical optimization was recently introduced as the classical step in quantum assisted eigensolver (QAE), a NISQ algorithm for the Hamiltonian ground state problem. Thus, our work provides a conceptual unification between the NISQ algorithms for the Hamiltonian ground state problem and the Hamiltonian simulation. We recover differential equation-based NISQ algorithms for Hamiltonian simulation such as quantum assisted simulator (QAS) and variational quantum simulator (VQS) as particular cases of our algorithm. We test our algorithm on some toy examples on current cloud quantum computers. We also provide a systematic approach to improve the accuracy of our algorithm.
Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an nondeterministic polynomial time-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. We harness the SDP-based formulation of the Hamiltonian ground-state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex and can be solved in polynomial time with the number of ansatz parameters, and every local minimum is a global minimum. We find numeric evidence that NISQ SDP can improve the estimation of ground-state energies in a scalable manner. Further, we efficiently solve constrained problems to calculate the excited states of Hamiltonians, find the lowest energy of symmetry constrained Hamiltonians, and determine the optimal measurements for quantum state discrimination. We demonstrate the potential of our approach by finding the largest eigenvalue of up to
21000 dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an NP-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for SDP. The classical optimization program of our NISQ solver is another SDP over a smaller dimensional ansatz space. We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time with the number of ansatz parameters and every local minimum is a global minimum. Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of up to
21000 dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
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.
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.
Abstract We provide a noisy intermediate-scale quantum framework for simulating the dynamics of open quantum systems, generalized time evolution, non-linear differential equations and Gibbs state preparation. Our algorithm does not require any classical–quantum feedback loop, bypass the barren plateau problem and does not necessitate any complicated measurements such as the Hadamard test. We introduce the notion of the hybrid density matrix, which allows us to disentangle the different steps of our algorithm and delegate classically demanding tasks to the quantum computer. Our algorithm proceeds in three disjoint steps. First, we select the ansatz, followed by measuring overlap matrices on a quantum computer. The final step involves classical post-processing data from the second step. Our algorithm has potential applications in solving the Navier–Stokes equation, plasma hydrodynamics, quantum Boltzmann training, quantum signal processing and linear systems. Our entire framework is compatible with current experiments and can be implemented immediately.
Background: Quantum simulations offer the potential to predict the structure and dynamics of nuclear many-body systems that are beyond the capabilities of classical computing. Generally, preparing the ground state of strongly interacting many-body systems relevant to nuclear physics is, however, inefficient, even using ideal quantum computers. In addition, currently available noisy intermediate-scale quantum (NISQ) era quantum devices possess modest numbers of qubits, limiting the size of quantum many-body systems that can be simulated. In this context, a reformulation of the quantum many-body problems using truncated model spaces and Hamiltonians is desirable to make them more amenable to near-term quantum computers. The importance of symmetries in low-energy theories, including effective field theories (EFTs), lattice quantum chromodynamics (QCD), and effective model spaces for nuclear systems, in particular their interplay with the reduction of active Hilbert spaces, is well known. Lesser known is the fact that the noncommutivity of some symmetries and truncations of the model space can be profitably combined with variational calculations to rearrange the entanglement into localized structures and enable more efficient simulations.Purpose: The goal of the present study is to explore and utilize the noncommutivity of symmetries and model-space truncations of quantum many-body systems important to nuclear physics, particularly in combination with variational algorithms for quantum simulations and effective Hamiltonian learning.Method: We introduce an iterative hybrid classical-quantum algorithm, the Hamiltonian learning variational quantum eigensolver (HL-VQE), that simultaneously optimizes an effective Hamiltonian, thereby rearranging entanglement into the effective model space, and the associated ground-state wave function. Quantum simulations, using classical computers and IBM's superconducting-qubit quantum computers, are performed to demonstrate the HL-VQE algorithm, in the context of the Lipkin-Meshkov-Glick (LMG) model of interacting fermions, where the Hamiltonian transformation corresponds to an orbital rotation. We use a mapping where the number of qubits scales with the
logarithm of the size of the effective model space, rather than the particle number.Results: HL-VQE is found to provide an exponential improvement in LMG-model calculations of the ground-state energy and wave function, compared to naive truncations without Hamiltonian learning, throughout a significant fraction of the Hilbert space. In the context of EFT, this corresponds to counterterms scaling exponentially with the cutoff as opposed to power law. Implementations on IBM's QExperience quantum computers and simulators for one- and two-qubit effective model spaces are shown to provide accurate and precise results, reproducing classical predictions.Conclusions: For a range of parameters defining the LMG model, the HL-VQE algorithm is found to have better scaling of quantum resources requirements than previously explored algorithms. In particular, the HL-VQE scales efficiently over a large fraction of the model space, in contrast to VQE alone. This work constitutes a step in the development of entanglement-driven quantum algorithms for descriptions of nuclear many-body systems. This, in part, leverages the potential of noisy intermediate-scale quantum (NISQ) devices. The exponential scaling of counterterms observed in this study suggests the possibility of more general applicability to other nonperturbative EFTs.