Skip to main content
Share Your Experience: Take the 2024 Developer Survey
74 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 ...
Tom van der Zanden's user avatar
41 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 ...
Yuval Filmus's user avatar
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, ...
Yuval Filmus's user avatar
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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Craig Gidney's user avatar
  • 5,862
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 ...
Yamar69's user avatar
  • 1,073
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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Discrete lizard's user avatar
  • 8,248
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 ...
Acccumulation's user avatar
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 ...
The Vee's user avatar
  • 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 ...
Tom van der Zanden's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 161k
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 ...
Craig Gidney's user avatar
  • 5,862
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 ...
amihart's user avatar
  • 91
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 ...
Craig Gidney's user avatar
  • 5,862
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 ...
R.. GitHub STOP HELPING ICE's user avatar
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 ...
Ran G.'s user avatar
  • 20.7k
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 ...
Stella Biderman's user avatar
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 ...
Craig Gidney's user avatar
  • 5,862
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 ...
David Richerby's user avatar
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 ...
countermode's user avatar
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 ...
Laakeri's user avatar
  • 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 ...
Clément's user avatar
  • 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 ...
David Richerby's user avatar
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.
Yuval Filmus's user avatar
5 votes
Accepted

How is the oracle function for Grover's Search algorithm obtained?

Here's the problem Grover's algorithm helps you solve: Input: a function $f$ Output: a value $r$ such that $f(r)=0$ If you're paying attention, you should ask how $f$ is specified. This is the ...
D.W.'s user avatar
  • 161k

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