# Quantum Algorithm SAT structure

"Quantum magic won't be enough" (Bennett et al. 1997)

If you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\sqrt{2^n}$ steps to find the correct one (using Grover's algorithm) If a quantum polynomial time algorithm for a $\text{NP}$-complete problem is ever found, it must exploit the problem structure in some way. I've some (basic) questions that no one seems to have asked so far on this site (maybe because they are basic). Suppose someone finds a bounded error quantum polynomial time algorithm for $\text{SAT}$ (or any other $\text{NP}$-complete problem), thus placing $\text{SAT}$ in $\text{BQP}$, and implying $\text{NP} \subseteq \text{BQP}$.

## Questions

The possibility (or not) to exploit the problem structure in a general enough (i.e. specific-instance independent) manner seems to be the very core of the $\text{P = NP}$ question. Now if a bounded error polynomial-time quantum algorithm for $\text{SAT}$ is found, and it must exploit the problem structure, wouldn't its structure-exploitation-strategy be usable also in the classical scenario? Is there any evidence indicating that such a structure-exploitation may be possible for quantum computers, while remaining impossible for classical ones?

Sources

Related

• Hi, two "editorial" comments: firstly your first paragraph seems like it is all a quote from Bennett et al. 1997 reading it it appears this is not the case - may be take the latter part out of the "Blockquote" format. Secondly: Your "sources" link does not work for me (I get a 404 error). – Quantum spaghettification May 28 '18 at 18:54