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.

Filter by
Sorted by
Tagged with
30
votes
4answers
1k 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 ...
29
votes
1answer
1k 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 ...
25
votes
2answers
1k 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. ...
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 ?...
15
votes
1answer
5k 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 ...
13
votes
3answers
515 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 ...
11
votes
2answers
337 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 ...
11
votes
2answers
727 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 ...
10
votes
3answers
8k 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 ...
10
votes
2answers
1k views

What are the real advantages of superdense coding?

In superdense coding, two qubits are prepared by Eve in an entangled state; one of them is sent to Alice and the other is sent to Bob. Alice is the one who wants to send (to Bob) two classical bits of ...
9
votes
1answer
243 views

Why exactly are variational algorithms considered promising?

There is obviously a great deal of work happening at the moment on variational quantum algorithms. However, I'm struggling to understand why exactly are they considered promising? Looking through some ...
9
votes
2answers
1k 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
4answers
1k 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 ...
8
votes
2answers
171 views

Why does QAOA achieve quantum supremacy in an algorithmic sense?

In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15): "If [...] the QAOA outperforms all known classical algorithms ...
8
votes
1answer
768 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
1answer
495 views

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

In supremacy experiment Google has used $\sqrt{X}$ and $\sqrt{Y}$ as two of their single qubit gates (paper). So My questions are: Is there any specific reason for choosing these gates and not $X$...
8
votes
1answer
77 views

How can one define contextuality within the circuit model?

It is in general believed that contextuality is one of the quantum resource that provides the quantum advantage. A context is usually defined in terms of a set of commuting observables. The quantum ...
8
votes
2answers
262 views

Decomposing Hamiltonian into qubit model representation

One of the main applications of VQE is its application to find the approximation to the ground state energy (smallest eigenvalue of the Hamiltonian) for a particular molecule through an iterative ...
8
votes
1answer
333 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 ...
8
votes
0answers
63 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 ...
7
votes
3answers
692 views

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Let's say I want to solve a computational task which input can be encoded in $n$ bits of information. The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
7
votes
3answers
889 views

What exactly makes quantum computers faster than classical computers?

What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
7
votes
2answers
498 views

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

Why exactly is machine learning on quantum computers different than classical machine learning? Is there a specific difference that allows quantum machine learning to outperform classical machine ...
7
votes
1answer
194 views

What did exactly Google do in simulating a random quantum circuit on a classical computer in supremacy experiment?

I've been working on Google quantum supremacy paper for quite some time now and I have a problem in understanding how exactly they simulate their actual random quantum circuit on a classical computer. ...
7
votes
1answer
135 views

List of practical quantum computing algorithms that have speed-up higher than quadratic speed-up?

From this link (provided by @KAJ226's comment in this question), it appears as though current error correction methods are not enough to get practical speedup out of algorithms that have quadratic ...
7
votes
1answer
106 views

Could random quantum circuits be efficiently approximately simulated?

Google's landmark result last year was to compute a task with a quantum computer that a classical computer could not compute, and they chose random circuit sampling. Part of their justification was ...
7
votes
3answers
127 views

Is there quantum advantage to be had with a D-Wave computer in 2020?

I've seen a lot of excitement in the popular press about the computers made by D-Wave Systems, but when I dig deep the only practical things that I can figure out that one can do with the computer are ...
7
votes
1answer
356 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 ...
7
votes
1answer
234 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. ...
7
votes
1answer
156 views

Is Gaussian boson sampling (used for showing quantum advantage) a subcategory of the continuous variable approach?

I read about the photonic QC Jiŭzhāng that showed quantum advantage by Gaussian boson sampling. I read that boson sampling itself is a sub-universal technique of QC (where they use single-photon ...
7
votes
1answer
436 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
1answer
613 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: ...
5
votes
3answers
2k 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-26, ...
5
votes
1answer
480 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 ...
5
votes
1answer
98 views

Could a new benchmark of quantum processors Q-Score by Atos be more useful than quantum volume?

A few days ago, Atos company published new benchmark for quantum computers. The benchmark is called Q-Score and it is defined as follows: To provide a frame of reference for comparing performance ...
5
votes
2answers
162 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 ...
5
votes
1answer
119 views

How powerful are boundedly many $T$-gates?

For a natural number $k$ (0 is a natural number), let $T_k$ be the collection of all languages that can be efficiently decided by quantum circuits consisting of Clifford gates and at most $k$ $T$-...
5
votes
1answer
133 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 ...
5
votes
0answers
40 views

Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?

Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
4
votes
1answer
528 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 ...
4
votes
2answers
196 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 ...
4
votes
1answer
127 views

Is the BB84 protocol an example of "quantum supremacy"?

This is a fairly broad question, I hope it fits here. I am wondering if the BB84 protocol is an example of "quantum supremacy", ie. something a quantum computer can do but something that is assumed a ...
4
votes
1answer
34 views

Anticoncentration for two independent random quantum circuits in parallel

Consider two Haar random $n$ qubit unitaries, $U_1$ and $U_2$. Consider the quantum state $$|\psi\rangle = (U_1 \otimes U_2) |0^{2n}\rangle. $$ Let $p_x = |\langle x| \psi \rangle|^{2}$, for $x \in \{...
4
votes
1answer
155 views

Spoofing XQUATH with the Feynman method

Consider the XQUATH conjecture for random quantum circuits, as mentioned here. (XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There is no polynomial-time classical algorithm that ...
3
votes
2answers
321 views

Question regarding integration of Haar random state

I am trying to understand the integration on page 4 of this paper. Consider a Haar random circuit $C$ and a fixed basis $z$. Each output probability of a Haar random circuit (given by $|\langle z | C |...
3
votes
1answer
147 views

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

To my basic knowledge I know that solving a generalized Sudoku problems is an NP-complete problem so, is there any possible way quantum computers give an advantage over classical computers in this ...
3
votes
3answers
446 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 ...
3
votes
2answers
324 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 ...
3
votes
2answers
104 views

Q-means, QRAM and how it helps algorithmic speedup

I am trying to understand how QRAM will help improve algorithm performance. I am reading a paper on Q-means classification, but I have noticed that some other algorithms (Grovers) seem to have a ...
3
votes
1answer
136 views

Schmidt vectors for random quantum states

Consider a random quantum circuit $U$ over $n$ qubits, drawn from the Haar measure. Consider the quantum state $$|\psi\rangle = U |0^{n}\rangle.$$ Now, partition $n$ into two and consider the Schmidt ...