PredictionBook is now read-only ( read more ).

Quantum version of ETH disproven by January 1, 2056

Created by JoshuaZ on 2015-10-15; known on 2056-01-01

  • JoshuaZ estimated 55% on 2015-10-15
  • Josh Holland estimated 50% on 2015-10-16
  • JoshuaZ said “Also to clarify, by quantum version of ETH I mean for solving NP complete problems requires exponential time on a quantum computer (with the usual distinction between ETH and SETH), not the same result for QMA. ” on 2015-10-17
  • jessriedel estimated 3% and said “So “Quantum version of ETH disproven” = “There is a quantum algorithm that solves 3-SAT in subexponential time in the worst case”? No way…” on 2016-01-02
  • JoshuaZ said “Jess, yes. I’m curious why you find it so unlikely. Ryan Williams is skeptical of ETH and SETH even in their classical forms. ” on 2016-01-03