Questions tagged [quantum-advantage]

For questions about schemes to prove that quantum devices can, at least in principle, be exponentially more efficient than their classical ones. Also often referred to as "quantum computational advantage" or "quantum supremacy". Typical examples are sampling problems such as boson sampling and random circuit sampling.

Filter by
Sorted by
Tagged with
2 votes
0 answers
36 views

Create a superposition among the basis states of G for the hidden subgroup problem, implementing $\frac{1}{\sqrt{|G|}}\sum_{g\in G} | g,0\rangle$

I’ve been studying Simon’s problem and developing simulation models using Mathematica to extend the problem to other abelian groups and hidden subgroups of order $\geq 2$. I can now obtain the $h^\...
Phillip Dukes's user avatar
0 votes
0 answers
60 views

Is there some theorem that proves that entanglement is necessary for quantum advantage? [duplicate]

Gottesman-Knill theorem kind of implies that entanglement is not sufficient to produce quantum advantage because it can be simulated in many cases (for Clifford gates combinations). Also it is kind of ...
Mauricio's user avatar
  • 2,202
3 votes
0 answers
37 views

Advantage of quantum computers over classical computers in fully modeling interactions between atoms?

I'm trying to better understand the advantage quantum computers offer in terms of their ability to more accurately model chemical reactions. As a way to come to a deeper understanding, my question is: ...
Poe's user avatar
  • 31
1 vote
1 answer
148 views

What is the state of the art quantum state preparation algorithm?

Encoding classical information into a quantum computer is a bottleneck of quantum machine learning. I want to learn which algorithm for state preparation is the best (in complexity) currently. The ...
Saul_better's user avatar
4 votes
1 answer
742 views

Does the D-Wave hardware show any advantage for academic use-cases, for example in condensed matter physics?

The D-Wave team put out a few papers (like this one and this one) in the last few years describing how their methods can find ground states of certain spin-glass Hamiltonians faster than classical ...
sheesymcdeezy's user avatar
19 votes
2 answers
2k views

Did D-Wave show quantum advantage in 2023?

I would like to know your thoughts on whether or not D-Wave has shown a a smoking-gun example of quantum advantage this year. I am genuinely not quite sure what to think, but I believe the answer to ...
sheesymcdeezy's user avatar
4 votes
0 answers
63 views

Ansatz for VQE demonstrating Quantum Advantage

What would be a possible ansatz quantum state in VQE (variational quantum eigensolver [1]) that would demonstrate the quantum advantage of VQE over classic computers? More specifically, I see that VQE ...
user20374's user avatar
3 votes
0 answers
118 views

Can we obfuscate the identity?

Motivated by Aaronson's call to find simple, verifiable proofs of quantumness, suppose we start off with a random polynomial-length circuit $U$ of, say, Clifford+T gates, and attach $U^\dagger$ to it, ...
Mark Spinelli's user avatar
1 vote
0 answers
34 views

Measure on the unitary space and complexity

I'm currently studying various quantum supremacy protocols and i'm struggling to have a clear and well defined view on the rôle of approximating the Haar-measure (through k-designs ...) and the ...
Johan-Luca's user avatar
1 vote
0 answers
59 views

Heuristics on Quantum computers

I found the article : Strengths and Weaknesses of Quantum Computing, 1997 Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani As far as I understand, this one states that quantum ...
deb2014's user avatar
  • 83
4 votes
2 answers
1k views

How do researchers know / prove they've achieved quantum supremacy?

I'm currently reading the book Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything by Michio Kaku, and I came upon the following sentence: Soon after Google made its claim ...
raddevus's user avatar
  • 141
4 votes
1 answer
62 views

How to benchmark approximate random unitary sampling

I'm currently studying a specific sampling "quantum advantage" (sorry for the buzzword) protocol wich consist of periodically driving a random Ising chain (https://iopscience.iop.org/article/...
Johan-Luca's user avatar
2 votes
0 answers
33 views

Quantum algorithms with few T gates?

Many existing quantum algorithms require millions or billions of T gates to reach a scale that is classically hard to simulate. However, existing Clifford + T circuits seem hard even with 100 or so T ...
shixian105's user avatar
0 votes
1 answer
108 views

Does quantum computing take more computer memory (storage) than classical computing?

Please clarify: Let's say we have 3 bits of memory for classical computation (CC), we can represent any number between 0 and 7. On the other hand, with 3 qubits of memory for quantum computation (QC), ...
MAK's user avatar
  • 31
0 votes
0 answers
63 views

Most promising QML algorithms in the NISQ era

This question was asked in the previous years, but how is 2023 state of the art Quantum Machine Learning ? Things seem to go fast in this area, for instance I saw Thales used 4 qubits for quantum ...
Duen's user avatar
  • 296
2 votes
1 answer
236 views

