23 votes
Accepted

Did D-Wave show quantum advantage in 2023?

A clear case of quantum advantage Google's quantum group demonstrated quantum advantage with a much earlier version of D-Wave hardware in the following figure from a 2016 paper, in which the D-Wave ...
user1271772 No more free time's user avatar
22 votes
Accepted

Why do the IBM and Google processors both have 53 qubits?

It's just a coincidence. I can speak from personal recollection on the Google side. Google originally intended to use a 72 qubit chip (Bristlecone) where qubits were essentially directly connected to ...
Craig Gidney's user avatar
  • 37.1k
19 votes
Accepted

When will we know that quantum supremacy has been reached?

The term quantum supremacy doesn't necessarily mean that one can run algorithms, as such, on a quantum computer that are ...
Niel de Beaudrap's user avatar
18 votes
Accepted

Quantum machine learning after Ewin Tang

I am not an expert in the field but there are a few points that I am aware of: There are proofs that certain quantum machine learning algorithms cannot be efficiently simulated on a classical ...
sheesymcdeezy's user avatar
17 votes

What exactly is "Random Circuit Sampling"?

There are a continuous set of possible states for $n$ qubits, each of which can be expressed as a superposition of the $2^n$ basis states. Mostly of these states are highly entangled, and would ...
James Wootton's user avatar
16 votes
Accepted

What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?

Google's paper/results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\...
Mark Spinelli's user avatar
15 votes
Accepted

What countries are leading this "Global Quantum Computing Race"?

There are several countries that are actively participating in the "Quantum Race", most of which are making significant investments. The estimated annual spending on non-classified quantum-technology ...
whurley's user avatar
  • 529
13 votes
Accepted

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Are there examples of quantum algorithms only composed of Clifford operations that show [...] A reduction in the "same spirit" of the $n^{800}→n$ for instance. No. An $n$ qubit Clifford+...
Craig Gidney's user avatar
  • 37.1k
13 votes
Accepted

Any simple description of a circuit for Yamakawa-Zhandry algorithm?

The Yamakawa-Zhandry algorithm is a breakthrough that has some properties similar to the other major quantum algorithms such as Shor's, and some that are quite a bit different. Apparently the ...
Mark Spinelli's user avatar
12 votes
Accepted

Are there problems in which quantum computers are known to provide an exponential advantage?

Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is ...
Squeamish Ossifrage's user avatar
12 votes

Are there problems in which quantum computers are known to provide an exponential advantage?

Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is ...
Emily Tyhurst's user avatar
12 votes
Accepted

Are there quantum algorithms showing a double exponential advantage?

Classical computers can simulate quantum computers with an exponential overhead. Thus, there cannot be a doubly exponential speedup (unless maybe in some blackbox setting, cf Deutsch-Jozsa).
Norbert Schuch's user avatar
11 votes

What is the advantage of quantum machine learning over traditional machine learning?

As so often, and especially in young research areas, the answer depends quite a lot on how you break down the question. Let me try a few examples: Does quantum mechanics change what is theoretically ...
Maria Schuld's user avatar
10 votes

What are the real advantages of superdense coding?

TL;DR: While two qubits must be transmitted in total, in the instant where two bits are to be communicated, only one qubit has to be sent. The information being sent is masked, but it is not truly ...
DaftWullie's user avatar
  • 58.1k
10 votes

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Quantum advantage using Clifford gates Gottesman-Knill theorem applies to stabilizer circuits only, not to all circuits consisting of Clifford gates. The former satisfy the stronger requirements of ...
Adam Zalcman's user avatar
  • 22.3k
9 votes

What exactly makes quantum computers faster than classical computers?

"What feature of a quantum algorithm makes it better than its classical counterpart?" First, a classical algorithm can be thought of as a quantum algorithm that makes no use of quantum ...
Niagara Falls's user avatar
9 votes

Quantum Supremacy: How do we know that a better classical algorithm doesn't exist?

For all we know, it is extraordinarily hard to prove that a problem which can be solved by a quantum computer is classically hard. The reason is that this would solve an important and long-standing ...
Norbert Schuch's user avatar
9 votes

Are there problems in which quantum computers are known to provide an exponential advantage?

The complexity class of decision problems efficiently solvable on a classical computer is called BPP (or P, if you don't allow randomness, but these are suspected to be equal anyway). The class of ...
tparker's user avatar
  • 2,741
9 votes
Accepted

Why does QAOA achieve quantum supremacy in an algorithmic sense?

"but for me quantum supremacy would mean that no classical algorithm can exist at all that solves the problem in a better way than a quantum algorithm." If that were the case, then "...
user1271772 No more free time's user avatar
9 votes

Why exactly are variational algorithms considered promising?

"As far as I understand there aren't many rigorous results on performance of these algorithms, similar to many classic machine learning approaches." You are correct in that, unlike Grover's ...
user1271772 No more free time's user avatar
9 votes

What is the fastest quantum computational algorithm by which quantum computer speed up than classic one?

Probably the best candidates are Deutsch-Jozsa, Bernstein-Vazirani and Simon algorithms. All these allow to solve tasks exponentially complex on classical computer with only one step regardless input ...
Martin Vesely's user avatar
8 votes
Accepted

Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings

TL/DR: The two-qubit gates are going by the moniker "Sycamore gates" in the paper, and it appears that they would ideally want to explore more of the $(\phi, \theta)$ phase-space but for ...
Mark Spinelli's user avatar
8 votes
Accepted

Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling

What does "obtaining samples" mean in this context? The same thing it means in a more classical context. Consider the probability distribution of the possible outcomes of a (possibly biased) coin ...
glS's user avatar
  • 24.9k
8 votes

Does Google's error correction paper invalidate Gil Kalai's arguments?

Note: views are my own. I think experiments of this type will refute Gil's arguments, but I would be uncomfortable claiming that yet. I like nice clear don't-even-really-need-statistics answers to ...
Craig Gidney's user avatar
  • 37.1k
7 votes

When will we know that quantum supremacy has been reached?

The term quantum supremacy, as introduced by Preskill in 2012 (1203.5813), can be defined by the following sentence: We therefore hope to hasten the onset of the era of quantum supremacy, when we ...
glS's user avatar
  • 24.9k
7 votes

Quantum Supremacy: How do we know that a better classical algorithm doesn't exist?

How do we know no better classical algorithm exist? We can know thanks to computational complexity theory, which studies the complexity of solving different problems with different computational ...
glS's user avatar
  • 24.9k
7 votes
Accepted

Making sense of the Sycamore's computing prowess - power consumption

They say in Section X.H of the supplement that the Summit supercomputer has a power capacity of 14 megawatts. They compare that to their own setup. Their power consumption is mainly their dilution ...
Greg Kuperberg's user avatar
7 votes
Accepted

Why Google has used $\sqrt{X}$ and $\sqrt{Y}$ instead of $X$ and $Y$ in supremacy experiment?

While Craig Gidney (from Google) is correct in his comment which says that $X$ and $Y$ do not create superpositions on states that are not in superposition, such as $|0\rangle$ and $|1\rangle$; even ...
user1271772 No more free time's user avatar
7 votes
Accepted

Does quantum computers give any advantage over classical computers in Sudoku?

You are correct that solving Sudoku for $n^2 \times n^2$ grids with $n\times n$ blocks is an NP complete problem. The quantum complexity class BQP is the class of decision problems solvable by a ...
user1271772 No more free time's user avatar
7 votes
Accepted

Confusion about the output distribution of Haar random quantum states

The two facts are connected in that they both arise as a result of rotational invariance of the Haar measure. We will derive them in the case of large $n$ since this is when the Porter-Thomas ...
Adam Zalcman's user avatar
  • 22.3k

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