Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes
Accepted

Can quantum computers design quantum computers autonomously better than other methods?

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 ...
Mithrandir24601's user avatar
  • 3,696
7 votes
Accepted

In a Quantum Turing Machine, how is the decision to move along the memory tape made?

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)...
John Watrous's user avatar
  • 6,097
7 votes
Accepted

What precisely is the quantum extended Church-Turing thesis?

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 ...
Greg Kuperberg's user avatar
6 votes

What precisely is the quantum extended Church-Turing thesis?

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 ...
Sanchayan Dutta's user avatar
5 votes
Accepted

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

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 ...
glS's user avatar
  • 25.2k
5 votes
Accepted

Has any research been done on quantum Zeno machines?

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 ...
David Bar Moshe's user avatar
4 votes

Can quantum computers design quantum computers autonomously better than other methods?

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 ...
Sanchayan Dutta's user avatar
4 votes

Does there exists an algorithm to construct a quantum circuit given an arbitrary unitary?

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 ...
Nikita Nemkov's user avatar
4 votes

Does there exists an algorithm to construct a quantum circuit given an arbitrary unitary?

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 ...
narip's user avatar
  • 3,004
3 votes

Quantum circuits, quantum Turing machine and universal quantum computer-comparing different models of quantum computations

A quantum computer (or quantum Turing machine or quantum circuit) cannot solve any problem that a classical computer could not, because one can simulate the other Initially in a comment I had ...
Mark Spinelli's user avatar
3 votes
Accepted

What is the minimum set of primitive operations for a quantum computer?

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 ...
Craig Gidney's user avatar
  • 37.5k
2 votes

What precisely is the quantum extended Church-Turing thesis?

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 ...
Mark Spinelli's user avatar
2 votes

Does the massive parallelization in Quantum computing imply parallelization of input (as opposed to Turing machine)?

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? ...
glS's user avatar
  • 25.2k
2 votes

Do biological brains compute using quantum mechanics?

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....
user245427's user avatar
1 vote
Accepted

Are Quantum Algorithms that construct another Quantum Algorithm still valid to solve problems in BQP?

Welcome to QCSE. Your wording is a little informal but I think you are asking whether BQP is "low for itself", that is, if $\mathsf{BQP}^\mathsf{BQP}=\mathsf{BQP}$. That is, I think you ...
Mark Spinelli's user avatar
1 vote

What is the minimum set of primitive operations for a quantum computer?

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.
Norbert Schuch's user avatar
1 vote
Accepted

How does a quantum circuit capture the "non-halting ability" of classical Turing machines?

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 ...
Egretta.Thula's user avatar
1 vote
Accepted

Do biological brains compute using quantum mechanics?

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/...
Enrique Segura's user avatar
1 vote
Accepted

Does the massive parallelization in Quantum computing imply parallelization of input (as opposed to Turing machine)?

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 ...
Martin Vesely's user avatar
1 vote

Has any research been done on quantum Zeno machines?

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 ...
Mark Spinelli's user avatar

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