Questions tagged [church-turing-thesis]

A hypothesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

Filter by
Sorted by
Tagged with
4
votes
2answers
285 views

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

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 ...
4
votes
2answers
198 views

How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?

Note: This has been cross-posted to CS Theory SE. If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
5
votes
3answers
1k 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 ...