add tag bqp

Link

edit approved Apr 27, 2018 at 16:50

agaitaarino

3.9k
2
13
42

improve style, give more direct source

Source Link

edited Apr 10, 2018 at 17:58

Didix

795
9
21

"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 an $\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}$. _Source

##Questions Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?

_Source

"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 an $\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}$. _Source

##Questions Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?

"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 an $\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 Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?

_Source

improve style, give more direct source

Source Link

edit approved Apr 10, 2018 at 17:58

Discrete lizard

3.1k
2
19
41

Consequences of $\text{SAT} \in \text{BQP}$SAT ∈ BQP

"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 an $\text{NP}$-complete problem is ever found, it must exploit the problem structure in some way. I've

(...)

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}$. _Source

##Questions Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?

^Sources

Consequences of $\text{SAT} \in \text{BQP}$

"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 an $\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 Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?

^Sources

Consequences of SAT ∈ BQP

"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 an $\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}$. _Source

##Questions Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?