For questions about the quantum analogue of the universal Turing machine; i.e., for questions about the theoretical construct that is the universal quantum computer. This tag is not for questions about the normal Turing machine; those would usually fit better on Computer Science SE.
Questions tagged [quantum-turing-machine]
19 questions
18
votes
2 answers
In a Quantum Turing Machine, how is the decision to move along the memory tape made?
Let, for a Quantum Turing machine (QTM), the state set be $Q$, and the alphabet of symbols be $\sum=\{0,1\}$, which appear at the tape head. Then, as per my understanding, at any given time while the QTM is calculating, the qubit that appears at its…
Prem
- 233
- 1
- 8
11
votes
3 answers
What precisely is the quantum extended Church-Turing thesis?
Context
Prof. Aaronson mentions that the quantum extended Church-Turing (quantum ECT) thesis has no known counterexamples cf. around 14:18 but doesn't mention its precise statement.
Questions
What precisely is the statement of the quantum extended…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
2 answers
Does there exists an algorithm to construct a quantum circuit given an arbitrary unitary?
Suppose there exists an algorithm that takes as input an arbitrary unitary matrix and produces as output a quantum circuit representing that matrix. Then in theory that algorithm could construct any quantum circuit. This would be quite…
treks2448
- 71
- 1
6
votes
0 answers
Is the universality of a qubit based quantum computer different from the universality of a continuous-variable quantum computer?
I understand that a quantum computer is universal if it can compute anything that a quantum Turing machine can. Another way to think about universality is that any unitary transformation on, e.g., a registry of qubits or their continuous-variable…
Kiro
- 2,025
- 17
- 24
6
votes
2 answers
Can quantum computers design quantum computers autonomously better than other methods?
We've seen people use computers to design computers, AI to write computer programs, robots teach themselves, and even robots build themselves. I understand that conventional computers can be used to emulate quantum computers.
Robotic arm builds…
Rob
- 2,339
- 1
- 16
- 30
5
votes
2 answers
Does the massive parallelization in Quantum computing imply parallelization of input (as opposed to Turing machine)?
Being a newbie in this field, I'm trying to understand what types of real-life workloads are suitable for migrating to Quantum computers.
Intuitively, it seems to me that if a Quantum computer ingests data by reading symbols one-by-one from a tape,…
Erez Buchnik
- 53
- 4
4
votes
2 answers
Has any research been done on quantum Zeno machines?
Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model related to Turing machines that allows a countably infinite number of algorithmic steps to be performed in finite time.…
user820789
- 3,440
- 13
- 43
4
votes
0 answers
Deutsch Algorithm on a Quantum Turing Machine
I understood how a Quantum Turing Machine works from this lecture.
It would be great if someone could give an example of how this machine could be used to solve a real problem though, for example, simulate the Deutsch algorithm on a Quantum Turing…
Mahathi Vempati
- 1,731
- 10
- 21
4
votes
2 answers
What is the minimum set of primitive operations for a quantum computer?
In 1938, in a famous paper, Alan Turing proved that you could simulate any Turing machine with the following six primitive operations:
1. Move one square to the right
2. Move one square to the left
3. Write a symbol on the current square
4. Read any…
user19266
4
votes
0 answers
Is continuous-variable quantum computing a model of a quantum universal Turing machine?
In this question of a few days ago, it was raised the question about the similarities or differences between the notion of universality in discrete-variable (DV) quantum computers and continuous-variable (CV) computers. My question is in the same…
RMPsp
- 41
- 2
3
votes
0 answers
Explicit Construction of Classical Rules in Quantum Turing Machine
I knew that we usually use circuit instead of Turing machine in Quantum computation.
In a deterministic Turing machine one has transition rules,
$$
\delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{\pm 1, 0\},
$$
where $Q, \Gamma$ are set of…
Taylor Huang
- 175
- 5
3
votes
1 answer
Quantum circuits, quantum Turing machine and universal quantum computer-comparing different models of quantum computations
Forgive me if this question was already asked somewhere on this site-I haven't found it but it is possible that I've overlooked it. So basically, I would like to summarize different notions of quantum models of computations, namely:
Quantum…
truebaran
- 203
- 1
- 6
3
votes
1 answer
How does a quantum circuit capture the "non-halting ability" of classical Turing machines?
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…
user1936752
- 3,311
- 1
- 9
- 24
1
vote
1 answer
Will quantum computers pass the Turing test?
Will quantum computers be able to pass the Turing test sooner than classical computers?
user10151
1
vote
1 answer
Are Quantum Algorithms that construct another Quantum Algorithm still valid to solve problems in BQP?
The title of this question is somewhat convoluted. Essentially, a problem is in BQP if there is a Turing machine that runs in polynomial time that computes a polynomial depth quantum circuit that solves the problem.
What about something like…
TwentyCents
- 117
- 4