Questions tagged [quantum-advantage]
"Quantum advantage" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.
6
votes
2answers
183 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 ...
4
votes
1answer
59 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
48 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 ...
13
votes
0answers
258 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 ...
6
votes
2answers
140 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
0answers
224 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 ...
8
votes
1answer
243 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 ...
6
votes
1answer
311 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 ("...
10
votes
3answers
3k 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 ...
27
votes
4answers
571 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
615 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. ...
