6 papers · 1 filter
Quantum speedups for linear programming via interior point methods
Simon Apers, Sander Gribling
We describe a quantum algorithm based on an interior point method for solving a linear program with inequality constraints on variables. The algorithm explicitly returns a…
Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers
Sander Gribling, Simon Apers, Harold Nieuwboer +1
Spectral gaps play a fundamental role in many areas of mathematics, computer science, and physics. In quantum mechanics, the spectral gap of Schrödinger operators has a long histo…
Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
Sander Gribling, Lennart Sinjorgo, Renata Sotirov
We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph on n vertices, the QMC problem is to determine the largest…
How to compute the volume in low dimension?
Arjan Cornelissen, Simon Apers, Sander Gribling
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, an…
Challenges and Opportunities in Quantum Optimization
Amira Abbas, Andris Ambainis, Brandon Augustino +43
Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum a…
Grothendieck inequalities characterize converses to the polynomial method
Jop Briët, Francisco Escudero Gutiérrez, Sander Gribling
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorit…