Questions tagged [quantum-advantage]

"Quantum advantage" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.

Filter by
Sorted by
Tagged with
27
votes
4answers
606 views

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

It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks. One of the most commonly cited examples of a problem in which quantum computers ...
21
votes
2answers
646 views

When will we know that quantum supremacy has been reached?

The term "quantum supremacy" - to my understanding - means that one can create and run algorithms to solve problems on quantum computers that can't be solved in realistic times on binary computers. ...
14
votes
0answers
320 views

Quantum machine learning after Ewin Tang

Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same ...
10
votes
3answers
4k views

What countries are leading this “Global Quantum Computing Race”?

The terms Quantum Computing Race and Global Quantum Computing Race have been used in the press and research communities lately in an effort to describe countries making investments into a "battle" to ...
9
votes
1answer
373 views

What exactly is “Random Circuit Sampling”?

Many people have suggested using "Random Circuit Sampling" to demonstrate quantum supremacy. But what is the precise definition of the "Random Circuit Sampling" problem? I've seen statements like "the ...
8
votes
2answers
269 views

Grover algorithm for a database search: where is the quantum advantage?

I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search. I ...
6
votes
2answers
157 views

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

According to the Wikipedia (Which quotes this paper https://arxiv.org/abs/1203.5813 by Preskill) the definition of Quantum Supremacy is Quantum supremacy or quantum advantage is the potential ...
6
votes
1answer
335 views

How to benchmark a quantum computer?

Using a simple puzzle game to benchmark quantum computers is the most clever approach I have seen so far. The author of the aforementioned article, James, makes a nice analogy to buying a laptop ("...
6
votes
0answers
262 views

What can tensor networks mean for quantum computing?

I am trying to understand what the importance of tensor networks is (or will/could be) for quantum computing. Does it make sense to study tensor networks deeply and develop them further to help pave ...
4
votes
1answer
82 views

What is the HOG test and how would it help proving quantum supremacy?

Proposed experiments in achieving quantum supremacy, such as with BosonSampling or using random circuits, have been described as using a (not necessarily Turing complete) quantum computer to perform ...
4
votes
0answers
50 views

Simulating quantum computers using anyon braiding

I am new to the concept of topological quantum computation (TQC). Recently I have been thinking about simulating a quantum computer on a classical computer. I know that if I use merely the unitary ...
2
votes
0answers
13 views

Strong vs weak simulations and the polynomial hierarchy collapse

A common argument for quantum computational "supremacy" assumes that there exists a classical sampler that outputs a probability $q_x$, $x \in \{0,1\}^{2^n}$ that approximates an output probability $...