  Bit commitment is a fundamental cryptographic primitive with numerous
applications. Quantum information allows for bit commitment schemes in the
information theoretic setting where no dishonest party can perfectly cheat. The
previously best-known quantum protocol by Ambainis achieved a cheating
probability of at most 3/4[Amb01]. On the other hand, Kitaev showed that no
quantum protocol can have cheating probability less than 1/sqrt{2} [Kit03] (his
lower bound on coin flipping can be easily extended to bit commitment). Closing
this gap has since been an important and open question.
  In this paper, we provide the optimal bound for quantum bit commitment. We
first show a lower bound of approximately 0.739, improving Kitaev's lower
bound. We then present an optimal quantum bit commitment protocol which has
cheating probability arbitrarily close to 0.739. More precisely, we show how to
use any weak coin flipping protocol with cheating probability 1/2 + eps in
order to achieve a quantum bit commitment protocol with cheating probability
0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol
described by Mochon[Moc07]. To stress the fact that our protocol uses quantum
effects beyond the weak coin flip, we show that any classical bit commitment
protocol with access to perfect weak (or strong) coin flipping has cheating
probability at least 3/4.
