Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Diese Arbeit etabliert unter der Annahme der Strong Exponential-Time Hypothesis (SETH) und ihrer Quantenversion (QSETH) starke untere Schranken für die klassische und quantenmechanische Lösbarkeit des lokalen Hamiltonian-Problems sowie für die Approximation der Quanten-Partitionsfunktion, indem sie eine neuartige, größen-erhaltende Konstruktion von Schaltungen zu Hamilton-Operatoren einführt, die eine effizientere Kodierung ermöglicht und durch einen optimierten Quantenalgorithmus ergänzt wird.