75
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.4k
42
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 ...
- 278k
23
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,437
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,073
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 ...
- 8,322
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
13
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.4k
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 ...
- 278k
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 ...
- 278k
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.♦
- 164k
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,892
9
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 ...
- 91
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
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.8k
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 ...
- 777
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 ...
- 82.1k
7
votes
Why did Google not use an NP problem for their quantum supremacy experiment?
Quantum computing is not a piece of magic, and there seems to be a widespread misconception about the power of quantum computers. I am by no means an expert in this field, but as far as I know QC is ...
- 171
7
votes
Accepted
Can current quantum computers decide languages that Turing Machines cannot?
No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated ...
- 1,339
6
votes
Is there a formalization of the computational model for quantum computers?
Peter Sellinger has been working on programming languages for quantum computing for a long time now. He is not the only one working in that field, of course, but I believe his work is accessible and ...
- 161
6
votes
Accepted
How $N$ qubits correspond to $2^N$ bits?
Despite what badly written pop-science explanations of quantum computation may tell you, a qubit is not two classical bits and $N$ qubits is not $2^N$ bits. Qubits are fundamentally different from ...
- 82.1k
6
votes
Accepted
Is there a complexity class QPP?
Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
- 278k
6
votes
Accepted
Is there a concept of probabilistic quantum computers?
It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in ...
- 178
5
votes
Accepted
Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
No, a quantum computer can't sum $n$ outputs from a black box function in $O(\lg n)$ queries.
For example, you could use magic summing power to easily do asymptotically better than Grover's algorithm ...
- 5,892
5
votes
Accepted
What would remain of Quantum Computing if quantum states were real numbers?
The gate set Hadamard + Toffoli is universal for quantum computation [1] and only uses real number coefficients (some negative). So all quantum algorithms can be run without involving imaginary ...
- 5,892
5
votes
Accepted
Understanding the state vector in Quantum Computing
No, it's not correct. It's not true in general that one entry will be 1 and all others 0; that is true for the basis vectors, but there are other states (other vectors) where that isn't true. You ...
D.W.♦
- 164k
5
votes
Accepted
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).
Thus, your ...
- 1,661
4
votes
What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
It depends.
If $\mathrm{BPP} = \mathrm{BQP} = \mathrm{EXP} = \mathrm{EXP}^\mathrm{NP}$, then any oracle separation result would necessarily go beyond $\mathrm{ELEMENTARY} = \cup_{k} k-\mathrm{EXP}$.
...
- 2,295
4
votes
Accepted
Inputting a superposition into a cNOT gate
This is more of a question on linear algebra rather than a question about quantum computation. You should probably have a firm grip on basic linear algebra (vector spaces, linear operators, inner ...
- 13.5k
4
votes
Doesn't a quantum algorithm being deterministic contradict the superposition principle?
If the algorithm has no error, then the system is not in a superposition when it is measured, but it is possible it was in a superposition during the computation, after which it was cleverly ...
- 4,437
Only top scored, non community-wiki answers of a minimum length are eligible