Return to Answer

Changed 'exponential time hypothesis' to 'strong exponential time hypothesis'.

Source Link

edited Dec 15, 2021 at 18:27

As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the ExponentialStrong Exponential Time Hypothesis (a by-now moderately accepted generalization of $\mathsf{P} \neq \mathsf{NP}$).
Regarding "sampling problems", here is what I might regard as the simplest/best evidence: The Deutsch--Josza Algorithm gives an efficient quantum algorithm $Q$ with the following property: On input a classical circuit $C$, we have $\Pr[Q(C) = 1] = 0$ if $C$'s truth-table is exactly 50% $1$'s, and $\Pr[Q(C) = 1] > 0$ if $C$'s truth-table is not exactly 50% $1$'s. Now suppose that for every efficient quantum algorithm (in particular, $Q$) there were an efficient randomized classical algorithm $A$ that had "approximately the same output distribution" as $Q$; say, for all outputs $y$, $$\Pr[Q = y] \text{ is within a factor of 1000 of }\Pr[A = y].$$ Then we would also have that $\Pr[A(C) = 1] > 0$ iff $C$'s truth-table is not exactly 50% $1$'s, which is equivalent to "$\mathsf{co}\text{-}\mathsf{C}_=\mathsf{P} = \mathsf{NP}$", which was shown (Ogihara and Toda, early '90s) to imply $\mathsf{PH}$ collapses to the second level (indeed, to $\mathsf{AM}\cap \mathsf{co}\text{-}\mathsf{AM}$). Indeed, the above "factor-$1000$ approximation" is a red herring; one only needs the weaker "approximate sampling" condition that the classical algorithm outputs each outcome with positive probability iff the quantum algorithm does.

As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the Exponential Time Hypothesis (a by-now moderately accepted generalization of $\mathsf{P} \neq \mathsf{NP}$).
Regarding "sampling problems", here is what I might regard as the simplest/best evidence: The Deutsch--Josza Algorithm gives an efficient quantum algorithm $Q$ with the following property: On input a classical circuit $C$, we have $\Pr[Q(C) = 1] = 0$ if $C$'s truth-table is exactly 50% $1$'s, and $\Pr[Q(C) = 1] > 0$ if $C$'s truth-table is not exactly 50% $1$'s. Now suppose that for every efficient quantum algorithm (in particular, $Q$) there were an efficient randomized classical algorithm $A$ that had "approximately the same output distribution" as $Q$; say, for all outputs $y$, $$\Pr[Q = y] \text{ is within a factor of 1000 of }\Pr[A = y].$$ Then we would also have that $\Pr[A(C) = 1] > 0$ iff $C$'s truth-table is not exactly 50% $1$'s, which is equivalent to "$\mathsf{co}\text{-}\mathsf{C}_=\mathsf{P} = \mathsf{NP}$", which was shown (Ogihara and Toda, early '90s) to imply $\mathsf{PH}$ collapses to the second level (indeed, to $\mathsf{AM}\cap \mathsf{co}\text{-}\mathsf{AM}$). Indeed, the above "factor-$1000$ approximation" is a red herring; one only needs the weaker "approximate sampling" condition that the classical algorithm outputs each outcome with positive probability iff the quantum algorithm does.

As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the Strong Exponential Time Hypothesis (a by-now moderately accepted generalization of $\mathsf{P} \neq \mathsf{NP}$).
Regarding "sampling problems", here is what I might regard as the simplest/best evidence: The Deutsch--Josza Algorithm gives an efficient quantum algorithm $Q$ with the following property: On input a classical circuit $C$, we have $\Pr[Q(C) = 1] = 0$ if $C$'s truth-table is exactly 50% $1$'s, and $\Pr[Q(C) = 1] > 0$ if $C$'s truth-table is not exactly 50% $1$'s. Now suppose that for every efficient quantum algorithm (in particular, $Q$) there were an efficient randomized classical algorithm $A$ that had "approximately the same output distribution" as $Q$; say, for all outputs $y$, $$\Pr[Q = y] \text{ is within a factor of 1000 of }\Pr[A = y].$$ Then we would also have that $\Pr[A(C) = 1] > 0$ iff $C$'s truth-table is not exactly 50% $1$'s, which is equivalent to "$\mathsf{co}\text{-}\mathsf{C}_=\mathsf{P} = \mathsf{NP}$", which was shown (Ogihara and Toda, early '90s) to imply $\mathsf{PH}$ collapses to the second level (indeed, to $\mathsf{AM}\cap \mathsf{co}\text{-}\mathsf{AM}$). Indeed, the above "factor-$1000$ approximation" is a red herring; one only needs the weaker "approximate sampling" condition that the classical algorithm outputs each outcome with positive probability iff the quantum algorithm does.

Source Link

created Dec 15, 2021 at 15:10

As mentioned in a comment, Grover's Algorithm implies a SAT algorithm running in time $\tilde{O}(\sqrt{2}^n)$, which breaks the Exponential Time Hypothesis (a by-now moderately accepted generalization of $\mathsf{P} \neq \mathsf{NP}$).
Regarding "sampling problems", here is what I might regard as the simplest/best evidence: The Deutsch--Josza Algorithm gives an efficient quantum algorithm $Q$ with the following property: On input a classical circuit $C$, we have $\Pr[Q(C) = 1] = 0$ if $C$'s truth-table is exactly 50% $1$'s, and $\Pr[Q(C) = 1] > 0$ if $C$'s truth-table is not exactly 50% $1$'s. Now suppose that for every efficient quantum algorithm (in particular, $Q$) there were an efficient randomized classical algorithm $A$ that had "approximately the same output distribution" as $Q$; say, for all outputs $y$, $$\Pr[Q = y] \text{ is within a factor of 1000 of }\Pr[A = y].$$ Then we would also have that $\Pr[A(C) = 1] > 0$ iff $C$'s truth-table is not exactly 50% $1$'s, which is equivalent to "$\mathsf{co}\text{-}\mathsf{C}_=\mathsf{P} = \mathsf{NP}$", which was shown (Ogihara and Toda, early '90s) to imply $\mathsf{PH}$ collapses to the second level (indeed, to $\mathsf{AM}\cap \mathsf{co}\text{-}\mathsf{AM}$). Indeed, the above "factor-$1000$ approximation" is a red herring; one only needs the weaker "approximate sampling" condition that the classical algorithm outputs each outcome with positive probability iff the quantum algorithm does.