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.

arXiv comment16 pages, 9 figures

References in corpus (66)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Bell nonlocality
• Supervised learning with quantum enhanced feature spaces
• Quantum Annealing in the Transverse Ising Model
• Quantum computational advantage using photons
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Efficient variational quantum simulator incorporating active error minimisation
• Contextuality supplies the magic for quantum computation
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• Variational Quantum Computation of Excited States
• Theory of variational quantum simulation
• Training variational quantum algorithms is NP-hard
• Graph-Theoretic Approach to Quantum Correlations
• Quantum state discrimination and its applications
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Efficient Symmetry-Preserving State Preparation Circuits for the Variational Quantum Eigensolver Algorithm
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Hardware-efficient variational quantum algorithms for time evolution
• A Non-Orthogonal Variational Quantum Eigensolver
• Application of fermionic marginal constraints to hybrid quantum algorithms
• Robust and versatile black-box certification of quantum devices
• Methodology for replacing indirect measurements with direct measurements
• Capacity and quantum geometry of parametrized quantum circuits
• All sets of incompatible measurements give an advantage in quantum state discrimination
• Physical characterization of quantum devices from nonlocal correlations
• Fisher Information in Noisy Intermediate-Scale Quantum Applications
• A variational toolbox for quantum multi-parameter estimation
• An efficient quantum algorithm for the time evolution of parameterized circuits
• Quantum Power Method by a Superposition of Time-Evolved States
• Finding optimal strategies for minimum-error quantum-state discrimination
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms
• Quantum Assisted Simulator
• The Meta-Variational Quantum Eigensolver (Meta-VQE): Learning energy profiles of parameterized Hamiltonians for quantum simulation
• Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation
• Penalty methods for variational quantum eigensolver
• Robust self-testing of quantum systems via noncontextuality inequalities
• Machine Learning meets Quantum Foundations: A Brief Survey
• Improvements in Quantum SDP-Solving with Applications
• Quantum inverse iteration algorithm for programmable quantum simulators
• Iterative Quantum Assisted Eigensolver
• Experimental quantum kernel machine learning with nuclear spins in a solid
• Variational Hamiltonian Diagonalization for Dynamical Quantum Simulation
• Quantum algorithms and lower bounds for convex optimization
• Long-time simulations with high fidelity on quantum hardware
• Convex optimization using quantum oracles
• Noise-Resilient Quantum Dynamics Using Symmetry-Preserving Ansatzes
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Optimal training of variational quantum algorithms without barren plateaus
• Quantum Assisted Eigensolver
• Quantum-Inspired Hierarchy for Rank-Constrained Optimization
• Critical Points in Quantum Generative Models
• Noisy intermediate scale quantum simulation of time dependent Hamiltonians
• NISQ Algorithm for Hamiltonian Simulation via Truncated Taylor Series

Cited by in corpus (17)

• Quantum machine learning of large datasets using randomized measurements
• Generalized Quantum Assisted Simulator
• 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
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• 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