7

Sort of, quite possibly, if by degrees This is a speculative, but plausible, answer First of all, how do qubits interact and states evolve with time? The description of how individual qubits evolve (i.e. a single qubit gate operation) is given by some Hamiltonian1. Multiple, non-interacting qubits (that are exactly the same) therefore evolve using ...


7

If we have a QTM with state set $Q$ and a tape alphabet $\Sigma = \{0,1\}$, we cannot say that the qubit being scanned by the tape head "holds" a vector $a|0\rangle + b|1\rangle$ or that the (internal) state is a vector with basis states corresponding to $Q$. The qubits on the tape can be correlated with one another and with the internal state, as well as ...


5

There are two notions of Zeno topics related to quantum computation. The first, which is controversial is usually called hypercomputation, which deals with the possibility of surpassing the limitations of the Church-Turing thesis by means of quantum computation. It is related to the Zeno effect through the fact that if it could be realized, it may solve the ...


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 would also include "the read head has to contain a small finite state machine" as one of the requirements. Anyways, the answer is yes it's basically the same requirements. The main difference is that the tape symbols are replaced by qubits, and the read head also needs to have a qubit. Correspondingly, "read the symbol" is replaced by &...


4

As far as we know, yes. This is essentially the Church-Turing thesis. Note that this is not a mathematical result, but more of a definition of what it means to be computable. You can find plenty of discussions about this around. A few notable examples are: What would it mean to disprove Church-Turing thesis? (on cstheory) Extended Church-Turing Thesis [and ...


4

The quantum Turing machine can move into a superposition of moving left and right. This is different from the classical Turing machine which can only move either left or right.


4

We don't yet know if quantum computers are actually better than classical computers, as @heather mentions here. As for now there are just some theoretical algorithms which we know of, specifically for quantum-computers, which have much better time complexities than equivalent classical algorithms. For example - prime factorization and discrete logarithms. ...


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 ...


2

In terms of a gate-based model, almost any single two-qubit gate (i.e. a random gate) is universal. Otherwise, there's simple gate sets with two gates which are universal, such as Toffoli + Hadamard.


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

do we need to come up with completely different quantum-based solutions for such problems, or is there a way to 'interpret' existing algorithms to the quantum domain and still expect some speedup? Generally speaking yes, you need to come up with different algorithms. You cannot simply take a classical algorithm and "quantize it" in a straightforward way. ...


2

There is evidence that quantum coherence and it's role in chemical reactivity is responsible for the magnetic field sensing in migratory birds, the so called avian compass, https://arxiv.org/abs/1206.5946v1. Similar quantum effects and chemistry could very well be occuring and playing a role in the brain, though as far as I know there isn't anything ...


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 ...


1

As far as we know - and I know, so correct me anyone if there's research to the contrary - the neuron interactions in the brain are well within the classical regime. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5681944/


1

The reason that a quantum computer is faster in same tasks is given by different computational paradigm based on quantum mechanics laws. They mainly exploit superposition (i.e. state of qubit is linear combination of zero state and one state) and quantum entanglement (i.e. two or more qubits are connected and they behave as one system, or in other words ...


1

Suppose we are given the ($n\times n$ adjacency matrix $M_0$ of graph $G_0$ and $M_1$ of graph $G_1$, and we wish to know whether $G_0\simeq G_1$. It is a folklore result that if we can prepare states: $$\vert\alpha_G\rangle=\sum\limits_{\sigma\in S_n}\vert \sigma (G)\rangle,$$ with $S_n$ being the symmetric group on $n$ elements, we can prepare such a ...


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