73
votes
Why did Google not use an NP problem for their quantum supremacy experiment?
there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.
This statement is wrong. There are many NP problems which ...
- 13.1k
40
votes
Can Quantum Computing solve Problems not even a Turing Machine can solve?
While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, ...
- 275k
40
votes
Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?
No, there will be absolutely no implication, for several reasons:
The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard ...
- 275k
23
votes
Accepted
Why is a quantum computer not capable of solving more problems than a classical computer?
Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each ...
- 81.4k
22
votes
Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?
No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how ...
- 4,282
19
votes
Can Quantum Computing solve Problems not even a Turing Machine can solve?
There's no difference in terms of computability. Classical computers can simulate quantum computers. A Turing machine can compute anything that a quantum computer can compute.
This isn't some ...
- 5,802
19
votes
Quantum Supremacy Task
First of all it seems that google has exaggerated a little bit by shooting the $10000$ years results. It seems that IBM, on his current and most powerful classic super computer, is able to perform the ...
- 1,053
18
votes
Will the future quantum computers use the binary, ternary or quaternary numeral system?
The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use ...
- 4,282
18
votes
Is there any proof that quantum computers are more efficient than classical computers?
Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any ...
- 20.6k
18
votes
Does this article imply that Turing-Computability is not the same as "effectively computable"?
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and ...
- 7,768
16
votes
Accepted
What specifically makes quantum computers useful?
Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. ...
- 5,802
14
votes
Accepted
Does this article imply that Turing-Computability is not the same as "effectively computable"?
There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them ...
- 710
13
votes
Accepted
Intuition behind the Hadamard gate
The Hadamard gate might be your first encounter with superposition creation. When you say you can relate the usefulness of the Pauli $X$ gate (a.k.a. NOT) to its ...
- 418
12
votes
Accepted
Are there any problems that require exponential time in quantum computing?
Most problems that require exponential time on a classical computer also require exponential time on a quantum computer. For example EXPTIME-complete problems will require exponential time on either ...
- 17.6k
12
votes
Intuition behind the Hadamard gate
The Hadamard gate operates on a single qubit. The state of a single qubit can be described as $\alpha \left|0\right\rangle + \beta \left|1\right\rangle$, where $|\alpha|^2 + |\beta|^2 = 1$. If you ...
- 275k
12
votes
Quantum Supremacy Task
The task performed by the Sycamore computer was meaningless. The output of the computation is essentially a random number.
So why does anyone care about it? On a very simple level, quantum computers ...
- 13.1k
11
votes
Why is a quantum computer not capable of solving more problems than a classical computer?
Classical computers are already Turing complete, i.e. they can calculate everything that a Turing machine can (a theoretical computer model from Computer Science). According to the Church–Turing ...
- 218
11
votes
Accepted
Is it proven that quantum computation is no better at solving NP complete problems than classical computation?
It is suspected that NP-complete problems cannot be solved in quantum polynomial time (i.e., that they are not in BQP), but this hasn't been proved. We don't expect a proof in the near future, since ...
- 275k
10
votes
Is there a formalization of the computational model for quantum computers?
Yes. The quantum Turing machine is a mathematical formalization of a computation model for a quantum computer.
See also https://en.wikipedia.org/wiki/Quantum_computing#Developments and https://en....
D.W.♦
- 154k
9
votes
Accepted
Known problems in BQP \ NP?
If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is also still an open problem.
It is ...
- 5,802
9
votes
Accepted
Does the order in which qubits are measured matter in quantum computing?
No, the order doesn't matter.
Proofs
Algebra. Take an input state $\sum_k c_k |k_0 k_1 k_2 ...\rangle$. Apply the definition of measurement from your textbook to it. Compute the expression for the ...
- 5,802
9
votes
Why did Google not use an NP problem for their quantum supremacy experiment?
Because then their experiment would have been a complete failure.
As I wrote in an answer on a sister site (which was somewhat poorly received there, but I think your question validates what I was ...
8
votes
Applying a multi qubit quantum gate to specific qubits
Don't use the swap method, it's very inefficient. And the other person's answer is specific to the CNOT gate, and to be frank, over-complicates things.
Here's a very simple algorithm that solves your ...
- 81
8
votes
Accepted
Do quantum logic gates work differently than traditional logic gates?
In layman's terms, the answer is yes: quantum gates are quite different from classical gates.
One reason is that quantum gates must be reversible. This practically means that AND gates don't even ...
- 20.6k
8
votes
Accepted
Is there a formalization of the computational model for quantum computers?
Just as Turing machines aren't widely used to model computation, so are quantum
Turning machines not wildly used to model quantum computation. Instead Quantum circuits are more popular. Quantum ...
- 767
7
votes
Quantum computer memory size
No, quantum computers are not going to have an enormous number of operations per second, in fact they are probably going to be much slower in the foreseeable future. The situation with memory seems ...
- 275k
7
votes
Accepted
Applying a multi qubit quantum gate to specific qubits
Expand-n-Swap
If you want to apply a gate to a subset of the qubits:
Expand operations up to $2^n$x$2^n$ with the tensor product / Kronecker product.
Use swap gates to make the target qubits ...
- 5,802
7
votes
Accepted
How correct was Justin Trudeau's explanation of Quantum Computing?
Trudeau's explanation wasn't wrong, but it also wasn't very informative.
Scott Aaronson, a well-known quantum computational complexity theorist, made a blog post discussing it:
What marks does ...
- 5,802
7
votes
Turing machines and their computational power
Your question is closely related to the Church–Turing thesis, which says that Turing machines can compute anything that can reasonably be described as an algorithm (i.e., a sequence of discrete ...
- 81.4k
Only top scored, non community-wiki answers of a minimum length are eligible