Semidefinite programming from optimization to quantum chemistry

In this paper we consider the general problem of designing the optimal quantum detection for minimum-error quantum state discrimination. Since it is hard to get an explicit solution and we must resort to numerical methods for the general case. We show the problem can be cast into a semidefinite programming(SDP) problem, we use the theory of SDP to solve it. Based on the idea, we propose a method for minimum-error discrimination by formulating the design of optimal quantum detection as a standard SDP problem; furthermore, based on the optimality conditions for SDP, we derive a set of optimality conditions for quantum detection. It is exemplified that this method is simple to implement and can be used to design optimum detection operators for minimum-error discrimination efficiently.In this paper we consider the general problem of designing the optimal quantum detection for minimum-error quantum state discrimination. Since it is hard to get an explicit solution and we must resort to numerical methods for the general case. We show the problem can be cast into a semidefinite programming(SDP) problem, we use the theory of SDP to solve it. Based on the idea, we propose a method for minimum-error discrimination by formulating the design of optimal quantum detection as a standard SDP problem; furthermore, based on the optimality conditions for SDP, we derive a set of optimality conditions for quantum detection. It is exemplified that this method is simple to implement and can be used to design optimum detection operators for minimum-error discrimination efficiently.

Chinese Control Conference (CCC)Jul 1, 20082 citations

NISQ Algorithm for Semidefinite Programming

Kishor Bharti, Tobias Haug, Vlatko Vedral +1 more

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 $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.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 $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.

Jun 7, 20214 citations

Approximation Algorithms, Quantum Information and Semidefinite Optimization

Nikhil Bansal, Ronald de Wolf, Monique Laurent

Jul 1, 20150 citations

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.