Noisy intermediate-scale quantum algorithm for semidefinite programming

Abstract

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 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 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, 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 $2^{1000}$ 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.

16 pages, 9 figures

References in corpus (13)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Quantum state discrimination and its applications
• Robust and versatile black-box certification of quantum devices
• Capacity and quantum geometry of parametrized quantum circuits
• All sets of incompatible measurements give an advantage in quantum state discrimination
• Fisher Information in Noisy Intermediate-Scale Quantum Applications
• Variational Hamiltonian Diagonalization for Dynamical Quantum Simulation
• Long-time simulations with high fidelity on quantum hardware
• Noise-Resilient Quantum Dynamics Using Symmetry-Preserving Ansatzes
• Optimal training of variational quantum algorithms without barren plateaus
• Critical Points in Quantum Generative Models
• NISQ Algorithm for Hamiltonian Simulation via Truncated Taylor Series

Cited by in corpus (16)

• Quantum machine learning of large datasets using randomized measurements
• Classically estimating observables of noiseless quantum circuits
• Towards multiqudit quantum processor based on a ${}^{171}$Yb${}^{+}$ ion string: Realizing basic quantum algorithms
• EHA: Entanglement-variational Hardware-efficient Ansatz for Eigensolvers
• Variational Quantum Algorithms for Semidefinite Programming
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Dual-VQE: A quantum algorithm to lower bound the ground-state energy
• Detecting Entanglement by Pure Bosonic Extension
• From barren plateaus through fertile valleys: Conic extensions of parameterised quantum circuits
• Noise-Resilient Quantum Reinforcement Learning
• Challenges and opportunities in the supervised learning of quantum circuit outputs
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems