I am trying to have a better understanding of the definition of the Quantum Turing Machine.

My questions:

  1. If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian and is an irrational number, how do we finish writing it on the output tape?
  2. How do we deal with the gates / unitary matrices when we are supposed to write the shortest description of a quantum program? We can always squeeze a deep quantum circuit into a single unitary matrix.
  • 7
    $\begingroup$ 1. If the output of a classical program is $\sqrt{2}$, how do we finish writing it on the tape? Does that mean that $\sqrt{2}$ is uncomputable? $\endgroup$ – Peter Shor Sep 13 '16 at 3:07
  • 6
    $\begingroup$ 2. For any classical problem, can't you define a classical gate that has $n$ wires in, $n$ wires out, and takes the input to the output? Why don't we just use that gate rather than writing complicated algorithms? $\endgroup$ – Peter Shor Sep 13 '16 at 3:08
  • $\begingroup$ @PeterShor, yes $\sqrt{2}$ is computable. So, yes, now I understand that a quantum computer can print $n$ digits of the number and halt. $\endgroup$ – Omar Shehab Sep 13 '16 at 18:26
  • 2
    $\begingroup$ Right. The same is true for quantum computers. Some definitions allow any unitary gate from two qubits to two qubits, but most interesting problems you want to solve involve maps from $n$ qubits to $n$ qubits. $\endgroup$ – Peter Shor Sep 15 '16 at 14:51
  • 1
    $\begingroup$ In the begining, you should check very well about quantum mechanics, before ansewring this question, because, there is tight relation ship between quantum mechanics and quantum turing machine $\endgroup$ – Youness Abdus Salam Apr 18 '17 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.