Is there something wrong with cross-entropy benchmarking, or is it still considered as a reasonable path towards quantum supremacy?

My question is strongly related with this one. Google's quantum supremacy claim uses Random Circuit Sampling. The principle is the following one: a realistic noise model for random circuits performed ...
Tristan Nemoz's user avatar
1 vote
1 answer
97 views

Are there some cases where Grover's algorithm was used to improve machine learning performance?

Grover algorithm showing quantum advantage, are there some cases where it was used to improve Machine Learing performance ?
Duen's user avatar
  • 296
7 votes
3 answers
536 views

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

In his paper "The Argument against Quantum Computers, the Quantum Laws of Nature, and Google’s Supremacy Claims", Gil Kalai argues that quantum advantage will never be reached. For NISQ ...
Tristan Nemoz's user avatar
1 vote
0 answers
51 views

What problems can quantum computers solve right now which classical computers cannot solve? [duplicate]

I know that an error-corrected quantum computer with unlimited amount of qubits can provide a significant speed up compared to classical computers for specific kind of problems, e.g. searching in an ...
maiT's user avatar
  • 143
4 votes
1 answer
157 views

Are there problems where quantum computers are faster (in practice!) than classical ones? [duplicate]

Today's Quanta Magazine article says "But it’s proved difficult to find examples of any algorithms with a clear “quantum advantage” that enables performance beyond the reach of classical machines....
Martin C. Martin's user avatar
3 votes
2 answers
2k views

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

What is the fastest quantum computational algorithm by which quantum computers speed up than classic one? Of course, those speedup algorithms have to be proven.
XL _At_Here_There's user avatar
5 votes
2 answers
244 views

Can we use cryptocurrency mining to verify claims of quantum advantage?

Beginning with the earlier works of work of Brakerski et al. or the more recent results of Kahanamoku-Meyer et al., interactive proofs of quantum advantage entail a classical verifier (Vicky) ...
Mark Spinelli's user avatar
9 votes
1 answer
697 views

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

