Questions tagged [quantum-advantage]
"Quantum advantage" or "quantum supremacy" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.
30
questions
2
votes
2answers
106 views
Interpretations of quantum computing power [closed]
Over the years I encountered different explanations of quantum computing advantage over classical computers. But I am not sure which explanations are in fact valid and which are not.
Quantum ...
2
votes
0answers
24 views
Boson Sampling with a single beamsplitter
In Boson Sampling as first proposed by Aaronson and Arkhipov in arxiv.org/abs/1011.3245, the interferometer is made up of phase shifters and beamsplitters. As these gates are universal, drawing the ...
3
votes
3answers
258 views
How to distinguish quantum random from classical random?
Given two sets of $N$ uniformly random binary bitstrings of size $m$, such as $$(x_0,x_1,...,x_m) \space \forall x_i \in \{0,1\}.$$
One generated from a quantum device and the other generated by ...
2
votes
1answer
64 views
What is the problem in demonstrating quantum supremacy?
I am new to the quantum world and it's computing. But it accidentally hit in my mind that DWave built a quantum computer with 2000 qubits which can be use to simulate the whole observable universe or ...
3
votes
2answers
127 views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
2
votes
1answer
74 views
How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?
According to these lecture notes from Berkeley, the Extended Church-Turing Thesis (ECT) asserts that:
...any "reasonable" model of computation can be efficiently simulated on a standard model such ...
3
votes
1answer
359 views
Making sense of the Sycamore's computing prowess - power consumption
I came here after reading about the announcement regarding the Sycamore processor and Google's Quantum Supremacy claim. I am hung up on several key things and I am hoping that I could find those ...
19
votes
2answers
4k views
What does Google's claim of “Quantum Supremacy” mean for the question of BQP vs BPP vs NP?
Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."
Does this mean that they have definitely proved that BQP ≠ BPP ?...
6
votes
2answers
224 views
Why does Google's quantum processor outperform IBM's?
I understand that both have 53 qubit devices, yet it is Google that has demonstrated quantum supremacy (although IBM refutes this!). I'm not sure if this is true but it seems like IBM cannot replicate ...
11
votes
3answers
345 views
Why do the IBM and Google processors both have 53 qubits?
As I understand from this IBM post both the IBM and Google teams have independently built 53-qubit processors. What is the significance of the number 53? It is purely coincidental, or is there a ...
7
votes
2answers
146 views
Are 20 repetitions of Sycamore's one- and 2-qubit gates sufficient to produce a uniformly random state?
In the answer to this question about random circuits, James Wootton states:
One way to see how well we [fully explore the Hilbert space] is to focus on just randomly producing $n$ qubit states. ...
5
votes
3answers
850 views
Quantum Supremacy: Some questions on cross-entropy benchmarking
I was skimming through the Google quantum supremacy paper but got stuck on this section:
For a given circuit, we collect the measured bit-strings $\{x_i\}$ and compute the linear XEB fidelity [24-...
5
votes
1answer
145 views
Number of qubits to achieve quantum supremacy?
Google's Sycamore paper describes achieving quantum supremacy on a $53$-qubit quantum computer. The layout of Sycamore is $n=6\times 9=54$ nearest neighbors, with one qubit nonfunctional. They apply ...
2
votes
1answer
312 views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
4
votes
1answer
353 views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
8
votes
2answers
475 views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was ...
3
votes
2answers
235 views
Do quantum supremacy experiments repeatedly apply the same random unitary?
It is my understanding that, given a quantum computer with $n$ qubits and a way to apply $m$ single- and 2-qubit gates, quantum supremacy experiments
Initialize the $n$ qubits into the all-zero's ket ...
5
votes
2answers
98 views
What is the point of building arithmetic circuits in a quantum computer?
My question simply is the following: is there any interests in building arithmetic circuits such as adders or multiplier on a quantum computer?
I'm asking this because it seems that classical ...
4
votes
0answers
38 views
Strong vs weak simulations and the polynomial hierarchy collapse
(Edited to make the argument and the question more precise)
An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a ...
8
votes
4answers
447 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
156 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
66 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 ...
16
votes
0answers
410 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 ...
7
votes
2answers
198 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 ...
7
votes
1answer
374 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 ...
12
votes
1answer
3k 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
377 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
5k 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
702 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 ...
22
votes
2answers
774 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. ...
