Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Disclaimer: I don't understand quantum computing.
Given a CNF boolean formula $\phi$ in $n$ variables and quantum computer with $q$ qubits, what is the complexity of solving $\phi$ as a function of $n,q$?
I am mainly interested when $q$ is polynomial in $n$.
Can we get $2^{o(n)}$ (small Oh, Exponential time hypothesis)?
I believe on a traditional computer the complexity is $C^n$ for a constant $C < 2$.
This is an open question. People who try to prove $\text{BQP} = \text{NP}$ usually use the SAT formulation, in my experience. But we don't know of any algorithm that addresses the structure of the SAT problem.
The best you can do is a naive implementation of a Grover-like amplitude dispersion, which will give you a square-root speedup. (You can read that in the linked discussion on CS stack exchange.)
Adding to psitae's answer, in 2 recent papers by Aaronson, Chia, Lin, Wang and Zhang (arXiv:1911.01973) and Buhrman, Patro and Speelman (arXiv:1911.05686) the Quantum Strong Exponential Time Hypothesis (QSETH) was formulated. This hypothesis in fact claims that there is no $2^{o(n)}$ quantum algorithm for solving $k-\mathrm{SAT}$.
