6
$\begingroup$

"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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Quantum spaghettification May 28 '18 at 18:54
3
$\begingroup$

wouldn't its structure-exploitation-strategy be usable also in the classical scenario?

Not necessarily. For example, Shor's algorithm exploits the structure of factoring in a way that classical computers can't. Specifically, Shor's algorithm looks for periods in the multiplicative subgroup of N-1 in a way that requires a quantum Fourier transform to be efficient.

Sometimes quantum algorithms do translate back into the classical domain. For example, you can use phase estimation to apply fractional QFTs in an efficient way. Translate this circuit directly into its classical equivalent, and you get an O(N log(N)) algorithm for fractional FFTs. But there's certainly no guarantees that what works well in the quantum context will work well in the classical context.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.