BPP ⊆ BQP

Inclusion · quantum setting · BV97

Statement

A quantum Turing machine simulates every bounded-error probabilistic polynomial-time computation with polynomial overhead, so BPP $\subseteq$ BQP — BV97.

Sketch

Each deterministic step of the probabilistic machine is executed reversibly, and each coin toss is a fresh qubit put into an equal superposition of $0$ and $1$; measuring at the end reproduces the acceptance probabilities.