4

I think there exist and the problem can be understood in an easier way. The problem is actually how to implement an arbitrary unitary gate, which has already been written into the book of Nielsen and Chuang(in chap 4.5, universal quantum gates). The content I mentioned in the link will tell you how to construct an arbitrary unitary gate with some fundamental ...


4

I will address the first two parts based on what I understood so far. The extended Church–Turing thesis or (classical) complexity-theoretic Church–Turing thesis states that "A probabilistic Turing machine can efficiently simulate any realistic model of computation.", whereas the quantum extended Church–Turing thesis or quantum complexity-theoretic ...


4

Taking the questions head on. I'm not sure that original references are very much the point, although there are some. It's not a hard question. The statement is that realistic polynomial time equals what a quantum computer (if you want to be rigorous, say a QTM) can do in polynomial time. The question has been answered many times in QCSE that a quantum ...


3

In the framing of the question (which I believe to be asked in good faith), there seems to be at least two objections. Sampling from a set of strings is not clearly a function, and Sampling is a physical process, outside of computation. Initially, with regard to the first objection, I assert that sampling is a function, as a search problem. For example, ...


3

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about ...


2

Regarding the "quantum (non-extended) Church-Turing Thesis," I think this asserts that there is no physical process, like a quasar or some other astronomical woo, that we know could produce a steady supply of qubits all in the same state $\alpha|0\rangle+\beta|1\rangle$, with the property that $\beta^2=\Omega_C$, that is, Chaitin's halting probability. We ...


2

There is an algorithm that goes by the name of Quantum Shannon Decomposition see the paper which allows to decompose any unitary into CNOTs and single-qubit gates. For an $n$-qubit unitary it produces roughly $\frac12 4^n$ CNOT gates which is only 2x more than the theoretical lower bound (see a related question Minimum number of 2 qubit gates to build any ...


1

If you take a look at the equivalence proofs by Yao (1993), Nishimura and Ozawa (2002), or Molina and Watrous (2018) you will notice that they always talk about quantum Turing machine computations that run for a predetermined number of steps. The equivalence means: $t$ steps of a quantum Turing machine running on an input of length $n$ can be simulated by a ...


Only top voted, non community-wiki answers of a minimum length are eligible