Recently, popular sources (including Aaranson's blog and Quanta Magazine) have made it look like the recent Yamakawa-Zhandry algorithm is akin to Shor's algorithm, in the sense that it could ...
Mauricio's user avatar
  • 2,202
15 votes
1 answer
497 views

Status of Google's quantum supremacy claim 2022

More than a year ago a couple of scientists made a splash by presenting a classical algorithm that took less than a week to simulate Sycamore's circuits on a small GPU cluster. Also, their simulations ...
MonteNero's user avatar
  • 2,369
7 votes
1 answer
258 views

What arguments point towards D-Wave devices being potentially useful?

I'm looking for any evidence pointing towards D-Wave's approach to quantum computation being promising to achieve any sort of computational advantage with respect to classical devices. Note that I'm ...
glS's user avatar
  • 23.4k
4 votes
3 answers
3k views

What are quantum computers actually doing today?

I am curious about what are quantum computers actually doing today. I seem to only be able to find information online about what they could be used for in the future (i.e. breaking encryption, quantum ...
Horus's user avatar
  • 41
2 votes
0 answers
86 views

Understanding the supremacy regime plot in Google's "Quantum supremacy using a programmable superconducting processor"

I was going through the Google's 2019 paper & had difficulties regarding some details. How are they calculating XEB in quantum supremacy regime? To calculate the XEB,we also need the ideal ...
Endeavour 's user avatar
3 votes
1 answer
147 views

Is there any rigorous proof that Quantum Annealing provides a quantum advantage?

Is there any rigorous proof that Quantum Annealing (QA) is of any benefit (e.g. in terms of time to optimal solution, convergence rate, etc.) for a specific problem? Or any empirical evidence for the ...
Nepomuk Hirsch's user avatar
2 votes
3 answers
167 views

Why do we need physical qubit if qubit can be simulated?

I do not see any advantage in constructing very costly and imperfect physical qubit while this qubit can be simulated with using conventional computer memory (noise-free). So what is the purpose when ...
Mariusz's user avatar
  • 379
2 votes
1 answer
66 views

I have question about cost of 'modular multiplication unitary' in Shor's algorithm

Here modular multiplication unitary means $U_a : |s\rangle \to|as\mod N\rangle$. My main question is, can the modular multiplication unitary $U_a$ can be constructed in time polynomial in the number ...
maar hybrid's user avatar
0 votes
0 answers
66 views

What tasks are quantum computers good at that classical computers are not?

At this stage, a large number of theoretical proofs have made us vaguely aware of the particularity of quantum computers. But what tasks are quantum computers good at that classical computers are not? ...
Ren-Xin Zhao's user avatar
2 votes
1 answer
207 views

Exponential advantage with Hadamard test

My question is the following: Let's assume that the only algorithm a quantum computer would be able to implement is the Hadamard test, which circuit is represented below, would we say that compared to ...
Marco Fellous-Asiani's user avatar
5 votes
1 answer
103 views

Quantum advantage without phase?

I'm wondering if one can (potentially) get any quantum advantage with $R_y$ single-qubit rotations and $CNOT$s only? (Note that I don't care about having a universal quantum computer.)
mavzolej's user avatar
  • 1,852
3 votes
2 answers
185 views

Are qubits just analog, continuous classical bits? [duplicate]

Topologically, classical bits (cbits) are essentially special cases of qubits restricted to the poles of the Bloch sphere. However, this restriction doesn't seem to be classical per se, but is simply ...
Tfovid's user avatar
  • 131
6 votes
2 answers
217 views

Proven quantum advantage (in the algorithmic sense) without error correction (for specific algo, or noise models)

I would like to know if there are some specific class of quantum algorithms, under some hypotheses about the noise model behind the quantum gates for which we know that there is an exponential ...
Marco Fellous-Asiani's user avatar
3 votes
2 answers
238 views

Derivation of the linear cross entropy

I'm looking at cross-entropy benchmarks and there's much that I'm reading at the moment but I'm stuck on one detail: how to derive the linear cross-entropy formula from the cross-entropy formula. The ...
James Whitfield's user avatar
5 votes
2 answers
970 views

Are there quantum algorithms showing a double exponential advantage?

I would like to know if there are known quantum algorithms that provide a double exponential advantage compared to the best known classical algorithms. More precisely, if the characteristics of the ...
Marco Fellous-Asiani's user avatar
4 votes
1 answer
618 views

What exactly makes VQE faster than classical optimization?

I have been trying to understand Variational Quantum Eigensolver (VQE), particularly from the non-linear binary programming perspective. But after reading a few resources I'm still confused about ...
user113988's user avatar
2 votes
0 answers
69 views

What is the explicit best known quantum algorithm for LWE?

Consider the learning with errors(LWE) problem which is known to be hard for quantum computers. Let $q \geq 2$ be a prime integer. Consider us being given (polynomially many samples of) either: $$A, ...
Tom Clancy's user avatar
3 votes
1 answer
264 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 ...
BlackHat18's user avatar
  • 1,251
5 votes
1 answer
80 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 \{...
Tom Clancy's user avatar
4 votes
0 answers
258 views

Reduced density matrix of a Haar random state and its Schmidt decomposition

Consider a Haar random quantum state $|\psi\rangle$. Note that $$\rho =\mathbb{E}[|\psi\rangle\langle \psi|] = \frac{\mathbb{I}_{n}}{2^{n}}.$$ $\mathbb{I}_n$ is the identity operator on $n$ qubits. ...
BlackHat18's user avatar
  • 1,251
5 votes
1 answer
450 views

Random quantum states and Schur-Weyl duality

Consider the following density matrix over $n$ qubits, with $C$ being a single qubit operator: $$ \rho_{n} = \int_{C \sim \text{Haar}} \big(C|0\rangle\langle0|C^\dagger\big)^{\otimes n} dC. $$ Let's ...
BlackHat18's user avatar
  • 1,251
1 vote
0 answers
78 views

Optimality of the SWAP test versus weak Schur sampling for testing unitarily invariant properties

Consider the following setting. I am either given the density matrix $|\psi\rangle \langle \psi|^{\otimes k}$ or the density matrix $\frac{\mathbb{I}^{\otimes k}}{2^{nk}}$, where $\mathbb{I}$ is the $...
BlackHat18's user avatar
  • 1,251
2 votes
1 answer
286 views

At what depth and for what architecture are random quantum circuits $1$-designs?

I was confused about something related to quantum $1$ designs. Let us recap two facts we know about random circuit ensembles that form a $1$ design. $1$ design, for a quantum circuit over $n$ qubits, ...
BlackHat18's user avatar
  • 1,251
11 votes
3 answers
2k 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 ...
Marco Fellous-Asiani's user avatar
1 vote
1 answer
206 views

How does a quantum computer execute a process by leveraging superposition?

I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power. A helpful metaphor is that of the maze. A ...
WriterState's user avatar
2 votes
2 answers
154 views

Random quantum circuits and general efficient POVM measurement

Let's consider a random quantum circuit $C$, applied to the $n$ qubit initial state $|0^{n}\rangle$, producing the state $|\psi\rangle$. Consider a general efficiently implementable $m$-outcome POVM ...
BlackHat18's user avatar
  • 1,251
13 votes
2 answers
167 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 ...
madeel's user avatar
  • 311
2 votes
1 answer
337 views

Average output state of random quantum circuits

Let $|\psi\rangle = C_1 |0^{n}\rangle$ be a quantum state, such that $C_1$ is a Haar random unitary circuit. Consider a density matrix $\rho$ as follows \begin{equation} \rho_1 = \mathbb{E}[|\psi\...
BlackHat18's user avatar
  • 1,251