A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices

Mareček, Jakub; Akhriev, Albert

Permalink

https://hdl.handle.net/2142/130322 Copy

Description

Title

A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices

Author(s)

• Mareček, Jakub
• Akhriev, Albert

Issue Date

2025-09-17

Keyword(s)

• Quantum algorithms
• Semidefinite programming
• Cutting-plane methods
• Randomized cutting-plane method

Abstract

There is a growing interest in quantum algorithms for optimization problems. Within convex optimization, interior-point methods and other recently proposed quantum approaches remain challenging to implement on noisy quantum devices. In this work, we explore an alternative framework for convex optimization in general, and semidefinite programming (SDP) in particular, based on a randomized variant of the cutting-plane method. We argue that quantum speed-ups in eigensolvers can be exploited to accelerate SDP solvers based on the cutting-plane method. To support this claim, we provide a practical implementation of the randomized cutting-plane (RCP) method for semidefinite programming and evaluate it on benchmark instances from SDPLIB, a widely used test suite. Moreover, we demonstrate that the RCP method is highly robust to noise in the boundary oracle, suggesting that it may be well-suited for execution on near-term noisy quantum devices.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130322&&

Copyright and License Information

Copyright 2025 is held by Jakub Mareček and Albert Akhriev.

Owning Collections