Questions tagged [quantum-turing-machine]

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 fit better on Computer Science SE.

Filter by
Sorted by
Tagged with
64
votes
3answers
3k views

Can a Turing machine simulate a quantum computer?

I know that a Turing machine1 can theoretically simulate "anything", but I don't know whether it could simulate something as fundamentally different as a quantum-based computer. Are there any ...
15
votes
2answers
566 views

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 ...
6
votes
2answers
188 views

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 ...
3
votes
3answers
379 views

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 ...
3
votes
1answer
203 views

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 ...
3
votes
0answers
77 views

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, ...
2
votes
2answers
98 views

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 ...
2
votes
0answers
26 views

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\...
1
vote
1answer
40 views

Will quantum computers pass the Turing test? [closed]

Will quantum computers be able to pass the Turing test sooner than classical computers?
0
votes
1answer
78 views

Can every process in nature be simulated by a Turing Machine or a quantum computer?

Given any initial condition or value A, A leads to B after a procedure of physics or nature P. Now is there any turing machine or quantum computer that can simulates P,converting A into B? In other ...
-1
votes
2answers
57 views

Do biological brains compute using quantum mechanics? [closed]

Someone on research gate said the answer was no Our brain is a neural network with a very complex connectome. Any system is in a sense a computer adhering quantum mechanics, but what is known ...