181 citations · 332 across the 25 of their papers we have counts for
17 papers · 1 filter
Improved quantum volume estimation with transducers and amortized quantum walks
Arjan Cornelissen, Simon Apers, Sander Gribling
The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential alg…
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 histor…
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…
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…
Basic quantum subroutines: finding multiple marked elements and summing numbers
Joran van Apeldoorn, Sander Gribling, Harold Nieuwboer
We show how to find all marked elements in a list of size using the optimal number of quantum queries and only a polylogarithmic overhead in the gate comple…
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…
Improved quantum lower and upper bounds for matrix scaling
Sander Gribling, Harold Nieuwboer
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled…
Improving quantum linear system solvers via a gradient descent perspective
Sander Gribling, Iordanis Kerenidis, Dániel Szilágyi
Solving systems of linear equations is one of the most important primitives in quantum computing that has the potential to provide a practical quantum advantage in many different a…
On a tracial version of Haemers bound
Li Gao, Sander Gribling, Yinan Li
We extend upper bounds on the quantum independence number and the quantum Shannon capacity of graphs to their counterparts in the commuting operator model. We introduce a von Neuma…
Quantum algorithms for matrix scaling and matrix balancing
Joran van Apeldoorn, Sander Gribling, Yinan Li +3
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear sy…
The Haemers bound of noncommutative graphs
Sander Gribling, Yinan Li
We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from qu…
Semidefinite programming formulations for the completely bounded norm of a tensor
Sander Gribling, Monique Laurent
We show that a certain tensor norm, the completely bounded norm, can be expressed by a semidefinite program. This tensor norm recently attracted attention in the field of quantum c…
Simon's problem for linear functions
Joran van Apeldoorn, Sander Gribling
Simon's problem asks the following: determine if a function is one-to-one or if there exists a unique such that $f(x) = f(x \…
Convex optimization using quantum oracles
Joran van Apeldoorn, András Gilyén, Sander Gribling +1
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracle…
Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling +1
Brandão and Svore very recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithm…