Tag Info

4

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

3

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

1

Here's a really old reference: "Quantum Networks for Elementary Arithmetic Operations" by Vedral et al (1995) And here's some state of the art stuff: In-place ripply carry adder: "A new quantum ripple-carry addition circuit " by Cuccaro et al 2004 Optimal Toffoli count ripply carry adder: Halving the cost of quantum addition by Gidney 2017 Carry lookahead ...

Only top voted, non community-wiki answers of a minimum length are eligible