3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ How do you capture a classical one? If the same as what you stated, the classical one, instead of using abstract Turing Machine we use the more concrete classical circuit, will also halt(except we have for loop? If so, the question reduced to for loop in quantum computers?) $\endgroup$
    – narip
    Commented Dec 1, 2021 at 10:08
  • $\begingroup$ Yeah you're right! $\endgroup$
    – user1936752
    Commented Dec 2, 2021 at 3:30

1 Answer 1

Reset to default
1
$\begingroup$

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]

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.