# Noisy intermediate-scale quantum algorithm for semidefinite programming

arXiv: https://arxiv.org/abs/2106.03891 · HTML: https://mlsanity.com/paper/2106.03891/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 67 references that are in the map.
- First posted on arXiv 7 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)

## Built on by (most cited first, 5 of 5)

- [Quantum machine learning of large datasets using randomized measurements](https://mlsanity.com/paper/2108.01039/) (2021)
- [Quantum thermodynamics and semi-definite optimization](https://mlsanity.com/paper/2505.04514/) (2025)
- [Post-variational quantum neural networks](https://mlsanity.com/paper/2307.10560/) (2023)
- [Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems](https://mlsanity.com/paper/2508.09103/) (2025)
- [Solving Conic Programs over Sparse Graphs using a Variational Quantum Approach: The Case of the AC Optimal Power Flow](https://mlsanity.com/paper/2509.00341/) (2025)

## Abstract (arXiv)

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