11 papers
Log-concavity and tunneling: adiabatic quantum optimization for convex functions (with a spike)
Arthur Braida, Elie Bermot, Simon Apers
Quantum tunneling is expected to provide a computational speedup in quantum computing, a phenomenon that Adiabatic Quantum Optimization (AQO) aims to leverage. While some academic…
Elfs, transducers and quantum walks
Simon Apers, Jérémie Roland, Yuxin Zhang
Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool…
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…
Quantum property testing in sparse directed graphs
Simon Apers, Frédéric Magniez, Sayantan Sen +1
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the out…
Randomized and quantum approximate matrix multiplication
Simon Apers, Arjan Cornelissen, Samson Wang
The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers…
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…