<p>I am trying to have a better understanding of the definition of the <a href="https://en.wikipedia.org/wiki/Quantum_Turing_machine" rel="nofollow">Quantum Turing Machine</a>. </p>

<p>My questions:</p>

<ol>
<li>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?</li>
<li>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.</li>
</ol>

CC BY-SA 3.0
2016-09-13T03:07:33.827Z
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?
Peter Shor 
CC BY-SA 3.0
2016-09-13T03:08:22.500Z
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?
Peter Shor 
CC BY-SA 3.0
2016-09-13T18:26:55.963Z
@PeterShor, yes $\sqrt{2}$ is computable. So, yes, now I understand that a quantum computer can print $n$ digits of the number and halt.
Omar Shehab
CC BY-SA 3.0
2016-09-15T03:45:15.357Z
@PeterShor, We don't use just the gate because we are limited by a finite set of primitive operations defined as a part of the Turing machine.
Omar Shehab
CC BY-SA 3.0
2016-09-15T14:51:40.927Z
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.
Peter Shor 
CC BY-SA 3.0
2017-04-18T05:45:48.713Z
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
Youness Abdus Salam
CC BY-SA 3.0
2018-04-04T00:43:56.350Z
@PeterShor - This question could be answered at: https://quantumcomputing.stackexchange.com/ .
Rob
<quantum-computing><automata-theory><turing-machines><kolmogorov-complexity><descriptive-complexity>
Questions about the definition of the Quantum Turing Machine
Omar Shehab
# Questions about the definition of the Quantum Turing Machine

(Asked by: username_0 on 2016-09-13)

I am trying to have a better understanding of the definition of the [Quantum Turing Machine](https://en.wikipedia.org/wiki/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.

**Tags:** quantum-computing, automata-theory, turing-machines, kolmogorov-complexity, descriptive-complexity

> **Comments:**
> **username_1**: 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?  
> **username_1**: 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?  
> **username_0**: @PeterShor, yes $\sqrt{2}$ is computable. So, yes, now I understand that a quantum computer can print $n$ digits of the number and halt.  
> **username_0**: @PeterShor, We don't use just the gate because we are limited by a finite set of primitive operations defined as a part of the Turing machine.  
> **username_1**: 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.  
> **username_2**: 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  
> **username_3**: @PeterShor - This question could be answered at: https://quantumcomputing.stackexchange.com/ .  

---

## 0 answers

