Równoważnie można używać modelu kwantowej maszyny Turinga działającej w czasie wielomianowym. Pomysł, że mechanika kwantowa mogłaby dać maszynom obliczeniowym moc przewyższającą klasyczne maszyny Turinga, wysunął w 1982 Richard Feynman. Jego pierwotną motywacją była wydajna symulacja układów kwantowych, a pierwszą definicję kwantowej maszyny Turinga podał w 1985 David Deutsch. Dopracowane sformułowania, dzięki którym obliczenia kwantowe ugruntowały się jako dziedzina teorii złożoności, podali następnie Andrew Yao oraz Bernstein i Vazirani. Ci dwaj ostatni wprowadzili ten model w teorii złożoności kwantowej i wykazali jego podstawowe własności, w tym związek z obliczeniami przez jednolite rodziny obwodów kwantowych. W praktyce współczesne sformułowania BQP najczęściej używają obwodów kwantowych, bo dobrze odpowiadają one opisowi algorytmów przez kubity, bramki kwantowe i pomiar.