Buchumschlag

Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Augustino, Brandon, Nannicini, Giacomo, Terlaky, Tamás, Zuluaga, Luis
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Quantum Physics Optimization and Control 68Q1, 90C22
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Inexact Feasible Interior Point Method for Linear Optimization with High Adaptability to Quantum Computers
von: Mohammadisiahroudi, Mohammadhossein, et al.
Veröffentlicht: (2023)

A quantum dual logarithmic barrier method for linear optimization
von: Wu, Zeguan, et al.
Veröffentlicht: (2024)

A preconditioned inexact infeasible quantum interior point method for linear optimization
von: Wu, Zeguan, et al.
Veröffentlicht: (2024)

T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
von: Marumo, Hiroki, et al.
Veröffentlicht: (2024)

On semidefinite programming characterizations of the numerical radius and its dual norm for quaternionic matrices
von: Friedland, Shmuel
Veröffentlicht: (2023)

Convex relaxation approaches for high-dimensional optimal transport
von: Khoo, Yuehaw, et al.
Veröffentlicht: (2025)

On semidefinite programming characterizations of the numerical radius and its dual norm
von: Friedland, Shmuel, et al.
Veröffentlicht: (2023)

On the equivalence of semidefinite programming and zero-sum semidefinite games
von: Elliott, Jesse, et al.
Veröffentlicht: (2026)

Topological structure and a polynomial-time solution of linear programming over the real numbers
von: Wei, Jing-Yuan
Veröffentlicht: (2018)

A constraint-based approach to function interpolation, with application to performance estimation for weakly convex optimisation
von: Rubbens, Anne, et al.
Veröffentlicht: (2024)

Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems
von: Bousselmi, Nizar, et al.
Veröffentlicht: (2023)

Certifying solutions of degenerate semidefinite programs
von: Kolmogorov, Vladimir, et al.
Veröffentlicht: (2024)

A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
von: Chiarini, Alberto, et al.
Veröffentlicht: (2024)

A quantum central path algorithm for linear optimization
von: Augustino, Brandon, et al.
Veröffentlicht: (2023)

A non-iterative polynomial algorithm for linear programming
von: Jing-Yuan, Wei
Veröffentlicht: (2013)

Solving exact and noisy rank-one tensor completion with semidefinite programming
von: Cifuentes, Diego, et al.
Veröffentlicht: (2025)

Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
von: Ostermann, Birte, et al.
Veröffentlicht: (2025)

A squared smoothing Newton method for semidefinite programming
von: Liang, Ling, et al.
Veröffentlicht: (2023)

Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety
von: Hua, Zheng, et al.
Veröffentlicht: (2021)

Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization
von: Nesterov, Yurii
Veröffentlicht: (2025)

Kurdyka-Łojasiewicz exponent via Hadamard parametrization
von: Ouyang, Wenqing, et al.
Veröffentlicht: (2024)

Kurdyka-Łojasiewicz exponent via square transformation
von: Ouyang, Wenqing
Veröffentlicht: (2025)

Halpern Acceleration of the Inexact Proximal Point Method of Rockafellar
von: Zhang, Liwei, et al.
Veröffentlicht: (2025)

Uncomputability of Global Optima for Nonconvex Functions in the Oracle Model
von: Lakshmanan, K
Veröffentlicht: (2023)

A preconditioned augmented Lagrangian method for solving semidefinite programming problems
von: Tang, Tianyun, et al.
Veröffentlicht: (2026)

Second-order sequential optimality conditions for nonlinear semidefinite optimization problems
von: Li, Huimin, et al.
Veröffentlicht: (2025)

Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
von: Gribling, Sander, et al.
Veröffentlicht: (2025)

Solving clustered low-rank semidefinite programs arising from polynomial optimization
von: Leijenhorst, Nando, et al.
Veröffentlicht: (2022)

Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
von: Tang, Tianyun, et al.
Veröffentlicht: (2024)

Accelerating preconditioned ADMM via degenerate proximal point mappings
von: Sun, Defeng, et al.
Veröffentlicht: (2024)

Solving Regularized Multifacility Location Problems with Unknown Number of Centers via Difference-of-Convex Optimization
von: Geremew, W., et al.
Veröffentlicht: (2026)

A new dual spectral projected gradient method for log-determinant semidefinite programming with hidden clustering structures
von: Namchaisiri, Charles, et al.
Veröffentlicht: (2024)

A semidefinite programming hierarchy for covering problems in discrete geometry
von: Riener, Cordian, et al.
Veröffentlicht: (2023)

On generators of $k$-PSD closures of the positive semidefinite cone
von: Bhardwaj, Avinash, et al.
Veröffentlicht: (2024)

HOT-POT: Optimal Transport for Sparse Stereo Matching
von: Clerc, Antonin, et al.
Veröffentlicht: (2026)

Duality attainment and strict feasibility of the generalized moment problem and its relaxations
von: Halaseh, Sami, et al.
Veröffentlicht: (2026)

Analysis of Kernel Mirror Prox for Measure Optimization
von: Dvurechensky, Pavel, et al.
Veröffentlicht: (2024)

Harnessing Inferior Solutions For Superior Outcomes: Obtaining Robust Solutions From Quantum Algorithms
von: Halffmann, Pascal, et al.
Veröffentlicht: (2024)

On exactness of SDP relaxation for the maximum cut problem
von: Bhardwaj, Avinash, et al.
Veröffentlicht: (2025)

A semidefinite programming characterization of the Crawford number
von: Friedland, Shmuel, et al.
Veröffentlicht: (2024)