Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
It is claimed that a quantum Turing machine is "computationally" equivalent to the circuit model. Quantum computing also includes all classical computing. However, we know that there are classical Turing machines that do not halt on certain inputs.
How does a quantum circuit capture this non-halting "ability" of classical Turing machines? The way we draw them, every quantum circuit inevitably halts when we perform the measurements at the end.
If you take a look at the equivalence proofs by Yao (1993), Nishimura and Ozawa (2002), or Molina and Watrous (2018) you will notice that they always talk about quantum Turing machine computations that run for a predetermined number of steps.
The equivalence means:
$t$ steps of a quantum Turing machine running on an input of length $n$ can be simulated by a uniformly generated family of quantum circuits with size polynomial in $t$, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time.
[Molina and Watrous, 2018]
