7 papers
A provable quantum advantage for approximate optimization via decoded quantum interferometry
Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones +2
Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantee…
Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice
Carsten Schubert, Niklas Paskarbeit, Maximilian J. Kramer +2
Grover's algorithm gives an optimal quadratic query advantage for black-box search. In cryptanalysis, however, the search often comes with additional probabilistic advice over the…
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Maximilian J. Kramer, Carsten Schubert, Jens Eisert
For general max-k-XORSAT with , no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless : a…
Optimal algorithmic complexity of inference in quantum kernel methods
Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2
Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained mode…
Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
Maximilian J. Kramer, Carsten Schubert, Jens Eisert
We establish tight inapproximability bounds for max-LINSAT, the problem of maximizing the number of satisfied linear constraints over the finite field , where each co…
A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
Franz J. Schreiber, Maximilian J. Kramer, Alexander Nietner +1
The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type…
Using deep learning to construct stochastic local search SAT solvers with performance bounds
Maximilian J. Kramer, Paul Boes, Jens Eisert
The Boolean Satisfiability problem (SAT), as the prototypical -complete problem, is crucial in both theoretical computer science and practical applications. To address…