Norbert Schuch

Harry Buhrman, Sevag Gharibian, Zeph Landau et al.

We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value.

Lilith Zschetzsche, Refik Mansuroğlu, Norbert Schuch

The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are $\mathsf{BQP}$-complete. Importantly, this class includes two known $\mathsf{BQP}$-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $\mathsf{PostBQP}$-hard problem. This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.