5 papers
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…
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…
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…