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


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.