4 papers · 2 filters
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…
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…