New answers tagged quantum-computing
5
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 with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, ...
7
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 very suitable for computational problems that employ some kind of cyclic structure. This happens to be true for problems like the integer factoring problem and ...
9
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 saying about how a general audience interprets it):
[the hyping of the result] plays on a discrepancy between what they mean by quantum supremacy (QS) and what ...
72
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 are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve.
What you are probably thinking of is NP-complete problems which is a ...
10
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 are essentially random number generators. However, they do not generate uniform random numbers. With a properly designed algorithm, we can make certain outputs ...
18
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 same task in $2.5$ days, saving the entire search space (Hilbert space) on a $250$ petabytes hard drive. This does not mean that google's result is not to be ...
1
The answer is, when working with sufficiently small numbers, we can simulate the quantum process on a classical computer. It might take exponentially longer on the classical computer, but for small numbers, that's still feasible (the exponential of a small number is still not too large).
See Question 6 at Scott Aaronson's FAQ (https://www.scottaaronson.com/...
Top 50 recent answers are included
